# notes on semaphores, part 2

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 and decrement\dec. One cannot query current value.
• On dec, if value is negative, calling that thread blocks till semaphore gets to 0 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 and wait 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);

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);

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;

count = count+1         count = count+1


Solution:

sem = semaphore(1);

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: