CIS 307: TOPIC: Semaphores

• Definition and initial implementation
• Comments
• Nutt's Implementation
• Implementation of Semaphores in XINU
• An implementation for testing programs involving semaphores

Semaphores are treated in Tanenbaum Section 2.2.5

Definition and initial implementation

People use the term "Semaphore" to refer to a variety of synchronization mechanisms. Here by "Semaphore" we mean the "non-busy-waiting" analog of SpinLocks. We show a possible implementation for semaphores. For now assume that semaphore's operations are atomic.

	type semaphore = record
			    count : integer;
  1.			    q     : queue of processes;
			 end record;
	procedure initsem (s : in out semaphore; n : integer) is
	begin
	   s.count := n; initialize s.q to the empty queue;
	end;
	procedure P(s : in out semaphore) is
	begin
  2.	   s.count := s.count - 1;
  3.	   if s.count < 0 then 
  4.	      Remove this process from Running, add it 
	              to s.q, and reschedule;
	end;
	procedure V(s : in out semaphore) is
	begin
  5.	   s.count := s.count + 1;
  6.	   if s.count <= 0 and s.q is not empty then
  7.	      Remove a process from s.q, add it to the Ready 
		      Queue, and reschedule;
	end;

Comments

• On line 1. we talk of a "queue of processes". A process is usually represented by a process id, a pointer or an index that refers to a Process Control Block (PCB). A PCB contains the relevant information about a process state.
• Lines 2., 3., and 4. form a critical region. The same is true for lines 5., 6., and 7.. As such they need to be enforced either by masking interrupts (in single processor systems) or by using spinlocks.
• The P operation is also called Down or Wait. The V operation is also called Up or Signal.
• Reschedule operates as follows: say A is the highest priority process in the Ready queue (you may assume that there is always one such process, at least a Null process).
  • If A has higher priority than the currently running process B, move B to the Ready queue and A to Running.
  • If A does not have higher priority than the currently running process B, do nothing.
  • If there is no running process, move A to Running.
• If initsem is called with the parameter n set to 0, we say that we have a Blocking Semaphore; if with 1, we say that we have a Boolean or Mutual Exclusion Semaphore; and if n is greater than 1, we say that we have a Counting Semaphore.
  Boolean semaphores are the non-busy-waiting analogs of spinlocks.

Using semaphores we can achieve a number of different behaviors:

• If S is a boolean semaphore, then we can implement related critical regions by prefixing them with the statement P(S); and affixing them with V(S);
• If S is a counting semaphore initialized to n (say, 10), then up to n (10) different processes could be executing a region enclosed by P(S)..V(S) statements.
• If S is a blocking semaphore, then we can make sure that a process completes execution of statement A before another process starts execution a statement B, by following A with the statement V(S) and preceding B with the statement P(S).

Nutt's Implementation

#define	 N   ..         /* The number of semaphores */

int      value[N];	/* Keeps the count for the semaphores   */
boolean  sem[N];	/* Spinlocks to protect critical region */
			/*   of semaphore */
boolean  hold[N];	/* Used to temporarily "enqueue" tasks  */
			/* waiting on sem */

void initsem(int s, m) {
	value[s] = m; sem[s] = FALSE; hold[s] = TRUE;}
void P(int s) {
	while (TS(sem[s]));	/* Lock */
	value[s]--;
	if (value[s] < 0) {
	   sem[s] = FALSE;	/* Unlock */
	   while(TS(hold[s])) yield(Q); /* Here the process enters */
			/* a new Critical Region where it gives    */
			/* control to Q, a scheduler. It is a loop */
			/* since we may repeatedly be given control*/
			/* back from yield and find a blocked semaphore.*/
	}else
	   sem[s] = FALSE;}	/* Unlock */
void V(int s){
	while (TS(sem[s]));	/* Lock */
	value[s]++;
	if (value[s] <= 0){	/* Somebody is waiting in hold to enter CR*/
	   while (!hold[s]);	/* We check if there is a concurrent V. */
				/* It is a loop */
				/* because we might have two or more */
				/* concurrent V operations executing.*/
	   hold[s] = FALSE;	/* Here we free a process waiting in P.*/
	}
	sem[s] = FALSE;}	/* Unlock */

Implementation of Semaphores in XINU

An implementation for testing programs that use semaphores