E. W. Dijkstra suggested using an integer variable for IPC problems. In his proposal, a new variable type, called a semaphore, was introduced. Dijkstra proposed having two atomic operations, DOWN and UP (P and V in Dijkstra’s original paper).
The DOWN operation on a semaphore checks to see if the value is greater than 0. If so, it decrements the value and just continues. If the value is 0, the process is put to sleep. Checking the value, changing it, and possibly going to sleep is all done as a single, indivisible action (this is why these operations are called atomic.). It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has completed or blocked.
This atomicity is absolutely essential to solving synchronization problems and avoiding race conditions. The UP operation increments the value of the semaphore addressed. typedef int semaphore; /* semaphores are a special kind of int */
semaphore s=0;
void down(semaphore &s) { while (s <= 0) { } ; s = s – 1; } void up(semaphore &s) { s=s+1; }
If two processes try to execute up(s) or down(s) simultaneously, these operations will be executed sequentially in an arbitrary order. Semaphores can be used for CS problem as follows
semaphore mutex = 1; /* controls access to CS */ proces_i (void) /* n-processes */ { while (TRUE) { down(mutex) ; /* CS_entry */ CS up (mutex) ; /* CS_exit */ non-CS } }