OS-操作系统学习笔记-5：进程同步与进程互斥（二）：信号量机制

在上一篇笔记中，我们介绍到了进程同步和进程互斥，以及用软件层面上的四种方法、硬件层面上的三种方法，分别实现进程互斥。但是这些方法大部分都存在着一些问题：

• “上锁”与“检查”是非原子操作
• 都无法做到“让权等待”

接下来，我们介绍一种全新的 信号量机制 。

1. 信号量机制

信号量机制可以让用户通过使用操作系统提供的 一对原语 来对 信号量 进行操作，从而方便地实现进程互斥和进程同步。信号量（Semaphore）其实就是一个变量，它可以记录系统中某个资源的数量，而原语指的是 wait(S) 原语和 signal(S) 原语（或者说是 P 操作和 V 操作），可以看作是两个函数。

1.1 整型信号量

信号量如果单纯是一个整数型的变量，那么就称为整型信号量，它的值记录了系统中某种资源的数量。在使用整型信号量的情况下，P 、V 操作是类似这样的：

int S = 1;
wait(int S)               
{                       
    while(S <= 0)            
    S = S-1              
}
signal(int S)
{
    S = S+1
}

同样以进程 P0，P1 为例进行说明：

P0：                    P1:
wait(S)                wait(S)            // 进入区
critical section       critical section   // 临界区
signal(S)              signal(S)          // 退出区 

假定 P0 想要进入临界区，那么它就会在进入区申请资源：执行 P 操作，进行“检查”和“上锁”，由于 S 一开始是1（表示目前有一个资源可以使用），所以 P0 可以跳过循环，成功申请到资源。此后，S 减一变为 0，代表已经没有可用资源了 —— 这一步也相当于上锁；对于 P1，当他想要申请资源的时候，同样先来到进入区执行 P 操作，由于 S = 0，所以此时 P1 陷入了死循环；再回到 P0 ，他完成任务后会在退出区释放资源，S加一变为 1，这时候 P1 才有机会退出循环，进而申请资源。

整个过程其实和之前介绍的方法是很类似的，但是由于这次，“检查”和“上锁”两个操作被封装在一个原语里，所以这两个操作必定是一气呵成、无法被打断的，这就避免了某个进程钻空子的现象。但是同时我们也发现，在 P0 时间片用完后，P1 仍然会占用处理机进行没有意义的死循环，也就是 仍然违背了“让权等待”的原则 。

于是在此基础上，又出现了记录型信号量

1.2 记录型信号量

与整型信号量仅用一个单一变量记录可用资源数不同，记录型信号量的数据结构类似于一个结构体，它不仅记录了可用资源数 value ，而且还提供了一个等待队列 L 。

记录型信号量的思想其实是，如果由于 P0 在使用临界资源而导致 P1 暂时无法使用，那么干脆就不给 P1 陷入循环的机会， 直接让它自己去阻塞队列 ，这样 P1 在被唤醒之前，永远无法占用处理机，也自然就不可能出现白白占用处理机的情况。而在 P0 释放资源后，我们才来考虑唤醒 P1。

记录型信号量的结构如下所示：

typedef struct {
    int value
    sturct process *L
} semaphore

同时，记录型信号量的 P、V 操作也有所不同，如下所示：

wait (semaphore S){
    S.value--
    if(S.value < 0){
        block(S.L)
    }
}
signal(semaphore S){
    S.value++
    if(S.value <= 0){
        wakeup(S.L)
    }
}

value

下面我们用例子来说明记录型信号量工作的过程，为了加深记忆，这里用四个进程来说明：

PO:            P1              P2           P3
wait(S)        wait(S)         wait(S)      wait(S)
临界区          临界区          临界区        临界区
signal(S)      signal(S)       signal(S)    signal(S)

假设计算机中有两台可用的打印机 A 和 B（也就是说，value = 2），有四个进程需要用到打印机资源。

一开始假定是 P0 先占有处理机，那么 P0 就会在进入区申请资源 。由于 value 一开始是 2，所以 P0 成功申请到资源 A，之后 value 数量减一变为 1，同时来到临界区开始“干活”；在 P0 的时间片完了之后，P1 占有处理机，此时同样申请到资源 B，value 由 1 变为 0，之后来到临界区“干活”。自此，两个打印机都被占用了。

在 P1 的时间片完了之后，P2 占有处理机，value 由 0 变为 -1 < 0，前面我们说过，value < 0 说明无可用资源，所以此时 P2 将自己 主动 送到了阻塞队列。接着来到了 P3，value 由 -1 变为 -2，P3 同样进入阻塞队列。P2，P3 都从运行态转为阻塞态。

