We assume that a lower-level mutual exclusion mechanism is available, using a test'n'set instruction, or Peterson's solution, or something equivalent. The 'Mutex' data type represents the variables used by the appropriate primitive and it has two operations defined upon it: 'enterCritical' and 'leaveCritical'.
public class Semaphore {
private int counter;
private Mutex lock;
private WaitQueue queue;public void wait(){
lock.enterCritical();
if (counter == 0){
disableInterrupts();
queue.add(thisProcess);
currentProcess.status = BLOCKED;
lock.leaveCritical();
enableInterrupts();
yieldProcessor(); // Schedule another process.
}else{
counter --;
lock.leaveCritical();
}
}public void signal(){
lock.enterCritical();
counter ++;
if (! queue.isEmpty()) {
Process p = queue.remove();
p.status = RUNNABLE;
counter --; // Decrement counter on behalf of WAITer.
}
lock.leaveCritical();
}
}
Note that we've used a wait queue to hold our list of WAITing processes. This is nice and fair (since the process which was put to sleep first is the one which is awakened first), and simple to implement.
Note that the signal operation decrements the counter on the behalf of the WAITing process it has just woken up. This is because the newly-awakened process has already left its critical section and therefore it is not safe for it to decrement the counter itself. (The newly-awakened process could attempt to enter another critical section in order to decrement the counter, but there're no guarantees that the counter would still be > 0.)
There's a bit more trickery in the WAIT operation: we disable interrupts before adding our process to the wait queue. Why? We've got mutual exclusion already, and doesn't that not work with multiple processors? Well, yes, but disabling interrupts is not being done here to achieve mutual exclusion. We don't want to stop other processes from running, just to make sure that our task continues to run. There is a danger that by making our own process BLOCKED and adding it to a wait queue, an interrupt might fire and preempt our process, and it never run again (because we have just marked it as BLOCKED). It is imperative that we leave the critical section before we become blocked, so that another process is able to enter its critical section some time and send us a SIGNAL. (On the other hand, we must add ourself to the queue and set the status to BLOCKED before leaving the critical section---otherwise there's a potential race condition with one process trying to block itself and another process trying to unblock it.)