操作系统
第二章进程的描述与控制

进程同步

# 进程同步

# 基本概念

在多道批处理系统中，多个进程是并发执行的，而并发执行的进程不可避免地需要共享一些系统资源（比如内存、打印机、摄像头等）。然而，有些资源在一个时间段内只允许一个进程使用，诸如各种物理设备、变量、数据、内存缓冲区等，这些称之为临界资源 —— 也就是说，一方面，并发执行的进程需要共享资源；另一方面，临界资源的访问又必须是互斥地进行（不能同时共享），很显然，这会导致资源访问上的矛盾。我们通过进程互斥来解决此类问题。

进程同步：指多个相关进程在执行次序上的协调

进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问

临界资源：一次仅供一个进程使用的资源

临界区：在进程中涉及到临界资源的程序段叫临界区

相关临界区：多个进程的临界区称为相关临界区

# 进程互斥的基本实现逻辑

为了实现临界资源的互斥访问，可以在逻辑上将一个进程对临界资源的访问过程分为四个部分：

do {
    extry section;       // 进入区
    critical section;    // 临界区
    exit section;        // 退出区
    remainder section;   // 剩余区
} while(true)

1
2
3
4
5
6

进入区：A 进程想要访问临界资源，首先会在进入区检查是否可以进入，由于此时没有其它进程占用临界资源，所以检查通过，同时它设置了一个 Flag 标志当前自己正在访问临界资源；
临界区：实际访问临界资源的那段代码
退出区：负责解除之前的 Flag
剩余区：其它处理

对于 B 进程，如果此时它也想要访问这个资源，同样就会在进入区做一个检查，它知道了 A 进程正在访问，所以自己就不能访问了。这样就实现了资源访问的互斥。

# 同步机制应遵循的原则

空闲让进：临界区空闲时，应该让想要进入临界区的进程立刻进来

忙则等待：同一时刻只允许一个进程进入临界区

有限等待：要求访问临界资源的进程，应该保证在有限时间内进入临界区

让权等待：当 A 进程进入临界区而导致 B 进程不能进入自己的临界区时，应该立刻释放处理机，防止进程陷入 “忙等” 状态。

# 信号量和 PV 操作

# 信号量机制

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

# 整型信号量

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

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

1
2
3
4
5
6
7
8
9
10

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

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

1
2
3
4

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

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

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

# 记录型信号量

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

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

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

typedef struct {
    int value
    sturct process *L
} semaphore

1
2
3
4

同时，记录型信号量的 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)
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

这里要注意的第一个地方是， value 是可用的资源数，当它大于 0 的时候自然是存在可用资源（供大于求），当它小于 0 的时候，则说明不仅无可用资源而且有其他进程等着用（供不应求）。
第二个地方是，在进入区 value 一定会减一，表示申请到了资源，或者表示存在着某个进程有想要申请资源的意愿
执行 ++ 或 -- 前， S.value 为正值时代表可利用的物理资源数； S.value 为负值时，其绝对值代表阻塞队列中等待的进程数。

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

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

1
2
3
4

假设计算机中有两台可用的打印机 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 ，代表占用的资源已经全数归还。

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

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

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

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

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。

# 信号量机制实现

# 进程互斥

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

semaphore mutex = 1;
P0(){
    P(mutex) //使用临界资源前需要加锁
    critical section //临界区代码段
    V(mutex) //使用临界资源前需要解锁
}
P1(){
    P(mutex)
    critical section //临界区代码段
    V(mutex)
}

1
2
3
4
5
6
7
8
9
10
11

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

PV 操作要成对出现，但不一定要在同一个进程中。不同的临界资源设置不同的互斥信号量。记录型信号量有时需要自己定义。

# 进程同步

多个进程（如 P1、P2）一起完成某项任务的时候，如何确保它们按照一定的先后顺序（先 P1 后 P2）有秩序地执行呢？信号量机制也可以很好地实现进程同步。它有三个关键步骤：

设置同步信号量初始值为 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

1
2
3
4
5
6

我们设想比较差的情况 —— P1 想要抢先执行 code 4，看看会发生什么。假设是 P1 首先占用处理机，那么就会执行 P 操作，这个操作使得信号量由 0 变成 -1，进而进入 if 代码块，使得 P1 进程阻塞；这之后，处理机来到 P0，执行 code1，code2，V 操作，使得信号量由 -1 变成 0，同时唤醒 P1 进程；P1 进程被唤醒后从 P 操作之后的断点继续执行（P1 被唤醒后不会重新再执行一遍 P 操作，否则会再次进入阻塞。与七态中进程所需资源得到满足后会从阻塞队列转入就绪队列相同，P1 会接着之前停下的地方继续），来到 code4。以上，整个过程确保了按照 code1，code2，code4 的顺序执行。

# 前驱关系

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

其实这种情况就是把多个同步问题结合起来，我们仍然可以用信号量机制来实现：

每一个前驱关系都是一个同步问题，要保证一前一后的操作
为每一个前驱关系各设置一个同步信号量
在 “前操作” 之后对相应的同步信号量执行 V 操作
在 “后操作” 之前对相应的同步信号量执行 P 操作

代码大概如下：

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

1
2
3
4
5
6
7
8
9
10

可以观察到，除了 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 在前面已经得到加一操作，所以此时绝对不会在这里卡住，可以顺利执行，直到结束。

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

# 信号量和 PV 操作解决进程同步问题

# 生产者 - 消费者

生产者 - 消费者问题是系统中并发进程内在关系的一种抽象，是典型的进程同步问题。生产者进程 P1 可以是计算进程、发送进程；而消费者进程 P2 可以是打印进程、接收进程等等。

有界缓冲：

一个生产者一次放入缓冲区一个产品，且无限次循环

一个消费者一次取出缓冲区一个产品，且无限次循环

两个进程独立

要解决的问题：

缓冲池满生产者不能放产品

缓冲池空消费者不能取产品

只能一个生产者或者消费者对缓冲区进行操作

进程个数：2

关系分析：

互斥关系 P1、P2 互斥访问缓冲区
同步关系 P1 生产后 P2 才能消费

信号量设置：

互斥信号量 mutex = 1 ，实现对缓冲区这个资源的互斥访问
同步信号量 empty = n ，表示空闲缓冲区的数量
同步信号量 full = 0 ，表示非空闲缓冲区的数量，也即产品数量

产品： P1 V P2 P （V 增加，P 锁定，生产者放入产品，消费者取出产品）

空间： P1 P P2 V

先考虑对互斥关系的实现。这里的临界资源是缓冲区，生产者进程把产品放进去，消费者进程从里面取走产品，这两者不能同时进行，所以这里是互斥的关系。P1、P2 都各有一对 PV 操作，用以实现对缓冲区资源的访问。另外，生产者在进行 PV 操作之前，必定要先生产产品；而消费者在进行 PV 操作之后，必定要使用产品。这时候，初步的伪代码是这样的：

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                              P(mutex)
        P(mutex)                             从缓冲区中取走产品 
		把产品放入缓冲区                       V(mutex)
        V(mutex)                             使用产品 
    }                                   }
}                                   }

1
2
3
4
5
6
7
8

接着考虑第一个同步关系，关注空缓冲区。先释放缓冲区，后使用缓冲区，且缓冲区满不再放入产品，所以这里 “前操作” 是消费者释放缓冲区，“后操作” 是生产者占用缓冲区，根据 “前 V 后 P”，我们需要在 “前操作” 之后针对 empty 这个信号量进行一次 V 操作，需要在 “后操作” 之前针对 empty 进行一次 P 操作。生产者执行 P 操作检查是否还有空缓冲区时，若缓冲区已满，将进入阻塞。所以，这时候代码变成：

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                             P(mutex)
        P(empty)                            从缓冲区中取走产品 
		P(mutex)                            V(mutex)
        把产品放入缓冲区                      V(empty)  
        V(mutex)                            使用产品 
    }                                   }     
}                                   }

1
2
3
4
5
6
7
8
9

再考虑第二个同步关系，关注产品。先生产产品并将其放入缓冲区，后从缓冲区取出产品并使用。这里划分出前后两个操作，所以再安排一对 PV 操作：

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(full)
        P(empty)                           P(mutex)
		P(mutex)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

1
2
3
4
5
6
7
8
9
10

这就是最后的代码了。现在我们试着跑一下流程：初始的时候 empty = n，表示所有缓冲区都是空闲的，同时 full = 0，表示一个产品都没生产出来。假如处理机首先来到 consumer 进程，那么就会通过 P(full) 检查是否有产品，这里当然是没有，所以它只能进行等待；处理机来到 producer，首先通过 P(empty) 检查是否有空闲缓冲区，这里当然有，于是它开始把生产的产品放入缓冲区，随后记录产品的数量，这个过程可以反复进行，直到所有缓冲区都被占用了，此时 producer 就会进入等待状态，等待 consumer 进程取出产品、释放缓冲区；当然还有可能的情况是，producer 尚未占用完所有缓冲区，进程就切换到 consumer 了，那么这时候 consumer 因为检查到有产品，所以也会取出产品、释放缓冲区。

P 操作不可以随意对调位置，V 操作可以。

这里要注意可能会引起 “死锁” 现象的一种写法。如下所示：

