Semaphores

Semaphore is a concept invented by Dutch Compute Scientist Dijkstra.
It is a global counter that can only be changed by 2 atomic operations: P(s) and V(s).
P will decrement s if s > 0 and return immediately but would suspend the thread if s = 0.
Once s > 0 due to V operation, the thread is restarted and decrement s and return control.
P stands for proberen( to test) in Dutch.

V will increment s by one. If there are threads waiting for s to become non-zero, V will restart exactly one thread that will complete and decrement s.

V stands for verhogen(to increment) in Dutch.

Binary semephore(where the max value of s is 1) is called lock. P will lock and V will unlock.

Counting Semaphore

Semaphore can be used as a counter and tells us about resources needed by threads.
A classic example is Producer-consumer problem. There is a shared buffer among producer and consumer threads and producers can produce when there are empty slots in the buffer. Consumer can consume if there are goods made by producer.

We will use 3 semaphores. A binary semaphore to lock the buffer. A counting Semaphore to count empty space(resource for producer) and a counting semaphore for how many good(resource for consumer ).

When a producer try to produce, it will do

P(empty_space_semaphore)   //check for empty space
P(lock)                    //lock
buf[loc].write()           //produce
V(lock)
V(goods_semaphore)         //Announce goods have been made

When consume, it will be basically the same, but with

P(goods_semaphore)        //consume
...
V(empty_space_semaphore)  //add empty space