In 1965, Dijkstra proposed a new and very significant technique for managing concurrent processes by using the value of a simple integer variable to synchronize the progress of interacting processes. This integer variable is called semaphore. So it is basically a synchronizing tool and is accessed only through two low standard atomic operations, wait and signal designated by P(S)
and V(S)
respectively.
In very simple words, semaphore is a variable which can hold only a non-negative Integer value, shared between all the threads, with operations wait and signal, which work as follow:
P(S): if S ≥ 1 then S := S - 1
else <block and enqueue the process>;
V(S): if <some process is blocked on the queue>
then <unblock a process>
else S := S + 1;
The classical definitions of wait and signal are:
S
, as soon as it would become non-negative(greater than or equal to 1
).S
, as there is no more process blocked on the queue.Semaphores are mainly of two types:
It is a special form of semaphore used for implementing mutual exclusion, hence it is often called a Mutex. A binary semaphore is initialized to 1
and only takes the values 0
and 1
during execution of a program.
These are used to implement bounded concurrency.
Here is a simple step wise implementation involving declaration and usage of semaphore.
Shared var mutex: semaphore = 1;
Process i
begin
.
.
P(mutex);
execute CS;
V(mutex);
.
.
End;