Semaphore Class

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.

[5] The name SSemaphore (with the extra 'S' ) was chosen to minimize any conflicts with existing semaphore definitions.

Figure 7.10 Header file for a basic semaphore class.

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 
 #include 
 #include 
 20 #include 
 #include 
 #include 
 #include 
 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 
 #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.

Table 7.10. SSemaphore Class Methods.

Method Name	Explanation
SSemaphore	This is the class constructor. This method assigns the proper values to the zero , lock , and unlock sembuf structures and saves the PID of the calling process. Additionally, it generates the private, single element semaphore and sets it to 0.
~SSemaphore	This method removes the semaphore from the system if the calling function is the process that generated the semaphore.
P	This method atomically tests and decrements the semaphore. It blocks if the semaphore is 0.
V	This method increments the semaphore.
Z	This method tests whether or not the semaphore is at 0. If it is not at 0, it blocks.
Put	Put assigns a value to a semaphore.
Get	Get returns the current value of a semaphore.

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 boneslittle is done to handle errors, and only basic semaphore functionality is addressed.

Program 7.5 Program code for the semaphore class.

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

Program 7.6 A rudimentary dining philosophers' solution using semaphore objects.

File : p7.6.cxx
 /*
 The dining philosophers
 */
 #include 
 + #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 .

Figure 7.11 10 seconds of output from the dining philosophers' program.

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

EXERCISE

As presented, the SSemaphore class generates a private semaphore. Private semaphores are fine for use with related processes but are difficult to use with unrelated processes. Modify the SSemaphore class to allow for the generation of a nonprivate semaphore. Rewrite the producer/consumer program (Program 7.4) using this newly defined class. Be sure to provide output to show that your class works and that it removes all semaphores when done.

EXERCISE

What if in Program 7.6 (the dining philosophers), odd-number philosophers acquired their forks as right and then left, and even-number philosophers acquired their forks as left and then right. Would this prevent deadlock? Modify Program 7.6 to implement this approach. Run your program a sufficient number of times to reasonably assure yourself that this approach does or does not work. Hint : Here is a command sequence to collect some summary information for a 100-second period:

linux$ p7.6 100 sort uniq -c