CS330 Semaphores


Highlights of this lab:


Definition of Semaphore

The original meaning of a semaphore was:

"A visual signaling apparatus with flags, lights, or mechanically moving arms, as one used on a railroad." (from http://dictionary.reference.com)

What do railroad tracks and computers have in common? Well, railroad semaphores were the inspiration of E. W. Dijkstra solution to the mutual exclusion problem in operating systems.

"...consider a stretch of railroad in which there is a single track over which only one train at a time is allowed.

Guarding this track is a semaphore. A train must wait before entering the single track until the semaphore is in a state that permits travel. When the train enters the track, the semaphore changes state to prevent other trains from entering the track. A train that is leaving this section of track must again change the state of the semaphore to allow another train to enter."

(from Sun Documentation: Programming with Synchronization Objects.)

Railroad semaphores serve as a signal to indicate whether or not a single track has a train on it. Similarly, semaphores in operating systems serve as a signal to indicate whether or not a shared resource is currently being used. The following is a definition of the operating systems semaphores (from The Free On-line Dictionary of Computing, http://www.foldoc.org/, Editor Denis Howe):

"[Semaphores are] the classic method for restricting access to shared resources (e.g. storage) in a multi-processing environment. They were invented by Dijkstra and first used in T.H.E operating system.

A semaphore is a protected variable (or abstract data type) which can only be accessed using the following operations:

	P(s)
	Semaphore s;
	{
	  while (s == 0) ;	/* wait until s>0 */
	  s = s-1;
	}

	V(s)
	Semaphore s;
	{
	  s = s+1;
	}

	Init(s, v)
	Semaphore s;
	Int v;
	{
	  s = v;
	}

P and V stand for Dutch "Proberen", to test, and "Verhogen", to increment. The value of a semaphore is the number of units of the resource which are free (if there is only one resource a "binary semaphore" with values 0 or 1 is used). The P operation busy-waits (or maybe sleeps) until a resource is available whereupon it immediately claims one. V is the inverse, it simply makes a resource available again after the process has finished using it. Init is only used to initialise the semaphore before any requests are made. The P and V operations must be indivisible, i.e. no other process can access the semaphore during the their execution.

To avoid busy-waiting, a semaphore may have an associated queue of processes (usually a FIFO). If a process does a P on a semaphore which is zero the process is added to the semaphore's queue. When another process increments the semaphore by doing a V and there are tasks on the queue, one is taken off and resumed. "

Note: These operations must be performed as an atomic hardware instruction to prevent two processes from gaining control of the same semaphore. The ideas above are concepts, but only safe when performed through one hardware instruction.


System Calls for Semaphores

The main system calls that will be needed for this lab are:

Background of these System calls

Semaphores are one of three types of IPC that are collectively referred to as "System V IPC".

These three "System V IPC" are:

These three have similar system calls and are similarly maintained by the kernel.

The following chart summarizes the system calls for these three System V IPC:

  Message Queue Semaphore Shared Memory
system call to create or open
msgget semget shmget
system call for control operations msgctl semctl shmctl
system call for IPC operations msgsnd
msgrcv
semop shmat
shmdt

The IPC facility is created using either msgget, semget, or shmget. Each IPC facility has a creator, owner, and access permissions.

What a Semaphore Looks Like

When you create a semaphore, you are actually creating a semaphore set.

The permissions, time stamps, and number of semaphores in the set, is stored in a structure called semid_ds which is included through the file <sys/sem.h> (on the current system the definition of semid_ds is actually in <bits/sem.h> which is included by the previous header):

/* Data structure describing a set of semaphores.  */
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;
};

The details of each semaphore in the set is stored in an anonymous structure, which is defined as follows in the man pages on semop:

    unsigned short semval; /* semaphore value */
    unsigned short semzcnt; /* # waiting for zero */
    unsigned short semncnt; /* # waiting for increase */
    pid_t sempid; /* process that did last op */ 

Because there may be more than one semaphore in the set, each one is indexed starting at 0.

For instance, if we create a set of three semaphores (with one semget call) you could represent it as the following:


Creating a Semaphore Set Using semget()

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

      int semget(key_t key, int nsems, int semflg);
The idea behind semget() is similar to the open() system call. With open(), the return is a file descriptor. With semget(), the return is a semaphore set id. Often the key is generated using the library routine ftok().
      #include <sys/types.h>
      #include <sys/ipc.h>

      key_t ftok(const char *pathname, int proj_id);

"The ftok function uses the identity of the file named by the given pathname (which must refer to an existing, accessible file) and the least significant 8 bits of proj_id (which must be nonzero) to generate a key_t type System V IPC key, suitable for use with msgget(2), semget(2), or shmget(2).

The resulting value is the same for all pathnames that name the same file, when the same value of proj_id is used. The value returned should be different when the (simultaneously existing) files or the project IDs differ." (from the man pages on linux)

Some sample uses of semget() are in program7_1.cpp (taken from Interprocess Communications in Unix)
/*
   Creating sets of semaphores 
*/

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <unistd.h>

main(void)
{
	int sem1, sem2, sem3;
	key_t ipc_key;

	ipc_key = ftok(".", 'S');
	if (( sem1 = semget (ipc_key, 3, IPC_CREAT | 0666))==-1)
	{
		perror("semget: IPC_CREAT | 0666");
	}
	printf("sem1 identifier %d\n", sem1);
	if ((sem2=semget(ipc_key, 3, IPC_CREAT| IPC_EXCL| 0666)) ==-1)
	{
		perror("semget: IPC_CREAT | IPC_EXCL | 0666");
	}
	printf("sem2 identifier %d\n", sem2);
	if ((sem3=semget(IPC_PRIVATE, 3, 0600)) == -1)
	{
		perror("semget: IPC_PRIVATE");
	}
	printf("sem3 identifier %d\n", sem3);
}
Note the following: Try the following commands at the prompt:
% ipcs
% ipcrm -s sem_id

Accessing an Existing Semaphore Set

In addition to creating semaphores, semget() can be used to get an ID for an existing semaphore. The syntax is the following:

semid=semget(ipc_key, 3, 0);
	//Notice that the final argument is zero.

Initializing, Viewing, and Removing Semaphore Sets Using semctl()

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

      int semctl(int semid, int semnum, int cmd, ...);

This function has three or four arguments.

To work with semctl, you first have to declare a union semun:

      union semun {
             int val;                  /* value for SETVAL */
             struct semid_ds *buf;     /* buffer for IPC_STAT, IPC_SET */
             unsigned short *array;    /* array for GETALL, SETALL */
                                       /* Linux specific part: */
             struct seminfo *__buf;    /* buffer for IPC_INFO */            
      };

For more on unions, see References section below.

You use either val, *buf, or *array depending on the command (note that the comments above indicate this correspondence)

For a list of commands used with semctl, you can refer to the following table:

Command
Description
IPC_STAT Return the current values of the semid_ds structure for the indicated semaphore identifier.
The returned information is stored in a user-generated structure referenced by the fourth argument to semctl.
To specify IPC_STAT the process must have read permission for the semaphore set associated with the semaphore identifier.
IPC_SET Modify a restricted number of members in the semid_ds structure.
The members sem_perm.uid, sem_perm.gid and sem_perm.mode (in the permission structure within semid_ds) can be changed if the effective ID of the accessing process is that of the super user, or is the same as the ID value stored in sem_perm.cuid or sem_perm.uid.
To make these changes, a structure of the type semid_ds must be allocated.
The appropriate members' values are then assigned and a reference to the modified structure is passed as the fourth argument to the semctl system call.
IPC_RMID Remove the semaphore set associated with the semaphore identifier
GETALL Return the current value of the semaphore set.
The values are returned via the array reference passed as the fourth argument to semctl
The user is responsible for allocating the array of the proper size and type prior to passing its address to semctl
Read permissions for the semaphore is required to specify GETALL
SETALL Initialize all semaphores in a set to the values stored in the array referenced by the fourth argument to semctl.
Again, the user must allocate the initializing array and assign values prior to passing the address of the array to semctl.
The process must have alter access for the semaphore set to use SETALL.
GETVAL Return the current value of the individual semaphore referenced by the value of the semnum argument.
SETVAL Set the value of the individual semaphore referenced by the semnum argument to the value specified by the fourth argument to semctl
GETPID Return the process ID from the sem_perm structure within the semid_ds structure
GETNCNT Return the number of processes waiting for the semaphore referenced by the semnum argument to increase in value
GETZCNT Return the number of processes waiting for the semaphore referenced by the semnum argument to become zero

Some sample uses of semctl() are in program7_3.cpp (taken from Interprocess Communications in Unix)

/* Taken from Interprocess Communications in UNIX, page 176 *$
/*
   Creating sets of semaphores
*/

#include <stdio.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>       //added

#define NS 3

/*This declaration is *MISSING* in many Solaris environments.
 *It should be in the  file but often is not! If you
 *receive a duplicate definition error for semun then comment out
 *the union definition.
 */
union semun
{
        int val;
        struct semid_ds *buf;
        ushort  *array;
        struct seminfo *__buf;
};

main(void)
{
        int sem_id, sem_value, i;
        key_t ipc_key;
        struct semid_ds sem_buf;
        static ushort sem_array[NS] = {3,1,4};
        union semun arg;


        ipc_key = ftok(".", 'S');
        /*
         * Create the semaphore
         */
        if (( sem_id = semget (ipc_key, NS, IPC_CREAT | 0666))==-1)
        {
                perror("semget: IPC_CREAT | 0666");
                exit (1);
        }
        printf("Semaphore identifier %d\n", sem_id);

        /*
         * Set arg (the union) to the addr of the storage location for
         * returned semid_ds values.
         */
        arg.buf= &sem_buf;
        if (semctl(sem_id, 0, IPC_STAT, arg) == -1) //get info
        {
                perror("semctl:IPC_STAT");
                exit (2);
        }

        printf("Created %s", ctime(&sem_buf.sem_ctime));

        /*
         * Set arg (the union) to the addr of the initializing vector
         */
        arg.array=sem_array;
        if (semctl(sem_id, 0, SETALL, arg) == -1)
        {
                perror("semctl: SETALL");
                exit (3);
        }

        for (i = 0; i < NS; ++i) //display contents
        {
                if ((sem_value = semctl(sem_id, i, GETVAL, 0)) == -1)
                {
                        perror("semctl: GETVAL");
                        exit (4);
                }
                printf("Semaphore %d has value of %d\n", i, sem_value);
        }
        if (semctl(sem_id, 0, IPC_RMID, 0) == -1) //remove semaphore
        {
                perror("semctl: IPC_RMID");
                exit (5);
        }
}

Performing Operations on a Semaphore Set Using semop()

semop() is really the guts behind making the semaphore work. It is used to control who gets the resource. The general idea is that if the semaphore is 0, then someone has access to the resource. If the semaphore is 1 (or greater), then the resource is free.

Let's say the semaphore is 1 (free). To indicate that we are taking over that resource, we want to perform an operation that makes the semaphore 0. Therefore, using semop(), we want to subtract 1.

Let's say the semaphore is 0 (indicating that someone is using the resource). If we are trying to take over that resource (by using semop() to subtract 1), then semop() will wait around and not continue in the code until the semaphore is set to 1.

In pseudo code, the idea is something like this (where semval is the value of the semaphore):

//wait to acquire resource (idea behind semop with acquire operation)
 
while (semval == 0) ;	/* wait until semval>0 */
semval = semval-1;

	 ==>Perform critical code here
 
//release the resource (idea behind semop with release operation)
 
semval=semval+1	

In reality, the prototype for semop is the following:

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

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

Notice that sops is a structure (struct sembuf). It contains the following members:

           unsigned short sem_num;  /* semaphore number */
           short sem_op;            /* semaphore operation */
           short sem_flg;           /* operation flags */

The following figure shows a relationship of three-element semaphore operation array to an N element set of semaphores:

The following code snippets provide an overview of how semop() can be used:

struct sembuf sem;
	  ...

semid = semget(ftok("tempfile.txt", 1357), 1, IPC_CREAT | IPC_EXCL | 0777);
      ...

//REQUEST (ACQUIRE) RESOURCE
sem.sem_num = 0;
sem.sem_op = -1;
sem.sem_flg = SEM_UNDO;

int sems = semop(semid, &sem, 1);
      ...

//RELEASE RESOURCE     
sem.sem_num = 0;
sem.sem_op = 1;
sem.sem_flg = SEM_UNDO;

int sems = semop(semid, &sem, 1);

You might also use the following format to initialize the values in sem:

struct sembuf sem={0, -1, SEM_UNDO};

Click to see complete code for a consumer/producer problem. (program7_4 from Interprocess Communications in UNIX)


References