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

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax