Reference: The Little Book of Semaphores by Allen B. Downey Link1
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
- Initialized with a value, only permitted operations are
decrement\dec. One cannot query current value.
dec, if value is negative, calling that thread blocks till semaphore gets to
inccalling 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
- 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(); |
decis what operations do,
waitis what they are used for.
pwere original names used by EWD
Basic synchronization pattern
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
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).
ThreadA ThreadB A1 B1 <<>> --------------------------------- <<>> A2 B2
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
wait for both semaphores. you need to
wait in each thread or it will lead to deadlock!
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
count = 0; ThreadA ThreadB count = count+1 count = count+1
sem = semaphore(1); ThreadA ThreadB sem.wait(); sem.wait(); count = count+1 count = count+1 sem.signal(); sem.signal();
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).
ThreadA ThreadB ... ThreadZ statement; statement; statement;
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();