处理机又来到 P0，P0 很快执行完了，于是在退出区执行 P 操作释放资源，将 value 加一变为 -1，之后由于通过 if 检测到阻塞队列中有进程等着用资源，所以马上唤醒了队头的 P2 ，P2 从阻塞态回到就绪态，并直接进入临界区开始自己的工作，在完成后同样来到退出区释放资源，value 由 -1 变为 0，但是在 if 中还是检测到了队列中仍然有进程等着用资源，于是马上把队头的 P3 唤醒，P3 回到就绪态，并直接进入临界区开始工作，此后，value 由 0 变为 1，此时 if 不通过，说明队列中再也没有其它进程等着了，该拿到资源的进程都拿到了。自此，P0，P2，P3 都拿到了 A 资源，而 P1 也在不久后完成工作，在退出区释放资源 B，此时 value 从 1 变回最初的 2 ，代表占用的资源已经全数归还。

PS：当然，实际情况还可能是，P2 拿到了 A 资源，P3 拿到了 B 资源，但分析过程也是大同小异的。

显然，记录型信号量与前面介绍的所有方法最大的区别就在于，不会再有进程白白占用处理机进行没有意义的循环 —— 相反地，这些进程非常“老实”地把自己送到了阻塞队列，选择在那里慢慢地等待，等待其它进程完成后将自己唤醒，这种做法“既方便了别人，也方便了自己”。这就正好与我们多次强调的”让权等待“非常契合了。

记录型信号量明显优于整型信号量，所以在提到 PV 操作的时候，一般默认指的都是记录型信号量。

1.3 例题

我们通过几道题加深一下印象：

• n 个并发进程，信号量初始值为 1，当 n 个进程都执行 P 操作后，信号量的值为多少？
• 信号量初值为 4，多次 PV 操作后变为 -2，那么获得资源的进程数目是多少？
• 5 个并发进程，信号量初始值为 3，那么信号量取值范围是多少？

（1）每执行一次 P 操作，信号量就会减一，所以对于 n 个并发进程，共需要执行 n 次 P 操作，所以此后信号量的值是 1-n

（2）信号量值为 -2，说明有两个进程位于阻塞队列，说明暂无空闲资源可用，换句话说，四个资源都被占用了，所以共有四个进程获得资源

（3）信号量初始值为3，所以最大值为3，如果 5 个进程都执行 P 操作，那么信号量会变成 3-5 = -2，即最小值为 -2，所以取值范围 -2 ~ 3。

2. 信号量机制的应用

2.1 信号量实现进程互斥

其实上面讲的例子就已经很好地实现了进程互斥，但是实际上我们可以简化一下写法，如下：

semaphore mutex = 1;
P0(){
    P(mutex)
    critical section
    V(mutex)
}
P1(){
    P(mutex)
    critical section
       V(mutex)
}

我们默认已经定义了 semaphore 的结构体，并用 mutex 变量记录可用资源的个数。要实现互斥，关键就是要 在临界区之前使用 P 操作进行上锁，在临界区之后使用 V 操作进行解锁 。

2.2 信号量实现进程同步

在前面，我们一直用大量的篇幅解释进程互斥的实现，那么如何实现进程同步呢？也就是说，多个进程一起完成某项任务的时候，如何确保它们按照一定的先后顺序有秩序地执行呢？

实际上，信号量机制也可以很好地实现进程同步。它的核心是三个关键步骤：

• 设置信号量初始值为 0
• 在”前操作“之后执行 V(S)
• 在”后操作“之前执行 P(S)

先来解释一下原理，即：为什么这样就可以保证两个操作的前后顺序呢？首先我们先记住一点， 0 是一个非常关键的”分水岭“ ，大于 0 的时候不会发生阻塞，小于 0 则会发生阻塞。

我们要确保”前操作“在前面，”后操作“在后面，实际上只要做到三件事：V 在”前操作“后面、P 在”后操作“前面、V 在 P 前面。第一个和第二个条件都是可以通过实际书写代码来做到的，而 要达到第三个条件 —— V 在 P 前面，就有必要让信号量初始值为 0 ，因为一旦初始值为 0，则每当 P 想要”违规“抢先于 V 执行的时候，都会由于首先执行信号量自减的操作而导致当前所在进程进入阻塞队列 ，也就是说：

P 先于 V 执行 ===> P 所在进程会被阻塞 ===> ”后操作“始终无法执行

