1

Here are some discussions about mutex (lock) and binary semaphore from two OS books.

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.

In Operating System Concepts, 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.

What does the first book mean by "the process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1)"?

Does the definition in the second book implement that "the process that locks the mutex (sets the value to zero) must be the one to unlock it (sets the value to 1)"? If yes, how?

  • Does the spinning waiting in the definition of acquire() decide that "the process that locks the mutex (sets the value to zero) must be the one to unlock it"?

  • If the spinning waiting in the definition of acquire() is replaced with calling system call to block the current process, is it still true that "the process that locks the mutex (sets the value to zero) must be the one to unlock it"

What does the first book mean by "it is possible for one process to lock a binary semaphore and for another to unlock it"?

Thanks.

1
  • 1
    It means that the thing the first book is calling a binary semaphore is the thing the second book is calling a mutex.
    – user253751
    Nov 11, 2020 at 17:33

2 Answers 2

3

The problem you have is that the "definition" you have quoted for acquire() and release() is overly simplistic. Mutexes don't really work that way.

Mutexes are controlled by the operating system. The calls to set and clear mutexes are system calls. The operating system remembers which process sets each mutex, and simply will not allow any other process to clear it. That is necessary to ensure that mutexes work the way they should.

Semaphores are also controlled by the operating system, but the rules for what the operating system will allow are different.

1
  • It is neither necessary nor appropriate to appeal to an operating system or any other implementation notion in giving the semantics of a programming language or library or, as here, generic notions of computation. See the last paragraph in the textbook quote. A mutex might be implemented by a memory location accessed by an atomic decrement-and-jump-if-not-zero instruction. Similarly "process" in the textbook context means a program running concurrently & doesn't need to be what a particular system uses that word for.
    – philipxy
    Nov 12, 2020 at 22:28
2

The purpose of a mutex lock is to ensure that only a single thread at a time can execute the critical section of code. Therefore it is necessary for the thread-safety that only the thread which acquired the lock can release it again. If other threads were able to release the lock, they could do it before the first thread exited the section, so you could have multiple threads executing in the critical section at the same time.

The implementation of release() in the second quote does not ensure that only the acquiring thread can release. So it is not an actual mutex, it is more like a binary semaphore. To implement a mutex the lock need to store the thread ID (or something like that) and not just a binary flag.

Mutexes and semphores implementations can use spin wait or blocking system calls to wait (typically a combination) but this is independent of the question of which thread can release the lock again.

5
  • Thanks. What does the first book mean by "it is possible for one process to lock a binary semaphore and for another to unlock it"?
    – Tim
    Nov 9, 2020 at 16:01
  • @Tim it means that if you have a binary semaphore, it doesn't have to be unlocked by the same process that locked it. But if you have a mutex, it does.
    – user253751
    Nov 9, 2020 at 16:08
  • @user253751 where does the definition of a mutex lock imply that "the process that locks the mutex (sets the value to zero) must be the one to unlock it "?
    – Tim
    Nov 9, 2020 at 18:46
  • @user253751 Could you give an example of ""it is possible for one process to lock a binary semaphore and for another to unlock it"? ?
    – Tim
    Nov 9, 2020 at 19:49
  • @Tim process A locks the semaphore and process B unlocks it.
    – user253751
    Nov 10, 2020 at 13:53

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.