Semaphore Basics

A semaphore is a signalling mechanism used to regulate access to a shared resource like a railroad track. A semaphore is used to signal to the driver of a train whether he can go ahead on the track or not. The upward position of the pivot arm in the picture shows that the track is available and the driver can go ahead. Had the arm been in horizontal position, the semaphore would have meant that the track was unavailable, possibly due to use by some other train and the driver must wait. A semaphore, as shown above, provides a system, using which only one train goes on the designated track.

The problem of regulating access to a shared resource occurs in software systems quite often. Think of a bank account that needs to be operated by the customer for drawing money via ATM and also by the clerk for clearing a check, by chance, at the same time. Only one of them should be allowed to access the bank account at one time time; the other must wait for the earlier transaction to get over. Semaphores were invented in the context of software by the noted Dutch computer scientist Edsger W. Dijkstra in early 1960s. Semaphores provide a mechanism for synchronizing processes and threads.

Just like semaphores on a railroad track are provided by the railroad company, semaphores in software are provided by the kernel. In case of railroad semaphores, the semaphore operations are done by the people in charge of its management and the train drivers. In case of software, the semaphore operations are done by processes and threads. Semaphores are advisory and things will be OK if we use them correctly. If we do not follow semaphores correctly, it would result in a run-time errors and the consequences may vary from plain corruption of the database to more severe situations in the case of process control and other real time systems.

There are three basic operations that can be done on a semaphore. First, we can create a semaphore. It is like a non-negative integer. It is important to note that it is like a integer, and not an integer like an int i in a program, because it is an object created by the kernel. We can create, increment and decrement a semaphore via kernel using system calls only. We create a semaphore with a non-negative integer initial value.

Now we come to the operations that can be done on a semaphore, once it has been created. There are two operations; these are named P and V respectively. P can be considered to be a synonym for terms like wait, acquire and lock. Similarly, V can be considered to be a synonym for terms like signal, release and unlock. The names P and V are initials for Dutch words corresponding to decrease and increase respectively.

The basic utility of semaphores comes from the fact that the P and V operations are guaranteed to be atomic. That is, the system calls for P and V operations would finish and processor would not be given to any other process in between. Both P and V are single system calls in operating systems. But it is instructive to see the effective work done by these calls. The P system call has the following functionality.

// P operation
if (semaphore == 0)
   block;   // The block ends as soon as semaphore becomes greater than 0
if (semaphore > 0) 
   semaphore--;

Similarly, the V system call has the functionality,

// V operation
semaphore++;

Consider the problem of writing on the terminal from two processes,

// Process 1
...
printf ("Hello World\n");
....

// Process 2
...
printf ("Did you complete the work?\n");
...

Let's assume that these two processes are started in the background and execute concurrently and the output text strings are a lot bigger than what is listed above. Since a process can lose its processor any time, there is a chance that the text written by the two processes gets intermingled on the terminal. We can prevent this problem using by using a semaphore. Let's assume there is a semaphore, sem with an initial value 1, indicating that the terminal is available for writing. To keep the pseudo code small, let's assume that both processes have access to this semaphore. Them if we modify the above pseudo code as,

// Process 1
...
P (sem);
printf ("Hello World\n");
V (sem);
...

// Process 2
...
P (sem);
printf ("Did you complete the work?\n");
V (sem);
...

the problem is resolved. The initial value of semaphore, sem, is 1, indicating that the terminal is available for writing. A process wishing to write on the terminal does a P (sem). If two processes try to do P (sem) at the same time, only one will succeed, as P is an atomic operation. As a result of P (sem), the sem becomes 0. So the process which did a successful P (sem) can peacefully go ahead and write on the terminal. If the other process tries to do P (sem), it blocks as sem value is 0. When the earlier process finishes writing, it does a V (sem), making the semaphore value 1. The other process which was blocked earlier because the semaphore value was 0, gets unblocked and can complete the P operation successfully and write on the terminal.

The code between P (sem) and V (sem) is frequently called the Critical Section as it can only be executed by any one process at any time. We have just solved the problem of mutual exclusion, as the processes mutually exclude each other from the critical section. In the above example, the semaphore takes on the values 0 and 1 only. So it is a binary semaphore. Binary semaphores are sometime called mutex, an abbreviation for mutual exclusion.

