Conceptually, a semaphore is a data structure that is shared by several processes.^[1] Semaphores are most often used to synchronize operations when multiple processes access a common, non-shareable resource. By using semaphores, we attempt to avoid starvation (which occurs when a process is habitually denied access to a resource it needs) and deadlock (which occurs when two or more processes each hold a resource that the other needs while waiting for the other process to release its resource). When used to synchronize the access to a resource, a semaphore is initially set to the number of available resources. Each time a process wants to obtain the resource, the associated semaphore is tested. A positive, nonzero semaphore value indicates the resource is available. To indicate it has gained access to the resource, the process decrements the semaphore. For events to progress correctly, the test and decrement operation on the semaphore must be atomic (i.e., noninterruptible/indivisible). If the tested semaphore is zero, indicating the resource is not available, the requesting process must wait. When a process is finished with a semaphore-associated resource, the process indicates the return of the resource by incrementing the semaphore. Once a resource is returned, other processes that have been waiting for the resource are notified by the system. Semaphores that control access to a single resource, taking the value of 0 (resource is in use) or 1 (resource is available), are often called binary semaphores.^[2] Semaphores controlling access to multiple resources, thus assuming a range of nonnegative values, are frequently called counting semaphores.

E. W. Dijkstra (1965) did much of the early work describing the use of semaphores to coordinate access to shared resources. Most college-level operating systems textbooks—for example, Silberschatz and Peterson (1989), Tanenbaum (2001), Nutt (2002), Stallings (2001), and Deitel (1990)—contain excellent discussions on the theory and use of semaphores for process synchronization.

Implementation-wise, a semaphore is a nonnegative integer that is stored in the kernel. Access to the semaphore is provided by a series of semaphore system calls. The semaphore system calls assure the user the test and decrement operations on the semaphore will be atomic. Likewise, the semaphore system calls, by default, cause the invoking process to block if the semaphore value indicates the resource is not available (i.e., the semaphore is a 0). When the resource becomes available and the semaphore becomes nonzero, the system notifies the queued, waiting processes of this event. To increase their flexibility, in UNIX semaphores are generated as sets (arrays) consisting of one or more semaphores. Operations acting upon individual semaphores within the set or upon the entire semaphore set are provided.

Before a semaphore set can be used, it must be created. The creation of the semaphore set generates a unique data structure that the system uses to identify and manipulate the semaphores. The definition of system semaphore data structure is found in the system-dependent include file <bits/sem.h>. This file is not directly referenced by the programmer, since the standard include file <sys/sem.h> includes this file.

struct semid_ds {
  struct ipc_perm sem_perm;             /* operation permission struct */
  __time_t sem_otime;                   /* last semop() time */
  unsigned long int __unused1;
  __time_t sem_ctime;                   /* last time changed by semctl() */
  unsigned long int __unused2;
  unsigned long int sem_nsems;          /* number of semaphores in set */
  unsigned long int __unused3;
  unsigned long int __unused4;
};

In keeping with its origins, and for System V compatibility, the semid_ds structure is also defined in <linux/sem.h> as

struct semid_ds {
  struct ipc_perm sem_perm;           /* permissions .. see ipc.h */
  __kernel_time_t sem_otime;          /* last semop time */
  __kernel_time_t sem_ctime;          /* last change time */
  struct sem      *sem_base;          /* ptr to first semaphore in array */
  struct sem_queue *sem_pending;      /* pending operations to be processed */
  struct sem_queue **sem_pending_last;/* last pending operation */
  struct sem_undo *undo;              /* undo requests on this array */
  unsigned short  sem_nsems;          /* no. of semaphores in array */
};

As with message queues, there is a bit of a disconnect between the way we view and discuss semaphores and the way they may actually be implemented at a system level. Additional system-specific details can be found in the source code for semaphore implementation in the kernel source directory /usr/src/linux-XX.XX.XX/ipc (where XX is the appropriate version number). On our system the files sem.c and util.h contain additional semaphore implementation details.

Using the <linux/sem.h> definition as our reference, the system semaphore data structure semid_ds contains a permission structure of type ipc_perm, which is used to specify the access permissions for the semaphore set. The access permission structure is followed by two time members. These store the time of the last operation on the semaphore (sem_otime) and the time of its last modification (sem_ctime). The next member is a reference, sem_base, to an array (set) of structures of type sem. The sem structure contains the semaphore value and the ID of the last process to operate on the semaphore. Here is the definition of a sem structure:

struct sem {
        int     semval;         /* current value         */
        int     sempid;         /* pid of last operation */
};

Following the pointer to the base of the semaphore array are three additional pointers. The sem_pending member references a linked list (treated as a queue) of pending semaphore operations. Normally, semaphore operations are done immediately, so requests are only added to this list if for some reason the request cannot processed immediately. The sem_pending_last member references the end of the same list. The sem_undo member references a list of undo operations. These operations, stored when a semaphore operation sets the SEM_UNDO flag, can be used to undo requested semaphore operations to return the semaphore to its previous state. The kernel uses the undo list information to reverse semaphore operations when a process exits without releasing its allocated semaphores. This action helps reduce the chance of deadlock. The system semaphore data structure also keeps track of the number of semaphores in the set (sem_nsems).

A conceptual arrangement of a system semaphore structure for a newly allocated set of three semaphores is shown in Figure 7.1.

Figure 7.1. Data structures for a set of three semaphores.

To create a semaphore or gain access to one that exists, the semget system call, shown in Table 7.1, is used.

<sys/types.h>
<sys/ipc.h>
<sys/sem.h>

The semget system call takes three arguments. The first argument, key, is used by the system to generate a unique semaphore identifier. The second argument, nsems, is the number of semaphores in the set. The system uses the nsems value when allocating the array of sem structures. Remember, as with all arrays in C/C++, the array of sem structures that represents the set of semaphores is indexed starting at 0. The nsems value should be less than or equal to the SEMMSL value, which sets the upper boundary for the number of semaphores for a given semaphore ID. The third argument, semflg, is used to specify access permission and/or special creation conditions. The low-order bits of the semflg value are used to specify the access permissions for the owner, group, and other. Read and write permissions control reading and alteration of the semaphore; execute permission settings are ignored. The flags IPC_CREAT and IPC_EXCL may be ORed with the permission value.

