Semaphore

Definition

Semaphore is two integer object that can be controlled by two routines. Under POSIX, it is sem_wait() and sem_post().

1
2
3
4
5

#include <semaphore.h>
sem_t =s;
sem_init (&s, 0, 1); 
// Initialise with value 1.
// Second parater 0 -> shares among threads.

1. sem_wait()
   1. Immediately reutrns (if >= 1)
   2. Wait until it becomes >= 1
   3. Remembet there are two methods of waiting;sleep, spin.
2. sem_post()
   1. Does not wait like sem_wait()
   2. It increases semaphore and awake one thread.
3. If semaphore is negative
   1. Thread waits only when semaphore is negative.
   2. It equals the num of threads waiting. User cannot know this number.

Binary Semaphore (lock)

Since there are two threads, the initial semaphore value must be 1.

1. Thread A decrease semaphore to 0 (sem_wait)
   1. since it is 0, it does not wait.
2. Thread B decrease semaphore to -1 (sem_wait)
   1. Since it is negative, B waits.
3. A calls sem_post, and semaphore becomes 0
   1. it awakes thread B.
4. B calls sem_post (after critical section), then semaphore becomes 1.

Semaphore as conditional variable

For example, in case where the parent process is waiting its child process to be finished, the communication (notation) can be done through the semaphore.

1. Parent creates the child, and sem_wait.
2. Child process sem_post once it finished its job.
3. Then parent can notice child is done and then proceed.

In this example, since there are only two processes, and parent has to wait after call sem_wait, the initial semaphore value should be 0 (of course).

Producer/consumer - Finite Buffer

• Also called as Bounded-Buffer

Assumption: Max = 1, empty = max, full = 0;
full is used by Consumer, empty is used by producer.
By setting values as above, there could be only one element within the queue, and producer&consumer will always have the same tendency within the given code.

1
2
3
4

1. consumer first -> wait(full) -> full = -1 -> now wait.
2. producer second -> wait(empty) -> empty = 0 so keep going -> put element in the queue -> post(full) -> full = 0.
3. consumer awake -> get the element -> post (empty) -> empty = 1.
// Now empty = 1, full = 0 as the beginning

Reader-Writer Lock

1. Reader increase reader variable after have read-lock.
   1. when havd read-lock, get write-lock together by calling sem_wait against writelock (semaphore).
   2. When release read-lock,. it released write lock with sem_post (if there is no reader left).
      1. -> This behaviour allows readers able to get read-lock.
      2. -> Writer, on the other hand, needs wait until all the readers are done.
      3. -> The last reader will release the write lock in the end.
2. This is unfair to writers as it may cause starvation as well. -> there is a implementation to fix it.
3. Shoudl be cautious using it as it may have significant overheads.

RCU : Read Copy Update - Lock free synchronization approach

• Can be used in Reader-Writer problem.
• Idea is that New readers are redirected to the modeifed data.
• Once old readers have finished the old data, can be reclaimed.
• Thid approach effectively splits the removal and reclamation up into two separate phases.