本文已收录到：清华大学操作系统课程笔记 专题
信号量和管程：都是操作系统提供的同步方法
今天来讲解 与 锁同级的一种抽象办法。——信号量
- 信号量(Semaphore)，有时被称为信号灯，是操作系统提供的，在多线程环境下使用的一种设施, 它负责协调各个线程, 以保证它们能够正确、合理的使用公共资源。
- 两个进程协调谁能使用，由操作系统作为“裁判”。信号量的取值表示资源的数量。
- 信号量是早期操作系统的主要同步机制，现在很少用，但在计算机科学研究中还是非常重要的。
信号量
问：信号量与前面讲的临界区中中断、锁之类的有什么区别？
答：进程、线程、互斥锁与信号量之间的联系和区别 – 高志远的个人主页 (gaozhiyuan.net)
信号量是一个抽象的数据类型，由一个整型sem（取值表示资源的数目）和两个原子操作组成。
申请资源的时候用P()，释放资源用V()。
也可以类比成一个厨房里的三个锅等。
信号量的特性
信号量的优先级高于用户的进程优先级，保证原子性。
信号量跟自旋锁还有个区别是自旋锁没法做到线程之间的排队，而信号量可以排队。Ps：这里我们假设信号量是先进先出排队算法
信号量的实现
classSemaphore是一个数据类型，里面有sem表示资源数量，还有一个等待队列q。
P()表示申请资源，sem减去1。如果没取之前还剩下最后一个，减1后等于0——没关系，可以继续。如果原来就没了，0个， 减去1等于-1，就需要执行if语句了，陷入等待队列，进程放在等待队列中，并阻塞。
用完后释放：sem++，如果+1后还是小于等于0，说明其他进程一直在等着。就从等待队列中remove出一个线程放到就绪队列中（这里我们说了，就绪队列中默认用先进先出等待算法）
Ps：这里我们会发现很简单，是为什么呢？——因为这里的P和V操作都是原子的，不会被拆的指令破碎。好家伙，说白了操作系统互斥问题是把自己的活给CPU底层实现了
信号量的使用
用信号量实现临界区的互斥访问
用信号量实现临界区的条件同步
条件同步：希望B线程执行完X后才能让线程A执行N。——很正常的需求，有时候B是一个需要预先处理的任务，不执行完的话A拿到的东西就不是我们希望的。
用信号量实现生产者-消费者问题
可以把生产者看成打印作业程序、消费者看成打印机。同一时刻缓冲区要么写要么读，不可同时操作——这一部分可以参考CMU15 445 索引并发控制中的Latches的两种模式兼容性。
BoundedBuffer结构体中的成员表示三个需求：
- 在一个线程进行生产或消费时，其余线程不能进行生产或消费等操作，即保持线程间旳同步；
- 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待；
- 只有缓冲区不为空时，消费者才能从中取出产品，否则必须等待；
所以：
- 互斥信号量mutex：实现进程对缓冲池的互斥使用
- 信号量full：表示缓冲池中满缓冲区的数量，初始值为0
- 信号量empty：表示缓冲池中空缓冲区的数量，初始值为n
下图是生产者消费者主要进行的操作：
实现互斥访问临界区：
现在，仅仅解决了互斥访问问题。下面还有条件同步需要解决。
下面这两句比较难理解，仔细读读~
左边：检查是否有空缓冲区，有了才能放一个资源，否则要等待。
右边：消费者取完一个资源后可以释放一个空缓冲区资源。
右边：消费者想取一个资源，要看里面是否有一个资源，没有的话要等待不能去取。
左边：生产者生产一个资源后就释放一个空缓冲区。
Ps：上面的empty、full缓冲区不好理解，你就理解成放置资源的盒子，如果生产了一个资源，就会锁定一个空盒子，释放一个满盒子。如果是消费者就是消费一个资源就是锁定一个空盒子，释放一个满盒子
使用信号量的缺点：读写代码困难、容易忘记释放信号量、不能有效避免死锁问题，需要在写程序的时候考虑到并处理。
管程——把P、V操作综合在一起
为了改进信号量处理临界区的麻烦。我们试图把P、V操作综合在一起，这就是管程。是一种并发程序的编程方法。管程并不由用户（程序）来实现，是由编程语言来实现。用户需要用管程时直接用现成的。
相当于把底层的同步和互斥抽象出来供程序员直接使用，其实就是封装的思想，对外提供接口。
管程的特点：
管程的思想：
条件变量
管程机制中的条件变量类似与信号量机制中的信号量。
条件变量的实现：
用条件变量实现生产者-消费者问题
但第二个行为确定性更好一些。
经典同步问题：哲学家就餐文题
五个人同时拿左边叉子。
，可以接受但性能不好。
继续改进：
经典同步问题：读者-写者问题
是计算机中的一种经典问题，经常存在于数据库等很多共享资源访问当中。
对共享数据的访问有读者（只能读，可以多线程同时读）和写者（可读可写，但只能有一个线程写）
右边。只能对第一个读者与写进行互斥，所以需要加一个判断。
只用最后一个离开的读者，才需要释放。
还要对Rcount本身进行读写互斥。关于读写互斥或者说读写兼容问题可以参考CMU数据库 索引并发控制 小节。
这种实现方式，是读者优先。
如何改成写者优先？因为我们希望读取的都是最新的数据。
还有其他优先策略吗？
有的，公平策略，有读者就不能有写者，有写者不能有读者。
下面用管程实现读者-写者问题：
while里的状态就决定了，是读者优先还是写者优先，还是公平的？
AW+WW：只要有写者，读者就一定要等待。——写者优先。
AR == 0：没有读者
WW > 0：有写者等着
——写者优先。
管程可以很好的实现优先策略。