If the semget system call is successful, a nonnegative integer, the semaphore identifier, is returned. If the value for key is IPC_PRIVATE or the value for key does not have a semaphore identifier associated with it, and IPC_CREAT has been specified, a new set of semaphores is created. When created, the semaphore set represented by the array of sem structures is not initialized. If IPC_CREAT is specified (but not IPC_EXCL) and the semaphore set for the indicated key value already exists, the semget system call returns the associated semaphore identifier. When using semget to access an established semaphore set (such as in a client process), the value of nsems can be set to 0 (a don't-care value).

When the semaphore is created, the system sets, respectively, the semid_ds members sem_perm.cuid, sem_perm.uid, sem_perm.cgid, and sem_perm.gid to the effective user and group ID of the invoking process. The member sem_otime is set to 0, and sem_ctime is assigned the current time. The nsems member stores the number of semaphores in the semaphore set.

If the semget system call fails, it returns a −1 and sets the value stored in errno. Error messages for semget are shown in Table 7.2.

Program 7.1 attempts to create several semaphore sets, each containing three semaphores.

File : p7.1.cxx
  |     /* Creating sets of semaphores */
  |     #include <iostream>
  |     #include <cstdio>
  |     #include <sys/types.h>
  +     #include <sys/ipc.h>
  |     #include <sys/sem.h>
  |     using namespace std;
  |     int
  |     main( ){
 10       int      sem1, sem2, sem3;
  |       key_t    ipc_key;
  |       ipc_key = ftok(".", 'S'),
  |       if ((sem1 = semget(ipc_key, 3, IPC_CREAT | 0666)) == -1) {
  |         cerr << "semget: IPC_CREAT | 0666" << endl;
  +       }
  |       cout << "sem1 identifier " <<  sem1 << endl;
  |       if ((sem2 = semget(ipc_key, 3, IPC_CREAT|IPC_EXCL|0666)) == -1) {
  |         cerr << "semget: IPC_CREAT | IPC_EXCL | 0666" << endl;
  |       }
 20       cout << "sem2 identifier " <<  sem2 << endl;
  |       if ((sem3 = semget(IPC_PRIVATE, 3, 0600)) == -1) {
  |         cerr << "semget: IPC_PRIVATE" << endl;
  |       }
  |       cout << "sem3 identifier " <<  sem3 <<  endl;
  +       return 0;
  |     }

The first call to semget, provided the system limits have not been reached, creates a set of three semaphores. The permissions for the set are read and alter (write) for the owner, group, and others (world). The value of the semaphore identifier is tied to the key value that is produced by the call to ftok. The second call to semget attempts to create a second set of three semaphores. The call uses the same key value as the first but includes the specification IPC_EXCL. With the IPC_EXCL flag set and the previous successful creation of the semaphore set using the same key value, this invocation of semget will fail. The third call to semget creates a three-semaphore set used by specifying IPC_PRIVATE instead of using the ftok key value. The semaphore identifier generated for this set will be private to this process.

When the program is run twice consecutively, the output generated will be similar to that shown in Figure 7.2.

linux$ p7.1
sem1 identifier 9797637
semget: IPC_CREAT | IPC_EXCL | 0666: File exists
sem2 identifier -1
sem3 identifier 9830406

linux$ p7.1
sem1 identifier 9797637
semget: IPC_CREAT | IPC_EXCL | 0666: File exists
sem2 identifier -1
sem3 identifier 9863175

Notice that when the program is run the second time, the same semaphore identifier (9797637) is returned from the initial call to semget. Without the IPC_EXCL flag, the semget system call will not fail if the semaphore set has already been created, but will instead return the associated semaphore identifier. The creation of a second private semaphore set by the second invocation of the program produces another unique semaphore identifier (9863175), which is different from the first private semaphore identifier (9830406). The output of the ipcs command, shown in Figure 7.3, verifies the presence and permissions of the three semaphore sets that were created by the user gray. Notice that the key for each of the private semaphore sets is 0.

linux$ ipcs -s
-----Semaphore Arrays------
key       semid     owner     perms     nsems     status
0x53157f08 9797637   gray      666       3
0x00000000 9830406   gray      600       3
0x00000000 9863175   gray      600       3

As written, Program 7.1 does not remove the semaphore sets it creates. Semaphores, like message queues, are a limited resource. In a programming setting, semaphores can be removed with the semctl system call (see the following section). Semaphores may also be removed at the command-line level using the ipcrm command (as discussed in Chapter 6, Section 6.1). If there are several semaphores to remove, a shell script, such as that shown in Program 7.2, can be used to automate the removal process.

File : clean
  |     #!/bin/ksh
  |     #
  |     #  Korn Shell script to remove all existing semaphores for a user
  |     #
  +     list=$(ipcs -s | grep "$USER" | cut -d' ' -f2)
  |     count=0
  |     for semaphore in $list
  |     do
  |      ipcrm sem $semaphore > /dev/null
 10      ((count=count+1))
  |     done
  |     print "$count semaphore(s) for $USER removed"

The semget system call (Table 7.3) is used to create or gain access to a set of semaphores. The semctl system call allows the user to perform a variety of generalized control operations on the system semaphore structure, on the semaphores as a set, and on individual semaphores. Additional manipulative operations on specific semaphores within a set are covered in the following section on semaphore operations (Section 7.4).

<sys/types.h>
<sys/ipc.h>
<sys/sem.h>

int semctl(int semid, int semnum, int cmd,
           union semun arg);

The semctl system call takes four arguments. The first argument, semid, is a valid semaphore identifier that was returned by a previous semget system call. The second argument, semnum, is the number of semaphores in the semaphore set. In most cases, this value is greater than 0 but less than the system limit. However, we will see occasions when the value for semnum is set to 0. These occasions arise when we ask semctl to perform an operation for which the number of semaphores in the set is not relevant. The third argument to semctl, cmd, is an integer command value (usually expressed as one of the symbolic constants found in the header files <sys/ipc.h> or <sys/sem.h>). As discussed in detail in Section 7.3.1, “Semaphore Control Details,” the cmd value directs semctl to take one of several control actions. Each action requires specific access permissions to the semaphore control structure (i.e., read or alter). The fourth argument to semctl, arg, is a union of type semun. Given the action specified by the preceding cmd argument, the data in arg can be one of any of the following four values:

In some versions of UNIX the definition of the semun union is found in the include files required by semctl. However, technically the user should define the union. To this end, the manual page for semctl contains the following cryptic reference.

#if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
/* union semun is defined by including <sys/sem.h> */
#else
/* according to X/OPEN we have to define it ourselves */
union semun {
        int val;                    /* value for SETVAL */
        struct semid_ds *buf;       /* buffer for IPC_STAT, IPC_SET */
        unsigned short int *array;  /* array for GETALL, SETALL */
        struct seminfo *__buf;      /* buffer for IPC_INFO */
};
#endif

This sequence of preprocessor directives determines whether the programmer defines the semun union. If __GNU_LIBRARY__ has been defined (is nonzero), and _SEM_SEMUN_UNDEFINED has not been defined, the definition of the union semun is found in the include file <sys/sem.h>. Otherwise, the user defines the union. To be safe, this set of preprocessor directives should be placed at the top any program that will make use of the fourth argument of the semctl call. Its omission may cause the semctl system call to fail, returning the value EFAULT (bad address). Further, when specifying arg as the fourth argument to semctl, the value for arg should be explicitly assigned (e.g., arg.buf=ptr_to_my_structure). This assignment must be done prior to the calling of semctl (see Program 7.3).

File : p7.3.cxx
  |     /*
  |          Using the semctl system call
  |      */
  |     #include <iostream>
  +     #include <cstdio>
  |     #include <sys/ipc.h>
  |     #include <sys/sem.h>
  |     #include <time.h>
  |     #define  NS    3        <-- 1
 10     #if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
  |                                        // definition in <sys/sem.h>
  |     #else
  |     union semun {                      // We define:
  |       int val;                         // value  for SETVAL
  +       struct semid_ds *buf;            // buffer for IPC_STAT, IPC_SET
  |       unsigned short int *array;       // array  for GETALL, SETALL
  |       struct seminfo *__buf;           // buffer for IPC_INFO
  |     };
  |     #endif
 20     using namespace std;
  |     int
  |     main( ){
  |       int             sem_id, sem_value, i;
  |       key_t           ipc_key;
  +       struct semid_ds sem_buf;
  |       unsigned short int  sem_array[NS] = {3, 1, 4};
  |       union semun     arg;
  |       ipc_key = ftok(".", 'S'),
  |
 30       if ((sem_id = semget(ipc_key, NS, IPC_CREAT | 0660)) == -1) {
  |         perror("semget: IPC_CREAT | 0660");
  |         return 1;
  |       }
  |       cout << "Semaphore identifier " << sem_id << endl;
  +       arg.buf = &sem_buf;        <-- 2
  |       if (semctl(sem_id, 0, IPC_STAT, arg) == -1) {
  |         perror("semctl: IPC_STAT");
  |         return 2;
  |       }
 40       cout << "Created " <<  ctime(&sem_buf.sem_ctime) << endl;
  |       arg.array = sem_array;        <-- 3
  |       if (semctl(sem_id, 0, SETALL, arg) == -1) {
  |         perror("semctl: SETALL");
  |         return 3;
  +       }
  |       for (i = 0; i < NS; ++i) {
  |         if ((sem_value = semctl(sem_id, i, GETVAL, 0)) == -1) {
  |           perror("semctl: GETVAL");
  |           return 4;
 50         }
  |         cout << "Semaphore " << i << " has value of " << sem_value << endl;
  |       }
  |       if (semctl(sem_id, 0, IPC_RMID, 0) == -1) {
  |         perror("semctl: IPC_RMID");
  +         return 5;
  |       }
  |       return 0;
  |     }

linux$ g++ -g -o p7.3 p7.3.cxx        <-- 1
linux$ gdb p7.3
GNU gdb 5.0rh-5 Red Hat Linux 7.1
Copyright 2001 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "i386-redhat-linux"...
(gdb) break 40        <-- 2
Breakpoint 1 at 0x8048890: file p7.3.cxx, line 40.
(gdb) run
Starting program: /home/faculty/gray/revision/07/p7.3
Semaphore identifier 10027013
Breakpoint 1, main () at p7.3.cxx:40
40        cout << "Created " <<  ctime(&sem_buf.sem_ctime) << endl;
Current language:  auto; currently c++
(gdb) print sem_buf
$1 = {sem_perm = {__key = 1393917704, uid = 500, gid = 1000, cuid = 500,
      cgid = 1000, mode = 432, __pad1 = 0, __seq = 306, __pad2 = 0,
      __unused1 = 0, __unused2 = 0}, sem_otime = 0, __unused1 = 0,
      sem_ctime = 1016545082, __unused2 = 0, sem_nsems = 3, __unused3 = 0,
      __unused4 = 0}
(gdb)

linux$ p7.3
Semaphore identifier 10027013
Created Tue Mar 19 08:38:02 2002

Semaphore 0 has value of 3
Semaphore 1 has value of 1
Semaphore 2 has value of 4

Additional operations on individual semaphores are accomplished by using the semop system call, shown in Table 7.5.

The semop system call requires three arguments and returns an integer value. If successful, semop returns a 0; otherwise it returns a −1 and sets errno to indicate the source of the error (see Table 7.9 for details). The first argument for semop, semid, is the semaphore identifier returned by a previous successful call to semget. The second argument, sops, is a reference to the base address of an array of semaphore operations that will be performed on the semaphore set associated with by the semid value. The semop system call will attempt to perform, in an all-or-nothing manner, all of the semaphore operations indicated by sops. The third argument, nsops, is the number of elements in the array of semaphore operations.

<sys/types.h>
<sys/ipc.h>
<sys/sem.h>

int semop(int semid, struct sembuf *sops,
          unsigned nsops);

Each element of the semaphore operation array is a structure of type sembuf.

/*
    User semaphore template for semop system calls.
 */

struct sembuf {
  unsigned short int sem_num;   // semaphore #: 0 = first
  short int sem_op;             // semaphore operation
  short int sem_flg;            // operation flags
};

The first member of the sembuf structure, sem_num, is the semaphore number (remember, the first semaphore is 0, the second 1, etc.). The second member of sembuf, sem_op, is the operation to be performed on the semaphore. A positive integer value means to increment the semaphore (in general, indicating a release or return of a resource), a negative value for sem_op means to decrement the semaphore (an attempt to acquire a resource), and a value of 0 means to test if the semaphore is currently at 0 (in use, all resource(s) allocated). Additional details on semaphore operations will be provided in a subsequent section. The third member of sembuf is an operation flag. These flags are

Figure 7.6 shows a relationship of an arbitrary three-element semaphore operation array to an N element set of semaphores.

Figure 7.6. Three-semaphore operations for an N element set of semaphores.

Semaphore Operation Details

When the sem_op value is negative, the process specifying the operation is attempting to decrement the semaphore. The decrement of the semaphore is used to record the acquisition of the resource affiliated with the semaphore. When a semaphore value is to be modified, the accessing process must have alter permission for the semaphore set. The actions taken by the semop system call when the value for sem_op is negative are summarized in Table 7.6.

When the sem_op value is positive, the process is adding to the semaphore value. The addition is used to record the return (release) of the resource affiliated with the semaphore. Again, when a semaphore value is to be modified, the accessing process must have alter permission for the semaphore set. The actions taken by the semop system call when the value for sem_op is positive are summarized in Table 7.7.

When the sem_op value is zero, the process is testing the semaphore to determine if it is at 0. When a semaphore is at 0, the testing process can assume that all the resources affiliated with the semaphore are currently allocated (in use). For a semaphore value to be tested, the accessing process must have read permission for the semaphore set. The action taken by the semop system call when the value for sem_op is 0 is summarized in Table 7.8.

Table 7.6. Actions Taken by semop when the Value for sem_op is Negative.

Condition	Flag Set	Action Taken by semop
semval >= abs(semop)		Subtract abs(sem_op) from semval.
semval >= abs(semop)	SEM_UNDO	Subtract abs(sem_op) from semval and update the undo counter for the semaphore.
semval < abs(semop)		Increment semncnt for the semaphore and wait (block) until • semval >= abs(semop), then adjust semncnt and subtract as noted in the previous two rows of table. • semid is removed, then return −1 and set errno to EIDRM. • A signal is caught, then adjust semncnt and set errno to EINTR.
semval < abs(semop)	IPC_NOWAIT	Return −1 immediately and set errno to EAGAIN.

Table 7.7. Actions Taken by semop when the Value for sem_op Is Positive.

Condition	Flag Set	Action Taken by semop
		Add sem_op to semval.
	SEM_UNDO	Add sem_op to semval and update the undo counter for the semaphore.

The errors returned by semop, with an explanation of their meaning, are shown in Table 7.9.

If semop is successful, for each of the semaphores modified/referenced, semop sets the value of sempid to that of the calling process for each semaphore specified in the array referenced by sops. Additionally, both the sem_otime and sem_ctime members are set to the current time.

Program 7.4 demonstrates the use of the semop system call. Two semaphores are used to coordinate concurrent producer and consumer processes. The producer process generates (at its own pace) an integer value. The value is stored in a non-shareable resource (in this case a file in the local directory). The consumer process, once a new value has been generated, retrieves the value from the same file and displays the value to the screen. Two semaphores are used by the producer process to prevent it from overwriting a previously stored integer value before the consumer process has retrieved it (should the producer process be speedier than the consumer process). The consumer process uses the two semaphores to prevent it from retrieving the same value multiple times (should the producer process be slow in generating new values). The semaphores, which we will arbitrarily call READ and MADE, are treated in a binary manner. By convention, the MADE semaphore is set to 1 by the producer process once the producer has stored its newly created integer value in the file. The READ semaphore is set to 1 by the consumer process once the consumer has read the value stored in the file by the producer. If the number has yet to be made by the producer or the number has not been read by the consumer, the corresponding semaphore value will be 0. The producer will gain access to the file to store the generated number only if the number currently in the file has been consumed. Likewise, the consumer can gain access to the file to read the stored number only if a new value has been made. Figure 7.7 shows the contents of the two semaphores in the producer and consumer processes and their relationship to one another. At the start we indicate that the current stored number has been read (we set READ to 1) and that a new number has not been generated (we set MADE to 0).

Figure 7.7. Semaphore values in the producer and consumer processes.

Table 7.8. Actions Taken by semop when the Value for sem_op is Zero.

Condition	Flag Set	Action Taken by semop
semval == 0		Return immediately.
semval != 0	IPC_NOWAIT	Return −1 immediately and set errno to EAGAIN.
semval != 0		Increment semzcnt for the semaphore and wait (block) until semval == 0, then adjust semzcnt and return. semid is removed, then return −1 and set errno to EIDRM. A signal is caught, then adjust semzcnt and set errno to EINTR.

Table 7.9. semop Error Messages.

#	Constant	perror Message	Explanation
4	EINTR	Interrupted system call	While in a wait queue for the semaphore, a signal was received by the calling process.
7	E2BIG	Argument list too long	The value for nsops is greater than the system limit.
11	EAGAIN	Resource temporarily unavailable	The requested operation would cause the calling process to block, but IPC_NOWAIT was specified.
12	ENOMEM	Cannot allocate memory	The limit for number of processes requesting SEM_UNDO has been exceeded.
13	EACCES	Permission denied	The requested operation is forbidden by the current access permissions.
14	EFAULT	Bad address	The value for sops references an illegal address.
22	EINVAL	Invalid argument	The semaphore identifier is invalid. The number of semaphores requesting SEM_UNDO is greater than the system limit.
27	EFBIG	File too large	The value for sem_num is < 0 or >= to the number of semaphores in the set.
34	ERANGE	Numerical result out of range	The requested operation would cause the system semaphore adjustment value to exceed its limit.
43	EIDRM	Identifier removed	The semaphore set associated with semid value has been removed.

A high-level algorithm for the producer and consumer processes would be as follows:

Producer

While 10 new numbers not generated

• Generate a new number

• If the current stored number has not been read, then wait

• Store the new number in the file

• Indicate that a new number has been made

Consumer

Forever

• If a new number has not been made, then wait

• Retrieve the new number from the file

• Indicate new number has been read

• Display the retrieved number

For discussion purposes, the program (which actually resides in a single file) has been divided into three sections, shown as Programs 7.4A, 7.4B, and 7.4C. The first part of the program, which establishes the operations that will be performed on the semaphores, creates the set of two semaphores and initializes them, is shown in Program 7.4A.

Example 7.4A. The first section of the producer/consumer problem.

File : p7.4.cxx
  |     /*
  |            The producer/consumer problem
  |      */
  |     #include <iostream>                    // Section ONE
  +     #include <cstdio>
  |     #include <unistd.h>
  |     #include <stdlib.h>
  |     #include <sys/types.h>
  |     #include <sys/ipc.h>
 10     #include <sys/sem.h>
  |     #define BUFFER "./buffer"
  |     #if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
  |                                            // definition in <sys/sem.h>
  |     #else
  +     union semun {                          // We define:
  |       int val;                             // value  for SETVAL
  |       struct semid_ds *buf;                // buffer for IPC_STAT, IPC_SET
  |       unsigned short int *array;           // array  for GETALL, SETALL
  |       struct seminfo *__buf;               // buffer for IPC_INFO
 20     };
  |     #endif
  |     using namespace std;
  |     int
  |     main(int argc, char *argv[ ]) {
  +       FILE           *fptr;
  |       static struct sembuf acquire = {0, -1, SEM_UNDO},        <-- 1
  |                            release = {0,  1, SEM_UNDO};
  |       pid_t           c_pid;
  |       key_t           ipc_key;
 30       static unsigned short   start_val[2] = {1, 0};
  |       int             semid, producer = 0, i, n, p_sleep, c_sleep;
  |       union semun     arg;
  |       enum { READ, MADE };
  |       if (argc != 2) {
  +         cerr << argv[0] <<  " sleep_time" << endl;
  |         return 1;
  |       }
  |       ipc_key = ftok(".", 'S'),
  |       if ((semid=semget(ipc_key, 2, IPC_CREAT|IPC_EXCL|0660)) != -1) {
 40         producer = 1;
  |         arg.array = start_val;
  |         if (semctl(semid, 0, SETALL, arg) == -1) {
  |           perror("semctl--producer--initialization");
  |           return 2;
  +         }
  |       } else if ((semid = semget(ipc_key, 2, 0)) == -1) {
  |         perror("semget--consumer--obtaining semaphore");
  |         return 3;
  |       }
 50       cout << (producer==1 ? "Producer" : "Consumer" )
               << " starting" << endl;

• (1)Define the two operations that can be done on a semaphore.

The program uses the symbolic constant BUFFER to reference a local file named ./buffer. This file acts as the non-shareable resource to be accessed by the producer and consumer processes. Following this definition is the declaration of the union semun as an argument of type semun is required for the semctl system call.

Using the sembuf structure as a template, the program defines two operations—acquire and release—that can be used with either of the semaphores. For both operations the value for the member sem_num has been set to 0. This value acts as a placeholder and will be changed dynamically to indicate which of the two semaphores within the set we are referencing. The sem_op member of each is set to −1 and 1 for acquire and release respectively. The value of −1 is used when we want to acquire a resource that is associated with a semaphore (indicated by decrementing the semaphore). The value 1 is used when we want to indicate the return of the resource (thus incrementing the associated semaphore). In either case, we set the value for sem_flg to SEM_UNDO to allow rollback. The variable arg, of type union semun, is declared and used as the fourth argument to the semctl system call. The values in the array start_val (1, 0) are used to set the initial values for the two semaphores. The enumerated constants READ and MADE act as indices to reference which of the two semaphores we are using.

The program begins by checking the command line to determine if an argument has been passed. The program expects a small integer value to be passed. This value is used to indicate the number of seconds the process should sleep in its processing cycle. The inclusion of sleep allows the producer and consumer process to progress at different rates, thus providing the user with an easy way to check the integrity of the semaphore arrangement.

The semget system call is used to create/gain access to the semaphore set. The flag combination IPC_CREAT | IPC_EXCL insures that the first time the program is run it will create the two-semaphore set. As written, the first invocation of the program is considered to be the producer (the process that will generate the integer values). The variable producer is set to 1 in the producer process to indicate this. Once the semaphore set is successfully created, the program uses the semctl system call to initialize the semaphore set to the values stored in start_val.^[3] When the program is run a second time, the resulting process is considered to be a consumer (a process that will obtain the stored integer value). In the second program invocation, the initial semget system call, which is within the if statement, fails, as the semaphore set has already been generated by the producer. The else-if branch of the same if statement invokes semget a second time without any flags set. This second invocation of semget allows the consumer process to gain access to the previously generated semaphore set.

The second section of the program, which contains the logic executed by the producer, is shown in Program 7.4B.

Example 7.4B. The second section of the producer/consumer problem—the producer logic.

 |                                            // Section TWO
 |       switch (producer) {
 |       case 1:                              // The PRODUCER
 |         p_sleep = atoi(argv[1]);
 +         srand((unsigned) getpid());
 |         for (i = 0; i < 10; i++) {
 |           sleep(p_sleep);
 |           n = rand() % 99 + 1;
 |           cout << "A. The number [" << n <<"] generated by producer" << endl;
60           acquire.sem_num = READ;
 |           if (semop(semid, &acquire, 1) == -1) {
 |             perror("semop -producer- waiting for consumer to read number");
 |             return 4;
 |           }
 +           if ((fptr = fopen(BUFFER, "w")) == NULL ){
 |             perror(BUFFER);
 |             return 5;
 |           }                                                  
 |           fprintf(fptr, "%d
", n);
70           fclose(fptr);
 |           release.sem_num = MADE;
 |           cout << "B. The number [" << n <<"] deposited by producer" << endl;
 |           if (semop(semid, &release, 1) == -1) {
 |             perror("semop -producer- indicating new number has been made");
 +             return 6;
 |           }
 |         }
 |         sleep(5);
 |         if (semctl(semid, 0, IPC_RMID, 0) == -1) {
80           perror("semctl –producer-");
 |           return 7;
 |         }
 |         cout << "Semaphore removed" << endl;
 |         break;

As noted, the first time the program is run, the value of the variable producer is set to 1. When producer contains a 1, the case 1: section of program code, the producer logic, is executed. The small integer value passed on the command line to indicate the number of seconds the process should sleep is converted by the library function atoi and stored for future reference in the variable p_sleep. Following this, the random number generator is initialized using the value of the current PID. A for loop that produces 10 random integer values in the range 1 to 99 is entered. After the program sleeps, a random number is generated and displayed to the screen (this allows the user to verify the activity of the program). Following this, the sem_num member of the acquire operation is set to the value READ. This directs the following semop system call to reference the READ semaphore, which is the first semaphore of the set. We use a value of 1 for the READ semaphore to indicate the current stored number has been read (consumed) and a value of 0 to indicate the number has not been read. As the initial value for the READ semaphore is 1, the very first time the producer tests the READ semaphore with the semop system call, the producer can acquire the semaphore. Once this occurs, the producer continues on to the next section of code where it opens the file, stores the generated value, and closes the file. In later passes through this code, the producer may or may not find the READ semaphore at 1. If the semaphore is at 0 (indicating the consumer has not read the value), the producer, by default, blocks (waits) for this event to occur. Once the produced value has been written to the file, the producer process, using the release operation, increments the MADE semaphore. By incrementing the MADE semaphore, the producer indicates a new number is now available for the consumer. When all 10 numbers have been generated, the producer exits the for loop and, after sleeping 5 seconds to allow for the consumption of the last produced value, it removes the semaphore set with the semctl system command. If needed, the unlink call can be used to remove the temporary file.

The logic for the consumer is shown in Program 7.4C.

Example 7.4C. The third section of the producer/consumer problem—the consumer logic.

  +       case 0:                              // Section THREE
  |         c_sleep = atoi(argv[1]);           // The CONSUMER
  |         c_pid = getpid();
  |         while (1) {
  |           sleep(c_sleep);
 90           acquire.sem_num = MADE;
  |           if (semop(semid, &acquire, 1) == -1) {
  |             perror("semop -consumer- waiting for new number to be made");
  |             return 8;
  |           }
  +           if ( (fptr = fopen(BUFFER, "r")) == NULL ){
  |             perror(BUFFER);
  |             return 9;
  |           }                                                 
  |           fptr = fopen(BUFFER, "r");
100           fscanf(fptr, "%d", &n);
  |           fclose(fptr);
  |           release.sem_num = READ;
  |           if (semop(semid, &release, 1) == -1) {
  |             perror("semop -consumer- indicating number has been read");
  +             return 10;
  |           }
  |          cout << "C. The number [" << n <<] obtained  by consumer "
  |               <<  c_pid << endl;
  |         }
110       }
  |       return 0;
  |     }

The consumer process, like the producer, converts the value passed on the command line into an integer value by using the library function atoi. The consumer then obtains its PID using the getpid system call. The PID is used to identify individual consumer processes when more than one consumer process is present. The consumer then enters an endless loop. It sleeps c_sleep seconds and then tests the MADE semaphore. To accomplish this, the sem_num member of the acquire operation structure is set to MADE. The call to semop, which is passed the reference to acquire, causes the consumer to block (wait) if the semaphore is at 0. Once the MADE semaphore becomes 1, the consumer opens the file where the number was written, reads the number, and closes the file. The consumer then indicates that it has read the number. The release structure member, sem_num, is set to READ to reference the second semaphore of the set. The following semop system call causes the contents of the READ semaphore to be incremented. The consumer then displays a short message to the screen indicating the value retrieved and its PID value. The consumer continues to consume values until the call to semop fails due to the removal of the semaphore set by the producer.

We can run the program to simulate a number of conditions. We begin by making the producer process slower than a single consumer process. The output in Figure 7.8 shows how this is accomplished.

Example 7.8. A single slow producer with a single consumer.

linux$ p7.4 2 & p7.4 0
Producer starting
[1] 31223
Consumer starting
A. The number [79] generated by producer
B. The number [79] deposited by producer
C. The number [79] obtained  by consumer 31224
A. The number [17] generated by producer
B. The number [17] deposited by producer
C. The number [17] obtained  by consumer 31224
   .
   .
   .
C. The number [53] obtained  by consumer 31224
A. The number [15] generated by producer
B. The number [15] deposited by producer
C. The number [15] obtained  by consumer 31224
Semaphore removed
semop -consumer- waiting for new number to be made: Identifier removed
[1]  + Done                          p7.4 2

In this example the program p7.4 is run twice on the command line. The first invocation of the program, which will be the producer,^[4] is passed the value 2. This directs the producer process to sleep 2 seconds each time it cycles through the for loop. The producer process is placed in the background by specifying & after the command-line sleep value. In the second invocation of the program, the consumer is passed the value 0 as the sleep value. The system responds to the command sequence by displaying the PID of the commands that were placed in background. The display of

[1] 31223

means that, for this invocation, the producer PID is 31223. As the two processes execute, we can clearly see from the output that the producer must first generate and deposit the value in the file before the consumer can obtain it. As the producing process is slower than the consuming process, the consumer process spends a portion of its time waiting for the producer to deposit a number. When all of the numbers have been produced, the producer process removes the semaphore set. When this happens, the consumer process exits. If we run this command sequence several times, we should find it behaves in a consistent manner. Although the consumer process is faster than the producer process, the consumer should never read the same value twice from the file (unless, by chance, the same number was generated twice by the producer).

We can reverse the conditions and make the producer process faster than the consumer process. The output shown in Figure 7.9 shows how this can be accomplished.

Example 7.9. A producer with a single slow consumer.

linux$ p7.4 0 & p7.4 2
[1] 31229
Producer starting
A. The number [28] generated by producer
B. The number [28] deposited by producer
A. The number [69] generated by producer
Consumer starting
C. The number [28] obtained  by consumer 31230
B. The number [69] deposited by producer
A. The number [83] generated by producer
C. The number [69] obtained  by consumer 31230
   .
   .
   .
A. The number [29] generated by producer
C. The number [65] obtained  by consumer 31230
B. The number [29] deposited by producer
C. The number [29] obtained  by consumer 31230
Semaphore removed
semop -consumer- waiting for new number to be made: Identifier removed
[1]  + Done                          p7.4 0

This output sequence is slightly different from the previous one. Notice, as before, the producer generates and deposits the number. The producer, being faster than the consumer, then goes on to generate another number. However, this number is not deposited until the slower consumer process has read the existing stored value. If we run this command sequence several times, we should again be able to confirm that the producer process never overwrites the existing stored value until the consumer process has read it.

7-5 EXERCISE

What if there are several competing consumer processes? Will the current set of semaphores handle things correctly? Will competing consumer processes alternate their access to the produced values? Will some consumer processes starve? Try the following command sequences (several times each) and explain what happens and why for each.

A) linux$ p7.4 2 & p7.4 1 & p7.4 0

