2.6 信号量与P/V操作

并发导致的程序结果不可再现，如何能让结果确定化呢？

上一节介绍了基于进程间协商的同步机制，但是这种机制基于的“忙检测”方法带来了额外的开销，信号量与P/V操作就是一种更好的解决进程间同步与互斥的方法；

一、信号量的提出

由图灵奖获得者、荷兰科学家dijkstra提出；（yyds！）

信号量其实是一个很简单的结构体，由两个成员构成；

struct semaphore
{
    int value;              // 信号量的值
    pointer_PCB queue;      // 信号量等待队列指针     
}

二、P、V操作

P（Proberen，尝试）操作

P操作首先会将信号量的值减一，然后进行判断。
如果信号量的值小于0，则将执行P操作的进程加到信号量指针指向的进程等待队列中；
如果信号量的值不小于0，则正常返回；

V（Verhogen，增量）操作

V操作首先会将信号量的值加一，然后进行判断。
如果信号量的值小于等于0，则将信号量指针指向的等待队列中的某一个进程唤醒；
如果信号量的值大于0，则正常返回；

三、P/V操作在典型问题中的应用：

（1）苹果桔子问题（多个进程共享同一个缓冲区，实现定向通信问题）：

桌子上有个盘子，每次只能放一个水果；
爸爸专门向盘子中放苹果，妈妈专门向盘子中放桔子；
儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果；

信号量的设置：

struct semaphore
{
    int s;                      // s代表可用的空盘子数，初值为1
    pointer_PCB s_queue;        

    int g1;                     // 盘子里有无桔子，初值为0
    pointer_PCB g1_queue;        

    int g2;                     // 盘子里有无苹果，初值为0
    pointer_PCB g2_queue;        
}

（2）P、V操作的部署：

共有father、mother、daughter、son四个进程并发运行；

先以不发生互斥的情况为例：

1、假设先执行$father$进程

process father
{
    P(s);       // 放苹果,将s减一,空盘子数变为0,并将进程放入等待队列中
    V(g2);      // g2加了一，表示有一个苹果可用
}

$s$变为$0$，$g2$变为$1$，操作都正常返回；

2、假设之后女儿来了

process daughter
{
    P(g2);  // 将g2减一，表示女儿去了一个苹果，
    V(s);   // 将s加一，表示有一个空盘了
}

$s$变为$1$，$g2$变为$0$，操作都正常返回；

再来看一种异常的情况:

1、先执行一次$father$进程，表示爸爸已经将苹果放入盘子中了，此时$s=0, g2=1$；

2、此时假设开始执行$son$进程（由于盘中没有苹果，$son$进程应该不允许执行才对）

process son
{
    P(g1);  // 取一个桔子，将g1减一
    V(s);   // 吃桔子，将s数量加一，表示空盘数量加一
}

$g1$原本为$0$，将$g1$减一后变为$-1$，会触发判断条件，将$son$进程加到$g1$所指向的等待队列中，并处于阻塞状态，不再参与调度了；
$V(s)$操作没有执行，程序执行完$P（g1）$后就堵塞了；

3、假设之后又开始执行$mother$操作(由于盘中已有苹果，$mother$进程也不能执行才对)

process mother 
{
    P(s);   // 妈妈要放桔子，空盘数量要减一
    V(g1);  // 妈妈放了桔子，桔子数量要加一
}

执行$P（s）$操作后，$s$减一变为$-1$，满足$P$操作小于$0$的条件，会将$mother4进程放入$s$所指的等待队列中，并处于阻塞状态，不参与调度了； 同样，$V（g1）$仍然没有执行；

此时$s = -1、g1 = -1、g2 = 1$;

4、假设之后要执行$daughter$进程

process daughter
{
    P(g2);  // 将g2减一，表示女儿取了一个苹果，
    V(s);   // 将s加一，表示有一个空盘了
}

$P（g2）$操作使得$g2$变为了$0$，并且不触发判断，正常返回；
$V（s）$操作将$s$变为了$0$，满足$V$操作的判断条件，会唤醒s指向等待队列中的$mother$
进程，因此$mother$进程会继续执行（从$V（g1）$继续执行）；

5、$mother$进程继续执行，将$g1$从$-1$修改为$0$，满足$V$操作的判断条件，会唤醒$g1$指向等待队列中的$son$进程，$son$进程从而继续执行（从$V(s)$继续执行）

6、$son$进程继续执行$V（s）$操作，将$s$由$0$变为了$1$，不满足$V$操作的判断条件，正常返回；

四个进程按照互斥的顺序执行了一遍，信号量中的值又回到了$s = 1，g1 = 0，g2 = 0$的情况；

P/V操作很好的解决了进程间的互斥情况；