0

Is a mutex lock always implemented as spin waiting? Can a mutex lock be implemented as block waiting? (Operating System Concepts section 5.4 only mentions the implementation by spin waiting. See below.) (For comparison, a semaphore's waiting can be implemented either by busy spinning in a loop or by being blocked. See Operating System Concepts 9ed Section 5.5 and 5.6 and Is there still busy waiting in the process-blocking implementation of a semaphore?)

If a mutex lock can be implemented as block waiting, is a mutex lock implemented as such the same as a binary semaphore? (Stalling's OS book says a mutex lock and a binary semaphore differ in whether the process that locks the mutex (sets the value to zero) must be the one to unlock it. It doesn't mention whether they differ in spinning waiting only. See below.)

In Operating System Concepts, Section 5.5 Mutex Locks defines a mutex lock as:

We use the mutex lock to protect critical regions and thus prevent race conditions. That is, a process must acquire the lock before entering a critical section; it releases the lock when it exits the critical section. The acquire()function acquires the lock, and the release() function releases the lock, as illustrated in Figure 5.8.

A mutex lock has a boolean variable available whose value indicates if the lock is available or not. If the lock is available, a call to acquire() succeeds, and the lock is then considered unavailable. A process that attempts to acquire an unavailable lock is blocked until the lock is released.

The definition of acquire() is as follows:

acquire() {
while (!available)
; /* busy wait */
available = false;;
}

The definition of release() is as follows:

release() {
available = true;
}

Calls to either acquire() or release() must be performed atomically. Thus, mutex locks are often implemented using one of the hardware mecha- nisms described in Section 5.4, and we leave the description of this technique as an exercise.

The main disadvantage of the implementation given here is that it requires busy waiting. While a process is in its critical section, any other process that tries to enter its critical section must loop continuously in the call to acquire(). In fact, this type of mutex lock is also called a spinlock because the process “spins” while waiting for the lock to become available.

Stalling's Operating Systems book says

A concept related to the binary semaphore is the mutex . A key difference between the two is that the process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1). In contrast, it is possible for one process to lock a binary semaphore and for another to unlock it.

Thanks.

Tim
  • 5,405
  • 7
  • 48
  • 84
  • 6
    You seem to be having a lot of trouble with this book. Maybe consider getting a different one, or doing some research alongside instead of reading it in a vacuum. – Useless Nov 09 '20 at 17:41
  • 1
    If a mutex was always implemented by spin-waiting how would that work on a one-processor (i.e., one core) system? – davidbak Nov 09 '20 at 22:23
  • Does this answer your question? [Mutex vs Semaphore: How to implement them \_not\_ in terms of the other?](https://softwareengineering.stackexchange.com/questions/340284/mutex-vs-semaphore-how-to-implement-them-not-in-terms-of-the-other) –  Apr 20 '21 at 19:28

1 Answers1

4

No. A mutex lock can be either spin waiting or blocking. It can even be a combination, e.g. it spin-waits for a number of cycles and if it doesn't acquire the lock it changes to blocking wait.

JacquesB
  • 57,310
  • 21
  • 127
  • 176
  • Thanks. If a mutex lock can be implemented as block waiting, is a mutex lock implemented as such the same as a binary semaphore? (Stalling's OS book says a mutex lock and a binary semaphore differ in whether the process that locks the mutex (sets the value to zero) must be the one to unlock it. It doesn't mention whether they differ in spinning waiting only. See the quote.) – Tim Nov 09 '20 at 17:20
  • 1
    @Tim: I suggest you study some of these mechanisms; there is source code available on the Internet for various mutex implementations. As it is, we're mostly talking about word definitions here, which won't get you very far. Once you understand the actual mechanisms, the meaning of the word definitions should become readily apparent. – Robert Harvey Nov 09 '20 at 17:22
  • @Tim: A semaphore can also be spin waiting or blocking or both, just like a mutex. – JacquesB Nov 09 '20 at 17:42
  • @JacquesB Both a binary semaphore and a mutex lock can be implemented as spin waiting, blocking or both. What differences are between them, to a user? – Tim Nov 09 '20 at 17:56
  • @Tim: A spin lock takes up processor resources when spinning, a block does not since the thread is suspended by the OS. But blocking requires a system call, so it has some overhead. This is why an implementation may combine them. If a lock is only locked for at short while, it is more efficient to spin wait. But if it is locked for longer than the system call overhed, it is better to block. – JacquesB Nov 09 '20 at 18:06
  • 1
    Depends on contention patterns and whether the user would like their cores and electricity to be doing something more productive than waiting for each other. It's a question in its own right, but try some research some before posting it. – Useless Nov 09 '20 at 18:06
  • I meant: what differences are between a binary semaphore and a mutex lock, to a user? – Tim Nov 09 '20 at 18:26
  • @Tim: This is answered in the second quote in the question. – JacquesB Nov 09 '20 at 18:42
  • I meant https://softwareengineering.stackexchange.com/questions/418800/why-is-it-that-the-process-that-locks-the-mutex-must-be-the-one-to-unlock-it – Tim Nov 09 '20 at 18:44