notes on semaphores, part 2

 Posted on December 5, 2019

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

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