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 '20 at 17:33
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 '20 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 '20 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 '20 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 '20 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 '20 at 19:49
  • @Tim process A locks the semaphore and process B unlocks it. – user253751 Nov 10 '20 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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