producer(){                         consumer(){
    while(1){                           while(1){
        生产产品                            P(mutex)
        P(mutex)                           P(full)
		P(empty)                           从缓冲区中取走产品 
        把产品放入缓冲区                     V(mutex) 
        V(mutex)                           V(empty)  
        V(full)                            使用产品 
    }                                   }     
}                                   }

1
2
3
4
5
6
7
8
9
10

这个写法的问题在于，还没有先检查缓冲区是否没满或者是否非空，就强行进行互斥的 “上锁”。假如还是按照前面的流程，一开始处理机在 consumer 这里，那么 consumer 实际上在没有检查缓冲区是否非空的情况下就直接 “上锁” 了，这导致它在 P(full) 这一步的时候被卡住，只能等待，而在之后切换到 producer 的时候，正常情况下他应该生产可供对方消费的产品，但是由于对方已经上了锁，所以 producer 在 P(mutex) 这一步也被卡住了，只能进行等待。这也就是说，producer 等待 consumer 释放临界区，而 consumer 等待 producer 使用缓冲区，双方陷入循环等待，造成了 “死锁”。

另一种情况，我们也可以设想一开始处理机是在 producer 这里，依然会导致 “死锁”。按照这种情况正常用完全部缓冲区之后，如果处理机还是在 producer 这里，那么 producer 在检查缓冲区是否已满之前也会将自己提前上锁，在 P(empty) 这一步陷入等待，之后即使进程切换到 consumer 这里，它也会因为对方提前上锁，而导致自己在 P(mutex) 这一步陷入等待。也就是说，这不过是前面那种” 死锁 “现象的翻版。

总之，关键就在于不管是消费者进程，还是生产者进程，都不能先上锁再检查，否则就有可能发生死锁。

# 苹果橘子问题

盘子缓冲区

2 水果 2 产品

爸爸妈妈 2 生产者，P1 P2

儿子女儿 2 消费者，C1 C2

进程个数：4

关系分析：

互斥关系 P1、P2、C1、C2 互斥访问缓冲区
同步关系 P1 生产后 C1 才能消费，P2 生产后 C2 才能消费

信号量设置：

互斥信号量 mutex = 1 ，实现对缓冲区这个资源的互斥访问
同步信号量 apple = 0 ，表示苹果的数量
同步信号量 orange = 0 ，表示橘子的数量

产品： P1 P2 V C1 C2 P （V 增加，P 锁定，生产者放入产品，消费者取出产品）

空间： P1 P2 P C1 C2 V

