信号量
信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。
信号量机制
进程间通信处理同步互斥的机制。信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。
PV操作
PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作
定义如下
设信号量为S，S可以取不同的整数，用来表示共享资源的使用情况或者指示协作进程之间交换的信息
P操作
每执行一次P操作其实就是意味请求分配一个资源
P(S)
{
S = S - 1;
若S>=0，表示可用资源分配，进程继续执行
若S<0，没有可分配的资源，将该进程状态置为等待状态(阻塞状态)，然后将该进程的PCB插入相应的S信号量等待队列末尾(其S的绝对值表示排在S信号量的等待队列中进程数目)，直到有其他进程在S上执行V操作为止。如：S为-1，则当有资源的话(有进程执行V操作)，则第一个唤醒该进程
}
V操作
每执行一次V操作，意味着进程释放了一个资源，并唤醒一个等待队列中进程
V(S)
{
S = S + 1;
若S>0，则该进程继续执行
若S<=0，表示还有进程在等待队列中，释放在S信号量队列中等待的第一个进程(按P操作的S值的绝对值，-1则第一个唤醒，和队列一样的思想先进先出)，将其状态改为就绪状态，并将其插入到就绪队列中；然后，继续执行该进程
}
注意：
- 每个程序中用户实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。若有多个分支，要认真检查其成对性。
- P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
- 互斥信号量的初值一般为1。
示例1
假设有进程A、B竞争进入临界区，用P、V操作实现进程之间的互斥。其中，S的初值为1。分析下面两个进程P、V操作
进程A 进程B：
P(S); P(S);
临界区操作; 临界区操作;
V(S); V(S);
分析：
- 1.假设A进程先进入，先执行P操作申请资源，S = S - 1 = 0，未小于0，有资源可以继续执行，然后执行临界区操作
- 2.这时，B进程进来了，执行P操作申请资源，S = S - 1 = -1，发现小于0，没资源了，就进入等待状态
- 3.A进程这是执行到V操作，S = S + 1 = 0，发现S的值<=0，就知道有进程在等待队列，唤醒该进程并释放资源
- 4.B进程被唤醒，进入就绪状态，由于之前已经执行过P操作，只是从等待队列中唤醒，无需再次执行P操作，直接执行临界区操作
- 5.最后B执行V操作，S = S + 1 = 1，发现没有等待队列中没有需要唤醒的，B进程结束
示例2
有三个进程，进程get从输入设备上不断读取数据，并放入缓冲区buffer1;进程copy不断地将缓冲区buffer1中的内容复制到缓冲区buffer2;进程put则不断将buffer2中的内容在打印机上输出。该三个进程是同步进行
关系图如下：
思路
信号量的设置
- S1:初值为1，保证get进程能够从设备读数据到buffer1。
- S2:初值为0，copy进程能否将buffer1的内容复制到buffer2。
- S3:初值为0，put进程能否将buffer2的内容打印输出。
- S4:初值为1，保证buffer2缓冲区可以使用
PV表示
get进程：
while(true) {
...
P(S1); //申请资源，S1 = S1 - 1 = 0，继续执行
从输入设备向缓冲区buffer1读数据;
V(S2); //唤醒S2进程
}
copy进程
while(true) {
P(S2); //申请资源，判断是否buffer1是否有资源
P(S4); //唤醒buffer2进程，保证buffer2没有进程在使用
将buffer1内容复制到buffer22;
V(S1); //释放S1资源，为get进程下次做准备，也就是相当于通知get进程
V(S3); //唤醒S3，为put进程赋予资源，通知put进程
}
put进程
while(true) {
P(S3); //判断是否有资源，看前面copy进程，也就是查看buffer2进程里是否有资源，否则就要进入等待队列
将缓冲区buffer2内容再打印机上输出;
V(S4); //释放资源，表示buffer2缓冲区可用，相当于通知copy进程
}
例题2 生产者---消费者问题
设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来。缓冲区只容纳一个产品，生产者不断地生产者，然后往空缓冲区送产品；而消费者则不断地从缓冲区取出产品，并消费掉
关系图
思路
- 生产者不能往满地缓冲区放产品
- 消费者不能从空地缓冲区取产品
信号量设置
- 设置empty表示不能往满缓冲区放产品，空缓冲区数目，初值为1
- 设置full表示不能从空缓冲区取产品，满缓冲区数目，初值为0
PV操作
P进程 生产者
while(true) {
P(empty); //判断缓冲区是否为空
生产一个产品;
送产品到缓冲区;
V(full); //增加满缓冲区数目，相当于通知消费者可以从缓冲区取chanp
}
Q进程 消费者
while(true) {
P(full); //判断是否小于0
从缓冲区取产品;
V(empty); //相当于通知生产者空缓冲区数目
}
例题3 多个生成者---消费者问题
设有若干个生产者P1,P2....若干个消费者Q1,Q2....，他们通过一个环形缓冲池联系
关系图
思路
和上面生产者---消费者一样，只不过是环形
- 生产者不能往“满”缓冲区中放产品，设置信号量empty,初值K，指示缓冲池空缓冲区数目
- 消费者不能从“空”缓冲区中取产品，设置信号量full，初始值为0，指示缓冲池中的满缓冲数目
- 缓冲池必须互斥访问，设置信号量mutex，初值为1
- 整型量i，j，初值为0，分别用于指示空缓冲区和满缓冲区位置
PV操作
生产者进程P1，P2，...，Pn;
i = 0;
while(true) {
生产产品;
P(empty); //判断缓冲区是否是满的
P(mutex); //判断是否有消费者在进程中，没有则并释放互斥信号，因为生产者与消费者不能同时访问
往Buffer[i]中放产品;
i = (i + 1) mod k; //取余
V(mutex); //解除互斥信号
V(full); //表示满缓冲区数目，相当于通知消费者
}
消费者进程Q1，Q2，...，Qn;
j = 0;
while(true) {
P(full); //判断缓冲区是否为空，就是满缓冲区数目大于0
P(mutex); //判断是否有生产者在进程中，没有则释放互斥信号
从buffer[j]取产品;
j = (j + 1) mod k; //取余
V(mutex); //解除互斥信号
V(empty); //通知生产者空缓冲区数目
消费产品;
}
例题4
桌上有一个水果的盘子,一次只能放一个水果，父亲向盘中放苹果或橘子,女儿专吃苹果，儿子专吃橘子，试用pv操作写出他们能正确同步的过程。
思路
该问题其实和生产者---消费者问题一样
- 爸爸是生产者
- 一个盘子只能放一种水果
- 父亲向盘中放苹果或橘子,女儿专吃苹果，儿子专吃橘子，互斥
信号量设置
设S代表盘子是否为空，初值为1；So示盘中是否有橘子,其初值为0；Sa表示盘中是否有苹果，其初值为0。
PV操作
爸爸
while(true) {
P(S); //判断盘子是否为空
if(放入的是橘子) {
V(So); //通知儿子
}
else {
V(Sa); //通知女儿
}
}
儿子
while(true) {
P(So); //判断是否为橘子
吃橘子;
V(S); //通知爸爸盘子为空了
}
女儿
while(true) {
P(Sa); //判断是否为苹果
吃苹果;
V(S); //通知爸爸盘子为空了
}