Binary Semaphores (Locks)
This lesson talks about a special kind of semaphores, the binary semaphores.
We are now ready to use a semaphore. Our first use will be one with which we are already familiar: using a semaphore as a lock. Look at the code snippet below.
sem_t m;sem_init(&m, 0, X); // initialize to X; what should X be?sem_wait(&m);// critical section heresem_post(&m);
Therein, you can see that we simply surround the critical section of interest with a sem_wait()
/sem_post()
pair. Critical to making this work, though, is the initial value of the semaphore m
(initialized to X
in the figure). What should X
be?
… (Try thinking about it before going on) …
Looking back at the definition of the sem_wait()
and sem_post()
routines above, we can see that the initial value should be 1.
To make this clear, let’s imagine a scenario with two threads. The first thread (Thread 0) calls sem_wait()
; it will first decrement the value of the semaphore, changing it to 0. Then, it will wait only if the value is not greater than or equal to 0. Because the value is 0, sem_wait()
will simply return and the calling thread will continue; Thread 0 is now free to enter the critical section. If no other thread tries to acquire the lock while Thread 0 is inside the critical section, when it calls sem_post()
, it will simply restore the value of the semaphore to 1 (and not wake a waiting thread, because there are none). The figure below shows a trace of this scenario.
A more interesting case arises when Thread 0 “holds the lock” (i.e., it has called sem_wait()
but not yet called sem_post()
), and another thread (Thread 1) tries to enter the critical section by calling sem_wait()
. In this case, Thread 1 will decrement the value of the semaphore to -1, and thus wait (putting itself to sleep and relinquishing the processor). When Thread 0 runs again, it will eventually call sem_post()
, incrementing the value of the semaphore back to zero, and then wake the waiting thread (Thread 1), which will then be able to acquire the lock for itself. When Thread 1 finishes, it will again increment the value of the semaphore, restoring it to 1 again.
The figure above shows a trace of this example. In addition to thread actions, the figure shows the scheduler state of each thread: Run (the thread is running), Ready (i.e., runnable but not running), and Sleep (the thread is blocked). Note that Thread 1 goes into the sleeping state when it tries to acquire the already-held lock; only when Thread 0 runs again can Thread 1 be awoken and potentially run again.
If you want to work through your own example, try a scenario where multiple threads queue up waiting for a lock. What would the value of the semaphore be during such a trace?
Thus we are able to use semaphores as locks. Because locks only have two states (held and not held), we sometimes call a semaphore used as a lock a binary semaphore. Note that if you are using a semaphore only in this binary fashion, it could be implemented in a simpler manner than the generalized semaphores we present in this chapter.
Get hands-on with 1400+ tech skills courses.