P1(){
  while(1){
      P(mutex)
      把苹果放入盘子
      V(apple)
  }
}
P2(){
  while(1){
      P(mutex)
      把橘子放入盘子
      V(orange)
  }
}
C1(){
   while(1){
       P(apple)
       从盘子中取走苹果
       V(mutex)
 }
C2(){
  while(1){
       P(orange)
       从盘子中取走橘子
       V(mutex)
 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 银行问题

IMG_20221024_140725

顾客的 V (full) 与 P (service) 应调换位置，并去除 “获取服务”

service 默认值应为 1

# 五个哲学家进餐问题

一张圆桌，五个哲学家，五支筷子（每两个哲学家中间会有一支筷子），哲学家要么思考，要么吃饭，吃饭前会拿起左右两边的筷子，吃饭后会放下筷子。如果筷子被其它哲学家拿走，则自己需要等待。我们的目的很简单：保证所有哲学家都有机会吃上饭，不能让一个或者多个哲学家始终无法吃饭。

如果哲学家 0 号拿起左右筷子后，进程切换到哲学家 1 号，那么 1 号是会被阻塞的，所以这样相邻的哲学家中有一个可以吃饭。但是，如果 0 号拿起左筷子后进程切换到 1 号，1 号也拿起自己的左筷子，以此类推，所有的哲学家都只有左筷子，这导致了所有的哲学家都被阻塞，没有任何哲学家能够吃饭，也没有人可以释放筷子，使这些哲学家都陷入无限的等待中，造成 “死锁” 的发生。

解决这个问题有三个方法：

# 实现原子操作

很容易想到，拿起左筷子和拿起右筷子并不是一个原子操作。准备一个互斥信号量 mutex = 1 ，并把拿筷子的操作封装在一个 PV 操作里。代码如下：

Pi(){
    while(1){
        P(mutex)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        V(mutex)
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
    }
}

1
2
3
4
5
6
7
8
9
10
11

在 0 号哲学家拿起左筷子之后，即使发生进程切换，1 号进程也会被卡在 mutex 的 P 操作，被送往阻塞队列，其它进程也同理。所以最后再次来到 0 号进程时便可以顺利拿起右筷子。这种做法保证了有一个哲学家是可以吃饭的。

这里涉及到了一个进程需要一次性两个资源才能完成任务的问题，也可以使用 AND 信号量集机制。AND 信号量集机制的 P 操作是一个相对苛刻的操作，要求一个进程要么拿到全部资源，要么一个资源也拿不到。一开始筷子数量足够，所以 0 号在一开始就可以一次性拿到左右筷子。同理，在释放筷子的时候，也是一次性释放两支筷子。代码如下：
Pi(){
    while(1){
        Swait(chopstick[(i+1)%5],chopstick[i]);
        eat()
        Ssignal(chopstick[(i+1)%5],chopstick[i]);
    }
}
1
2
3
4
5
6
7
1
2
3
4
5
6
7

# 只有四个人参与这个过程

之前的情况是五个哲学家，五支筷子，所以容易出现谁也无法吃饭的情况，但是如果规定整个过程最多只有四个哲学家参与，即使这四个哲学家每个人都拿走了一支筷子，也还剩下一支筷子可以分配给某个哲学家。

如何限定 “最多四个人可以参与这个过程” 呢？准备一个互斥信号量 count ，但是这个信号量初值不再是 1 ，而是 4，表示最多允许四个哲学家参与过程。当 count 减少到 -1 的时候，就不能再让哲学家进来了。代码如下：

Pi(){
    while(1){
        P(count)
        P(chopstick[i])
        P(chopstick[(i+1)%5])
        eat()
        V(chopstick[i])
        V(chopstick[(i+1)%5])
        V(count)
    }
}

1
2
3
4
5
6
7
8
9
10
11

再来演示前面发生 “死锁” 的过程。假如从 0 号进程开始，在他拿到左筷子之后，进程切换到 1 号进程，由于 count 数量充足，所以它不会阻塞，而是同样拿到了左筷子… 以此类推，到了 4 号哲学家的时候，由于 count = -1 < 0 ，所以它此时无法进来。 4 号哲学家左边的筷子在第一轮谁也没拿到，第二轮轮到 3 号哲学家时，就可以拿到这支筷子了。总会存在至少一个进程可以吃到饭。

# 奇数拿左边，偶数拿右边

还可以考虑对拿筷子的优先顺序进行调整。规定对于奇数哲学家，总是先拿左筷子再拿右筷子；对于偶数哲学家，总是先拿右筷子再拿左筷子。那么 0 号哲学家和 1 号哲学家就会争夺 1 号筷子，而 2 号哲学家和 3 号哲学家就会争夺 3 号筷子。如图所示：

伪代码如下：

Pi(){
    while(1)
	{
		if(i%2 == 0) // 偶数哲学家，先右后左。
		{
			P(chopstick[(i + 1)%5]) ;
			P(chopstick[i]) ;
			eat();
			V(chopstick[(i + 1)%5]) ;
			V(chopstick[i]) ;
		}
		else   //奇数哲学家，先左后右。
		{
			P(chopstick[i]) ;
			P(chopstick[(i + 1)%5]) ;
			eat();
			V(chopstick[i]) ;
			V(chopstick[(i + 1)%5]) ;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

假如从 0 号进程开始，很显然 0 号先拿到 1 号筷子，所以在之后切换进程的时候，1 号进程就会直接被阻塞。接着来到 2 号进程，显然他先拿到 3 号筷子，所以之后轮到 3 号进程的时候，3 号进程直接被阻塞。现在轮到 4 号进程，它优先拿到右边的 0 号筷子，之后进程又切换到其它地方。但是，由于先前 3 号进程已经被阻塞，所以在再次轮到 4 号进程的时候，并没有人和他一起争夺 4 号筷子，换言之，4 号进程可以拿到 4 号筷子，再加上之前优先拿到的 0 号筷子，4 号进程现在就可以吃饭了。

这只是其中一种情况，但无论是哪一种，在一对进程的争抢中必然有一个进程首先被送到阻塞队列，因此这个 “被淘汰的” 进程很难再去影响其它进程，相当于间接提高了其它进程拿到筷子的可能性。就像我们上面的例子一样，一下子 “淘汰了” 1 号和 3 号两个进程，并且这两个进程当时并没有带着筷子进入阻塞队列，所以对于其它进程 2 号、4 号、 0 号来说，再次拿到一支筷子的可能性就大大提高了。所以，我们还是能够达到最初的目的，也就是至少让一个哲学家吃上饭。

# 管程

信号量机制效率低，且通信对用户不透明

# 管程的基本思想

管程 = 共享资源 + 同步操作

进入管程无法直接访问临界资源，而是通过管程的方法来访问临界资源：

上次更新: 2023/01/06, 19:28:46

← 进程的特征进程通信→