31. Semaphores

前面已经学习了使用lock和condition varivable来实现并发，这一节学习semaphore信号量。有了semaphore，就只有统一的原语操作了，可以用semaphore来实现lock和condition variavle的功能。问题来了：如何使用semaphore来代替lock和condition variable？semaphore的定义是怎样的？Binary semaphore是怎样的？

31.1 Semaphores: A Definition

一个semaphore有一个integer，并且可以对该值进行两个操作。在POSIX标准中，两个操作是sem_wait()和sem_post()。semaphore的初始值和要使用该semaphore进行什么操作有关，所以要先对其进行初始化：

sem_init()对semaphore进行初始化，第一个参数是s的地址，第二个参数0表明同一个进程的线程可以共享该semaphore，第三个参数1代表semaphore的初始值。

初始化后就可以对semaphore进行sem_wait()和sem_post()两个操作：

注意：当semaphore为负数时，其绝对值代表有多少个线程正在等待。

31.2 Binary Semaphores (Locks)

现在来看看如何使用semaphore来构建一个lock。

这里的X应该设置为1，这样就可以把semaphore当作lock来使用了。

康康两个线程使用semaphore构建的lock的一种情况：

31.3 Semaphores For Ordering

semaphore也可以用来实现线程之间的同步等待，使用semaphore实现同步原语，和之前得condition varivable比较像。

对于代码中得父线程和子线程，想实现父线程等待子线程结束再结束：

也就是这种效果：

这种情况下semaphore的初始值应该为0。康康使用semaphore的两种情况：

第一种父线程sleep等待子线程：

第二种父线程无须sleep等待子线程：

31.4 The Producer/Consumer (Bounded Buffer) Problem

使用semaphre来解决生产者消费者模型：
First Attempt：

使用两个semaphore，empty和full：

生产者要等buffer有空间才能放数据，消费者要等buffer有数据才能取数据。简单起见，先将MAX设置为1。这种做法可以解决多线程的同步问题。

但是现在如果将MAX调大一点，比如10，并且有多个生产者，多个消费者。问题就来了，有可能会race condition。假设两个生产者，其中一个先执行了put()，但是在还没有对fill更新时，由于中断换另一个生产者运行，另一个生产者拿到了和上一个生产者相同的fill，这样二者就会向同一个fill位置上放入数据，就会导致数据丢失。那么该怎么办呢？

A Solution: Adding Mutual Exclusion

其实问题就在于忘记解决互斥问题了，也好办，加把lock就好了。

看起来好像很简单，但是这种做法是有问题的，有可能造成deadlock？在哪里？假设现在两个线程，一个生产者，一个消费者。消费者先上CPU运行，首先它拿到了mutex，然后由于full为0 ，被sleep。这时生产者开始运行，但是由于mutex被消费者拿到了，生产者不得不等待消费者释放锁，造成了循环等待的deadlock。

At Last, A Working Solution

解决方法也很简单，减小加锁的范围，只在真正的cirtical section加锁：

31.5 Reader-Writer Locks

读写锁也是一个很经典的问题，其实在对数据进行读写时，虽然不允许同时写入，但往往为了提高性能，同时读取是被允许的，并且对正确性也没有影响。使用semaphore来实现读写锁：

可以看到一共使用了两把锁，其中一把lock用来读，另一把writelock用来写。

对于写，申请和释放锁的流程比较简单，因为某一时间只允许一个进程写数据，那么就单纯的申请释放锁就ok了。

对于读，由于可以允许多个读者，所以稍微复杂一点。申请时，申请到lock后，要将读者数+1。并且判断读者数是否为1，如果为1代表这个来的读者是第一个要读，那么就要申请writelock，如果没有线程在占用writelock写数据，该读者就可以开始读了；如果不为1，代表前面已经有读者在读了，那么该读者跟着一起读了。最后要将lock释放，以允许别的线程接着申请读锁。释放时，首先还是要申请lock，然后将读者数-1。如果读者数为0，代表没人读了，那就可以释放写锁了。如果不为0，代表还有人在读，不能释放读锁。最后释放写锁。