The above example of mutual exclusion is a case of process synchronization as the processes synchronize themselves such that only one process executes the critical section at a time. Now consider a somewhat different situation: two processes wish to synchronize their execution at a point. For example, a server is split between two processes and both must finish initialization before the client request processing can start.

// Process 1
// Initialization
...
...
// Wait for Process 2 to complete its initialization before doing anything further
...
...

// Process 2
// Initialization
...
...
// Wait for Process 1 to complete its initialization before doing anything further
...
...

The solution is to have one semaphore for each process, with an initial value 0. Once a process finishes initialization, it does a V on its semaphore. Next it does a P on the other process's semaphore.

// Process 1
// Initialization
...
...
// My initialization is complete; signal
V (sem1); 
// Wait for Process 2 to complete its initialization before doing anything further
P (sem2);
...
...

// Process 2
// Initialization
...
...
// My initialization is complete; signal
V (sem2); 
// Wait for Process 1 to complete its initialization before doing anything further
P (sem1);
...
...

The solution can be scaled to more than two processes. Each process has a semaphore for which it does a V operation after finishing its initialization. Next it does a P operation on the semaphores of all other processes.

In the above examples, the semaphore had two values, 0 and 1. What about semaphore values greater than 1? Remember, a semaphore represents whether a resource like a terminal, a ready process, etc., is available or not. So, if there is more than one instance of a resource, the semaphore will have a value greater than 1. It will have a maximum value equal to the number of instances of that resource.

Consider the case where multiple threads wish to write on a terminal. If it is free-for-all situation, the output from different threads will get mixed up and it will be difficult to know who wrote what. So we define a spooler thread with N buffers. The threads wishing to write to the terminal write to these buffers. The spooler thread writes these buffers on the terminal in chronological order and, after writing, marks each buffer clean, so that it can be used again. This is a case of the Producer-Consumer problem. The threads wishing to write on the terminal are the producers as they produce strings to be printed on the terminal. The spooler thread is the consumer. It consumes the strings and writes them on the terminal. The strings are passed from the producers to the consumer via buffers. How does a producer know that there is an empty buffer out there and it can go ahead and write? How does the producer tell that it has written a buffer on the terminal and that the buffer can be re-used by the producers? The answer lies in Counting Semaphores which have a value equal to number of resources. Also, we have a binary semaphore which takes care that only one producer uses the buffer data structures at a time.

...
// Buffer data structures
#define MAX_BUFFERS 20
char buf [MAX_BUFFERS] [100];
int buffer_index;
int buffer_print_index;
...
// part of the main thread
// initialization
buffer_index = buffer_print_index = 0;
//  mutual exclusion semaphore mutex with an initial value 1.
create_semaphore (mutex, 1); 
// counting semaphore, indicating the number of available buffers.
create_semaphore (buffer_count_sem, MAX_BUFFERS); 
// counting semaphore, indicating the number of strings to be printed.
create_semaphore (spool_signal_sem, 0); 
...
// There might be multiple producer threads
producer_thread () 
{
     // get a buffer
     P (buffer_count_sem);
    // There might be multiple producers
    // We must ensure that only one producer uses buffer_index
    // at a time
     P (mutex);
        int i = buffer_index;
        buffer_index++;
        if (buffer_index == MAX_BUFFERS)
            buffer_index = 0;
    V (mutex)
       sprintf (buf [i], "Time is %ld\n", time ());
    V (spool_signal_sem);
}

// There is only one spooler thread
spooler () 
{
    // wait for a spool buffer
    P (spool_signal_sem);
    printf ("%s", buf [buffer_print_index]);
    // Contents of one buffer printed
    // one more buffer is available for use by producers
    V (buffer_count_sem);
    // Since there is only one thread (spooler) 
    // using buffer_print_index, mutex is not necessary
    buffer_print_index++;
    if (buffer_print_index == MAX_BUFFERS)
       buffer_print_index = 0;
}

• POSIX Semaphores
  

• System V Semaphores
• POSIX Threads Synchronization in C