30 Semaphores

Semaphores are a synchronisation tool, proposed by E.W. Dijkstra that :

• simplifies synchronisation for the programmer
• does not require (much) busy waiting, and
• can guarantee bounded waiting time and progress

Consists of :

• A semaphore type S, that records a list of waiting processes and an integer
• Two standard atomic ($\leftarrow$ very important) operations by which to modify S: wait() and signal()

Works like :

• The semaphore is initialised with a count value of the maximum number of processes allowed in the critical section at the same time.
• When a process calls wait(), if count is zero, it adds itself to the list of sleepers and blocks, else it decrements count and enters the critical section
• When a process exits the critical section it calls signal(), which increments count and issues a wakeup call to the process at the head of the list, if there is such a process.
  • It is the use of ordered wake-ups (e.g. FIFO) that makes semaphores support bounded (i.e. fair) waiting.

Semaphore as General Synchronisation Tool

• We can describe a particular semaphore as :
  • A Counting semaphore - integer value can range over an unrestricted domain (e.g. allow at most N threads to read a database, etc.)
  • A Binary semaphore - integer value can range only between 0 and 1
    • Also known as mutex locks, since ensure mutual exclusion.
    • Basically, it is a counting semaphore initialised to 1.

Critical Section Solution with Semaphore

Semaphore mutex; // Initialized to 1
do {
	wait(mutex); // Unlike the pure spin-lock, we are blocking here.
		[critical section]
	signal(mutex);
		[remainder section]
} while (TRUE);

Semaphore Implementation : State and Wait

We can implement a semaphore within the kernel as follows (note that the functions must be atomic, which our kernel must ensure):

typedef struct {
	int count;
	process_list; // Hold a list of waiting processes/threads
} Semaphore;
 
void wait(Semaphore *S) {
	S->count--;
	if (S->count < 0) {
		add process to S->process_list;
		sleep();
	}
}

• Note that, here, we decrement the wait counter before blocking (unlike the previous description).
• This does not alter functionality but has the useful side-effect that the negative count value reveals how many processes are currently blocked on the semaphore.

Semaphore Implementation : Signal

void signal(Semaphore *S) {
	S->count++;
	if (S->count <= 0) { // If at least one waiting process, let him in.
		remove next process, P, from S->process_list
		wakeup(P);
	}
}