Reference: The Little Book of Semaphores by Allen B. Downey Link1
Semaphores
In real life a semaphore is a system of signals used to communicate visually, usually with flags, lights or some other mechanism. In software world it is a data structure for solving a variety of synchronization problems.
Semaphore was invented by Edsger W. Dijkstra.
Semaphore is like an int
with:
- Initialized with a value, only permitted operations are
increment\inc
anddecrement\dec
. One cannot query current value. - On
dec
, if value is negative, calling that thread blocks till semaphore gets to0
or above. - On
inc
calling thread increments semaphore and other waiting thread gets unblocked
Note: when you signal a semaphore, you don’t know if any thread is waiting on it or not.
Value of Semaphore:
- if value is positive, it represents that #threads can
dec
without blocking - if value is negative, it represents that #threads are blocked and waiting
- if value is 0, it means there are no waiting threads
s = semaphore(1); // <<-- creates a new semaphore with value 1
s.increment(); |
s.signal(); | equivalent operations
s.v(); |
s.decrement(); |
s.wait(); | equivalent operations
s.p(); |
inc
&dec
is what operations do,signal
andwait
is what they are used for.v
&p
were original names used by EWD
Basic synchronization pattern
signalling
Thread1 sends signal to other thread to indicate that something has happened. Makes it possible to guarantee that a secion of code in one thread will run before a section of code in another thread. This solves synchronization problem.
sem = semaphore(1);
ThreadA ThreadB
statement a1; sem.wait();
sem.signal() statement b1;
guarantees that a1 < b1
rendezvous
Idea is that two or more threads rendezvous at a point of execution and neither is allowed to proceed until al have arrived. (This is very similar to barrier).
Problem:
ThreadA ThreadB
A1 B1
<<>> --------------------------------- <<>>
A2 B2
Solution:
semA = semaphore(1);
semB = semaphore(2);
ThreadA ThreadB
A1 B1
semA.signal(); semB.signal();
semB.wait(); semA.wait();
A2 B2
This solution is hard-coded for just two threads and is not a practical. Also note the order of signal
and wait
for both semaphores. you need to signal
before wait
in each thread or it will lead to deadlock!
mutex
semaphores can be used to enfoce mutual exclusions as well. A mutex is a like a token that moves from one thread to another.
CriticalSection/cs
–> a section of code for which it is critically important to prevent concurrent access
Problem:
count = 0;
ThreadA ThreadB
count = count+1 count = count+1
Solution:
sem = semaphore(1);
ThreadA ThreadB
sem.wait(); sem.wait();
count = count+1 count = count+1
sem.signal(); sem.signal();
multiplex
Generalized mutex so that is allows multiple threads to run in cs
at same time, but it enforces an upper limit on #concurrent thread access (reader-writer lock kind of thing).
Problem:
ThreadA ThreadB ... ThreadZ
statement; statement; statement;
Solution:
m = semaphore(4); // only 4 threads can concurrently access a cs
ThreadA ThreadB ... ThreadZ
m.wait(); m.wait(); m.wait();
statement; statement; statement;
m.signal(); m.signal(); m.signal();