Synchronization: Semaphores

Goal

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)
           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

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 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);
          S--;
       }

and signal is given by

       signal(S) {
          S++;
       }

We can use the semaphore to synchronize our processes:

       // Entry Section
       wait(S);

       // Critical Section
       if (0 < V)
           V--;

       // Exit Section
       signal(S);

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.

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.

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.

semctl
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> #include<sys/ipc.h> #include<sys/sem.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:

• sem_num:   This refers to the particular semaphore we are going to adjust in the semaphore structure. The number of semaphores, numsems was determined when the semaphores structure was created, using semget. Counting starts at 0.
• sem_op:   The operation we will perform on the semaphore.
  • positive: the value is added to the semaphore's current value
  • negative: the value is added to the semaphore's current value, provided the current value is at least zero. If the value would be less than zero, the process will wait for the value to become large enough so that the sum is at least zero. If the flag IPC_NOWAIT is set, process does not wait.
  • zero: the process waits for the value of the semaphore to reach zero, unless IPC_NOWAIT is specified.
• sem_flag One of two possible flags:
  • IPC_NOWAIT: do not wait on the semaphore, return immediately if the operation cannot be carried-out. In this case, the error EAGAIN is returned.
  • SEM_UNDO: if the process should terminate before it can restore the count on the semaphore, then the count is restored by the Operating System. Suppose your process decrements a semaphore, taking its value to zero, but terminates before it can reset the semaphore back to one. Any process waiting for the semaphore to be one again would be stuck. The Operating System takes care of this if this flag is set.

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

semop
Purpose	Implement a predefined action on a semaphore set
Include	#include<sys/types.h> #include<sys/ipc.h> #include<sys/sem.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 SUCCESS
Errors	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)
           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)
           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 )
           COUNT++;
           //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

• A Consumer must constantly poll COUNTER to test if it is positive. Similarly, a Producer must constantly poll COUNTER to test if it is below BUFFER_MAX.

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:

• INCREMENT: Increment FULL and Decrement EMPTY
  The idea is that a Producer fills one more spot in BUFFER and removes one more empty spot
• DECREMENT: Decrement FULL and Increment EMPTY
  The idea is that a Consumer empties one more spot in BUFFER and removes one more full spot

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);