B) linux$ p7.4 0 & p7.4 1 & p7.4 1 & p7.4 1

C) linux$ p7.4 2 & p7.4 1 & p7.4 0 & p7.4 1

7-6 EXERCISE

As shown by the code listed below, we can add another operation for semop (called zero) that can be used to determine if a specified semaphore is at 0 (see Table 7.8 for the actions taken by semop when the value for sem_op is zero).

static struct sembuf
     acquire = {0, -1, SEM_UNDO},
     release = {0,  1, SEM_UNDO},
     zero    = {0,  0, SEM_UNDO};

Modify Program 7.4, incorporating the zero operation, so the producer can use this operation on the appropriate semaphore to determine if it should continue its processing. To verify that your solution is not rapidly passing through the producer loop, comment out the producer's call to sleep (line 78). Once you are positive your implementation is solid, uncomment the call to sleep. Generate sufficient output to assure the user that the producer process never overwrites a value that has not been consumed and that a consumer process never consumes the same value twice.

7-7 EXERCISE

Modify Program 7.4 to support multiple producers as well as multiple consumers accessing a single non-shareable resource. Hint: You may need additional semaphores to coordinate activities.

As with message queues, the syntax and manipulation of semaphores is somewhat complex, making them a prime candidate for incorporation into a C++ class. A semaphore class would define the relationships between semaphore data and the functions (methods) that manipulate this data. A declaration of a simplified semaphore class called SSemaphore^[5] is shown in Figure 7.10.

