CS330 Semaphores

Highlights of this lab:

Lab Code

To get the sample and exercise code, please use the following commands in your cs330 directory: 
   wget www.labs.cs.uregina.ca/330/SemaphorePosix/Lab6.zip
   unzip Lab6.zip

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)  /* idea of the sem_wait */
	Semaphore s;
	{
	  while (s == 0) ;	/* wait until s>0 */
	  s = s-1;
	}

	V(s)    /* idea of the sem_post */
	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.

Functions for Posix Semaphores

The main functions that will be needed for this lab are:

See the following website for information and an exercise

http://www.csc.villanova.edu/~mdamian/threads/posixsem.html

Just in case, this reference is not available, the content from this site is available in this pdf file.

You will be given a slightly modified version of the starting producer-consumer code

References