Three Commonly Used Techniques

There are three common uses of semaphores: locks, countdown-and-lock, and notification.

Locks

The obvious one is locks. As discussed on the Basic Concept page, if a semaphore is initialized to 1, then Wait() and Signal() are equivalent to Lock() and Unlock(), respectively. The following is a comparison:

Semaphore S("Lock", 1);

S.Wait();
// critical section
S.Signal();

    Mutex S("Lock");

S.Lock();
// critical section
S.Unlock();

However, there is an advantage in using semaphores. When a mutex lock is created, it is always in the "unlock" position. If a binary semaphore is used and initialized to 0, it is equivalent to having a mutex lock that is locked initially. Therefore, the use of binary semaphores is a little more flexible.

Countdown and Lock

Do not forget that every semaphore has a private counter. Although we cannot use it directly, we can take advantage of its counting "effect." In some applications, we might want to allow a number of threads to pass through certain point and then block the others. For example, suppose we are writing a program to simulate a ferry that can only carry 100 passengers, each of which is also simulated by a thread. Thus, we might use a semaphore with an initial value of 100 as follows: 

Semaphore  S("Counter", 100);
To simulate boarding, each passenger thread executes a wait call: 
// each passenger thread
S.Wait();
// the passenger is on the ferry
In this case, only 100 passengers can pass through the Wait() call. When the 101st call to Wait() comes, since the counter is zero, the calling thread is blocked. In this way, we can easily use a semaphore to permit a fixed number of threads to pass through a point and blocks the remaining.

Let us look at another example. Suppose a showroom can hold no more than 30 visitors. Each visitor is represented with a thread. Visitors stop by the showroom, stay for a while, exit, come back some time later, and visit the showroom again. How do we make sure that the showroom will always has no more than 30 visitors? This is simple. We just install a counter. When a visitor enters, the counter is increased by one and when a visitor exits, the counter is decreased by one. Once the counter value becomes 30, we close the door until a visitor leaves the showroom. The "door" can be simulated with a semaphore S with initial value 30. Before each visitor can enter the showroom, he must wait on semaphore S, and before each visitor leaves the showroom, he signals semaphore S. In this way, when the semaphore counter reaches zero, the showroom has 30 visitors, and the next visitor will be blocked by semaphore S until a visitor exits and signals S.

Because of this capability, we refer to this way of using semaphores as countdown and lock.

What if you do not want all 30 visitors coming and going? Instead, you insist that all visitors enter the room at the same time, and wait until all of them leave before the next batch can come in? This is similar to a movie theater that visitors can only come in before a movie starts? Semaphores cannot solve this problem directly. However, with the help of semaphores, we can implement a synchronization primitive, called barrier, to achieve this goal. We will discuss barriers on a later page.

To Beginners

Many beginners many handle the showroom example in a very inefficient way as follows. Set up a counter variable, say C, and use a mutex lock L to protect C from race condition. Then, when a visitor comes, he locks L. When he becomes the owner, he tests if C is zero. If the counter is not zero, the visitor thread subtracts one from the counter, releases lock L. Otherwise, the threads releases the counter and wait on another lock or semaphore. This approach looks very natural. However, it is very inefficient and, in fact, it could be wrong. When a semaphore has the count-down capability, we should use it rather than creating an extra and unsafe copy. Moreover, how to wait if the counter C is zero is another place a beginner could go wrong.

Notification

The third technique is notification. In some cases, a thread A cannot continue because the anticipated event, which is handled by another thread B, has not happened. Once thread B finishes its job and notifies thread A, then A can continue. In this simple scheme, thread A must be blocked on a semaphore S until thread B signals it. Because we want to block A first, S must have initial value 0. Hence, our code looks like the following:

Thread A Thread B
Semaphore S("Block", 0);
// wait for B's signal
S.Wait();
// use B's result
    // produce result
S.Signal();
// now both threads continue

If thread A arrives the Wait() call first, since the counter is zero, thread A blocks until thread B's Signal() comes. After this point, both threads can continue and thread A can use the results generated by thread B before the Signal() call. On the other hand, if thread B reaches the Signal() call earlier than thread A arrives at its Wait() call, since there is no waiting thread, thread B's call causes 1 to be added to the counter. Sometime later when thread A reaches its Wait() call, it can pass through because the counter is 1. Because thread B has already produced its result, thread A can use B's result immediately. In summary, thread A executes a Wait() to expect the completion of some task by another thread B. Once thread B executes its Signal() call, it means the task of B has completed and thread A can continue and use the result. Isn't it a notification? In this scheme, there is no critical section, because the Wait() and Signal() may be in different threads.

Let us take a look at a very simple example. Suppose we have two threads A and B. However, for some reason, we want to execute them in an alternating order. More precisely, suppose that A and B repeatedly print out ping and pong, respectively. An alternating execution would force A and B to print out in the order of 

ping pong ping pong ping pong ........
An initial thought would be that B is blocked first by a semaphore, say SB. After A finishes printing ping, it notifies B by signaling SB. However, A should not continue before B can finish printing pong, and, as a result, A blocks itself by semaphore SA. Similarly, after B finishes printing pong, it notifies A by signaling semaphore SA, and then blocks itself until A's notification comes. In summary, we have the following:

Thread A Thread B
while (1) {
  // wait for B's notification
  SA.Wait();
  cout << "ping ";   // notify B
  SB.Signal();
} 		    while (1) {
  // wait for A's notification
  SB.Wait();
  cout << "pong ";   // notify A
  SA.Signal();
}

So, A and B are very similar except for the semaphore names. The remaining is to figure out the initial values. Because we want to print like ping pong ping pong ... (i.e., A's output comes out first), the initial value of semaphore SA should be 1 so that when A reaches that point, it can go through and print. On the other hand, the initial value of SB should be 0 so that it can be blocked until the notification from A comes.

The idea of the alternating execution is shown below. Red squares indicate semaphore wait, green circles mean signal, the dashed lines show the notifying and notified threads. When the synchronization of a program gets more complex, drawing a diagram is usually very helpful.