[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]
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;
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