File : SSemaphore.h
  |     /*
  |       A VERY simplified semaphore class for use in a std UNIX
  |       environment.  See the text for instructions on how to use
  |       this class.  Copyright (c) 2002 J. S. Gray
  +
  |       Exit codes for class operations:
  |
  |       1 - Semaphore allocation failure   2 - Unable remove semaphore
  |       3 - Unable to LOCK semaphore       4 - Unable to UNLOCK semaphore
 10       5 - Failure on wait for ZERO       6 - Unable to assign value
  |       7 - Unable to return value
  |     */
  |
  |     #ifndef SSemaphore_h
  +     #define SSemaphore_h
  |     #define _GNU_SOURCE
  |     #include <iostream>
  |     #include <cstdio>
  |     #include <sys/types.h>
 20     #include <sys/ipc.h>
  |     #include <sys/sem.h>
  |     #include <stdlib.h>
  |     #include <unistd.h>
  |     using namespace std;
  +
  |     class SSemaphore {
  |       public:
  |         SSemaphore ( );                 // Constructor
  |         ~SSemaphore( );                 // Destructor - remove semaphore
 30         int  P( );                      // LOCK (decrement semaphore)
  |         void V( );                      // UNLOCK (increment semaphore)
  |         int  Z( );                      // WAIT while semaphore is NOT 0
  |         void Put( const int );          // Assign a value to semaphore
  |         int  Get( );                    // Return value of the semaphore
  +       private:
  |         #if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
  |                                         // definition in <sys/sem.h>
  |         #else
  |         union semun {                   // We define:
 40           int val;                      // value  for SETVAL
  |           struct semid_ds *buf;         // buffer for IPC_STAT, IPC_SET
  |           unsigned short int *array;    // array  for GETALL, SETALL
  |           struct seminfo *__buf;        // buffer for IPC_INFO
  |         };
  +         #endif
  |         union  semun  arg;              // For semctl call
  |         struct sembuf zero,lock, unlock; // hoo ha's for P,V & Z operations
  |         int   semid;                    // ID of semaphore
  |         pid_t my_pid;                   // PID of creator
 50     };
  |     #endif

