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.

3
  • 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 9, 2020 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 9, 2020 at 22:23
  • Does this answer your question? Mutex vs Semaphore: How to implement them _not_ in terms of the other?
    – user289860
    Apr 20, 2021 at 19:28

1 Answer 1

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.

9
  • 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 9, 2020 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. Nov 9, 2020 at 17:22
  • @Tim: A semaphore can also be spin waiting or blocking or both, just like a mutex.
    – JacquesB
    Nov 9, 2020 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 9, 2020 at 17:56
  • 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 9, 2020 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.