所以，在这种情况下，就只能转而执行 V 所在的进程了。在这个进程里，由于 V 在”前操作“后面，所以一定是”前操作“执行完了再去执行 V。而执行 V 就会自增信号量，同时唤醒对方进程，对方进程再去顺序执行 P 操作 —— 虽然此时信号量又自减，但是是在加一的基础上自减，所以并不会导致再次阻塞 ，所以 P 执行完后就顺序执行”后操作“。由此，我们确保了两个操作一定是严格按照先后顺序执行的。

来看下面的例子：

// 顺序应该是：code1,code2,code4

P0：                 P1:
code 1               P(S)
code 2               code 4
V(S)                 code 5
code 3               code 6

我们设想比较差的情况 —— P1 拼命想要抢先执行 code 4，看看会发生什么。假设是 P1 首先占用处理机，那么就会执行 P 操作，这个操作使得信号量由 0 变成 -1，进而进入 if 代码块，使得 P1 进程阻塞；这之后，处理机来到 P0，执行 code1，code2，V 操作，使得信号量由 -1 变成 1，同时唤醒 P1 进程；P1 进程使得信号量由 1 变成 0，但是不满足 if 条件，所以不会阻塞自己，而是正常往下执行，来到 code4。以上，整个过程确保了按照 code1，code2，code4 的顺序执行。

2.3 信号量实现进程前驱关系

前面描述的都是两个进程的同步问题，但有时候也可能出现像下图这样多个进程互相依赖、有序运行的情况。其中，code * 语句仍然是前操作或者后操作，P1 进程有 code1 语句，P2 进程有 code2 语句…… 以此类推，这里要求六个进程必须按照箭头所指方向有序运行。

其实这种情况就是把多个同步问题结合起来，对于每一对前驱关系来说，都有属于本关系的信号量，所以我们仍然是可以用信号量机制来实现的。代码大概如下：

P1:          P2:          P3:          P4:        
code1        P(signal1)   P(signal2)   P(signal3)
V(signal1)   code2        code3        code4 
V(signal2)   V(signal3)   V(signal7)   V(signal5)
             V(signal4)
P5:          P6:         
P(signal4)   P(signal5)   
code5        P(signal6) 
V(signal6)   P(signal7)
             code6

可以观察到，除了 P1 进程之外，其它进程首先执行的都是 P 操作，所以一旦这些进程之一首先拿到处理机使用权，都无一例外地会进入阻塞队列。由于情况很多，这里我们试着只分析某一种情况 ——

假设一开始是 P2 占有处理机，那么由于 signal1 初始为 0，导致了 P2 进队列，此后处理机来到 P3，P3 同样进队列……. 以此类推，阻塞队列就会变成：

随后总算来到 P1 进程了，P1 进程作为一切的开始，特殊之处就在于它不是以 P 操作开始的，P1 会首先执行 V(signal1)，这一步把 signal1 加一，同时唤醒 P2 进程，P2 进程进入就绪队列：

再之后，P1 执行 V(signal2)，这一步把 signal2 加一，同时唤醒 P3 进程，P3 进程也进入就绪队列。

P1 执行完之后，就绪队列队头的 P2 进入运行态，执行到 V(signal3) 的时候，signal3 加一，同时唤醒 P4 进程，P4 进程进入就绪队列，

再之后，P2 执行 V(signal4)，这一步把 signal4 加一，同时唤醒 P5 进程，P5 进程也进入就绪队列。

P2 执行完之后，处理机调度就绪队列队头的 P3 开始执行，P3 执行到 V(signal7) 的时候，signal7 加一， 注意这一步没有唤醒任何进程

P3 执行完之后，处理机调度就绪队列队头的 P4 开始执行，P4 执行到 V(signal5) 的时候，signal5 加一，同时唤醒 P6 进程，P6 进程进入就绪队列

P4 执行完之后，处理机调度就绪队列队头的 P5 开始执行，P5 执行到 V(signal6) 的时候，signal6 加一， 注意这一步没有唤醒任何进程（阻塞队列已经没有进程了）

P5 执行完之后，处理机调度就绪队列队头的 P6 开始执行，P6 的 signal6 、signal7 在前面已经得到加一操作，所以此时绝对不会在这里卡住，可以顺利执行，直到结束。

这样基本就把整个流程过了一遍，当然，经过排列组合之后，是有很多情况的，但是分析过程都是大同小异的。

3. 信号量集机制

