CIS 307: TOPIC: Semaphores

[Definition and initial implementation], [Comments], [Nutt's Implementation], [Implementation of Semaphores in XINU], [An implementation for testing programs involving semaphores], [Combining SpinLock and Semaphore Behaviors]

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

Using semaphores we can achieve a number of different behaviors:

Nutt's Implementation

Here we show code similar to the code used by G.J.Nutt in his Operating Systems book. This code implements N semaphores for a multiprocessing system. 

#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 otherwise have two or more */
				/* consecutive V operations all setting (see next */
				/* statement) hold[s] to false. */
	   hold[s] = FALSE;	/* Here we free a process waiting in P,*/
				/* namely on hold[s].  */
	}
	sem[s] = FALSE;}	/* Unlock */

Implementation of Semaphores in XINU

You may examine the implementation of semaphores in XINU. Examine in particular the files sem.h, wait.c, and signal.c. Do you think that this implementation works only in a shared memory multiprocessing system? or only in a single processor system?

An implementation for testing programs that use semaphores

Here is code that implements semaphores as pipes. Of course nobody would ever think to use such an implementation in practice. This code is shown here for two reasons. Firstly, it can be used to test concurrent programs with semaphores. Second, it reminds us that IPC primitives can be implemented in terms of each other. That is, IPC primitives are chosen not just on the basis of functionality, but also on the basis of performance (things like data rate and latency). 
/* sem.h - CreateSem, P, V, DelSem */

typedef int *semaphore;  

semaphore CreateSem (int count);  /* Returns a new semaphore */

void P(semaphore s);              /* P, or wait, or down on semaphore */

void V(semaphore s);              /* V, or signal, or up on semaphore */

int DelSem(semaphore s);          /* Deletes an existing semaphore */

/* sem.c - CreateSem, P, V, DelSem */

/*
 This implementation of semaphores is strictly for kicks since
 it assumes the availability of pipes!
 A semaphore is represented by a pipe. The P operation is simulated
 by reading a character from the pipe. The V operation is simulated
 by writing a character to the pipe. The kind of the semaphore is
 specified when the semaphore is created. If the argument is 0, we get a
 blocking semaphore, if 1, a boolean semaphore, and if n>1, a counting
 semaphore.
 */

#include 
#include 
#include "sem.h"

semaphore CreateSem (int count){
/* Create and return a new semaphore */
   int *fd;
   int i;

   fd = (int *)malloc(8); /* Allocating space for two filedescriptors */
   if (pipe(fd) < 0) {
      printf("Cannot create pipe.\n");
      exit(0);}
   for(i=0;i



Combining SpinLock and Semaphore Behaviors


It has been noticed that spinlocks are good on multiprocessors systems for 
implementing small critical regions. And of course semaphores are good
to prevent busy waiting. One can combine spinlocks and 
semaphores and reap the benefits of both. One can do the following:


   Abstract Data Type SpinSem is
      int x; {Used to implement the "spin" action}
      int waitcount; {Counts number of processes asleep on s}
      semaphore b; {This is a blocking semaphore}
      spinlock s;  {Used to implement critical regions within SpinSem}
    procedure init(self : SpinSem) is
    begin
      self.x = 0;
      self.waitcount = 0;
      init(self.b, 0);
      init(self.s);
    end;
    procedure lock(self : SpinSem; int n) is
      {Notice that n will be local to each process using SpinSem}
    begin
      n = 0;
      while (TS(self.x) == 1) {
        lock(self.s);
        n++;
        if (n > MAXN) {   {MAXN is an appropriate integer constant}
           self.waitcount++;
           unlock(self.s);
           P(self.b);
        } else
           unlock(self.s);
      }
    end;
    procedure unlock(self: SpinSem; int n) is
    begin
      lock(self.s);
      if (n > MAXN) {
         n = 0;
         self.waitcount--;
      }
      if self.waitcount > 0 {
         unlock(self.s);
         V(self.b);
      } else {
         unlock(self.s);
         self.x = 0;
      }
    end;



Notice that the users of SpinSem become divided into two sets. Those
that spin more that MAXN times (the Slow processes) and those that don't
(the Fast processes). For the fast processes SpinSem acts like
a spinlock. The slow processes instead recognise that they are spinning too
much and they block. When a process (slow or fast) exits the critical 
region it checks to see if some slow process is blocked and if so it unblocks
it, otherwise it frees the critical region. 






ingargiola.cis.temple.edu