Synchronization: Semaphores


The goal of this tutorial is explain how semaphores can be used to solved synchronization problems, which arise through cooperation between processes. The tutorial will start with the basics on creating and setting-up semaphores, then tackle the most basic use of semaphores, to protect critical sections of code. Finally, the Bounded Buffer Problem, described in the tutorial on Cooperation, will be tackled.

The Critical Section Problem

I assume you have read the tutorial on cooperating processes, and Interprocess Communication (IPC) facilities provided by the Operating System for process cooperation. The most synchronization problem confronting cooperating processes, is controling access to shared resource. Suppose two processes share access to a file, or shared memory segment (or when we discuss threads in a couple of weeks, we'll see threads share the same memory, so they must synchronize their actions), and at least one of these processes can modify the data in this shared area of memory. That part of the code of each program, where one process is reading from or writing to a shared memory area, is a critical section of code, because we must ensure that only one process execute a critical section of code at a time. The Critical Section Problem is to design a protocol that the processes can use to coordinate their activities when one wants to enter its critical section of code.

Suppose we have two processes that share a memory segment of four bytes which stores an integer value. Let this value be named by the variable V. Process 1 (P1) and Process 2 (P2) have a section of code with the following lines:

       if (0 < V)

These lines of code will be part of a critical section of code, because it is important that each process be allowed to execute all of them without interference from the other process. Here is an example of how the processes can interfere with each other:

  1. V has the value 1
  2. P1 tests 0 < V, which is true
  3. P1 is removed from the CPU and replaced by P2
  4. P2 tests 0 < V, which is true
  5. P2 executes V--, so V has the value 0
  6. P1 given back the CPU and starts where it last left off: executing V--, so V has the value -1
By interfering with each other during the execution of the lines of code, the two processes caused the value of the common variable V to drop below 0, which they were trying to prevent from happening.

The protocol developed for solving the Critical Section Problem involved three steps:

  1. Entry section: Before entering the critical section, a process must request permission to enter
  2. Critical section: After permission is granted, a process may execute the code in the critical section. Other processes respect the request, and keep out of their critical sections.
  3. Exit section: The process acknowledges it has left its critical section.
The problem that remains is how to effectively implement this protocol. How can the processes communicate their requests and grant their permissions so that only one process at a time is in a critical section.

The Solution

The Dutch scientist E.W. Dijkstra showed how to solve the Critical Section Problem in the mid-sixties, and introduced the concept of a semaphore to control synchronization. A semaphore is an integer variable which is accessed through through two special operations, called wait and signal. Why we need special operations will be discussed shortly. Originally, Dijkstra called the two special operations P (for proberen, the dutch word for test) and V (for verhogen, the dutch word to increment). Let S be an integer variable, our semaphore, then the classical definition of wait is given by

       wait(S) {
          while(S ≤ 0);

and signal is given by

       signal(S) {

We can use the semaphore to synchronize our processes:

       // Entry Section

       // Critical Section
       if (0 < V)

       // Exit Section

  1. Process P calls wait(S)
  2. While S is 0, P waits.
  3. When S is 1, P is allowed to enter its critical section
  4. While P is in its critical section, the value of S is zero, blocking other processes from entering their critical section.
  5. When P is finished and ready to leave its critical section, it executes signal resetting S to 1 and allowing another process to enter.
A semaphore which can take the value zero or one is called a binary semaphore, or mutex, for mutually exclusive.

There is a glaring weakness with this implementation: the code for wait is no better than the code we were trying to protect: For the semaphore to work, S must be shared, so it is tested and changed in wait, and this requires synchronization between the processes; so how does this resolve the original problem?

Atomic Operations

The problem we have is that we have some lines of code which need to be executed without interference from other processes; this is no problem as long as a process has control of the CPU, but if it is taken-off the CPU by the Operating System before it can finish executing its section of code, another process may have an opportunity to trash its work. The code must be run atomically: in one uninterruptible unit. So, for semaphores to solve the problem, the implementation of the two functions wait and signal must be atomic: there can be no interruptions while these operations are being implemented.

Operating systems, like Unix, which have semaphores, guarantee that the operations wait and signal are run atomically. How can they do this? It is the Operating System that determines when to switch a process off the CPU; while the Operating System cannot decide when it must leave a process on the CPU, it can govern its own CPU use. So, the Operating System keeps track of the semaphore and its value: when processes call operations on the semaphore such as wait and signal they are actually making system calls which request the Operating System to check the semaphore and change its value. The Operating System then steps in and performs the operation, without interruption.

System V Semaphores

Unix System V introduced semaphores to Unix in the mid-eighties. Since the Operating System maintains semaphores and operates on them, the actual code required is rather complicated. To add to this confusion, a Unix semaphore is not really a single integer value, but an array of integer values. We'll see later why we may want to use more than one semaphore. I will refer to Unix semaphores as semaphore structures, since they include (possibly) multiple semaphores.

Semaphores are to be shared by processes which are unrelated to each other. This means that they need to have some means of coordinating their access to the same semaphore. The way this is done is for all processes which will use the semaphore to exchange a shared key value. This key value is defined the same way in each process. The value of the key can be any integer, although if there already exists a semaphore structure with that key, that semaphore will be used. One way to be sure that your key is unique is to see what semaphore structures the system already has set-up. Typing ipcs -sem on the command line will list all semaphore structures. Unix only allows a few semaphore structures at a time (a maximum of 10 in the whole system), so most any key you choose is likely to be unique.

There are five basic steps in allocating a semaphore structure:

  1. Request a semaphore structure, using the common key
  2. Initialize the semaphore structure by setting the values of each semaphore
  3. Define the basic operations we want to perform on the semaphore structure
  4. Use the basic operations in our program
  5. Remove the semaphore structure when we are done with it.
The first step is a request of a semaphore structure.
Purpose Request a semaphore structure
Include #include<sys/types.h>
Useage int  semget(key_t key, int numsems, int flag)
Arguments key:    key value
numsems:    number of semaphores
flag:    IPC_CREAT or IPC_EXCL
Returns -1 on error
semaphore ID if successful
Errors ENOMEM:  No memory available
EEXIST:  structure exists and IPC_EXCL set

There are three ways you may want to call semget

       //Create the structure if it doesn't exist
       //or use an existing structure with the same key
       semaid = semget(key, numsems, IPC_CREAT);

       //Require a new structure is created:
       //Throws an error if a structure exists with the key
       semaid = semget(key, numsems, IPC_CREAT | IPC_EXCL);

       //Create the structure if it doesn't exist using a private key
       //The return value semaid can only be shared with related processes
       semaid = semget(IPC_PRIVATE, numsems, IPC_CREAT);

The return value semaid will be used to refer to the semaphore structure in all further functions.

Once you have the semaid, you initialize the structure, by setting the value of every semaphore in the set. The function for doing this is semctl which is a catch-all for alot of different functions. You will want to see the manpages: man 2 semctl for all the details.
Purpose Mainly to remove a semaphore structure from the system, and to set the values of each semaphore in the structure.
Include #include<sys/types.h>
Useage int semctl(int semaid, int semnum, int cmd, union semun arg);
Arguments semaid:    semaphore ID
semnum:    between 0 and numsems-1
cmd:    SETVAL or SETALL
arg:    see below
Returns 0, for the two commands above
Errors NONE
Using this structure is a little complicated, so lets start with the definition of union semun. This union structure is not actually defined in any of the header files, so you will have to define the structure in your program before you call main:

union semun {
      int val; /* used for SETVAL only */
      struct semid_ds *buf; /* for IPC_STAT and IPC_SET, not discussed here */
      ushort *array; /* used for GETALL and SETALL */

To make the discussion concrete, I will consider how to set the value of the semaphore structure in two cases: where we want to set one particular semaphore, and when we want to set the value for all semaphores at once (the case of two semaphores in the structure). Here is the code to set one semaphore in a set

       union semun    arg;
       arg.val = 1;

       //This sets the first semaphore to the value 1
       //(numbering starts at 0)
       semctl(semaid, 0, SETVAL, arg);

If we want to set all the values of the semaphore structure, we need an array of integers, and to set each value in the array:

       union semun    arg;
       int    arr[2];
       arr[0] = 1;
       arr[1] = 5;
       arg.array = arr;

       //Second argument is not used
       semctl(semaid, 0, SETALL, arg);

We use a special structure type, struct sembuf, to define the basic operations we want to define on the semaphore set. Here is the structure:

struct sembuf {
      int sem_num; /* member # in {0, . . . , numsems - 1} */
      short sem_op; /* operation: negative, zero, positive */
      short sem_flag; /* IPC_NOWAIT or SEM_UNDO */

Each argument is important:

Lets look at how we would set-up the semaphore operations wait and signal. Suppose we have created a semaphore structure having one semaphore, with semaphore ID semaid, and this semaphore has been set to an initial value one. The two operations which I will label WAIT and SIGNAL are defined as follows:

       struct sembuf    WAIT[1], SIGNAL[1];

       //Defining WAIT
       WAIT[0].sem_num = 0;
       WAIT[0].sem_op = -1;
       WAIT[0].sem_flag = SEM_UNDO;

       //Defining SIGNAL
       SIGNAL[0].sem_num = 0;
       SIGNAL[0].sem_op = 1;
       SIGNAL[0].sem_flag = SEM_UNDO;

Using our semaphore actions is actually easy, we call the operation semop

Purpose Implement a predefined action on a semaphore set
Include #include<sys/types.h>
Useage int semop(int semaid, struct sembuf semoparray[], size_t nops);
Arguments semaid:    semaphore ID
semopsarray:    operations to be performed on the semaphores
nops:    length of semopsarray
Returns -1 on error

EAGAIN:  Process would wait and IPC_NOWAIT set


Here is how our code protecting the critical section now looks

       // Entry Section
       semop(semaid, WAIT, 1);

       // Critical Section
       if (0 < V)

       // Exit Section
       semop(semaid, SIGNAL, 1);

Removing a semaphore structure can only be done by the user ID of the creator of the semaphore structure. This can be done on the command line using ipcrm semaid, or you can explicitly remove the semaphore structure within the program using semctl

int semctl (semid, 0, IPC_RMID, 0)

You will find more details at FAQ.

The Bounded Buffer Problem

You will want to refresh your memory Bounded Buffer Problem. We now add an additional feature to our Critical Section Problem: the shared resource is stored in a buffer, BUFFER (a storage facility for data) of limited size. We have two types of processes, Producers who try to add to BUFFER and Consumers who try to remove from BUFFER. One possible solution to this problem is to treat use a single binary semaphore just as in the Critical Section Problem together with a variable COUNTER, which is shared in common (say as a shared memory segment.) Here is code for the Consumer:

       // Entry Section
       semop(semaid, WAIT, 1);

       // Critical Section
       if (0 < COUNT)
           //OK to take from BUFFER
           . . . BUFFER . . .

       // Exit Section
       semop(semaid, SIGNAL, 1);

and for the producer

       // Entry Section
       semop(semaid, WAIT, 1);

       // Critical Section
       if (COUNT < BUFFER_MAX )
           //OK to add to BUFFER
           . . . BUFFER . . .

       // Exit Section
       semop(semaid, SIGNAL, 1);

This presents one solution to the Bounded Buffer Problem, and in many circumstances it may be perfectly fine. But there is a problem which you should be aware of, that may make its performance unsuitable

Suppose a Consumer must have the data in the BUFFER, but BUFFER is empty. The only way to determine whether data has been added to the buffer is to continually enter the Critical Section and check COUNTER. This creates what is called a spinlock, where the process enters a useless cycle waiting for a resource. If the resource will be available quickly, this is not a problem; but if the resource may take some time, this spinlock position wastes CPU time that could be more productively spent. A solution to this problem is to use a semaphore to count as well. A semaphore which is used as a counter is called a counting semaphore.

It is pretty clear how we can use a counting semaphore to restrict the Consumer's behavior: set a semaphore to the value of BUFFER_MAX, and have each Consumer decrement its value, each Producer increment its value. If the count goes to zero, Consumers are forced to wait. Unfortunately, Unix System V semaphores effectively have no upper limit, so we cannot use just one counter to control both Consumers and Producers. Here is how we can implement a counter using semaphores. A Producer creates data and fills BUFFER, a Consumer takes data and empties BUFFER. We use two semaphores to implement our counter: EMPTY and FULL. We need two actions on the counter INCREMENT and DECREMENT:

By combining these two additional semaphores to keep count, with our binary semaphore we can solve the Bounded Buffer Problem. I'll show you how to define the action of INCREMENT for the Producer process (the action SIGNAL is the same as we saw before--reseting the binary semaphore):

struct sembuf    CONSUMER[3},PRODUCER[3], SIGNAL[1];

       //Defining PRODUCER
       //Code for the binary semaphore
       PRODUCER[0].sem_num = 0;
       PRODUCER[0].sem_op = -1;
       PRODuCER[0].sem_flag = SEM_UNDO;

       //Defining INCREMENT
       //Our FULL semaphore
       PRODUCER[1].sem_num = 0;
       PRODUCER[1].sem_op = 1;
       PRODUCER[1].sem_flag = SEM_UNDO;

       //Defining INCREMENT
       //Our EMPTY semaphore
       PRODUCER[2].sem_num = 0;
       PRODUCER[2].sem_op = -1;
       PRODUCER[2].sem_flag = SEM_UNDO;

I'll leave the defining of the action CONSUMER to you. Here is the new implementation for the Bounded Buffer Problem for the Consumer and Producer:

       // Entry Section
       semop(semaid, CONSUMER, 3);

       // Critical Section
       //OK to take from BUFFER
       . . . BUFFER . . .

       // Exit Section
       semop(semaid, SIGNAL, 1);

and code for the Producer

       // Entry Section
       semop(semaid, PRODUCER, 3);

       // Critical Section
       //OK to add to BUFFER
       . . . BUFFER . . .

       // Exit Section
       semop(semaid, SIGNAL, 1);