2018-04-07

The Little Book of Semaphores

###Semaphores
现实世界的semaphores是一个用来沟通的信号系统。计算机世界的semaphores是一个数据结构，被用来解决synchronization问题。Semaphores的发明者是Edsger Dijkstra。

###定义
Semaphores是一个Integer，再加上下面的约束：

创建的时候，可以指定任意的数字。只能对它执行increment和decrement操作，不能直接访问semaphore的int value。
当一个thread decrement一个semaphore：如果结果为负，则thread阻塞。但是，在执行decrement之前，无法知道当前thread是否会被阻塞。
当一个thread increment 一个semaphore：选择一个阻塞的thread使其被唤起。然后，两个thread都继续执行。

###语法
increment ：signal 或者 V
decrement：wait 或者P

如果说要一个完整的函数名，可能是下面的形式：

1 2	fred.increment_and_wake_a_waiting_process_if_any() fred.decrement_and_block_if_the_result_is_negative()

increment 和decrement 描述了方法做了什么；

signal 和 wait 描述了方法被用来做什么；

V 和 P 是Dijkstra提出的原语。

基本的同步模式（Basic synchronization patterns）

Signaling

可以用来保证一个线程中的一段代码会早于另外一个线程中的一段代码运行。

Thread A

1 2	statement a1 sem.signal()

Thread B

1 2	sem.wait() statement b1

a1 > b1

Rendezvous

要求： a1 > b2 and b1 > a2

Thread A

statement a1
aArrived.signal() 
bArrived.wait()
statement a2   // critical point

Thread B

statement b1
bArrived.signal()
aArrived.wait()
statement b2   // critical point

mutex

mutex很像一个在线程间传递的token，获得到token的线程可以处理。

Mutex 是mutual exclusion的缩写。用mutex去保护critical regions

Thread A 和 Thread B

mutex.wait()
#critical section
count = count + 1 //for example
mutex.signal()

Multiplex

和mutex和像，只是容许多个线程同时进入critical regions。为了实现这样的效果，直接将semaphores 初始化为n（n个线程同时进入critical regions）。

1
2
3

multiplex.wait()
//critical section
multiplex.signal()

Barrier

Rendezvous只容许两个线程。但是如果容许多个线程，就是Barrier，要求所有线程都不能执行critical point，除非所有的线程都已经执行了rendezvous。

n = the number of threads
count = 0 //有多少线程已经到来了 
mutex = Semaphore(1) //对count的修改，进行并发控制
barrier = Semaphore(0) //一直阻塞，直到所有的线程到达。

rendezvous
mutex.wait()
count = count + 1 
mutex.signal()

if count == n: barrier.signal()

barrier.wait()   // 这样的wait和signal紧接着的情况，很常见，被叫做turnstile(旋转门)
barrier.signal() // 因为它既可以控制线程们一个个的通过，也可以被锁住，不让所有的线程通过。

cirtical point

Reusable barrier

当所有的线程通过后，再次不容许任何线程通过，就可以再次使用。也被叫做two-phase barrier

Preloaded turnstile

turnstile是一个常用的组件，它有个不好的地方就是强制线程一个个的通过。可能造成大量的线程切换。

基于reusable barrier ，如果最后一个打开旋转门的线程，可以预加载足够多的signal，就可以让相同数量的线程通过旋转门。

# rendezvous
mutex.wait()
  count += 1
  if count == n:
    turnstile.signal(n)   // unlock the first
mutex.signal()

turnstile.wait()     // first turnstile
# critical point  

mutex.wait()
  count -= 1
  if count == 0:
    turnstile2.signal(n)  // unlock the second
mutex.signal()

turnstile2.wait()     // second turnstile

Queue

//TODO

基本的同步模式 （Basic synchronization patterns）