Semaphore Operations

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.

Table 7.5. Summary of the semop System Call.

Include File(s)			Manual Section	2
Summary	int semop(int semid, struct sembuf *sops, unsigned nsops);
Return	Success	Failure		Sets errno
		-1		Yes

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

• IPC_NOWAIT If the semaphore operation cannot be performed (such as when attempting to decrement a semaphore or test if it is equal to 0), the call returns immediately. No other semaphores in the set are modified if one of the specified semaphore operations fails with the IPC_NOWAIT flag.
• SEM_UNDO If IPC_NOWAIT has not been indicated, the SEM_UNDO flag allows an operation to be undone if a blocked operation (one waiting for a specific condition) subsequently fails. The system keeps track of the adjustment values needed for each semaphore set. The adjustment values are kept on a per-process basis and actually indicate how many resources are being held, while the systemwide semaphore value indicates how many resources are currently free.

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.

7.4.1 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.

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

File : p7.4.cxx
 /*
 The producer/consumer problem
 */
 #include  // Section ONE
 + #include 
 #include 
 #include 
 #include 
 #include 
 10 #include 
 #define BUFFER "./buffer"
 #if defined(__GNU_LIBRARY__) && !defined(_SEM_SEMUN_UNDEFINED)
 // definition in 
 #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_CREATIPC_EXCL0660)) != -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.

[3] Notice that the union member arg.array is assigned the base address of the array start_val prior to invoking semctl .

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

Program 7.4B The second section of the producer/consumer problemthe 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.

Program 7.4C The third section of the producer/consumer problemthe 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.

Figure 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

[4] This may be an invalid assumption on some systems, as process scheduling may allow the program invoked second to be run first and thus become the producer. If your output indicates this is happening, enter the two commands on separate linesdo not forget to add the & after the first command to place it in the background.

[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.

Figure 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.

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

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.

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.