Semaphores

带着问题学习：如何使用信号量（semaphores）？

1. Semaphores: A Definition

semaphore是一个具有整数值的对象，可以使用两个例程来对其进行操作。
POSIX中两个例程为sem_wait()和sem_post()。
在使用之前必须初始化，如下所示：

该例程sem_init()的第三个参数表示初始化值为1，第二个参数0表示在一个进程中线程可共享semaphore。

注：当semaphore的值为负数时，其值表示为处于等待状态的线程的数量。

2. Binary Semaphores(Locks)

使用一个semaphore作为锁（lock），如下所示：

注：上图中X应该为1。

假设有两个线程0和1：
第一种情况：线程0一直运行到结束

第二种情况：线程0持有锁调用了sem_wait()但还没有调用sem_post()，线程1尝试调用set_wait()进入critical section。

3. Semaphores For Ordering

使用semaphore作为排序原语（ordering primitive），如下所示：

注：上图中X应该为0（上图有两种情况要考虑）。

4. The Producer/Consumer (Bounded Buffer) Problem

要回到上次谈及的Producer/Consumer问题。

4.1 First Attempt

上述代码MAX = 1时不管是单线程还是多线程都能正常运行；但是如果MAX > 1，就出现了问题：当有多个producer和多个consumer时，两个producer分别为P_a和P_b同时调用put()（F1），当P_a准备进入F2阶段时被打断（数据被放入缓冲区的第0号元素），这意味着第0号元素的旧数据被覆盖。

4.2 A Solution: Adding Mutual Exclusion

上述问题解决方法就是添加互斥锁（mutual exclusion），因为其为关键部分（critical section）。

上述代码会发生死锁（deadlock）， WHY？

4.3 Avoiding Deadlock

产生死锁原因：假设有一个producer和一个consumer，consumer首先持有锁（line C0），然后调用sem_wait()（line C1），由于没有数据，此调用导致consumer被阻塞而让出CPU（但是consumer仍然持有锁）；然后producer开始运行，它首先要做的就是持有锁（line P0），由于锁被consumer持有，producer不得不进入等待状态。一直如此下去，产生死锁。

4.4 At Last, A Working Solution

为了解决上述问题，我们必须减小锁的范围。如下所示：

5. Reader-Writer Locks

不同的数据结构可能需要不同的锁。
对于一个list的查找和插入，只要保证在查找时插入操作不会进行，那么就可以允许许多查找同时运行。支持这种特殊操作的特殊类型的锁就叫做reader-writer lock。

这种锁实现了reader和writer不能同时工作（例如：一旦一个reader获取了锁，那么其他reader也可以获取锁，但是writer不能获取锁）。这就可能造成starvation（不公平，我们要反抗！）。

6. The Dining Philosophers

Dijkstra提出并解决的最著名的并发问题之一就是The Dining Philosophers。如下所示：
5个哲学家围着桌子坐，每两个哲学家之间有一个叉子，每个哲学家都有自己的思考时间（不需要任何叉子、吃饭）。为了吃饭，哲学家需要两个叉子（左边和右边）。

如下是每个哲学家的循环操作：

while (1)
{
	think();
	get_forks(p);
	eat();
	put_forks(p);
}

对于每个哲学家，都能进行左右两边操作：

int left(int p) { return p; }
int right(int p) { return (p + 1) % 5； }

当然，我们也需要semaphore帮助这些哲学家解决问题。假设每个哲学家都有一个semaphore：

sem_t forks[5]

6.1 Broken Solution

假设每个哲学家的semaphore都初始化为1，且每个哲学家都知道它自己的序号。如下所示：

上述代码存在问题：死锁（deadlock）。如果每个哲学家都只拿左（右）边的叉子，每个哲学家最终都会有一个叉子而进入一直等待状态。

6.2 A Solution: Breaking The Dependency

解决上述问题最简单的方法就是改变至少一位哲学家获取叉子的方式。
不妨假设序号4的哲学家（序号从0开始）获取叉子的方式与其他哲学家不同。如下所示：

还有其他著名的问题如：cigarette smoker's problem、sleeping barber problem等，都是关于并发的。

7. Thread Throttling

还有一个重要问题：程序员如何防止“太多”线程同时执行某项操作而致操作系统瘫痪？

解决方案：设置并发线程的阈值并使用semaphore限制执行同一段代码的线程的数量。

8. How To Implement Semaphores

最后，使用locks和condition variables来构造我们自己的semaphores。