As defined, the SSemaphore class creates a private semaphore set with a single element. There are seven public methods and six private data members in the class. The functionality of each method is shown in Table 7.10.

The C++ code that implements the semaphore class is found in the program file SSemaphore.cxx (Program 7.5). As shown, the code is bare bones—little is done to handle errors, and only basic semaphore functionality is addressed.

File : SSemaphore.cxx
  |     /*
  |         SSemaphore implementation - Copyright (c)  2002  J. S. Gray
  |      */
  |     #include "SSemaphore.h"
  +                                           // Generate a private semaphore
  |     SSemaphore::SSemaphore(  ){
  |       zero.sem_num   = 0, zero.sem_op   =  0, zero.sem_flg   = SEM_UNDO;
  |       lock.sem_num   = 0, lock.sem_op   = -1, lock.sem_flg   = SEM_UNDO;
  |       unlock.sem_num = 0, unlock.sem_op =  1, unlock.sem_flg = SEM_UNDO;
 10       my_pid = getpid( );
  |       if((semid = semget( IPC_PRIVATE, 1, 0660 )) == -1 ){
  |           exit( 1 );
  |       }
  |       Put( 0 );                           // Default - set to zero @ start
  +     }
  |                                           // Remove semaphore if creator
  |     SSemaphore::∼SSemaphore( ) {
  |       if ( getpid( ) == my_pid )
  |         if ( semctl( semid, 0, IPC_RMID ) == -1 )
 20           exit( 2 );
  |     }
  |                                          // LOCK semaphore
  |     int                                  // Atomic test & decrement
  |     SSemaphore::P( ){
  +       if ( semop( semid, &lock, 1 ) == -1 )
  |         exit( 3 );
  |       return 0;
  |     }
  |                                          // UNLOCK semaphore
 30     void                                 // Increment semaphore
  |     SSemaphore::V( ){
  |       if ( semop( semid, &unlock, 1 ) == -1 )
  |         exit( 4 );
  |     }
  +
  |     int                                  // Wait for semaphore to be 0
  |     SSemaphore::Z( ){
  |       if ( semop( semid, &zero, 1 ) == -1 )
  |         exit( 5 );
 40       return 0;
  |     }
  |                                          // Assign value to the semaphore
  |     void
  |     SSemaphore::Put( int const value ){
  +       arg.val = value;
  |       if ( semctl(semid, 0, SETVAL, arg ) == -1 )
  |         exit( 6 );
  |     }
  |                                          // Return value of the semaphore
 50     int
  |     SSemaphore::Get( ){
  |       int sem_value;
  |       if ((sem_value=semctl(semid, 0, GETVAL, 0)) == -1 )
  |         exit( 7 );
  +       return sem_value;
  |     }