前面所说的信号量机制都属于多个进程申请同一个资源的情况，如果是多个进程申请多个资源，那么就需要用到 信号量集机制 了。信号量集机制包括 AND 信号量集机制和一般信号量集机制，它的核心是为每一个资源分配一个信号量，在某个进程申请多个资源的时候， 要么全部资源同时都分配给它，要么全部资源一个也不分配给它 。与信号量机制使用的 wait 和 signal 不同，信号量集机制使用的是 Swait 和 Ssignal （S 表示 Simultaneous，同时的），并且在具体实现上的思路也有所不同。

3.1 AND 信号量集机制

AND 信号量集机制的 PV 操作如下：

Swait(S1,S2,...,Sn)
{
    if(S1>=1 && S2>=1 &&...&& Sn>=1)    // 注意这里是先检查后分配
        for (i=1;i<=n;i++) Si--
    else block(Si.L)
}
Ssignal(S1,S2,...,Sn)
{
    for(i=1;i<=n;i++){
        Si++
        wakeup(Si.L)
    }        
}

假设有 P0，P1 两个进程，它们都需要在临界区同时用到两个资源 AB，这两个资源 AB 的信号量分别用 S1 = 1，S2 =2 表示：

PO:               P1:                     
Swait(S1,S2)      Swait(S1,S2)       
临界区             临界区             
Ssignal(S1,S2)    Ssignal(S1,S2)   

一开始处理机来到 P0，if 判断的条件很苛刻，要求必须所有资源都够用才能给 P0 分配所需资源，因为初始信号量分别为 1 和 2 ，所以 P0 同时申请到了资源，来到临界区执行任务；而对于 P1，尽管 B 资源满足 S2 = 1 >= 1，但是 A 资源是不满足条件的， 但凡有一个条件不满足，P1 进程都无法得到任何资源 ，所以此时 P1 进程被送到 A 资源对应的阻塞队列。

之后，P0 完成任务后来到退出区，二话不说先把自己占有的资源都释放了，释放 A 资源的时候顺便查看对应的阻塞队列是否有进程在等待，刚好 P1 在阻塞队列，所以这时候把 P1 唤醒，送它到就绪队列；释放 B 资源的时候也查看对应的阻塞队列是否有进程在等待，这时候是没有的。

P0 执行完之后，P1 再从就绪态进入运行态，完成自己的工作。

3.2 一般信号量集机制

一般信号量集机制的 PV 操作如下：

Swait(S1,t1,d1, S2,t2,d2 ,..., Sn,tn,dn)
{
    if(S1>=t1 && S2>=t2 &&...&& Sn>=tn)   
        for (i=1;i<=n;i++) Si = Si-di
    else block(Si.L)
}
Ssignal(S1,d1, S2,d2,..., Sn,dn)
{
    for(i=1;i<=n;i++){
        Si = Si+di
        wakeup(Si.L)
    }        
}

这里不难发现，一般信号量集机制是相对于 AND 信号量集机制来说，更加普遍和一般的机制 ——

从 P0 进程的角度来说，执行 P 操作的时候，不仅要传多个信号量进去，而且每一个信号量还有配套的 t 和 d，分别表示“最小必须满足值”和“分配数目”，也就是说，每一个资源 Si 的数目都必须大于等于对应的 ti，才能将其中的 di 个分配给某个进程；同理，执行 V 操作的时候，也是要传多对 Si，di 进去，让每一种资源都得到一定的释放，同时唤醒对应阻塞队列中的进程。

从 P1 进程的角度来说，可能由于某个资源被分配给 P0 而导致自己对应的 ti 不符合要求， 但凡有一个条件不满足，P1 进程都无法得到任何资源 ，所以 P1 进入这个对应资源的阻塞队列，直到后面 P0 释放对应资源并尝试唤醒队列中的进程的时候，P1 才会从阻塞态回到就绪态，进入就绪队列。

4. 总结

最后，我们再来回顾一下这篇笔记所讲的内容。在之前，我们已经谈到了很多实现进程互斥的方法，但是这些方法几乎都违背了”让权等待“的原则，于是人们想到通过信号量机制来解决这个问题 —— 其中，真正发挥作用的就是记录型信号量。除了实现进程互斥，信号量机制还能很好地实现进程同步、进程前驱关系，从而近乎完美地解决了异步所带来的问题。之后又补充了信号量集机制，主要用于多个进程请求多个资源的情况，核心是：（为了防止“死锁”）对若干个临界资源的分配采取原子操作方式，要么全部分配到进程，要么一个也不分配。