-4

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.

What does the first book mean by "it is possible for one process to lock a binary semaphore and for another to unlock it"? Could someone give a useful example of it?

Does "locking" a binary semaphore mean calling "wait()"

  • with immediately returning (because the binary semaphore originally had value 1) or
  • without immediate returning (because the binary semaphore originally had value 0)?

(The former is more similar to lock a mutex lock than the latter.)

Thanks.

2
  • 1
    The answer is probably what follows immediately or soon in the textbook. What does the textbook next say about this? Anyway this claim of theirs that only the setter can reset a mutex is an idiosyncratic interpretation of the term. Traditionally a mutex & binary semaphore are the same thing. (Particular systems, languages & libraries also coopt these general terms.) PS Putting words in scare quotes doesn't make clear the idiosyncratic meaning you are not giving. PS How can a wait & return happen at the same time? – philipxy Nov 10 '20 at 0:04
  • 2
    You might find the (free) book Little Book of Semaphores useful. It explains a lot about synchronization, and definitely shows that the semaphore is the primitive building block upon which other more convenient concurrency tools like mutexes and conditional variables are built. Understanding that hierarchy might answer some of your questions right away. – davidbak Nov 10 '20 at 1:15
4

"Locking" isn't really the best term to describe when one process signals and one process waits on a semaphore. That usage is typically the foundation for things like concurrent queues or channels. So one process signals another process when some data is ready, and the semaphore is used so the waiting process isn't spinning. It's more about coordinating turn taking than locking.

3

It's actually the normal way to use semaphores.

Say you need to perform four tasks, and you can continue once all four tasks are finished. So you dispatch each task on a different thread, and each task ends by signalling a semaphore. Just after dispatching the four tasks, you lock the semaphore four times. (Well, you try. But your code stops after locking the semaphore for the first time until one task is finished etc. ). When all the four tasks are finished and have signalled the semaphore, your code continues running.

And with this very normal use of semaphores, it gets locked four times on one thread, and signalled once each from four different threads.

2
  • Thanks. What is "Just after dispatching the four tasks, you lock the semaphore four times"? Could you write some pseudo code? – Tim Nov 11 '20 at 0:59
  • @Tim, in the context of semaphores, "locking" should be read as "calling wait()", where the usual expectation is that the wait call will block the calling process. – Bart van Ingen Schenau Nov 11 '20 at 9:51
2

Traditionally, semaphores are part of the file (or in memory equivalent). They are generally manipulated at the “application” level...which I mean that the programmer is free to decide on the reading and writing semantics and writes the code for manipulating semaphores as part of writing the rest of the code dealing with the file structure unique to the “application.”

Archiving is an example of how set and free by different programs would write a semaphore. One program changes the data in a file and sets a this-needs-archiving semaphore. Later an archiving program archives the file and clears the this-needs-archiving semaphore.

The semaphore is a signal. Locking a file is only one possible use a programmer might implement via semaphores. And even then, other programs need not respect the protocol. Generally, mutexes are more robust and traditionally tied to the underlying file system and not part of an “application’s” file format (in the case of a DBMS this is more nuanced).

Indeed there are many nuances possible and the traditional distinctions have eroded. The classic way of thinking about semaphores is Design of the Unix Operating System by Bach.

2
  • I'm pretty sure there's nothing about semaphores or mutexes in general that tie them in any way to any "underlying file system". – davidbak Nov 10 '20 at 1:18
  • There were traditional connotations. But forty years is a long time. However, the traditional connotations provide clarity because that's from whence the drift drifts. The file system is the only robust way to enforce mutual exclusion because if it isn't enforced there then the operating system probably won't respect it in ordinary cases. Of course with distributed systems it's even more complex than the traditional model. But that's engineering for you. – ben rudgers Nov 10 '20 at 1:56

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.