To use this class, the files SSemaphore.h and SSemaphore.cxx should reside locally. The SSemaphore class is compiled into object code with the command line

linux$  g++ SSemaphore.cxx –c

At the top of the source file that uses a SSemaphore object, add the statement

#include "SSemaphore.h"

to make the class definition available to the compiler. When compiling the source file, include the message queue object code file

linux$  g++  your_file_name.cxx   SSemaphore.o

In 1965 Dijkstra presented what is now considered to be a classic synchronization problem involving a group of dining philosophers. In brief, the group of philosophers is sitting around a table. Each engages in the activity of thinking and eating. To eat, the philosopher must obtain the forks on his or her left and right. Both forks are needed for dining, and once obtained, neither fork is released until the philosopher is done. For N philosophers, there are N forks (not 2 × N). Clearly, if all the philosophers are to eat, some sort of synchronization of their activities is needed.

We can use the recently presented SSemaphore class to implement a naive solution to the dining philosophers' problem. In essence, each fork will be represented by a single binary semaphore. If a philosopher can obtain both the left and right fork (think semaphore), he or she will eat for a random number of seconds, and when done, return the forks. If either instrument is not available, he or she will wait. Keep in mind that this solution has a very basic flaw. Should all the philosophers pick up their left fork at the same time, we would have deadlock. This could occur, as each left fork is also the right fork of the philosopher to the left. With every philosopher waiting for his or her right fork (the left fork of the philosopher on his or her right), no progress can be made. Program 7.6 implements our less-than-perfect solution.

