Concurrency III

31. Semaphores

• Edsger Dijkstra has his famous shortest paths algorithm in graph theory, once said: Goto Statements Considered Harmful
• Semaphore is an object with an integer value and two atomic operations: sem_wait and sem_post (according to the POSIX standard).

• example:

  #include <semaphore.h>
  sem_t s;
  sem_init(&s, 0, 1); // sem_init(semaphore, shouldBeSharedWithThreadsInProcess, initialValue)
  

• Semaphore values:

  • initial 0: Not Available
  • initial 1: Available
  • Then it gets decremented by 1 when sem_wait is called and incremented by 1 when sem_post is called.
  • Negative values indicate how many threads are waiting for the semaphore to become available.
  • If the value is negative, the thread calling sem_wait will go to sleep; however, if 0, it will return immediately.

aspect	sem_wait	sem_post
affect on semaphore value	-1	+1
affect on threads	block	unblock
wait	every caller is queued waiting until the semaphore value is > 0	it does not wait

• **Binary Semaphore** (locks): is a semaphore with an initial value of 1. it can take 2 values: 0 and 1 and it is used to implement locks.
• **Semaphore for ordering** is a semaphore with an initial value of 0. it makes a thread wait for another thread to finish its work and then signals the first thread to continue, it is used as an ordering primitive (just as a condition variable).
• The Producer/Consumer (Bounded Buffer) Problem: