计算机与操作系统-06-并发程序设计

本文主要内容来自 SpriCoder的博客，更换了更清晰的图片并对原文的疏漏做了补充和修正。

并发进程程序设计的概念

顺序程序设计

程序是实现算法的操作（指令）序列；

程序顺序执行是指其在处理器上执行是严格有序的，前一个操作被执行完后，才能开始后继操作，被称为程序执行的内部顺序性；

把一个具体问题的求解过程设计成一个程序或者若严格顺序执行的程序序列，这称为程序执行的外部顺序性。

顺序程序设计的特性

1. 程序执行的顺序性：程序指令执行是严格按序的，每个操作必须在下一个操作开始前结束；
2. 计算环境的封闭性：程序运行时如同独占受操作系统保护的资源，资源状态只能由程序本身决定和改变，不受外界因素改变；
3. 计算结果的确定性：程序执行结果与执行速度和执行时段无关；
4. 计算过程的可再现性：程序对相同数据集的执行轨迹是确定的。

进程的并发执行

1. 多道程序设计让多个程序同时进入内存去竞争处理器以获得运行机会
2. OS 允许计算机系统在一个时间段内存在多个正在运行的进程，即允许多个进程并发执行
3. OS 保证按照“顺序程序设计”方法编制的程序在并发执行时不受影响，如同独占计算机
4. 这些按照顺序程序设计思想编制的进程在 OS 中并发执行属于无关的并发进程

并发程序设计的引入例

顺序程序设计

循环地（从输入机读 78 秒再计算 52 秒再向磁带机输出 20 秒）按照顺序程序设计方法，设计成如下一个程序：

处理器利用率：\(\frac{52}{78 + 52 + 20} \approx 34.7\%\)

并发程序设计例子

换一种设计思路，设计 3 个独立运行的程序，让它们同时进入多道程序系统去并发执行：

while(1) { input，send }
while(1) { receive，process，send }
while(1) { receive，output }

1. 处理器利用率 \(=\frac{52 \times n}{78 \times n + 52 + 20}\)
2. 计算一定是在接收结束之后的，\(\lim\limits_{n\rightarrow \infty}\frac{52 \times n}{78 \times n + 52 + 20} \approx 66.7\%\)后，利用率会大大提高。

并发程序设计

1. 程序并发执行是指一组程序的执行在时间上是重叠的，所谓重叠的是指一个程序执行第一条指令是在另一个程序执行完最后一条指令之前开始的。
   1. 宏观上，并发性反应了一个时间段内有几个程序都处于运行但运行尚未结束的状态。
   2. 微观上，任一时刻都只有一个程序在运行。
2. 并发实质是处理器在几个程序之间的多路复用，对有限物力资源强制行使多用户共享，消除计算机部件之间的互等现象，提高资源利用率。
3. 并发使得程序失去了封闭性、顺序性、确定性和可再现性。
4. 并发程序设计指一个程序被设计成可以与其他程序并发执行。

并发程序设计的特性

1. 并行性：多个进程在多道程序系统中并发执行或者在多处理器系统中并行执行，提高了计算效率
2. 共享性：多个进程共享软件资源
3. 交往性：多个进程并发执行时存在制约，增加了程序设计的难度

并发进程的制约关系

无关与交往的并发进程

无关的并发进程：一组并发进程分别在不同的变量集合上运行，一个进程的执行与其他并发进程的进展无关；

交往的并发进程：一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。

与时间有关的错误

对于一组交往的并发进程，执行的相对速度无法相互控制。如果程序设计不当，可能出现各种“与时间有关的”错误：

1. 表现一：结果不唯一，不同的执行序列有不同的结果。
2. 表现二：永远等待

结果错误的例子：机票问题

1. 每两条机器指令之间都存在着一定的时间缝隙，导致时间片轮转可能导致的抢占问题。
2. 时间片轮转调度，如果并发数足够高，那么可能导致一张票被非常多的人抢到。
3. 此时出现把同一张票卖给两个旅客的情况，两个旅客可能各自都买到一张同天同次航班的机票，可是，Aj 的值实际上只减去 1，造成余票数不正确。特别是，当某次航班只有一张余票时，可能把一张票同时售给两位旅客。

永远等待的例子：内存管理问题

由于 borrow 和 return 共享代表主存物理资源的临界变量 X，对并发执行不加限制会导致错误。

例如：

1. 一个进程调用 borrow 申请主存，在执行比较 B 和 X 大小的指令后，发现 B>X，但在执行{进程进入等待主存资源队列}前
2. 另一个进程调用 return 抢先执行，归还所借全部主存资源
3. 这时，由于前一个进程还未成为等待者，return 中的{释放等主存资源进程}相当于空操作，以后当调用 borrow 的应用进程被置成{等主存资源}时，可能己经没有其他进程再来归还主存，从而，申请资源的进程处于永远等待状态

进程的交互：进程互斥与进程同步

因此，交互的并发进程在执行时必须进行制约，才能保证得到合理的结果

进程互斥（竞争）

1. 并发进程之间因相互争夺独占性资源而产生的竞争制约关系
2. 一个进程的执行可能影响到同其竞争资源的其他进程，如果两个进程要访问同一资源，那么，一个进程通过操作系统分配得到该资源，另一个将不得不等待。
3. 进程互斥是解决进程间竞争关系（间接制约关系）的手段。
4. 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源

竞争带来的问题

1. 资源竞争的两个控制问题：
   1. 一个是死锁（Deadlock）问题： 一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁。
   2. 一个是饥饿（Starvation）问题： 一个进程由于其他进程总是优先于它而被无限期拖延，可以使用 FCFS 来解决饥饿问题。
2. 操作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题

竞争关系：死锁

1. 临界资源：互斥使用的资源
2. 死锁： 一组进程因争夺资源陷入永远等待的状态
3. P0 和 P1 两个进程，均需要使用 S 和 Q 两类资源，每类资源数为 1
   1. P0：申请（S）\(\to\) 申请（Q） \(\to\) 释放（S）\(\to\) 释放（Q）
   2. P1：申请（Q）\(\to\) 申请（S） \(\to\) 释放（Q）\(\to\) 释放（S）
   3. 以上两个进程互相持有对方的资源的锁，导致无法继续进行。

进程同步（协作）

1. 并发进程之间为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
2. 某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行
3. 是解决进程间协作关系（直接制约关系）的手段。
4. 进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一个协作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒
5. 同步和异步
   1. 同步：等待/阻塞
   2. 异步：不等/平行
6. 进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调

并发进程之间的关系

“忙式等待”方法解决临界区调度的缺点

1. 临界区管理的简单方法
   1. 关中断
   2. 测试并建立指令
   3. 对换指令
   4. Peterson 算法
2. 存在问题
   1. 对不能进入临界区的进程，采用忙式等待测试法，浪费 CPU 时间
   2. 将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重用户编程负担
3. 通用的解决方法：信号量与 PV 操作

并发进程设计控制

进程的无关性 *

进程的无关性是进程的执行与时间无关的一个充分条件

Bernstein 条件

\[ R(P_i)={a_{i1},a_{i2},..., a_{in}}，程序 P_i 在执行期间引用的变量集\\ W(P_i)={b_{i1},b_{i2},...,b_{im}}，程序 P_i 在执行期间改变的变量集 \]

若两个进程的程序\(P_1\)和\(P_2\)能满足 Bernstein 条件，即满足：\(R(P_1)\cap W(P_2) \cup R(P_2) \cap W(P_1) \cup W(P_1) \cap W(P_2) = \emptyset\)则并发进程的执行与时间无关，保持封闭性和可再现性。

1. \(R(P_1)\cap W(P_2) \cup R(P_2) \cap W(P_1)\)，表明一个程序在两次读操作之间存储单元的数据不会被改变。
2. \(W(P_1) \cap W(P_2)\)：表明程序的写操作结果不会丢失。

Bernstein 条件例子

1. 例如，有如下分属四个进程中的四条语句：

S1: a := x + y
S2: b := z + 1
S3: c := a - b
S4: w := c + 1

1. 于是有：
   1. \(R(S1)=\{x,y\} , R(S2)=\{z\}, R(S3)=\{a,b\}, R(S4)=\{c\}\)
   2. \(W(S1)=\{a\}, W(S2)=\{b\} , W(S3)=\{c\} , W(S4)=\{w\}\)
2. \(S_1\)和\(S_2\)可并发执行，满足 Bernstein 条件
3. 其他语句并发执行可能会产生与时间有关的错误

并发程序设计的优点

1. 单处理器系统：有效利用资源，让处理器和设备、设备和设备同时工作，充分发挥硬件设备的并行工作能力。
2. 多处理器系统：让进城在不同处理器上物理地并行工作，加快计算速度。
3. 简化程序设计：编写并发执行的小程序进度较快，更容易保证正确性。

顺序程序设计与并发程序设计 *

临界区

互斥与临界区

临界资源：互斥共享变量所代表的资源，即一次只能被一个进程使用的资源

1. 举例：火车上的卫生间就是一种互斥使用的共享资源
2. 使用共享变量代表共享资源

临界区（critical section）：并发进程中与互斥共享变量相关的程序段，与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预见。

多个并发进程访问临界资源时，存在竞争制约关系，如果两个进程同时停留在相关的临界区内，就会出现与时间相关的错误。

竞争条件（race condition）

调度原则：

1. 互斥使用，有空让进
2. 忙则要等，有限等待
3. 择一而入，算法可行（避开饥饿）

临界区的描述

确定临界资源：shared <variable>

确定临界区：region <variable> do <statement_list>

两个进程的临界区有相同的临界资源，就是相关的临界区，必须互斥进入。

两个临界区不相关，进入就没有限制。

临界区管理的三个要求（Dijkstra，1965）

1. 一次至多允许一个进程能够进入临界区内执行：在某些特殊情况下可能会突破
2. 如果已有进程在临界区，其他试图进入的进程应等待，一个进程不能无限止地等待进入临界区
3. 一个进程不能无限止地停留在临界区内（进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入）

临界区的使用

临界区的嵌套使用

临界区管理实现的尝试

临界区管理：尝试一

1. 存在的问题： 两个进程可能都进去
2. 进程 P1 测试 inside2 与随后置 inside1 之间（由于时间片轮转等诸多原因），P2 可能发现 inside1 有值 false，于是它将置 inside2 为 true，并且与进程 P1 同时进入临界区，而对于 P2 而言也是同理的

临界区管理：尝试二

1. 优先表示自己在临界区内，存在的问题： 两个进程都进不去
2. 延迟进程 P2 对 inside2 的测试，先置 inside1 为 true，用以封锁 P2，但是有可能每个进程都把自己的标志置成 true，从而出现死循环，这时没有进程能在有限时间内进入临界区，造成永远等待。

解决思路

问题：框内的（测试锁、建立锁）两条指令执行过程不能中断：

解决算法：peterson 算法 *

1. 通用性和效率比较差

// 公共的变量声明部分
bool inside[2];      // 存储是否进入的情况
inside[0] = false;
inside[1] = false;
enum{0, 1} turn;     // 指示器 turn 来指示可以由哪个进程进入

上图中的绿色箭头可以理解为激活和唤醒。下图中展示了一种修改方案：这种修改是不可行的。

1. P0 中执行了 turn=1, 暂时进不去
2. 等 P1 中执行 turn=0, P0 可以进去
3. P0 使用完临界区，退出临界区的时候，将 turn=0（好像是多余的），此时 P1 还是进不去，要等 p0 执行 turn=1，使得 P1 有机会进入临界区
4. 之后，P1 退出临界区的时候，turn=1，P0 暂时进不去，等在 P1 中执行 turn=0，P0 可以再次进入临界区
5. 因此，P0 和 P1 使用临界区的次序变成了完全一比一的交替方式，这只能是临界区互斥使用的一个特例，不能满足临界区互斥使用的完全随机性。

临界区管理实现的硬件方式

关中断 *

1. 实现互斥的最简单方法：进程进入临界区时关中断，进程退出临界区时开中断。
2. 关中断后，时钟中断也会被屏蔽，进程上下文切换完全由中断事件引起。
3. Linux 关中断：cli()，开中断：sti()
4. 关中断适用场合

关中断方法优点

简单、有效，队操作系统自身很有用。

关中断方法的缺点

1. 关中断时间过长影响性能和系统效率
2. 不适用于多处理器系统

测试并建立指令

TS（Test and Set）指令的处理过程：返回条件码

TS(x) {
	if (x == false) {
		x = true;
		return true;
	} else
		return false;
}

// TS 指令实现进程互斥
bool lock = false;
process	Pi {	// i = 1, 2, ..., n
    bool pi;
    repeat pi = TS(lock) until pi; // 循环请求锁
    { 临界区; }
    lock = fakse;  // 解锁
}

对换指令

对换指令是交换两个字的值

swap(a, b) {
    temp = a;
    a = b;
    b = temp;
}
// 对换指令实现进程互斥
bool lock = false;
process Pi {           // i = 1, 2, ..., n
    Boolean pi;
    pi = true;
    repeat swap(lock, pi) until !pi；// 循环请求锁
    { 临界区; }
    lock = false； // 解锁
}

实现临界区管理的硬件设施

TS 和 swap 指令均是忙式等待，效率低。

简单的解决办法是在进出临界区时开关中断，这样临界区执行就不会中断了，执行就有原子性：

1. 关中断
2. 临界区
3. 开中断

操作系统原语就采用这种实现思路。

但是，临界区的指令长度应该短小精悍，这样才能保证系统效率。不建议用户程序使用，滥用是可怕的！

PV 操作与进程互斥

问题的提出

1. TS 或 swap 指令管理临界区，采用忙式轮询，效率低
2. 关开中断管理临界区，不便交给用户程序使用
3. 参考：操作系统访问硬件资源时采用“请求-等待-中断恢复”方式

同步和同步机制 *

1. 著名的生产者-消费者问题是典型的进程同步问题。
2. 为什么 count 的值是不确定的，因为我们并没有对 count 进行封锁（同步）
3. 课本 134 页

信号量的构思

信号量：一种可动态定义的软件资源。信号量是一种变量类型，有两个分量，一个是信号量的值，另一个是信号量队列指针。

核心数据结构：等待进程队列

信号量声明：资源报到，建立队列

申请资源的原语：若申请不得，调用进程入队等待

归还资源的原语：若队列中有等待进程，需释放

信号量撤销：资源注销，撤销队列

信号量分类：

1. 按照用途：
   1. 公用信号量：联系一组并发进程，相关进程均可在此信号量上执行 PV 操作，初值为 1，实现进程互斥。
   2. 私有信号量：联系一组并发进程，仅允许此信号量所拥有的进程执行 P 操作，其他相关进程可以在其上执行 V 操作，初值为 0 或正整数，多用于进程同步。
2. 按照取值：
   1. 二值信号量：值为 0 或 1，用于解决互斥问题。
   2. 一般信号量（计数信号量），允许大于 1 的整数值，主要解决进程同步。

记录型信号量的定义

设 s 为一个记录型数据结构，一个分量为整型量 value，另一个为信号量队列 queue，P 和 V 操作原语定义：

1. P(s)：将信号量 s 减去 1，若结果小于 0，则调用 P(s) 的进程被置成等待信号量 s 的状态。正数表示资源可复用次数，负数绝对值表示队列中进程个数，0 值表示无资源且无进程等待。
2. V(s)：将信号量 s 加 1，若结果不大于 0，则释放（唤醒）一个等待信号量 s 的进程，使其转换为就绪态

原语：CPU 处于内核态，在关中断环境下执行的一段指令序列。

原子性：不被中断，确保安全且完整执行这段指令序列。

强调：对于信号量，只允许使用 P 和 V 原语操作访问信号量，不能直接对信号量的整型值做读写操作，也不能直接对信号量的队列做任何其他操作。

PV 原语操作含义及其伪代码

// 基本数据结构定义
typedef struct semaphore {
   int value;           /* 信号量值，正值表示资源可复用次数，0 值表示无资源且无进程等待，负数的绝对 */
   struct pcb* list;    /* 信号量队列指针，等待队列 */
};

// P 操作原语
void P(semahore s) {
   s.value--;           /* 信号量值减 1 */
   if(s.value < 0)
      sleep(s.list);
   /* 若信号量值小于 0，执行 P 操作的进程调用 sleep(s.list) 阻塞自己，被置成等待信号量 s 状态并移入 s 信号量队列，转向进程调度程序 */
}

// V 操作原语
void V ( semaphore s) {
   s.value++;           /* 信号量值加 1 */
   if(s.value <=0)
      wakeup(s.list) ;
   /* 若信号量值小于等于 0，则调用 wakeup(s. list) 从信号量 s 队列中释放一个等待信号量 s 的进程并转换成就绪态，进程则继续执行 */
}

// PV 操作解决进程互斥问题框架
semaphore s;
s = 1;
cobegin
   process Pi {
      // code here
      P(s);
      临界区;
      V(s);
      // code here
   }
coend;

补充：二值信号量数据结构定义 *

设 s 为一个记录型数据结构，一个分量为整型量 value，仅能取值 0 或 1，另一个为信号量队列 queue，P 和 V 操作原语定义：

typedef struct binary_semaphore {
	int value;		   // 取值为 0 或 1
	struct pcb* list;  // 等待队列
};

void BP(binary_semaphore s) {
	if (s.value == 1) {
		s.value = 0;
	} else {
		sleep(s.list);
	}
}

void BV(binary_sempahore s) {
	if (s.list is empty()) {
		s.value = 1;
	} else {
		wakeup(s.list);
	}
}

信号量与 PV 操作管理临界资源的的举例（火车上的卫生间） *

信号量与进程状态转化模型及其队列模型

信号量与进程状态转换模型

信号量与进程状态转换模型（队列模型）

信号量与 PV 操作的推论

1. 推论 1：若信号量 s 为正值，则该值等于在封锁进程之前对信号量 s 可施行的 P 操作次数、亦等于s 所代表的实际还可以使用的物理资源数
2. 推论 2：若信号量 s 为负值，则其绝对值等于登记排列在该信号量 s 队列之中等待的进程个数、亦即恰好等于对信号量 s 实施 P 操作而被封锁起来并进入信号量 s 队列的进程数
3. 推论 3：通常，P 操作意味着请求一个资源，V 操作意味着释放一个资源；在一定条件下，P 操作代表阻塞进程操作，而 V 操作代表唤醒被阻塞进程的操作

信号量的应用

信号量程序设计的一般结构

semaphore s = 1;
cobegin
Process Pi /* i=1,...,n */
{
	// code here
	P(s);  // 申请进入临界区
	/* critical region 临界区 */
	V(s);  // 申请退出临界区
		   // code here
};
coend

1. 说明： 在表达纯粹互斥关系时信号量初值为 1，且同一个信号量的 P 操作和 V 操作处于同一个进程之中。
2. 但是这种情形不适用于同步关系。
3. 假设有 n 个进程，则 s 的取值范围为 [1-n, 1]

信号量与 PV 操作控制并发进程之间的临界资源

求解互斥问题

飞机票问题

int A[m];
semaphore mutex = 1;
cobegin
process Pi {
	int Xi;
	while (true) {
		// 按旅客订票要求找到 A[j];
		P(mutex);
		Xi = A[j];
		if (Xi >= 1) {
			// 如果售票成功，在 if 内释放信号量
			Xi--;
			A[j] = Xi;
			V(mutex);
			// 输出一张票;
		}
		else {
			// 如果票不足，则跳出后释放信号量
			V(mutex);
			// 输出“票已售完”;
		}
	}
}
coend

1. P 操作和 V 操作在执行路径上一一匹配。
2. 只有相同航班的票数才是相关的临界资源，所以用一个信号量处理全部机票会影响进程并发度。
3. 下面的例子是将不同航班的信号量分开：

int A[m];
semaphore s[m];
s[j] = 1;
cobegin
process Pi {
	int Xi;
	while (true) {
		// 按旅客定票要求找到 A[j];
		P(s[j]);
		Xi = A[j];
		if (Xi >= 1) {
			Xi--;
			A[j] = Xi;
			V(s[j]);
			// 输出一张票;
		} else {
			V(s[j]);
			// 输出“票已售完”;
		}
	}
}
coend

哲学家就餐问题

问题描述：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。

Dijkstra 最早设计了哲学家就餐问题，哲学家顺时针编号。

// 存在死锁的哲学家就餐问题
semaphore fork[5];
for (int i = 0; i < 5; i++)
	fork[i] = 1;

cobegin
process	philosopher_i() {  // i= 0,1,2,3,4
	while (true) {
		think();			   // 思考
		P(fork[i]);			   // 先取右手的叉子
		P(fork[(i + 1) % 5]);  // 再取左手的叉子
		eat();				   // 吃饭
		V(fork[i]);			   // 放下左手的叉子
		V(fork[(i + 1) % 5]);  // 放下右手的叉子
	}
}
coend

1. 上面的代码存在死锁的问题：特殊的执行轨迹比如每一个哲学家都拿到了一侧的叉子
2. 上述解法可能出现永远等待，有若干种办法可避免死锁
   1. 至多允许四个哲学家同时取叉子（C. A. R. Hoare 方案）
   2. 奇数号先取左手边的叉子，偶数号先取右手边的叉子

至多允许四位哲学家同时取叉子

// 设置侍者，添加房间信号量来控制同时取叉子的哲学家个数。
semaphore fork[5];
for (int i = 0; i < 5; i++)
	fork[i] = 1;
semaphore room = 4;	 // 增加一个侍者，设想有两个房间 1 号房间是会议室，2 号房间是餐厅
cobegin
process	philosopher_i() { /*i=0,1,2,3, 4 */
	while (true) {
		think();
		P(room);  // 控制最多允许 4 位哲学家进入 2 号房间餐厅取叉子
		P(fork[i]);
		P(fork[(i + 1) % 5]);
		eat();
		V(fork[(i + 1) % 5]);
		V(fork[i]);
		V(room);
	}
}
coend

限制奇数哲学家优先取左手，偶数哲学家优先取右手

// 限制奇数哲学家优先取左手，偶数哲学家优先取右手
process philosopher(int i) {
	if (i % 2 == 0) {
		P(fork[i]);				 // 偶数哲学家先右手
		P(fork[(i + 1) mod 5]);	 // 后左手
		eat();
		V(fork[i]);
		V(fork[(i + 1) mod 5]);
	} else {
		P(fork[(i + 1) mod 5]);	 // 奇数哲学家，先左手
		P(fork[i]);				 // 后右手
		eat();
		V(fork[(i + 1) mod 5]);
		V(fork[i]);
	}
}

求解同步问题

1. 进程同步：并发进程为完成共同任务基于某个条件来协调执行先后关系而产生的协作制约关系
2. 一个进程的执行等待来自于其他进程的消息
3. 解决的基本思路：
   1. 定义一个信号量：其数值代表可用消息数
   2. 等待消息进程：执行 P，无消息则等待
   3. 发出消息进程：执行 V，有等待进程则释放

生产者与消费者

问题描述：有 \(n\) 个生产者和 \(m\) 个消费者，连接在一个有 \(k\) 个单位缓冲区的有界缓冲区上。其中，生产者进程 \(Producer_i\) 和消费者进程 \(Consumer_j\) 都是并发进程。

1. 只要缓冲区未满，生产者 \(Producer_i\) 生产的产品就可投入缓冲区
2. 只要缓冲区不空，消费者进程 \(Consumer_j\) 就可从缓冲区取走并消耗产品可能情形：
   1. \(n=1, m=1, k=1\)
   2. \(n=1, m=1, k>1\)
   3. \(n>1, m>1, k>1\)

一个生产者、一个消费者、一个缓冲单元

生产者和消费者共享缓冲区：

1. 缓冲区有空位时，生产者可放入产品，否则等待
2. 缓冲区有产品时，消费者可取出产品，否则等待

解决思路：

1. 同步关系 1：消费者一开始在等待产品到来，考虑设置一个信号量（等待产品）；一开始无产品，初值为 0
2. 同步关系 2：消费者则在等待缓冲区中有空位，也可设置一个信号量（等待缓冲区）；一开始缓冲区有空位，初值为 1

核心是缓冲区只允许放一个产品

int B;			/* 共享缓冲区 */
semaphore sput; /* 可以使用的空缓冲区数 */
semaphore sget; /* 缓冲区可以使用的产品数 */
sput = 1;		/* 缓冲区内允许放入一件产品 */
sget = 0;		/* 缓冲区内没有产品 */

process producer() { while (true) { product = produce(); P(sput); B = product; V(sget); // 允许 get } }	process consumer() { while (true) { P(sget); product = B; V(sput); // 允许 put consume(product); } }

一个生产者、一个消费者、多个缓冲单元

P 操作的次序是重要的，可能导致死锁。

int B[k];		/* 共享缓冲区 */
semaphore sput; /* 可以使用的空缓冲区数 */
semaphore sget; /* 缓冲区可以使用的产品数 */
sput = k;		/* 缓冲区内允许放入一件产品 */
sget = 0;		/* 缓冲区内没有产品 */
int putptr = 0, getptr = 0;

多个生产者、多个消费者、多个缓冲单元

如果没有 \(S_1\)、\(S_2\) 的话，在多个生产者和消费者时，对于生产者和消费者序列本身需要用 \(S_1\)、\(S_2\) 控制。

该例题中同时使用了互斥信号量和同步信号量，注意区分二者的功能。

int B[k];		/* 共享缓冲区 */
semaphore sput; /* 可以使用的空缓冲区数 */
semaphore sget; /* 缓冲区可以使用的产品数 */
sput = k;		/* 缓冲区内允许放入 k 件产品 */
sget = 0;		/* 缓冲区内没有产品 */
int putptr = 0, getptr = 0;
semaphore s1 = 1, s2 = 1;              /* 互斥信号量 putptr, getptr */

苹果-桔子问题

int plate;
semaphore sp;  /* 盘子里可以放几个水果 */
semaphore sg1; /* sg1 = 1，当且仅当盘子里有桔子，即允许取走桔子 */
semaphore sg2; /* sg2 = 1，当且仅当盘子里有苹果，即允许取走苹果 */
sp = 1;		   /* 盘子里允许放入一个水果*/
sg1 = 0;	   /* 不允许取走桔子 */
sg2 = 0;	   /* 不允许取走苹果 */

小结

1965 年 Dijkstra 发明的同步控制的编程方法：

并发程序设计习题讲解

信号量-前驱关系

semaphore s1 = 0; /*表示进程 P1 是否已经执行完成*/
semaphore s2 = 0; /*表示进程 P2 是否已经执行完成*/
semaphore s3 = 0; /*表示进程 P3 是否已经执行完成*/
semaphore s4 = 0; /*表示进程 P4 是否已经执行完成*/
semaphore s5 = 0; /*表示进程 P5 是否已经执行完成*/
main() {
	cobegin
	P1();
	P2();
	P3();
	P4();
	P5();
	p6();
	coend
}

读者/写者问题

读者与写者问题（reader-writer problem）（Courtois, 1971）也是一个经典的并发程序设计问题。有两组并发进程：读者和写者，共享一个文件 F，要求：

1. 允许多个读者可同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任意写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的写者和读者全部退出
5. 使用 PV 操作求解该问题

读者优先

1. rmutex 控制对 read_count 的互斥访问；
2. 读者需要对互斥信号量 rmutex 进行排队；
3. 只有第一个读者需要对 wmutex 排队，后来的读者不需要对 wmutex 排队，可以插队到写者前面；
4. 为了保证读时不被打断，读时用 wmutex 信号量阻塞写者；当前所有读者读完后，写者才开始写。

semaphore rmutex = 1; // 控制对 read_count 的互斥访问
semaphore wmutex = 1; // 控制对文件内容的互斥写
int read_count = 0;

process reader_i() {
	while (true) {
		P(rmutex);	// rmutex 用于互斥访问 read_cout
		if (read_count == 0)
			P(wmutex);	// 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
		++read_count;
		V(rmutex);

		read();

		P(rmutex);
		if (--read_count == 0)
			V(wmutex);	// 如果当前结束的是最后一个读者，允许开始写
		V(rmutex);
	}
}

process writer_i() {
	while (true) {
		P(wmutex);	// wmutex 用于互斥访问
		write();
		V(wmutex);
	}
}

该代码并没有将读者的优先级提高到理论最高优先级。笔者在另一篇文章 再论“读者优先” 设计了新的算法，在不抢占资源的情况下将读者的优先级提高到了理论最高优先级。

写者优先

1. 后来的写者可以插队到先来的、还未开始读的读者前面；
2. 互斥变量 z 保证了每次最多只有一个读者在互斥变量 rmutex 排队；
3. “第一个”写者到来时，写者可以立刻对 rmutex 排队，且此时最多只有一个读者在 rmutex 排队；
4. “后来的”写者到来时，不用对 rmutex 排队，直接等前面的写者写完后继续写；
5. “最后一个”写者离开时，开放 rmutex 使得读者可以开始读；
6. 写者使用 rmutex 阻塞读者。

读写公平

1. 只比读者优先增加了一个互斥信号量 S；
2. 所有读者和写者一起对互斥信号量 S 排队，这样后来的读者无法插队到先来的写者前面；
3. 其他性质与读者优先相同。

semaphore rmutex = 1; // 控制对 read_count 的互斥访问
semaphore wmutex = 1; // 控制对文件内容的互斥写
semaphore S = 1; // 控制读写公平的信号量
int read_count = 0;

process reader_i() {
	while (true) {
		P(S);
		P(rmutex);	// rmutex 用于互斥访问 read_count
		if (read_count == 0)
			P(wmutex);	// 如果当前是第一个读者，阻塞写者，以保证读到的数据不被更改
		++read_count;
		V(rmutex);
		V(S);

		read();

		P(rmutex);
		if (--read_count == 0)
			P(wmutex);	// 如果当前没有读者，允许开始写
		V(rmutex);
	}
}

process writer_i() {
	while (true) {
		P(S);
		P(wmutex);	// wmutex 用于互斥访问
		write();
		V(wmutex);
		V(S);
	}
}

睡眠的理发师问题

1. 理发店理有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子
2. 如果没有顾客，理发师便在理发椅上睡觉
3. 一个顾客到来时，它必须叫醒理发师
4. 如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开
5. 使用 PV 操作求解该问题

int waiting = 0;  // 等候理发顾客坐的椅子数
int CHAIRS = N;	  // 为顾客准备的椅子数
semaphore customers, barbers, mutex;
customers = 0;	// customers = 1，当且仅当有顾客可以理发
barbers = 0;	// barber = 1， 当且仅当理发师可以理发
mutex = 1;		// mutex 用于控制对 waiting 的互斥访问

农夫猎人问题

有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农夫向笼中放入羊；动物园等待取笼中的老虎，饭店等待取笼中的羊。请用 P、V 操作原语写出同步执行的程序。

和苹果-桔子问题没有本质区别。

semaphore Scage = 1;
semaphore Stiger = 0;
semaphore Ssheep = 0;

银行业务问题

某大型银行办理人民币储蓄业务，由 n 个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号。请用信号量和 P，V 操作正确编写储蓄员进程和顾客进程的程序。

类似苹果-桔子。

semaphore customer_count, server_count, mutex;
customer_count = 0;
server_count = n;
mutex = 1;

缓冲区管理

有 n 个进程将字符逐个读入到一个容量为 80 的缓冲区中（n>1），当缓冲区满后，由输出进程 Q 负责一次性取走这 80 个字符。这种过程循环往复，请用信号量和 P、V 操作写出 n 个读入进程（P1， P2，…，Pn）和输出进程 Q 能正确工作的动作序列。

生产者消费者问题。

semaphore mutex = 1, empty = 80, full0;
int count = 0, in = 0;
char buffer[80];

一次性 V 80 次。

售票问题

汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好门应通知司机开车，然后售票员进行售票。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员，汽车当前正在始发站停车上客，试用信号量与 P、V 操作写出他们的同步算法。

吸烟者问题

一个经典同步问题：吸烟者问题（patil，1971）。

三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者。试用信号量和 P、V 操作求解该问题。

该代码是在吸烟者完成取物品后、完成吸烟前唤醒供应者，与题意不符，但不影响算法的正确性。

独木桥问题

独木桥问题 1

东西向汽车过独木桥，为了保证安全，只要桥上无车，则允许一方的汽车过桥，待一方的车全部过完后，另一方的车才允许过桥。请用信号量和 PV 操作写出过独木桥问题的同步算法。

semaphore wait = 1, mutex1 = 1, mutex2 = 1;
int count1 = 0, count2 = 0;

独木桥问题 2

在独木桥问题 1 中，限制桥面上最多可以有 k 辆汽车通过。试用信号量和 P，V 操作写出过独木桥问题的同步算法。

semaphore wait = 1, mutex1 = 1, mutex2 = 1, bridge = k;
int count1 = 0, count2 = 0;

独木桥问题 3

在独木桥问题 1 中，以 3 辆汽车为一组，要求保证东方和西方以组为单位交替通过汽车。试用信号量和 P，V 操作写出汽车过独木桥问题的同步算法。

semaphore wait = 1, mutex1 = 1, mutex2 = 1;
int counter1 = 0, counter2 = 0, counteru1 = 0, countd1 = 0, counteru2 = 0, counterd2 = 0;
semaphore S1 = 3, S2 = 0;

独木桥问题 4

在独木桥问题 1 中，要求各方向的汽车串行过桥，但当另一方提出过桥时，应能阻止对方未上桥的后继车辆，待桥面上的汽车过完桥后，另一方的汽车开始过桥。试用信号量和 P，V 操作写出过独木桥问题的同步算法。

semaphore stop = 1, wait = 1, mutex1 = 1, mutex2 = 1;
int count1 = 0, count2 = 0;

管程

管程的提出

使用信号量和 PV 操作实现进程同步与互斥时，对共享资源的管理分散于各个进程中。管程希望能够集中和封装对同一个共享资源的所有访问。

管程是管理进程的进程，管程是一种软件模块和机制。

管程和条件变量

1. 管程试图抽象相关并发进程对共享变量访问，以提供一个友善的并发程序设计开发环境。
2. 管程是由若干公共（共享）变量及其说明和所有访问这些变量的过程所组成
   1. 管程的局部变量只能由该管程的过程读取
   2. 把分散在各进程中的临界区集中起来进行管理
3. 防止进程有意或无意的违法同步操作，进程只能互斥地调用管程中的过程。
4. 便于用高级语言来书写程序

管程定义和属性

管程的定义：管程是由局部于自己的若干公共（共享）变量及其说明和所有访问这些公共变量的过程所组成的软件模块

管程的属性：

1. 共享性：管程中的移出过程可被所有调用管程的过程的进程所共享
2. 安全性：管程的局部变量只能由此管程内部分访问，不允许进程或其他管程直接访问。
3. 互斥性：任一时刻，共享资源的进程可以访问管程中的管理此资源的过程，但最多只有一个调用者能够真正进入管程，其他调用者必须等待直到管程可用。

管程的形式

type <管程名>= monitor {
	<局部变量说明>;
	<条件变量说明>;
	<初始化语句>;
	define<管程内定义的，管程外可调用的过程或函数名列表>;
	use<管程外定义的，管程内将调用的过程或函数名列表>;

	<过程名/函数名>(<形式参数表>) {
		<过程/函数体>;
	}

	<过程名/函数名>(<形式参数表>) {
		<过程/函数体>;
	}
}

管程的结构

1. wait() 操作请求资源
2. signal() 操作唤醒条件变量

管程的条件变量

1. 当资源不足导致进程阻塞时，同时开放管程，让挡在管程外的一个进程进入管程。
2. 条件变量：是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它，用于阻塞进程的信号量。
   1. wait()：当一个管程过程发现无法继续时（如发现没有可用资源时），它在某些条件变量上执行 wait()，这个动作引起调用进程阻塞，直到另一个进程在该条件变量上执行 signal()
   2. signal()：
      1. 如果存在其他进程由于对条件变量执行 wait() 而被阻塞，便释放之
      2. 如果没有进程在等待，那么信号不被保存，并不是立即退出管程等待队列，而是进入 next 信号量，以保证多个进程都可以正常退出。
   3. 条件变量仅仅维护阻塞队列的作用，如果没有等待时发生 signal() 操作，相当于空操作。
3. 使用 signal() 释放等待进程时，可能出现两个进程同时停留在管程内。解决方法：
   1. 执行 signal() 的进程等待，直到被释放进程退出管程或等待另一个条件
   2. 被释放进程等待，直到执行 signal() 的进程退出管程或等待另一个条件
4. 霍尔（Hoare, 1974）采用第一种办法
5. 汉森（Hansen）选择两者的折衷，规定管程中的过程所执行的signal() 操作是过程体的最后一个操作

管程和进程对比

1. 管程定义公用数据结构，进程定义私有数据结构
2. 管程将共享变量上的同步操作集中统一管理，临界区分散在每个进程中。
3. 管程为了解决进程共享资源的互斥，进程为了占有系统资源和实现系统并发。
4. 管程被想要使用共享资源的所有进程调用，管程和调用它的进程不能并行工作；进程间可以并行工作。

管程的实现（Hoare 方法）

1. 霍尔方法使用 P 和 V 操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理
2. 不要求 signal() 操作是过程体的最后一个操作，且 wait() 和 signal() 操作可被设计成可以中断的过程
3. 使用 signal() 释放一个等待进程时，霍尔管程让执行 signal() 的进程等待，直到被释放进程退出管程或等待另一个条件
4. 霍尔管程基于 PV 操作原语实现：
   1. wait() 和 signal() 可以是程序过程
   2. 可以用语言机制实现霍尔管程

Hoare 管程的数据结构

互斥信号量 mutex

1. 对每个管程，使用用于管程中过程互斥调用的信号量 mutex（初值为 1）；
2. 任何一个进程，调用管程中的任何过程时，应执行 P(mutex)；进程退出管程时，需要判断是否有进程在 next 信号量等待，如果有（即 next_count>0），则通过 V(next) 唤醒一个发出 signal 的进程，否则应执行 V(mutex) 放管程，以便让其他调用者进入
3. 为了使进程在等待资源期间，其他进程能进入管程，故在 wait 操作中也必须执行 V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源

进程的信号量 next 和计数器 next-count

1. 对每个管程，引入信号量 next（初值为 0），凡发出 signal 操作的进程应该用 P(next) 阻塞自己，直到被释放进程退出管程或产生其他等待条件
2. 进程在退出管程的过程前，须检查是否有别的进程在信号量 next 上等待，若有，则用 V(next) 唤醒它。next-count（初值为 0），用来记录在 next 上等待的进程个数

挂起等待资源的进程的信号量 x-sem 和计数器 x-count

1. 引入信号量 x-sem（初值为 0），申请资源得不到满足时，执行 P(x-sem) 阻塞。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器 x-count（初值为 0）记录等待资源的进程数
2. 执行 signal() 操作时，应让等待资源的进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用 V(x-sem) 来实现

// 每个管程定义如下数据结构 ：
typedef struct InterfaceModule {  // InterfaceModule 是结构体名字
	semaphore mutex;			  // 进程调用管程过程前使用的互斥信号量
	semaphore next;				  // 发出 signal 的进程阻塞自己的信号量
	int next_count;				  // 在 next 上等待的进程数
};

mutex = 1;		 // mutex = 0 当且仅当管程内有进程
next = 0;		 // next = 1 当且仅当管程内有进程在等待
next_count = 0;	 // 初始化语句

Hoare 管程的 enter() 和 leave() 操作

void enter(InterfaceModule& IM) {
	P(IM.mutex);  // 如果当前管程当中还有进程在等待，则当前进程在进入管程之前阻塞自己
}

void leave(InterfaceModule& IM) {  // 当前进程执行完毕，准备离开管程
	if (IM.next_count > 0)		   // 判断是否有正在等待的进程
		V(IM.next);				   // 有就释唤醒一个正在等待的进程
	else
		V(IM.mutex);  // 否则开放管程
}

Hoare 管程的 wait() 操作

semaphore x_sem = 0;	  // 与资源相关的信号量，初始化为 0
int x_count = 0;	  // 在 x_sem 上等待的进程数

void wait(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	x_count++;				// 等资源进程个数加 1，x_count 初始化为 0
	if (IM.next_count > 0)	// 判断是否有等待的进程
		V(IM.next);			// 有就唤醒一个等待中的管程
	else
		V(IM.mutex);  // 否则开放管程
	P(x_sem);		  // 等资源进程阻塞自己
	x_count--;
}

Hoare 管程的 signal() 操作

void signal(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	if (x_count > 0) {	  // 判断是否有等待资源的进程
		IM.next_count++;  // 等待的进程个数加 1
		V(x_sem);		  // 释放一个等资源的进程
		P(IM.next);		  // 发出 signal，进程阻塞自己
		IM.next_count--;  // 等待的进程个数减 1
	}
}

合并汇总

void enter(InterfaceModule& IM) {
	P(IM.mutex);  // 如果当前管程当中还有进程在等待，则当前进程在进入管程之前阻塞自己
}

void leave(InterfaceModule& IM) {  // 当前进程执行完毕，准备离开管程
	if (IM.next_count > 0)		   // 判断是否有正在等待的进程
		V(IM.next);				   // 有就释唤醒一个正在等待的进程
	else
		V(IM.mutex);  // 否则开放管程
}

semaphore x_sem = 0;  // 与资源相关的信号量，初始化为 0
int x_count = 0;	  // 在 x_sem 上等待的进程数

void wait(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	x_count++;				// 等资源进程个数加 1，x_count 初始化为 0
	if (IM.next_count > 0)	// 判断是否有等待的进程
		V(IM.next);			// 有就唤醒一个等待中的管程
	else
		V(IM.mutex);  // 否则开放管程
	P(x_sem);		  // 等资源进程阻塞自己
	x_count--;
}

void signal(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	if (x_count > 0) {	  // 判断是否有等待资源的进程
		IM.next_count++;  // 等待的进程个数加 1
		V(x_sem);		  // 释放一个等资源的进程
		P(IM.next);		  // 发出 signal，进程阻塞自己
		IM.next_count--;  // 等待的进程个数减 1
	}
}

typedef struct InterfaceModule {  // InterfaceModule 是结构体的名字
	semaphore mutex;			  // 进程调用管程过程前使用的互斥信号量
	semaphore next;				  // 发出 signal 的进程挂起自己的信号量
	int next_count;
};	// 在 next 上等待的进程数
// 初始化语句
mutex = 1;
next = 0;
next_count = 0;

void enter(InterfaceModule& IM) {
	P(IM.mutex);  // 判有否发出过 signal 的进程
}

void leave(InterfaceModule& IM) {
	if (IM.next_count > 0)
		V(IM.next);	 // 有就释放一个发出过 signal 的进程
	else
		V(IM.mutex);  // 否则开放管程
}

semaphore x_sem;  // 与资源相关的信号量
int x_count = 0;  // 在 x_sem 上等待的进程数

void wait(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	x_count++;				// 等资源进程个数加 1，x_count 初始化为 0
	if (IM.next_count > 0)	// 判断是否有发出过 signal 的进程
		V(IM.next);			// 有就释放一个
	else
		V(IM.mutex);  // 否则开放管程
	P(x_sem);		  // 等资源进程阻塞自己，x_sem 初始化为 0
	x_count--;
}

void signal(semaphore& x_sem, int& x_count, InterfaceModule& IM) {
	if (x_count > 0) {	  // 判断是否有等待资源的进程
		IM.next_count++;  // 发出 signal 进程个数加 1
		V(x_sem);		  // 释放一个等资源的进程
		P(IM.next);		  // 发出 signal 进程阻塞自己
		IM.next_count--;  // 发出 signal 进程个数减 1
	}
}

管程求解进程同步与互斥问题

互斥问题：

1. 读者写者问题
2. 哲学家就餐问题

同步问题：

1. 生产者-消费者问题
2. 苹果-桔子问题

霍尔管程求解读者/写者问题-写者优先

霍尔管程求解哲学家就餐问题

cobegin
process philosopher_i() {
L:
    thinking();
    dining_philosopers.pickup(i);
    eating();
    dining_philosophers.putdown(i);
    goto L;
}
coend

AND 型信号量（课本 188-189 第 53 题）

求解可以使用 AND 型信号量 SP 和 SV 操作

1. SP(fork[i], fork[(i+1)%5])
2. SV(fork[i], fork[(i+1)%5])

霍尔管程解决生产者消费者问题

霍尔管程求解苹果桔子问题

1. 桌上有一只盘子，每次只能放入一只水果。爸爸专向盘子中放苹果（apple)，妈妈专向盘子中放桔子（orange），一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。使用 Hoare 管程求解该问题
2. SP：盘子
3. SS：桔子
4. SD：苹果

进程通信（信息传递）

进程通信的概念

1. 交往进程通过信号量操作实现进程互斥和同步，这是一种低级通信方式
2. 进程有时还需要交换更多的信息（如把数据传送给另一个进程），可以引进高级通信方式：进程通信机制，实现进程间用信件来交换信息，进程通信扩充了并发进程的数据共享
3. 通信方式包括很多种
   1. 信号通信机制：只能发送单个信号
   2. 管道通信机制
   3. 消息传递机制
   4. 信号量通信机制
   5. 共享内存通信机制。
4. 当进程互相交互时，必须满足两个基本要求：同步和通信
   1. 为实施互斥，进程间需要同步
   2. 为了协作，进程间需要交换信息
5. 消息传递提供了这些功能，最典型的消息传递原语
   1. send：发送消息的原语
   2. receive：接收消息的原语

信号通信机制

软中断（P152 页）

信号是一种软中断，用于内核或进程对某个进程发出中断，向进程通知某个特定事件的发生或迫使进程执行信号处理程序。

中断和信号：

1. 相同：
   1. 概念上一致
   2. 异步过程
   3. 均采用向量表
   4. 均有屏蔽设施
2. 不同：
   1. 中断由硬件和软件结合实现，信号完全依靠软件实现。
   2. 中断向量和中断处理程序均位于系统空间；信号向量表位于用系统空间，但信号处理程序由应用程序提供，在用户空间处理。

信号通信机制

1. 用户、内核和进程都可以生成和发送信号。
2. 由进程执行指令而产生的信号称为同步信号，如除以 0；
3. 像击键之类的进程之外的事件所引起的信号叫做异步信号。

消息格式

进程直接通信

1. 发送或接收信件的进程指出信件发给谁或从谁那里接收信件
   1. send（P, 信件）：把信件发送给进程 P
   2. receive（Q, 信件）：从进程 Q 接收信件
2. 对称直接寻址，发送进程和接收进程必须命名对方以便通信，原语 send() 和 receive()义如下：
   1. send(P, messsage) 发送消息到进程 P
   2. receive(Q, message) 接收来自进程 Q 的消息
3. 非对称直接寻址，只要发送者命名接收者，而接收者不需要命名发送者，send() receive()义如下：
   1. send(P, messsage) 发送消息到进程 P
   2. receive(id, message) 接收来自任何进程的消息，变量 id 置成与其通信的进程名称

进程间接通信

1. 发送或者接收信件通过一个信箱来进行，该信箱有唯一标识符
2. 消息不是直接从发送者发送到接收者，而是发送到由临时保存这些消息的队列组成的一个共享数据结构，这些队列通常成为信箱（mailbox）
3. 一个进程给合适的信箱发送消息，另一进程从信箱中获得消息。
4. 信箱为操作系统所有是指由操作系统统一设置信箱，归系统所有，供相互通信的进程共享，消息缓冲机制就是一个著名的例子。
5. 一个进程为其他进程提供服务，此时信箱又叫做端口（port）
6. 间接通信的 send() receive()义如下：
   1. send(A,message)：把一封信件（消息）传送到信箱 A，本身执行包含两种情况
      1. 同步的（阻塞型），等待进程回答消息才继续。
      2. 异步的（非阻塞型），不等待进程回答，先继续执行，之后再回来处理。
   2. receive(A,message)：从信箱 A 接收一封信件（消息）
      1. 同步的（阻塞型），没有信息则挂起，知道有信息进入，如果有消息立即返回
      2. 异步的（非阻塞型），查询信箱后，进程立即返还控制权，如果有消息则返回消息，否则返回标志码。
7. 一般我们选择非阻塞式send 和阻塞式receive：发送可以一直发送信息直到满，接受通常是服务器进程，知道有信息才被唤醒。
8. “发送”和“接收”两条原语的功能为：
   1. 发送信件：如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则，发送信件者被置成等待信箱状态
   2. 接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则，接收信件者被置成等待信箱中信件的状态
9. send 和 receive 的代码实现

间接通信的信箱

1. 信箱是存放信件的存储区域，每个信箱可以分成信箱特征和信箱体两部分
   1. 信箱头指出信箱容量、信件格式、存放信件位置的指针等
   2. 信箱体用来存放信件，信箱体分成若干个区，每个区可容纳一封信

发送信件原语的处理流程

1. 若指定的信箱未满
2. 则把信件送入信箱中指针所指示的位置，释放等待该信箱中信件的等待者
3. 否则，发送信件者被置成等待信箱的状态

接收信件原语的处理流程

1. 若指定信箱中有信件
2. 则取出一封信件，释放等待信箱的等待者
3. 否则，接收信件者被置成等待信箱中信件的状态

管道和套接字

1. 管道（pipeline）是 Unix 和 C 的传统通信方式
   1. 进程通过管道读写数据时，另一个进程需要等待
   2. 发送者和接收者必须都知道对方存在
   3. 发送者和接受者之间要实现正确的同步关系

2. 套接字（socket）起源于 Unix BSD 版本，目前已经被 Unix 和 Windows 操作系统广泛采用，并支持 TCP/IP 协议，即支持本机的进程间通信，也支持网络级的进程间通信
3. 管道和套接字都是基于信箱的消息传递方式的一种变体，它们与传统的信箱方式等价，区别在于没有预先设定消息的边界。换言之，如果一个进程发送 10 条 100 字节的消息，而另一个进程接收 1000 个字节，那么接收者将一次获得 10 条消息

消息传递通信机制

1. 消息传递的复杂性在于地址空间隔离，发送进程无法将信息直接复制到接收空间的地址空间中，需要由操作系统完成。
2. 消息缓冲是在 1973 年由 P.B.Hansan 提出的一种进程间高级通信设施，并在 RC4000 系统中实现
3. 消息缓冲通信的基本思想是：由操作系统统一管理一组用于通信的消息缓冲存储区，每一个消息缓冲存储区可存放一个消息（信件）。当一个进程要发送消息时，先在自己的消息发送区里生成待发送的消息，包括：接收进程名、消息长度、消息正文等。然后，向系统申请一个消息缓冲区，把消息从发送区复制到消息缓冲区中，注意在复制过程中系统会将接收进程名换成发送进程名，以便接收者识别。随后该消息缓冲区被挂到接收消息的进程的消息队列上，供接收者在需要时从消息队列中摘下并复制到消息接收区去使用，同时释放消息缓冲区。

消息缓冲通信

1. 消息缓冲通信涉及的数据结构：
   1. sender：发送消息的进程名或标识符
   2. size：发送的消息长度
   3. text：发送的消息正文
   4. next-ptr：指向下一个消息缓冲区的指针
2. 在进程的 PCB 中涉及通信的数据结构：
   1. mptr：消息队列队首指针
   2. mutex：消息队列互斥信号量，初值为 1
   3. sm：表示接收进程消息队列上消息的个数，初值为 0，是控制收发进程同步的信号量
3. 发送原语和接收原语的实现如下：
   1. 发送原语 Send：申请一个消息缓冲区，把发送区内容复制到这个缓冲区中；找到接收进程的 PCB，执行互斥操作 P(mutex)；把缓冲区挂到接收进程消息队列的尾部，执行 V(sm)、即消息数加 1；执行 V(mutex)
   2. 接收原语 Receive：执行 P(sm)看有否信件；执行互斥操作 P(mutex)，从消息队列中摘下第一个消息，执行 V(mutex)；把消息缓冲区内容复制到接收区，释放消息缓冲区

消息传递机制解决进程互斥和同步问题

解决进程互斥问题

create_mailbox(box);
send (box，null)；
void Pi() { /*i = l,2,...，n*/
   message msg；
   while (true){
      receive(box，msg)；
      /* 临界区 */ ;
      send( box,msg)；
   }
}
cobegin
   Pi();
coend

1. 阻塞式 receive()语和非阻塞式 send()语。
2. 消息可以看做是传递的令牌

消息传递求解生产者消费者问题

int capacity;                    /* 缓冲区最多个数 */
void producer(void){             /* 生产者进程 */
   int item;
   message m;                    /* 消息缓冲区 */
   while(true){
      item = produce_item();     /* 生产消息 */
      receive(consumer, &m);     /* 等待消费者发送空缓冲区 */
      build_message( &m，item);  /* 构造一条发送的消息 */
      send(consumer, &m);        /*发送消息给消费者*/
   }
}
void consumer(void){             /*消费者进程*/
   int item,i ;
   message m;
   for(i = 0; i < capacity ; i++)
      send (producer，&m);       /*给消费者发送空缓冲区*/
   while(true){
      receive( producer,&m);     /*接收含有 item 的消息*/
      item = extract_item(&m);   /*从 item 取消息*/
      send(producer,&m);        /*回送空缓冲区给生产者*/
      consume_item(item);        /*使用消息*/
   }
}

1. consumer 发送 capacity 条空消息，生产者对信息加工后给消费者。
2. 通过上面方式，整体信息数不变。

高级进程通信机制

基于流的进程通信

1. 多个进程使用一个共享的消息缓冲区（可称为管道、多路转接器、套接字）
2. 一些进程往消息缓冲区中写入字符流（send/write）
3. 一些进程从消息缓冲区中读出字符流（receive/read）
4. 信息交换单位基于字符流，长度任意

基于字符流的进程通信规约

远程过程调用 RPC（Remote Procedure Call）

1. 采用客户/服务器计算模式
2. 服务器进程提供一系列过程/服务，供客户进程调用
3. 客户进程通过调用服务器进程提供的过程/服务获得服务
4. 考虑到客户计算机和服务器计算机的硬件异构型，外部数据表示 XDR 被引入来转换每台计算机的特殊数据格式为标准数据格式

RPC 执行步骤

1. 客户进程以普通方式调用客户存根
2. 客户存根组织 RPC 消息并执行 Send，激活内核程序
3. 内核把消息通过网络发送到远地内核
4. 远地内核把消息送到服务器存根
5. 服务器存根取出消息中参数后调用服务器过程
6. 服务器过程执行完后把结果返回至服务器存根
7. 服务器存根进程将它打包并激活内核程序
8. 服务器内核把消息通过网络发送至客户机内核
9. 客户内核把消息交给客户存根
10. 客户存根从消息中取出结果返回给客户进程
11. 客户进程获得控制权并得到了过程调用的结果

基于 RPC/XDR 的高级通信规约

死锁的产生

死锁的产生

1. 允许多个进程并发执行共享系统资源时，系统必须提供同步机制和进程通信机制
2. 然而，对这种机制使用不当的话，可能会出现进程永远被阻塞的现象
3. 例如，两个进程分别等待对方占有的一个资源，于是两者都不能执行而处于永远等待，这种现象称为“死锁”

例 1-进程推进顺序不当产生死锁

设系统有打印机、绘图仪各一台，被进程 Q1 和 Q2 共享。两个进程并发执行，按下列次序请求和释放资源：

进程资源轨迹图：

例 2-PV 操作使用不当产生死锁

例 3-资源分配不当引起死锁

若系统中有 m 个资源被 n 个进程共享，每个进程都要求 k 个资源，而 m < nK 时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁

例 4-对临时性资源使用不加限制引起死锁

进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。

进程 P1 等待进程 P3 的信件 S3 来到后再向进程 P2 发送信件 S1；P2 又要等待 P1 的信件 S1 来到后再向 P3 发送信件 S2；而 P3 也要等待 P2 的信件 S2 来到后才能发出信件 S3。这种情况下形成了循环等待，产生死锁。

独木桥（例）

只能在一个方向行车，可能发生死锁，也可能发生饥饿。

死锁的定义

一组进程处于死锁状态是指：每一个进程都在等待被另一个进程所占有的、不能抢占的资源。例如，

1. 存在 n 个进程 P1, P2, …, Pn
2. 进程 Pi 因为申请不到资源 Ri 而处于等待状态
3. 而 Ri 又被 Pi+1 占有，Rn 被 P1 占有
4. 显然，这 n 个进程的等待状态永远不能结束，
5. 这 n 个进程就处于死锁状态

操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。

例如，n 个进程 P1，P2，…，Pn，Pi 因为申请不到资源 Rj 而处于等待状态，而 Rj 又被 Pi+1 占有，Pn 欲申请的资源被 P1 占有，此时这 n 个进程的等待状态永远不能结束，则说这 n 个进程处于死锁状态。

解决死锁问题的三个方法

综合上面的例子，产生死锁的因素不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关

可从三个方面来解决死锁问题：

1. 死锁防止
2. 死锁避免
3. 死锁检测和恢复

死锁产生的四个必要条件

1. 互斥条件： 进程应互斥使用资源，任一时刻一个资源仅为一个进程独占
2. 占有和等待条件： 一个进程请求资源得不到满足而等待时，不释放已占有的资源
3. 不可剥夺条件： 任一进程不能从另一进程那里抢夺资源
4. 循环等待条件： 存在一个循环等待链，每一个进程分别等待它前一个进程所持有的资源

前三个是死锁存在的必要条件，但不是充分条件，第四个条件是前三个条件同时存在时所产生的结果。

死锁的防止

破坏四个必要条件之一，死锁就可防止。

破坏第一个条件-资源共享化

使资源可同时访问而不是互斥使用。

可再入程序、只读数据文件、时钟、磁盘等软硬件资源均可用这种办法管理，但有许多资源如可写文件、磁带机等由于特殊性质决定只能互斥占有，而不能被同时访问，所以这种做法许多场合行不通。

破坏第二个条件-静态分配

静态分配是指进程在执行中不再申请资源，就不会出现占有某些资源再等待另一些资源的情况。所有并发执行的进程要求的资源总和不超过系统拥有的资源数。

静态分配实现简单，被许多操作系统采用，但会严重地降低资源利用率，因为在每个进程占有的资源中，有些资源在运行后期使用，甚至有些资源在例外情况（极个别情况）下才被使用，可能造成进程占有一些几乎不用的资源，而使其他想用这些资源的进程产生等待。

破坏第三个条件-剥夺式调度

采用剥夺式调度方法，适用于内存和处理器资源，不适用于所有资源。

方法：

1. 如果要申请新的资源，必须主动释放已占用资源（剥夺式），若仍需要占用此资源，则需要重新发起申请。
2. 资源管理程序为进程分配新资源时，若有资源则分配，否则将剥夺进程已占有的全部资源，并让进程进入等待资源状态，资源充足后再唤醒它重新申请所有需要的资源。

破坏第四个条件-层次分配和按序分配

上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法

采用层次分配策略：

1. 在层次分配策略下，资源被分成多个层
2. 一个进程得到某一层的一个资源后，它只能再申请在较高层的资源
3. 当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源
4. 当一个进程获得了某一层的一个资源后，它想再申请该层中的另一个资源，那么，必须先释放该层中的已占资源

层次策略的变种按序分配策略：

1. 把系统的所有资源排一个顺序，例如，系统若共有 n 个进程，共有 m 个资源，用 \(r_i\) 表示第 i 个资源，于是这 m 个资源是：\(r_1, r_2, ..., r_m\)
2. 规定如果进程不得在占用资源 \(r_i(1\leq i \leq m)\) 后再申请 \(r_j(j<i)\)。不难证明，按这种策略分配资源时系统不会发生死锁。

死锁的避免

1. 当不能防止死锁的产生时，如果能掌握并发进程中与每个进程有关的资源申请情况，仍然可以避免死锁的发生
2. 只需在为申请者分配资源前先测试系统状态，若把资源分配给申请者会产生死锁的话，则拒绝分配，否则接收申请，为它分配资源。

银行家算法（资源分配拒绝法）

1. 银行家算法：
   1. 银行家拥有一笔周转资金，借钱给有偿还能力的客户
   2. 客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就一定不能归还贷款
   3. 银行家应谨慎的贷款，防止出现坏帐
2. 用银行家算法避免死锁：
   1. 操作系统（银行家）
   2. 操作系统管理的资源（周转资金）
   3. 进程（要求贷款的客户）
3. 银行家算法允许前三个必要条件存在，通过核实的资源分配算法确保不会出现进程循环等待链，从而避免死锁。
4. 系统首先检查申请者对资源的最大需求量
   1. 如果现存的资源可以满足它的最大需求量时，就满足当前的申请
   2. 如果不能则拒绝启动该进程。
5. 换言之，仅仅在申请者可能无条件地归还它所申请的全部资源时，才分配资源给它。

银行家算法的数据结构

一个系统有 \(n\) 个进程和 \(m\) 种不同类型的资源，定义包含以下向量和矩阵的数据结构：

1. 系统中每类资源总数向量：\(Resource=(R_1,R_2,...,R_m)\)
2. 系统中每类资源当前可用数向量：\(Available=(V_1,V_2,...,V_m)\)
3. 每个进程对各类资源的最大需求矩阵：\(Claim[i,j]\)，如果 \(Claim[i,j]=k\) 表示进程 \(P_i\) 需要 \(R_j\) 类资源的最大数目为 \(k\) 个。
4. 每个进程已占有各类资源数量矩阵：\(Allocation[i,j]\)，若 \(Allocation[i,j] = k\) 表示进程 \(P_i\) 占有 \(R_j\) 类资源 \(k\) 个，初始值为 0。
5. 每个进程尚需要各类资源数量矩阵 \(Need[i,j]\)，若 \(Need[i,j] = k\) 表示进程 \(P_i\) 还需要 \(R_j\) 类资源 \(k\) 个。\(Need[i,j] = Claim[i,j] - Allocation[i,j]\)
6. 每个进程从当前申请各类资源数量矩阵 \(Request[i,j]\)，若 \(Request[i, j] = k\)，表示进程 \(P_i\) 当前申请 \(R_j\) 类资源 \(k\) 个。

银行家算法中下列关系式确保成立

系统要启动一个新进程工作（第 \(n+1\) 个），对于资源 \(Resource[i]\) 即 \(R_i\) 的最大需求需求满足不等式：

\[ Claim[(n+1), i] \le R_i - \sum\limits_{k=1}\limits^nClaim[k, i] \]

也就是应当满足当前系统中所有进程对资源 \(R_i\) 的最大需求数，加上启动的新进程的资源最大需求数，不超过系统拥有的最大资源数时才启动该进程（进程拒绝启动法）。

算法性质：

1. \(\forall 1 \le i \le m, 1 \le k \le n. R_i=V_i+\sum A_{ki}\) 表示所有资源要么被分配、要么尚可分配；
2. \(C_{ki} \leq R_i\) 对 \(i=1,..,m, k=1,..,n\) 表示进程申请资源数不能超过系统拥有的资源总数；
3. \(A_{ki} \leq C_{ki}\) 对 \(i=1,..,m,k=1,..,n\) 表示进程申请任何类资源数不能超过声明的最大资源需求数；

系统安全性

系统安全性定义：在时刻 \(T_0\) 系统是安全的,仅当存在一个进程序列 \(P_1,..,P_n\)，对进程 \(P_k\) 满足公式：

\[ \forall 1 \le i \le m, 1 \le k \le n.Need[k, i] \leq Available[i] + \sum\limits_{j=1}\limits^{k-1}Allocation[j, i] \]

即，从该时刻开始，有一种合法的进程调度序列，使得对于每个进程，所需要的资源数目都不高于当前可用资源加上前面的进程释放的资源之和。

银行家算法的基本思想

1. 系统中的所有进程进入进程集合。
2. 在安全状态下系统收到进程的资源请求后，先把资源试探性分配给它。
3. 系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量的进程（从而，保证这个进程运行完毕并归还全部资源）
4. 把这个进程从集合中去掉，系统的剩余资源更多了，反复执行上述步骤。（进程退出系统，资源回收）
5. 最后，检查进程集合，若为空表明本次申请可行，系统处于安全状态，可实施本次分配;否则，有进程执行不完，系统处于不安全状态，本次资源分配暂不实施，让申请进程等待。
6. 注：安全序列是不唯一的，2019 年有考察。

银行家算法的程序及实现

typedef struct state {//全局数据结构
   int resource[m];
   int available[m];
   int claim[n][m];
   int allocation[n][m];
};
void resource_allocation() { //资源分配算法
   if(allocation[i,*]+request[*]>claim[i,*])
      {error}; //申请量超过最大需求值
   else {
      if(request[*]>available[*])
         {suspend process.};
      else { //尝试分配，define newstate by:
         allocation[i,*]=allocation[i,*]+request[*];
         available[*]=available[*]-request[*];
      }
   }
   if(safe(newstate))
      {carry out allocation};
   else {
      {restore original state};
      {suspend process};
   }
}
bool safe(state s) { //安全性测试算法
   int currentavail[m];
   set <process> rest;
   currentavail[*]=available[*];
   rest={all process};
   possible=true;
   while(possible){ //rest 中找一个 Pk，满足以下条件
      claim[k,*]-allocation[k,*]<=currentavail[*]
      if(found){
         currentavail[*]=currentavail[*]+allocation[k,*];
         rest=rest-{Pk};
      }else{
         possible=false;
      }
   }
   return(rest=null);
}

银行家算法例子

银行家算法例 1

P 或者 R 再申请资源时，不能分配，因为现在只剩下 2 个资源，不能满足它们的最大需求

实例说明系统所处的安全或不安全状态（1）

1. 如果系统中共有五个进程和 A、B、C 三类资源
2. A 类资源共有 10 个,B 类资源共有 5 个,C 类资源共有 7 个
3. 在时刻\(T_0\),系统目前资源分配情况如下：

1. 可以断言目前系统处于安全状态，因为序列\(\{P_1,P_3,P_4,P_2,P_0\}\)能满足安全性条件

2. 假设\(P_1\)又请求 1 个 A 类资源和 2 个 c 类资源，得到新的状态如下图所示：
   1. \(Request1(1, 0, 2) \leq Need(1, 2, 2)\)
   2. \(Request1(1, 0, 2) \leq Available(3, 3, 2)\)

3. 判定新状态是否安全?可执行安全性测试算法，找到一个进程序列\(\{P_1,P_3,P_4,P_0,P_2\}\)能满足安全性条件，所以可正式把资源分配给进程 P1；

4. 假设\(P_4\)发起资源请求，按照银行家算法检查，资源不足不予以分配
   1. \(Request4(3, 3, 0) \leq Need(4, 3, 1)\)
   2. \(Request4(3, 3, 0) > Available(2, 3, 0)\)
5. 假设\(P_0\)发起资源请求，按照银行加算法检查，得到中间结果如下
   1. \(Request0(0, 2, 0) \leq Need(7, 3, 1)\)
   2. \(Request0(0, 2, 0) \leq Available(2, 3, 0)\)

死锁的检测

死锁的检测

1. 解决死锁问题的另一条途径是死锁检测方法
2. 这种方法对资源的分配不加限制，但系统定时运行一个“死锁检测”程序，判断系统内是否已出现死锁，若检测到死锁则设法加以解除
3. 检测的一种方法：可设置两张表格来记录进程使用资源的情况
   1. 等待资源表记录每个被阻塞进程等待的资源
   2. 占用资源表记录每个进程占有的资源
4. 进程申请资源时，先查该资源是否为其它进程所占用
   1. 若资源空闲，则把该资源分配给申请者且登入占用资源表
   2. 否则，则登入进程等待资源表

1. 死锁检测程序定时检测这两张表，若有进程\(P_i\)等待资源\(r_k\)，且\(r_k\)被进程\(P_j\)占用，则说\(P_i\)和\(P_j\)具有“等待占用关系”，记为\(W(P_i, P_j)\)
2. 死锁检测程序反复检测这两张表，可以列出所有的“等待占用关系”
3. 如果出现\(W(P_i, P_j)，W(P_j, P_k)，...，W(P_m,P_n)，W(P_n, P_i)\)时，显然，系统中存在一组循环等待资源的进程：\(P_i，P_j，P_k，...，P_m，P_n\)，也就是说出现了死锁

资源分配图与死锁定理

1. 资源分配图的图例
   1. 每个资源用一个方框表示
   2. 方框中的黑圆点表示此资源类中的各个资源
   3. 每个进程用一个圆圈表示
   4. 有向边表示进程申请资源和资源被分配情况
2. 约定\(P_i\rightarrow R_j\)为请求边，表示进程\(P_i\)申请资源类\(R_j\)中的一个资源得不到满足而处于等待\(R_j\)类资源的状态，该有向边从进程开始指到方框的边缘，表示进程\(P_i\)申请\(R_j\)类中的一个资源。
3. \(Rj\rightarrow Pi\)为分配边，表示\(R_j\)类中的一个资源已被进程\(P_i\)占用，由于已把一个具体的资源分给了进程 Pi，故该有向边从方框内的某个黑圆点出发指向进程。

1. 图 3.6 中存在环路，经过分析是存在死锁的
2. 图 3.7 中存在环路，但是经过分析是不存在死锁的，因为\(R_1\)和\(R_2\)资源都不只一个，\(P_2\)和\(P_4\)进程归还后是可以避免的。
3. 我们可以用矩阵和向量来求解，手机图片

死锁检测算法

1. 如果进程-资源分配图中无环路，此时系统没有发生死锁。
2. 如果进程-资源分配图中有环路，且每个资源都只有一个资源则发生死锁。
3. 如果进程-资源分配图中有环路，且所涉及资源有多个资源，则未必发生死锁，需要具体问题具体分析：可以通过消去法来判断，消去即不阻塞其他进程又与其他进程相关的进程的所有请求边和分配边，得到一个孤立点。接着将等待资源的进程分配后再次消去，如果最后所有的进程都成为孤立点则是无死锁的，图是可完全简化的，否则图是不可以完全简化的。

死锁定理

系统为死锁状态的充分条件是：当且仅当该状态的进程-资源分配图是不可完全简化的。该充分条件称为死锁定理

死锁检测的数据结构

把两张表格中记录的进程使用和等待资源的情况用一个矩阵 A 来表示

死锁检测程序可用 Warshall 的传递闭包算法

1. 检测是否有死锁发生，即对矩阵 \(A\) 构造传递闭包\(A^*[bij]\)
2. \(A^*[bij]\)中的每个\(bij\)是对\(A[bij]\)执行如下算法

for k:=1 to n do
   for i:=1 to n do
      for j:=1 to do
         bij:= bij 并 (bik 并 bkj)

死锁检测和恢复

1. 死锁被检测到后可以通过各种方法来解除系统死锁以恢复到可运行状态，方法有资源剥夺法、进程回退法、进程撤销法和系统重启法。
   1. 资源剥夺法：剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。可仿照撤销陷于死锁的进程那样来选择剥夺资源的进程。
   2. 进程回退法：根据系统保存的检查点让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检査点、回退及重启机制。
   3. 进程撤销法：
      1. 撤销陷于死锁的所有进程，解除死锁，继续运行。
      2. 逐个撤销陷于死锁的进程，回收其资源并重新分派，直至死锁解除。但是究竟先撤销哪个死锁进程呢？可选择符合下面条件之一的进程先撤销： PU 消耗时间最少者、产生的输出量最少者、预计剩余执行时间最长者、分得的资源数量最少者或优先级最低者。
   4. 系统重启法：结束所有进程的执行并重新启动操作系统。这种方法很简单，但先前的工作全部作废，损失很大。
2. 检测死锁是否出现和发现死锁后实现恢复的代价大于防止和避免死锁花费的代价，但是这样的代价是值得的，因为死锁不是经常出现的。
   1. 检测策略的代价依赖于死锁出现的频率
   2. 恢复的代价是指处理器时间的损失。