File : p7.6.cxx
  |     /*
  |          The dining philosophers
  |      */
  |     #include <iostream>
  +     #include "SSemaphore.h"                // Our basic semaphore class
  |     const int MAX = 5;
  |     SSemaphore Forks[MAX];
  |     void Philosopher( int );
  |     void Eat_It( const int,const int, const int );
 10     int
  |     main(int argc, char *argv[] ) {
  |       int i;
  |       if ( argc < 2 ) {
  |         cerr << "Usage: " << argv[0] << " secs_to_wait " << endl;
  +         return 1;
  |       }
  |       for( i=0; i < MAX; ++i )
  |         Forks[i].Put(true);
  |       for(i = 0; i < MAX; ++i )
 20         Philosopher( i );
  |       sleep(atoi(argv[1]));                // Parent process waits a bit
  |       return 0;
  |     }
  |     void
  +     Philosopher(int number ){
  |       if (fork() == 0) {                   // Run in the child
  |         int left, right;
  |         srand(getpid( ));
  |         left = number;
 30         right= (number+1) % MAX;
  |         do {
  |           cout << "A. P" << number << " is thinking
";
  |           sleep(rand( ) % 3 + 1);          // Take a while to THINK
  |           cout << "B. P" << number << " ASKS to eat with forks "
  +                << left << " & " << right << endl;
  |           Forks[left].P( );                 // Acquire left fork
  |             Forks[right].P( );              // Acquire right fork
  |               Eat_It(number, left, right);
  |             Forks[right].V( );
 40           Forks[left].V( );
  |         } while( true );
  |       }
  |     }
  |     void
  +     Eat_It(const int number, const int left, const int right) {
  |       cout << "C. P" << number << " is EATING   with forks "
  |            << left << " & " << right << endl;
  |       sleep(rand( ) % 3 + 1);              // Take a while to EAT
  |       cout << "D. P" << number << " is now DONE with forks "
 50            << left << " & " << right << endl;
  |     }

