Imagine a computer system in which all users share a single printer and can simultaneously print. How would the output appear? If lines of users’ jobs were interspersed, the system would be unusable. Shared devices, such as printers, are called exclusive resources because they must be accessed by one process at a time. Processes must execute the code that accesses these shared resources in a mutually exclusive manner.

A critical section is a code segment that must be executed in a mutually exclusive manner, that is, only one thread of execution can be active in its boundaries. For example, code that modifies a shared variable is considered to be part of a critical section, if other threads of execution might possibly access the shared variable during the modification. The critical section problem refers to the problem of executing critical section code in a safe, fair and symmetric manner.

Program 14.1 contains a modification of Program 3.1 on page 67 to generate a process chain. It prints its message one character at a time. The program takes an extra command-line argument giving a delay after each character is output to make it more likely that the process quantum will expire in the output loop. The call to wait ensures that the original process does not terminate until all children have completed and prevents the shell prompt from appearing in the middle of the output of one of the children.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>
#include "restart.h"
#define BUFSIZE 1024

int main(int argc, char *argv[]) {
    char buffer[BUFSIZE];
    char *c;
    pid_t childpid = 0;
    int delay;
    volatile int dummy = 0;
    int i, n;

    if (argc != 3){   /* check for valid number of command-line arguments */
        fprintf (stderr, "Usage: %s processes delay
", argv[0]);
        return 1;
    }
    n = atoi(argv[1]);
    delay = atoi(argv[2]);
    for (i = 1; i < n; i++)
        if (childpid = fork())
            break;
    snprintf(buffer, BUFSIZE,
             "i:%d  process ID:%ld  parent ID:%ld  child ID:%ld
",
             i, (long)getpid(), (long)getppid(), (long)childpid);

    c = buffer;
   /********************** start of critical section **********************/
    while (*c != '') {
        fputc(*c, stderr);
        c++;
        for (i = 0; i < delay; i++)
            dummy++;
    }
   /********************** end of critical section ************************/
    if (r_wait(NULL) == -1)
        return 1;
    return 0;
}

Each process in Program 14.1 executes the statements in sequential order, but the statements (and hence the output) from the different processes can be arbitrarily interleaved. An analogy to this arbitrary interleaving comes from a deck of cards. Cut a deck of cards. Think of each section of the cut as representing one process. The individual cards in each section represent the statements in the order that the corresponding process executes them. Now shuffle the two sections by interleaving. There are many possibilities for a final ordering, depending on the shuffling mechanics. Similarly, there are many possible interleavings of the statements of two processes because the exact timing of processes relative to each other depends on outside factors (e.g., how many other processes are competing for the CPU or how much time each process spent in previous blocked states waiting for I/O). The challenge for programmers is to develop programs that work for all realizable interleavings of program statements.

Code with synchronized critical sections can be organized into distinct parts. The entry section contains code to request permission to modify a shared variable or other resource. You can think of the entry section as the gatekeeper—allowing only one thread of execution to pass through at a time. The critical section usually contains code to access a shared resource or to execute code that is nonreentrant. The explicit release of access provided in the exit section is necessary so that the gatekeeper knows it can allow the next thread of execution to enter the critical section. After releasing access, a thread may have other code to execute, which we separate into the remainder section to indicate that it should not influence decisions by the gatekeeper.

A good solution to the critical section problem requires fairness as well as exclusive access. Threads of execution that are trying to enter a critical section should not be postponed indefinitely. Threads should also make progress. If no thread is currently in the critical section, a waiting thread should be allowed to enter.

Critical sections commonly arise when two processes access a shared resource, such as the example of Program 14.1. Be aware that critical sections can arise in other ways. Code in a signal handler executes asynchronously with the rest of the program, so it can be thought of as logically executing in a separate thread of execution. Variables that are modified in the signal handler and used in the rest of the program must be treated as part of a critical section. In Program 8.6 on page 271, the signal handler and the results function compete for access to buf and buflen. The entry section or gatekeeper is the code in results to block SIGUSR1; the exit section is the code to unblock SIGUSR1 and to restore the original signal mask.

Program 2.3 on page 39 illustrates a related problem that can arise with recursive calls to nonreentrant functions such as strtok. Although this example is not strictly a critical section problem by the definition given above, it has the same characteristics because the single thread of execution changes its execution environment when a function call pushes a new activation record on the stack.

In 1965, E. W. Dijkstra [30] proposed the semaphore abstraction for high-level management of mutual exclusion and synchronization. A semaphore is an integer variable with two atomic operations, wait and signal. Other names for wait are down, P and lock. Other names for signal are up, V, unlock and post.

If S is greater than zero, wait tests and decrements S in an atomic operation. If S is equal to zero, the wait tests S and blocks the caller in an atomic operation.

If threads are blocked on the semaphore, then S is equal to zero and signal unblocks one of these waiting threads. If no threads are blocked on the semaphore, signal increments S. In POSIX:SEM terminology, the wait and signal operations are called semaphore lock and semaphore unlock, respectively. We can think of a semaphore as an integer value and a list of processes waiting for a signal operation.

void wait(semaphore_t *sp) {
   if (sp->value > 0)
      sp->value--;
   else {
      <Add this process to sp->list>
      <block>
   }
}

void signal(semaphore_t *sp) {
   if (sp->list != NULL)
      <remove a process from sp->list and put in ready state>
   else
      sp->value++;
}

The wait and signal operations must be atomic. An atomic operation is an operation that, once started, completes in a logically indivisible way (i.e., without any other related instructions interleaved). In this context, being atomic means that if a process calls wait, no other process can change the semaphore until the semaphore is decremented or the calling process is blocked. The signal operation is atomic in a similar way. Semaphore implementations use atomic operations of the underlying operating system to ensure correct execution.

wait(&S);                                /* entry section or gatekeeper */
<critical section>
signal(&S);                                             /* exit section */
<remainder section>

Processes using semaphores must cooperate to protect a critical section. The code of Example 14.5 works, provided that all processes call wait(&S) before entering their critical sections and that they call signal(&S) when they leave. If any process fails to call wait(&S) because of a mistake or oversight, the processes may not execute the code of the critical section in a mutually exclusive manner. If a process fails to call signal(&S) when it finishes its critical section, other cooperative processes are blocked from entering their critical sections.

Process 1 executes:           Process 2 executes:
  a;                            wait(&sync);
  signal(&sync);                b;

Because sync is initially 0, process 2 blocks on its wait until process 1 calls signal.

Process 1 executes:           Process 2 executes:
   for( ; ; ) {                  for( ; ; ) {
      wait(&S);                     wait(&Q);
      a;                            b;
      signal(&Q);                   signal(&S);
   }                             }

Process 1 executes:           Process 2 executes:
   for( ; ; ) {                  for( ; ; ) {
      wait(&Q);                     wait(&S);
      wait(&S);                     wait(&Q);
      a;                            b;
      signal(&S);               signal(&Q);
      signal(&Q);               signal(&S);
   }                             }

A semaphore synchronizes processes by requiring that the value of the semaphore variable be nonnegative. More general forms of synchronization allow synchronization on arbitrary conditions and have mechanisms for combining synchronization conditions. OR synchronization refers to waiting until any condition in a specified set is satisfied. The use of select or poll to monitor multiple file descriptors for input is a form of OR synchronization. NOT synchronization refers to waiting until some condition in a set is not true. NOT synchronization can be used to enforce priority ordering [76]. AND synchronization refers to waiting until all the conditions in a specified set of conditions are satisfied. AND synchronization can be used for simultaneous control of multiple resources such as that needed for Exercise 14.10. POSIX:XSI semaphore sets described in Chapter 15 are capable of providing AND synchronization.

A POSIX:SEM semaphore is a variable of type sem_t with associated atomic operations for initializing, incrementing and decrementing its value. The POSIX:SEM Semaphore Extension defines two types of semaphores, named and unnamed. An implementation supports POSIX:SEM semaphores if it defines _POSIX_SEMAPHORES in unistd.h. The difference between unnamed and named semaphores is analogous to the difference between ordinary pipes and named pipes (FIFOs). This section discusses unnamed semaphores. Named semaphores are discussed in Section 14.5.

#include <semaphore.h>
sem_t sem;

The POSIX:SEM Extension does not specify the underlying type of sem_t. One possibility is that sem_t acts like a file descriptor and is an offset into a local table. The table values point to entries in a system table. A particular implementation may not use the file descriptor table model but instead may store information about the semaphore with the sem_t variable. The semaphore functions take a pointer to the semaphore variable as a parameter, so system implementers are free to use either model. You may not make a copy of a sem_t variable and use it in semaphore operations.

POSIX:SEM semaphores must be initialized before they are used. The sem_init function initializes the unnamed semaphore referenced by sem to value. The value parameter cannot be negative. Our examples use unnamed semaphores with pshared equal to 0, meaning that the semaphore can be used only by threads of the process that initializes the semaphore. If pshared is nonzero, any process that can access sem can use the semaphore. Be aware that simply forking a child after creating the semaphore does not provide access for the child. The child receives a copy of the semaphore, not the actual semaphore.

SYNOPSIS

  #include <semaphore.h>

  int sem_init(sem_t *sem, int pshared, unsigned value);
                                                                POSIX:SEM

If successful, sem_init initializes sem. Interestingly, POSIX does not specify the return value on success, but the rationale mentions that sem_init may be required to return 0 in a future specification. If unsuccessful, sem_init returns –1 and sets errno. The following table lists the mandatory errors for sem_init.

sem_t semA;

if (sem_init(&semA, 0, 1) == -1)
   perror("Failed to initialize semaphore semA");

The sem_destroy function destroys a previously initialized unnamed semaphore referenced by the sem parameter.

SYNOPSIS

    #include <semaphore.h>

    int sem_destroy(sem_t *sem);
                                                POSIX:SEM

If successful, sem_destroy returns 0. If unsuccessful, sem_destroy returns –1 and sets errno. The sem_destroy function sets errno to EINVAL if *sem is not a valid semaphore.

sem_t semA;

if (sem_destroy(&semA) == -1)
   perror("Failed to destroy semA");

The semaphore operations described in this section apply both to POSIX:SEM unnamed semaphores and to POSIX:SEM named semaphores described in Section 14.5.

The sem_post function implements classic semaphore signaling. If no threads are blocked on sem, then sem_post increments the semaphore value. If at least one thread is blocked on sem, then the semaphore value is zero. In this case, sem_post causes one of the threads blocked on sem to return from its sem_wait function, and the semaphore value remains at zero. The sem_post function is signal-safe and can be called from a signal handler.

SYNOPSIS

    #include <semaphore.h>

    int sem_post(sem_t *sem);
                                                  POSIX:SEM

If successful, sem_post returns 0. If unsuccessful, sem_post returns –1 and sets errno. The sem_post operation sets errno to EINVAL if *sem does not correspond to a valid semaphore.

The sem_wait function implements the classic semaphore wait operation. If the semaphore value is 0, the calling thread blocks until it is unblocked by a corresponding call to sem_post or until it is interrupted by a signal. The sem_trywait function is similar to sem_wait except that instead of blocking when attempting to decrement a zero-valued semaphore, it returns –1 and sets errno to EAGAIN.

SYNOPSIS

    #include <semaphore.h>

    int sem_trywait(sem_t *sem);
    int sem_wait(sem_t *sem);
                                                  POSIX:SEM

If successful, these functions return 0. If unsuccessful, these functions return –1 and set errno. These functions set errno to EINVAL if *sem does not correspond to a valid semaphore. The sem_trywait sets errno to EAGAIN if it would block on an ordinary sem_wait.

The sem_wait and sem_trywait functions may set errno to EINTR if they are interrupted by a signal. Any program that catches signals must take care when using semaphore operations, since the standard allows sem_wait and sem_trywait to return when a signal is caught and the signal handler returns. Program 14.2 restarts the sem_wait if it is interrupted by a signal.

Program 14.2 shows how to implement a shared variable that is protected by semaphores. The initshared function initializes the value of the shared variable. It would normally be called only once. The getshared function returns the current value of the variable, and the incshared function atomically increments the variable. If successful, these functions return 0. If unsuccessful, these functions return –1 and set errno. The shared variable (shared) is static, so it can be accessed only through the functions of semshared.c. Although shared is a simple integer in Program 14.2, functions of the same form can be used to implement any type of shared variable or structure.

#include <errno.h>
#include <semaphore.h>

static int shared = 0;
static sem_t sharedsem;

int initshared(int val) {
    if (sem_init(&sharedsem, 0, 1) == -1)
        return -1;
    shared = val;
    return 0;
}

int getshared(int *sval) {
    while (sem_wait(&sharedsem) == -1)
        if (errno != EINTR)
            return -1;
    *sval = shared;
    return sem_post(&sharedsem);
}

int incshared() {
    while (sem_wait(&sharedsem) == -1)
        if (errno != EINTR)
            return -1;
    shared++;
    return sem_post(&sharedsem);
}

Programs 14.3 and 14.4 return to the original critical section problem of Program 14.1. The new version uses threads to illustrate the need to protect the critical section. The function in Program 14.3 is meant to be used as a thread. It outputs a message, one character at a time. To make it more likely to be interrupted in the middle of the message, the thread sleeps for 10 ms after each character is output. Program 14.4 creates a number of threadout threads and waits for them to terminate.

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#define BUFSIZE 1024
#define TEN_MILLION 10000000L

/* ARGSUSED */
void *threadout(void *args) {
    char buffer[BUFSIZE];
    char *c;
    struct timespec sleeptime;

    sleeptime.tv_sec = 0;
    sleeptime.tv_nsec = TEN_MILLION;
    snprintf(buffer, BUFSIZE, "This is a thread from process %ld
",
             (long)getpid());
    c = buffer;
   /*****************start of critical section ********************/
    while (*c != '') {
        fputc(*c, stderr);
        c++;
        nanosleep(&sleeptime, NULL);
    }
   /*******************end of critical section ********************/
    return NULL;
}

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void *threadout(void *args);

int main(int argc, char *argv[]) {
    int error;
    int i;
    int n;
    pthread_t *tids;

    if (argc != 2){   /* check for valid number of command-line arguments */
        fprintf (stderr, "Usage: %s numthreads
", argv[0]);
        return 1;
    }
    n = atoi(argv[1]);
    tids = (pthread_t *)calloc(n, sizeof(pthread_t));
    if (tids == NULL) {
        perror("Failed to allocate memory for thread IDs");
        return 1;
    }
    for (i = 0; i < n; i++)
        if (error = pthread_create(tids+i, NULL, threadout, NULL)) {
            fprintf(stderr, "Failed to create thread:%s
", strerror(error));
            return 1;
        }
    for (i = 0; i < n; i++)
        if (error = pthread_join(tids[i], NULL)) {
            fprintf(stderr, "Failed to join thread:%s
", strerror(error));
            return 1;
        }
    return 0;
}

Program 14.5 is a version of Program 14.3 that protects its critical section by using a semaphore passed as its parameter. Although the main program does not use signals, this program restarts sem_wait if interrupted by a signal to demonstrate how to use semaphores with signals. Program 14.6 shows the corresponding main program. The main program initializes the semaphore to 1 before any of the threads are created.

#include <errno.h>
#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <unistd.h>
#define TEN_MILLION 10000000L
#define BUFSIZE 1024

void *threadout(void *args) {
    char buffer[BUFSIZE];
    char *c;
    sem_t *semlockp;
    struct timespec sleeptime;

    semlockp = (sem_t *)args;
    sleeptime.tv_sec = 0;
    sleeptime.tv_nsec = TEN_MILLION;
    snprintf(buffer, BUFSIZE, "This is a thread from process %ld
",
             (long)getpid());
    c = buffer;
   /****************** entry section *******************************/
    while (sem_wait(semlockp) == -1)        /* Entry section */
        if(errno != EINTR) {
            fprintf(stderr, "Thread failed to lock semaphore
");
            return NULL;
        }
   /****************** start of critical section *******************/
    while (*c != '') {
        fputc(*c, stderr);
        c++;
        nanosleep(&sleeptime, NULL);
    }
   /****************** exit section ********************************/
    if (sem_post(semlockp) == -1)         /* Exit section */
        fprintf(stderr, "Thread failed to unlock semaphore
");
   /****************** remainder section ***************************/
    return NULL;
}

semlock = sem_init(*semlock, 0, 1)

semlock = sem_init(*semlock, 0, 0)

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void *threadout(void *args);

int main(int argc, char *argv[]) {
    int error;
    int i;
    int n;
    sem_t semlock;
    pthread_t *tids;

    if (argc != 2){   /* check for valid number of command-line arguments */
        fprintf (stderr, "Usage: %s numthreads
", argv[0]);
        return 1;
    }
    n = atoi(argv[1]);
    tids = (pthread_t *)calloc(n, sizeof(pthread_t));
    if (tids == NULL) {
        perror("Failed to allocate memory for thread IDs");
        return 1;
    }
    if (sem_init(&semlock, 0, 1) == -1) {
        perror("Failed to initialize semaphore");
        return 1;
    }
    for (i = 0; i < n; i++)
        if (error = pthread_create(tids + i, NULL, threadout, &semlock)) {
            fprintf(stderr, "Failed to create thread:%s
", strerror(error));
            return 1;
        }
    for (i = 0; i < n; i++)
        if (error = pthread_join(tids[i], NULL)) {
            fprintf(stderr, "Failed to join thread:%s
", strerror(error));
            return 1;
        }
    return 0;
}

Exercise 14.19 illustrates the importance of properly initializing the semaphore value. The sem_getvalue function allows a user to examine the value of either a named or unnamed semaphore. This function sets the integer referenced by sval to the value of the semaphore without affecting the state of the semaphore. Interpretation of sval is a little tricky: It holds the value that the semaphore had at some unspecified time during the call, but not necessarily the value at the time of return. If the semaphore is locked, sem_getvalue either sets sval to zero or to a negative value indicating the number of threads waiting for the semaphore at some unspecified time during the call.

SYNOPSIS

    #include <semaphore.h>

    int sem_getvalue(sem_t *restrict sem, int *restrict sval);
                                                                POSIX:SEM

If successful, sem_getvalue returns 0. If unsuccessful, sem_getvalue returns –1 and sets errno. The sem_getvalue function sets errno to EINVAL if *sem does not correspond to a valid semaphore.

POSIX:SEM named semaphores can synchronize processes that do not share memory. Named semaphores have a name, a user ID, a group ID and permissions just as files do. A semaphore name is a character string that conforms to the construction rules for a pathname. POSIX does not require that the name appear in the filesystem, nor does POSIX specify the consequences of having two processes refer to the same name unless the name begins with the slash character. If the name begins with a slash (/), then two processes (or threads) that open the semaphore with that name refer to the same semaphore. Consequently, always use names beginning with a / for POSIX:SEM named semaphores. Some operating systems impose other restrictions on semaphore names.

SYNOPSIS

  #include <semaphore.h>

  sem_t *sem_open(const char *name, int oflag, ...);
                                                        POSIX:SEM

#include <errno.h>
#include <fcntl.h>
#include <semaphore.h>
#include <sys/stat.h>
#define PERMS (mode_t)(S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
#define FLAGS (O_CREAT | O_EXCL)

int getnamed(char *name, sem_t **sem, int val) {
    while (((*sem = sem_open(name, FLAGS, PERMS, val)) == SEM_FAILED) &&
            (errno == EINTR)) ;
    if (*sem != SEM_FAILED)
        return 0;
    if (errno != EEXIST)
        return -1;
    while (((*sem = sem_open(name, 0)) == SEM_FAILED) && (errno == EINTR)) ;
    if (*sem != SEM_FAILED)
        return 0;
    return -1;
}

SYNOPSIS

  #include <semaphore.h>

  int sem_close(sem_t *sem);
                                POSIX:SEM

#include <errno.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>
#include "restart.h"
#define BUFSIZE 1024
int getnamed(char *name, sem_t **sem, int val);

int main  (int argc, char *argv[]) {
    char buffer[BUFSIZE];
    char *c;
    pid_t childpid = 0;
    int delay;
    volatile int dummy = 0;
    int i, n;
    sem_t *semlockp;

    if (argc != 4){       /* check for valid number of command-line arguments */
        fprintf (stderr, "Usage: %s processes delay semaphorename
", argv[0]);
        return 1;
    }
    n = atoi(argv[1]);
    delay = atoi(argv[2]);
    for (i = 1; i < n; i++)
        if (childpid = fork())
            break;
    snprintf(buffer, BUFSIZE,
             "i:%d  process ID:%ld  parent ID:%ld  child ID:%ld
",
             i, (long)getpid(), (long)getppid(), (long)childpid);
    c = buffer;
    if (getnamed(argv[3], &semlockp, 1) == -1) {
        perror("Failed to create named semaphore");
        return 1;
    }
    while (sem_wait(semlockp) == -1)                         /* entry section */
        if (errno != EINTR) {
            perror("Failed to lock semlock");
            return 1;
        }
    while (*c != '') {                                  /* critical section */
        fputc(*c, stderr);
        c++;
        for (i = 0; i < delay; i++)
            dummy++;
    }
    if (sem_post(semlockp) == -1) {                           /* exit section */
        perror("Failed to unlock semlock");
        return 1;
    }
    if (r_wait(NULL) == -1)                              /* remainder section */
        return 1;
    return 0;
}

SYNOPSIS

  #include <semaphore.h>

  int sem_unlink(const char *name);
                                      POSIX:SEM

#include <errno.h>
#include <semaphore.h>

int destroynamed(char *name, sem_t *sem) {
    int error = 0;

    if (sem_close(sem) == -1)
        error = errno;
    if ((sem_unlink(name) != -1) && !error)
        return 0;
    if (error)        /* set errno to first error that occurred */
        errno = error;
    return -1;
}

The exercises in this section are along the lines of the runsim program developed in the exercises of Section 3.9. In those exercises, runsim reads a command from standard input and forks a child that calls execvp to execute the command. That runsim program takes a single command-line argument specifying the number of child processes allowed to execute simultaneously. It also keeps a count of the children and uses wait to block when it reaches the limit.

In these exercises, runsim again reads a command from standard input and forks a child. The child in turn forks a grandchild that calls execvp. The child waits for the grandchild to complete and then exits. Figure 14.1 shows the structure of runsim when three such pairs are executing. This program uses semaphores to control the number of simultaneous executions.

Figure 14.1. The structure of runsim when the grandchildren, not the children, call execvp.

int getlicense(void);

int returnlicense(void);

int initlicense(void);

int addtolicense(int n);

int removelicenses(int n);

runsim n

void docommand(char *cline);

Most books on operating systems [107, 122] discuss the classical semaphore abstraction. The book UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers by Schimmel [103] presents an advanced look at how these issues apply to design of multiprocessor kernels.