As written, the program expects the user to pass an integer command-line value that will be used for the number of seconds the program should run. A value of 10 seems to produce a reasonable amount of output. In line 7 of the program, an array of five private semaphore objects is instantiated. This array represents the five forks. The loop at line 17 sets each of the semaphores to true (fork available). This is followed by a second loop that calls the Philosopher function MAX times. Upon each invocation, the Philosopher function generates a child process to carry on the activities of the philosopher. The philosopher's activities consist of thinking for a random amount of time and eating. To eat, the left and right fork (semaphore) must be acquired. When both semaphores have been procured, the Eat_It function is called where, for a random amount of time, the eating activity is carried out. While the child processes carry on their activities, the parent process sleeps for a period (see line 21). When the parent process exits, the destructor for the semaphore objects is called. The child processes exit as they encounter an error condition when the attempt to access a removed semaphore.

Figure 7.11 shows a typical run when the value 10 is passed to the program. To save space, the output is displayed as two columns.

linux$ g++ p7.6.cxx SSemaphore.o -o p7.6     A. P2 is thinking
                                             D. P0 is now DONE with forks 0 & 1
linux$ p7.6 10                               A. P0 is thinking
A. P0 is thinking                            B. P1 ASKS to eat with forks 1 & 2
A. P1 is thinking                            C. P1 is EATING   with forks 1 & 2
A. P2 is thinking                            B. P3 ASKS to eat with forks 3 & 4
A. P3 is thinking                            C. P4 is EATING   with forks 4 & 0
A. P4 is thinking                            B. P2 ASKS to eat with forks 2 & 3
B. P1 ASKS to eat with forks 1 & 2           D. P4 is now DONE with forks 4 & 0
C. P1 is EATING   with forks 1 & 2           A. P4 is thinking
B. P3 ASKS to eat with forks 3 & 4           C. P3 is EATING   with forks 3 & 4
C. P3 is EATING   with forks 3 & 4           B. P0 ASKS to eat with forks 0 & 1
B. P0 ASKS to eat with forks 0 & 1           D. P1 is now DONE with forks 1 & 2
B. P2 ASKS to eat with forks 2 & 3           A. P1 is thinking
B. P4 ASKS to eat with forks 4 & 0           C. P0 is EATING   with forks 0 & 1
D. P1 is now DONE with forks 1 & 2           D. P3 is now DONE with forks 3 & 4
A. P1 is thinking                            C. P2 is EATING   with forks 2 & 3
D. P3 is now DONE with forks 3 & 4           A. P3 is thinking
A. P3 is thinking                            B. P1 ASKS to eat with forks 1 & 2
C. P0 is EATING   with forks 0 & 1           B. P4 ASKS to eat with forks 4 & 0
C. P2 is EATING   with forks 2 & 3           D. P0 is now DONE with forks 0 & 1
D. P2 is now DONE with forks 2 & 3           D. P2 is now DONE with forks 2 & 3
                                             B. P3 ASKS to eat with forks 3 & 4

linux$  p7.6 100 | sort | uniq -c

Semaphores are specialized data structures used to coordinate access to a non-shareable resource (section of code). Cooperating (or possibly competing) processes use the semaphore(s) to determine if a specific resource is available. If the resource is unavailable, by default the system places the requesting process in an associated queue. The system notifies the waiting process when the resource is available. This alleviates the process from using polling to determine the availability of the resource. Semaphores can be categorized as binary or counting. Binary semaphores are used to synchronize access to a single instance of a non-shareable resource, while counting semaphores are used with multiple instances of a non-shareable resource.

The actions needed to manipulate semaphores are provided by a series of system calls. The semget system call is used to generate a new semaphore/ semaphore set (array) or to gain access to an existing semaphore. The semctl system call allows the user to set initial semaphore values, obtain their current value, and remove the semaphore. Operations on semaphores are performed with the semop system call. These operations (which are atomic) are used to decrement (obtain), increment (release), and test for zero-specific semaphores. Sets of operations can be specified if several semaphores are needed to coordinate access to a specific resource. The sets of operations may also be marked as being atomic.

While the syntax for using semaphores is somewhat complex, they do provide a standardized way of implementing classic primitive semaphore operations referenced in most operating system texts. As with many of the previous communication techniques, controlling access to a resource by using semaphores implies all involved processes will follow the rules. Semaphores cannot prevent processes from accessing a controlled resource.

binary semaphore

counting semaphore

critical region

ctime library function

deadlock

dining philosophers

GETALL

GETNCNT

GETVAL

GETZCNT

IPC_CREAT

IPC_EXCL

IPC_NOWAIT

IPC_PRIVATE

IPC_RMID

IPC_SET

IPC_STAT

sem structure

SEM_UNDO

semaphore class

semctl system call

semget system call

semid_ds structure

semop system call

semun union

SETALL

SETVAL

starvation