操作系统 （并发进程） 徐锋 Email: xf@nju.edu.cn 南京大学计算机科学与技术系 2018年9月18日3时52分.

Presentation on theme: "操作系统 （并发进程） 徐锋 Email: xf@nju.edu.cn 南京大学计算机科学与技术系 2018年9月18日3时52分."— Presentation transcript:

1 操作系统 （并发进程） 徐锋 南京大学计算机科学与技术系 2018年9月18日3时52分

2 主要内容 并发进程概述 临界区管理 信号量与PV操作 管程 进程通信 死锁

3 并发进程概述 顺序程序设计 将一个程序设计成为一个顺序执行的程序模块，不同的程序也是按顺序执行。 特点： （程序与程序的执行一一对应）
执行的顺序性 内部顺序性、外部顺序性 环境的封闭性 执行结果的确定性 计算过程的可再现性

4 并发进程概述 顺序程序设计举例 某程序需要循环执行输入、计算、输出三个过程
while(TRUE) {input; process; output;} input 78ms, process 52ms, output 20ms I1 P1 O1 I2 P2 O2 … 串行执行

5 并发进程概述 顺序程序设计举例,处理器效率 处理器的利用率 = 52n/(78n + 52n + 20n) = 52/150 ≈ 35%
130 150 228 280 300 378 430 450 时 间 输入机 处理器 磁带机 处理器的利用率 = 52n/(78n + 52n + 20n) = 52/150 ≈ 35%

6 并发进程概述 顺序程序设计 优缺点： 程序编制、调试方便 计算机系统效率较低

7 并发进程概述 并发程序设计 将一个程序分成若干个可同时执行的程序模块，每个程序模块和它执行时所处理的数据就组成了一个进程。 特点： 并发性
共享性 制约性 交互性

8 并发进程概述 进程的并发性 一组进程在执行时间上重叠，一个进程执行的第一条指令是在另一个进程执行的最后一条指令完成之前开始的 宏观： 微观：
在一个时间段中几个进程同时处于活动状态 微观： 任一时刻仅有一个进程在处理器上运行 实质： 一个CPU在几个进程之间的多路复用

9 并发进程概述 并发程序设计举例一（相关进程） 某程序需要循环执行输入、计算、输出三个过程 设计为三个可并行执行的程序模块
while(TRUE) {input; send;}; ms while(TRUE) {receive; process; send;}; 52ms While(TRUE) {receive; output;}; ms 三个进程通过缓冲区交换信息 receive receive send send Ii Pi Oi 缓冲区1 缓冲区2

10 并发进程概述 并发程序设计举例一 进程 I P O t1 I1 P1 t2 I2 O1 P2 t3 I3 O2 P3 时间 O3

11 并发进程概述 并发程序设计举例一，处理器效率 处理器的利用率 = 52n/(78n + 52 + 20) ≈ 67%, 当n →∞ 时 间
150 228 306 384 130 208 286 364 时 间 输入机 处理器 磁带机 处理器的利用率 = 52n/(78n ) ≈ 67%, 当n →∞

12 并发进程概述 … 并发程序设计举例二（无关进程） 进程A，由指令a1, a2, a3组成； 进程B，由指令b1, b2, b3组成。

13 并发进程概述 并发进程间的关系 无关 交互（往） 一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的执行进度无关
一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果

14 并发进程概述 无关的并发进程判断 并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件
R(Pi) = {a1, a2, …, an}, 指进程Pi在执行期间引用的变量集 W(Pi) = {b1, b2, …, bm}, 指进程Pi在执行期间改变的变量集 若两个进程的上述变量集合满足下列条件： (R(P1)∩W(P2)) ∪ (R(P2) ∩W(P1)) ∪ (W(P1) ∩W(P2)) = { } 则并发进程的执行与时间无关

15 并发进程概述 无关的并发进程判断举例 有如下四个进程： 解：
P1: a = x + y; P2: b = z + 1; P3: c = a – b; P4: w = c + 1; 判断哪两个进程可并发执行？ 解： R(P1) = {x, y}, R(P2) = {z}, R(P3) = {a, b}, R(P4) = {c} W(P1) = {a}, W(P2) = {b}, W(P3) = {c}, W(P4) = {w} P1和P2的上述集合满足Bernstein条件，可并发执行。

16 并发进程概述 并发进程间的交互（往） 竞争关系（间接制约关系） 协作关系（直接制约关系） 进程的互斥关系是一种特殊的进程同步关系
解决手段，进程互斥访问 若干个进程要访问同一共享资源时，任何时刻最多允许一个进程访问，其他进程必须等待，直到占有资源的进程释放该资源 协作关系（直接制约关系） 解决手段，进程同步 两个以上的进程基于某个条件来协调它们的活动。一个进程的执行依赖于其协作进程的消息或信号，当没有得到该消息或信号时需要等待，直到消息或信号到达时被唤醒 进程的互斥关系是一种特殊的进程同步关系

17 并发进程概述 并发程序设计的优点： 对于单处理器系统，可让处理器和个I/O设备同时工作，发挥硬件的并行能力
对于多处理器系统，可让各进程在不同的处理器上并行执行，加快计算速度 简化程序设计任务

18 并发进程概述 采用并发程序设计的目的 充分发挥硬件的并行工作能力，提高系统效率 是多道程序设计的基础

19 并发进程概述 有交互关系的并发进程执行时带来的问题 由于一组有交互关系的并发进程，其执行的相对速度无法控制，导致出现多种与时间有关的错误出现
与时间有关错误的表现形式： 结果不唯一 永远等待

20 并发进程概述 结果不唯一错误举例，订票问题 process Ti ( i = 1, 2 ) var Xi:integer; begin
{按旅客定票要求找到Aj}； ①Xi := Aj; ②if Xi>=1 then begin ③ Xi:=Xi-1; ④ Aj:=Xi; ⑤ {输出一张票}；end else {输出票已售完}； end;

21 并发进程概述 永远等待错误举例，内存管理问题 procedure borrow (var B:integer) begin
①if B>x then ② {申请进程进入等待队列等主存资源} ③x:=x-B; ④{修改主存分配表，申请进程获得主存资源} end; procedure return (var B:integer) ①x:=x+B; ②{修改主存分配表} ③{释放等主存资源的进程}

22 临界区管理 临界区： 临界资源： 临界区管理： 并发进程中与共享变量有关的程序段，称为临界区(Critical Section)
共享变量代表的资源，称为临界资源(Critical Resource) 临界区管理： 保证一个进程在临界区执行时，不让另一各进程进入相关的临界区。（实现对共享变量的互斥访问）

23 临界区管理 临界区调度的原则 一次至多一个进程能够进入它的临界区 不能让一个进程无限地留在临界区 不能强迫一个进程无限等待进入临界区
“无空等待、有空让进、择一而入、算法可行”

24 临界区管理 临界区的描述 临界区的嵌套 临界资源（共享变量） 临界区
shared 变量名 临界区 region 变量名 do 语句（复合语句） 临界区的嵌套 例，region X do {…; region Y do {…}; …} 嵌套可能导致进程无限地留在临界区

25 临界区管理 临界区管理的尝试 引入进程标志，分别指示进程进入临界区的情况 第一种尝试，先测试，后置位 第二种尝试，先置位，后测试
不能保证同一时间只有一个进程进入临界区 第二种尝试，先置位，后测试 会出现死循环的情况，永远等待

26 临界区管理 临界区管理的尝试(1) inside1,inside2:Boolean
inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Begin ①while inside2 do begin end; ②inside1 := true; ③临界区; ④inside1 := false; end; process P2 ①while inside1 do begin end; ②inside2 = true; ④inside2 := false; coend

27 临界区管理 临界区管理的尝试(2) inside1,inside2:Boolean
inside1 := false; /* P1不在其临界区内 */ inside2 := false; /* P2不在其临界区内 */ cobegin process P1 Begin ①inside1 := true; ②while inside2 do begin end; ③临界区; ④inside1 := false; end; process P2 ①inside2 = true; ②while inside1 do begin end; ④inside2 := false; coend

28 临界区管理 实现临界区管理的软件方法 Dekker算法 Peterson算法

29 临界区管理 Dekker算法， 采用指示器变量turn来指示该由哪个进程进入临界区 具体实现： // 变量定义及初始化
var inside : array[1..2] of boolean; turn :integer; turn := 1 or 2; inside[1]:=false; inside[2]:=false;

30 临界区管理 Dekker算法（续） cobegin process P1 begin inside[1]:=true;
while inside[2] do if turn=2 then begin inside[1]:=false; while turn=2 do begin end; end 临界区; turn = 2； end; process P2 begin inside[2]:=true; while inside[1] do if turn=1 then begin inside[2]:=false; while turn=1 do begin end; end 临界区; turn = 1； end; coend.

31 临界区管理 Dekker算法（续） 基本思想： 缺点：
进程P1(或P2)进入自己的临界区时，把自己的标志位insidei置为true，并检查对方标志位 如果对方不在也不想进入临界区，进程Pi可立即进入临界区；如果双方都想进入，咨询指示器turn，若turn为1(或为2)，P1(或P2)知道应该自己进入 缺点： 算法复杂难以理解

32 临界区管理 Peterson算法 基本思想： 用对turn的置值和while语句来限制每次只有一个进程进入临界区；
进程执行完临界区程序后，修改insidei状态使等待进入临界区的进程可在有限时间内进入。 算法满足临界区管理的三个条件。

33 临界区管理 Peterson算法 算法描述（1） // 变量定义及初始化
var inside: array[1..2] of boolean; turn : integer; turn := 1 or 2; inside[1] := false; inside[2] := false;

34 临界区管理 Peterson算法 算法描述（2） cobegin process P2 process P1 begin begin
① inside[1] := true; ② turn := 2; ③ while (inside[2] and turn = 2) do begin end; ④ 临界区； ⑤ inside[1] := false; end; process P2 begin ① inside[2] := true; ② turn := 1; ③ while (inside[1] and turn = 1) do begin end; ④ 临界区； ⑤ inside[2] := false; end; coend.

35 临界区管理 实现临界区管理的硬件方法 关中断（阻止进程交替执行） 测试并建立指令，TS （测试与上锁不能分离） var
TS(x): 若x = true, 则x := false; return true; 否则return false; 实现： var s: boolean; s := true; process Pi var pi : boolean; begin repeat pi := TS(s) until pi; 临界区； end;

36 临界区管理 实现临界区管理的硬件方法 对换指令，Swap
Swap(a,b): temp := a; a := b; b := temp; 例如：XCHG指令 实现： var lock : boolean; lock := false; process Pi var pi : boolean; begin pi := true; repeat Swap(lock, pi ) until pi = false; 临界区； end;

37 信号量与PV操作 同步问题 生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题 问题描述（有界缓冲问题）
生产者（如，计算进程、发送进程） 消费者（如，打印进程、接收进程） 问题描述（有界缓冲问题） 有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界环形缓冲上。其中，pi和ci都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；类似，只要缓冲区不空，消费者ci就可从缓冲区取走并消耗产品。

38 信号量与PV操作 生产者-消费者问题示意 … … … 缓冲区指针： in，生产者进程投入产品指针 out, 消费者进程取产品指针
缓冲区计数器： counter 生产者-消费者问题示意 in C1 P1 1 2 send receive 3 k-1 … … 4 k-2 out 5 k-3 send 6 receive … Cm Pn Buffer

39 信号量与PV操作 生产者-消费者问题算法描述 counter := counter + 1;
if (counter = 1) wakeup (consumer) end; process consumer while (TRUE) begin if (counter = 0) sleep(); nextc := buffer[out]; out := (out + 1) mod k; counter := counter – 1; if (counter = k-1) wakeup (producer) consume the item in nextc; 生产者-消费者问题算法描述 var k: integer; type item: any; buffer: array[0..k-1] of item; in, out: integer := 0; counter: integer := 0; process producer while (TRUE) begin produce an item in nextp; if (counter = k) sleep(); buffer[in] := nextp; in := (in + 1) mod k;

40 信号量与PV操作 生产者-消费者算法存在的问题 解决方法： 由于生产者和消费者进程执行速度的不一致导致：
缓冲器计数器出错 错过等待唤醒 解决方法： 交互进程之间通过交换信号或消息来达到调整相互执行速度，从而保证进程协调运行的目的

41 信号量与PV操作 进程同步机制： 操作系统实现进程同步的机制，通常由同步原语组成 常见的同步机制： 信号量与PV操作 管程 消息传递

42 信号量与PV操作 信号量与PV操作 前述临界区管理方法存在的问题 1965，Dijkstra提出了新的同步机制
软件方法：复杂度高、效率低，将测试能否进入临界区的责任推给用户，降低系统的可靠性，加重用户编程负担 硬件方法：虽然简单，但硬件设施采用忙式等待测试、浪费CPU时间 1965，Dijkstra提出了新的同步机制 同步原语：P(Proberen, 测试)原语, V(Verhogen, 增量)原语 除赋初值外，信号量仅能由同步原语操作

43 信号量与PV操作 信号量的分类 按用途可分为： 按取值可分为： 按信号量的结构： 公用信号量（进程互斥） 私有信号量（进程同步）
二元信号量（0/1，互斥） 一般信号量（非负整数，同步） 按信号量的结构： （简单数据类型）整型信号量 记录型信号量

44 信号量与PV操作 整型信号量（初步） 设s为一正整型量
P(s)：当信号量s大于0时，将信号量s减一，否则调用P(s)的进程等待直至信号量s大于0。 描述： while s <= 0 do null operation //忙式等待 s := s - 1; V(s)：将信号量s加一 s := s + 1;

45 信号量与PV操作 记录型信号量（系统内核实现） s为一个记录型变量，包括两个分量
value，整型量，非负初值 queue，进程队列，初值为空 P(s)：将信号量s的value值减去1，若结果小于0，则调用P(s)的进程被置为等待信号量s的状态，并加入queue队列 V(s)：将信号量s的value值加1，若结果不大于0，则唤醒queue队列中某个等待信号量s的进程

46 信号量与PV操作 记录型信号量，描述： type semaphore = record value : integer;
queue: list of process; end; procedure P (var s: semaphore); begin s.value := s.value – 1; if s.value < 0 then W(s.queue); procedure V (var s: semaphore); s.value := s.value + 1; if s.value <= 0 then R(s.queue);

47 信号量与PV操作 当信号量代表某个物理资源时，关于记录型信号量和PV操作的三个推论
若s.value为正，则该值代表实际还可以使用的物理资源数量 若s.value为负，则其绝对值代表s.queue队列中等待该物理资源的进程数目 P操作意味着请求一个资源（可能被阻塞），V操作意味着释放一个资源（唤醒被阻塞的进程）

48 信号量与PV操作 二元信号量 记录型信号量的一个特例，其value分量仅能取值为0或1
BP(s)：if s.value = 1 then s.value = 0 else w(s.queue); BV(s)：if s.queue is empty then s.value := 1 else R(s.queue); 表达能力等同与一般的记录型信号量（稍有差别）

49 信号量与PV操作 采用记录型信号量实现互斥 与硬件指令实现的区别， 实现互斥的一般形式：
P,V操作只对信号量测试一次（等待），而TS指令需要反复测试（忙等待） 实现互斥的一般形式： var mutex: semaphore; mutex := 1; cobegin … process Pi begin P(mutex); 临界区； V(mutex); end; … coend;

50 信号量与PV操作 记录型信号量与PV操作解决售票问题 var A: Array[1..m] of integer;
mutex: semaphore; mutex := 1; cobegin … process Pi var Xi : integer; begin L1: 按旅客要求找到对应的A[j]; P(mutex); Xi := A[j]; if Xi >= 1 then begin Xi := Xi - 1; A[j] := Xi; V(mutex); 输出一张票； end else 提示票已售完； end; goto L1; end; … coend.

51 信号量与PV操作 记录型信号量与PV操作解决售票问题(改进方案) var A: Array[1..m] of integer;
s: Array[1..m] of semaphore; s[j] := 1; cobegin … process Pi var Xi : integer; begin L1: 按旅客要求找到对应的A[j]; P(s[j]); Xi := A[j]; if Xi >= 1 then begin Xi := Xi - 1; A[j] := Xi; V(s[j]); 输出一张票； end else 提示票已售完； end; goto L1; end; … coend.

52 信号量与PV操作 五个哲学家吃通心面（面条）问题
有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿，然后想吃通心面。为了吃面，每个哲学家必须获得两把叉子，规定每人只能直接从其左边或右边去取叉子

53 信号量与PV操作 五个哲学家吃通心面（面条）问题解决 叉子是共享资源，需要互斥访问
引入五个记录型互斥信号量 每个哲学家吃之前，先对其左右两个叉子所对应的信号量P操作，吃完后，对其进行V操作 上述解决方法，将有可能出现所有哲学家都吃不到通心面而饿死的问题（相互等待） 至多允许四个哲学家同时吃 奇数号先取左手边叉子，偶数号先取右手边叉子 每个哲学家取到手边得两把叉子才吃，否则，一把也不取

54 信号量与PV操作 记录型信号量解决生产者-消费者问题 单个生产者和单个消费者问题 单一产品的多个生产者和多个消费者问题
多类产品的多个生产者和多个消费者问题

55 信号量与PV操作 单个生产者和单个消费者问题 生产者与消费者的同步问题
引如两个信号量，empty, full解决进程间同步问题，取代counter计数器 empty指示生产者是否可以向缓冲区放入产品 full指示消费者是否可从缓冲区获得产品 先生产，后消费，empty.value = k, full.value = 0 生产者，P(empty) 、生产、V(full) 消费者，P(full)、消费、V(empty)

56 信号量与PV操作 单一产品的多个生产者和多个消费者问题 生产者与消费者之间的同步问题 多个生产者之间互斥访问in指针的问题
同单个生产者和单个消费者问题 多个生产者之间互斥访问in指针的问题 多个消费者之间互斥访问out指针的问题 引入mutex信号量，解决互斥问题 既有同步又有互斥信号量的情况下，原则上，用于互斥信号量上的P操作总在后面执行

57 信号量与PV操作 多类产品的多生产者和多消费者问题 一个缓冲区长度为1的多类产品的多生产者和多消费者问题 引入3个信号量
sp，允许放入盘子，初值是缓冲器长度 sg1, 初值为0，允许消费第一类产品 sg2, 初值为0，允许消费第二类产品

58 信号量与PV操作 读者-写者问题 有两类并发进程，读进程与写进程，共享一个文件，为防止出错，要求：1）允许多个读进程同时对文件读；2）只允许一个写进程写信息；3）写进程在没有写完成之前不允许读；4）写之前应该让所有已经在读或写的进程操作完成。 引入一个计数器和两个信号量解决此问题 int rc, 读进程计数器 W，允许写信号量，初值为1 mutex，互斥访问rc计数器信号量，初值为1

59 读者优先的读者-写者问题 var rc: integer; w, mutex: semaphore; rc := 0; w := 1;
procedure read begin P(mutex); rc := rc +1; if rc = 1 then P(W); V(mutex); 读文件； rc := rc – 1; if rc = 0 then V(w); end; procedure wite begin P(w); 写文件； V(w); end;

60 读者-写者问题的进一步思考 读者优先的解决方法，可能会出现写进程无限期被推迟的情况，为解决此问题，可考虑： 公平的读者-写者问题
写者优先的读者-写者问题 pthread提供了读写锁pthread_rwlock_t，对应哪种实现？ 参见pthread教程！

61 读者-写者近似公平的解决方法

62 二元信号量实现一般信号量（错误） typedef struct semaphore { int value;
binary_semaphore wait, mutex; wait = 0; mutex = 1; }; Semaphore S; P(S): BP(S.mutex); S.value -- ; if (S.value < 0) { ① BV(S.mutex); ② BP(S.wait); } else BV(S.mutex); V(S): S.value ++ ; if (S.value <= 0) { ① BV(S.wait); } BV(S.mutex);

63 二元信号量实现一般信号量（正确） typedef struct semaphore { int value;
binary_semaphore wait, mutex; wait = 0; mutex = 1; }; Semaphore S; P(S): BP(S.mutex); S.value -- ; if (S.value < 0) { BV(S.mutex); BP(S.wait); } V(S): S.value ++ ; if (S.value <= 0) { BV(S.wait); } else BV(S.mutex); 有几种实现方法，各有优缺点，参见相关课外阅读资料。

64 信号量与PV操作(理发师问题) 理发师问题
理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师就在理发椅上睡觉。当一个顾客到来后，他必须叫醒理发师。如果理发师正在理发时又有顾客到来，那么，如果有空椅子可坐，顾客就坐下来等待，否则离开理发店。 引入3个信号量和一个控制变量 int waiting, 等候理发师的顾客数，初值为0 customer, 是否有人需要理发，初值为0 barbers，是否有理发师可以理发，初值为0 mutex，互斥信号量，初值为1

65 信号量与PV操作(理发师问题) var waiting: integer; procedure customer
customers, barbers, mutex: semaphore; customers := 0; barbers := 0; mutex := 1; waiting := 0; procedure barber begin while (TRUE) P(customers); P(mutex); waiting := waiting – 1; V(barbers); V(mutex); 理发； end; procedure customer begin P(mutex); if (waiting < n) then waiting := waiting + 1; V(customer); V(mutex); P(barbers); 理发； end else V(mutex); end;

66 管程 为什么引入管程？ 信号量与PV操作存在的问题：
不利于系统对临界资源的管理 难以防止进程有意或无意的违法同步操作 容易造成程序设计错误

67 管程 什么是管程？ 基本思想： 代表共享资源的数据结构及其上操作的一组过程构成了管程
把分散在各进程中的临界区集中起来进行管理，并把系统中的共享资源用数据结构抽象地表示出来。 代表共享资源的数据结构及其上操作的一组过程构成了管程 管程是一种程序设计语言结构成分，和信号量有同等的表达能力

68 管程 管程的基本结构 TYPE <管程名> = MONITOR <管程变量说明>;
define <（能被其他模块引用的）过程列表>; {移出部分} use <（要引用的外部模块定义的）过程列表>; procedure <过程名>(<形式参数>); begin <过程体>; end; … <管程的局部数据初始化语句>; end.

69 管程 管程的工作流程 … 等待调用的进程队列 入口 管程等待区域 局部数据 条件变量 过程1 … 过程k 初始化代码 出口 管程
condition c1 局部数据 wait(c1) 条件变量 … 过程1 condition cn … wait(cn) 过程k urgent queue 初始化代码 signal 出口

70 管程 条件变量： wait同步原语： signal同步原语： 当调用管程过程的进程无法继续运行时，用于阻塞进程的一种信号量

71 管程 使用signal原语释放等待进程时，将有可能出现两个进程同时停留在管程中的情况，这与管程的互斥性相违背，解决方法：

72 管程 管程实现： Hoare方法， Hanson方法，对signal原语进行了限制，仅允许在过程体的最后调用signal原语。
采用PV操作实现进程互斥进入管程，以及对共享资源的互斥访问 Hanson方法，对signal原语进行了限制，仅允许在过程体的最后调用signal原语。

73 Hoare方法实现管程 每个管程需要引入两个信号量和一个计数器 实现wait操作和signal操作，用于进程间在某个特定条件上的同步
TYPE interf = RECORD semaphore mutex = 1，用于互斥方式调用管程过程 semaphore next = 0, 用于发出signal的进程挂起自己 int next_count = 0, 在next上等待的进程数 END; 实现wait操作和signal操作，用于进程间在某个特定条件上的同步 semaphore x_sem = 0，用于在某个特定条件上的同步 int x_count = 0, 在特定条件上等待的进程数 外部过程确保互斥进入管程

74 Hoare方法实现管程 void wait(semaphore x_sem, int x_count, interf IM){
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, interf IM) { if (x_count > 0) { IM.next_count ++; V(x_sem); P(IM.next); IM.next_count --;

75 Hoare方法实现管程 任何外部过程必须采用如下形式，才能保证互斥进入管程 P(IM.mutex) … //过程体
if (IM.next_count > 0) V(IM.next); else V(IM.mutex);

76 管程实现生产者消费者问题

77 pthread-mutex,condition实现生产者消费者问题

78 管程方式实现哲学家进餐问题 TYPE dining-philosophers = MONITOR
var state:array[0..4] of (thinking, hungry, eating); self:array[0..4] of condition; define pickup, putdown; use wait, signal; produce test(k:0..4) begin if (state[(k-1) mod 5] <> eating) and (state[k] = hungry) and (state[(k+1) mod 5] <> eating) then begin state[k] := eating; signal(self[k], s-count[k], IM); end;

79 管程方式实现哲学家进餐问题 procedure pickup(i:0..4) begin state[i] := hungry;
test(i); if (state[i] <> eating) then wait(self[i], s-count[i], IM); end; procedure putdown(i:0..4) state[i] := thinking; test((i – 1) mod 5); test((i + 1) mod 5); for i:=0 to 4 do state[i] := thinking; end

80 管程 管程与进程的区别 管程定义公共数据结构；进程定义私有数据结构 管程把共享变量上的同步操作集中在一起；而临界区则分散在各进程中
管程为管理共享资源而建立；进程为占有资源和实现系统并发而存在 管程与调用它的进程串行工作；而进程之间可并行工作 管程是语言和操作系统的成分，具有静态性；进程是动态的，存在生命周期，需要创建和撤消

81 进程通信 为什么需要进程通信？ 进程间的交互需要进程间存在通信机制 竞争－互斥（特殊的同步） 协作－同步 交换数据

82 进程通信 常见的通信机制 信号通信 共享文件 共享存储区 消息传递

83 进程通信 信号通信机制, signal,Minix中sigaction系统调用
信号通信又称软中断，是一种简单的通信机制，通过发送一个特定的信号来通知进程某个异常事件发生 信号可以是内核发送给进程，也可以是一个进程发送给另一个进程 例：SIGLD、SIGHUP、SIGKILL、SIGCHLD等信号用于进程的终止

84 进程通信 共享文件通信机制 又称管道通信，引入一个特殊的称之为管道的共享文件连接两个读写进程
管道(pipeline)，允许进程按先进先出的方式传送数据，也能使进程同步执行操作 字节流 字节流 共享文件 P1写进程 P2读进程

85 进程通信 共享文件通信机制的实现 可借助于文件系统的机制实现，包括管道文件的创建、打开、关闭和读写。
进程对共享文件互斥使用，即一个进程正在读或写时，另一个进程必须等待。 由于共享文件有大小限制，因此通信进程之间必须能够正确的同步 通信双方必须知道对方是否存在

86 进程通信 有名管道或FIFO通信机制(UNIX) 普通管道机制的缺陷
仅能连接具有共同祖先的进程 管道具有临时性，难以提供全局服务 一种永久性通信机制，具有Unix文件名、访问权限，并且性能与普通的管道相同

87 进程通信 共享存储区通信机制 是进程通信中最快捷和有效的方法 具体过程：
向系统共享存储区申请一个分区段，并指定关键字；若系统已为其他进程分配了该分区，则返回对应的关键字给申请者。 分区段连接到进程的虚地址空间，进程可通过对该区段的读、写来直接通信

88 进程通信 共享存储区通信机制示例 A进程 共享存储区 … B进程 内核

89 进程通信 消息传递机制（基本概念） 信号→消息，低级→高级，信息的规模扩大 消息，是一组信息，由消息头和消息体组成。
两个基本的消息传递原语：send, receive send, receive可以实现为同步操作也可实现为异步操作（一般实现为异步send，同步receive）

90 死锁 死锁的产生 死锁的定义 死锁的防止 死锁的避免 死锁的检测和解除

91 死锁 死锁的产生 计算机系统中存在许多独占资源，如 为保证有效管理，独占资源的使用必须经历：
硬件资源：磁带机、绘图仪等 软件资源：进程表、临界区等 为保证有效管理，独占资源的使用必须经历： 申请资源，若资源不可用，则申请者进入等待状态 使用资源 归还资源 当一个进程需要独占多个资源，而操作系统允许多个进程并发执行共享系统资源时，可能会出现进程永远处于等待状态的现象（死锁）

92 死锁 死锁举例 进程推进顺序不当产生死锁 进程P ①请求读卡机 ②请求打印机 … ③释放读卡机 ④释放打印机 进程Q ①请求打印机
②请求读卡机 … ③释放读卡机 ④释放打印机 产生死锁的执行序列 P① Q① P② Q②

93 死锁 死锁举例 PV操作使用不当产生死锁（与前例类似） 同类资源分配不当引起死锁 对临时性资源使用不加限制引起死锁
S1 S2 S3 死锁举例 PV操作使用不当产生死锁（与前例类似） 死锁也可能在不包括资源的情况下产生 同类资源分配不当引起死锁 5个同类资源，5个请求进程，每个进程需要请求2个资源才能继续执行，并最终运行结束 按照轮流分配，每次分配一个资源的分配方式将导致死锁 对临时性资源使用不加限制引起死锁 进程通信中，信件是临时性资源，使用不当出现死锁 P1等P3的信件S3到达后向P2发送信件S1 P2等P1的信件S1到达后向P3发送信件S2 P3等P2的信件S2到达后向P1发送信件S3

94 死锁 死锁产生的因素 系统拥有资源的数量 资源分配策略 进程对资源的要求 并发进程的推进顺序

95 死锁 死锁的定义 为避免与硬件故障以及其他程序性错误混淆，在定义死锁前给定六个假设：
任意一个进程要求资源的最大数量不超过系统能提供的最大量 如果一个进程要求的资源均得到满足，那么，它一定能够在有限时间内结束 一个资源在任何时间最多只被一个进程所占有 一个进程一次申请一个资源，且只有在申请资源得不到满足时才处于等待状态 一个进程结束时释放它占有的全部资源 系统具有有限个进程和有限个资源 一组进程处于死锁状态是指：如果在一个进程集合中得每个进程都在等待只能由该集合中其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。

96 死锁 由于死锁会造成很大的损失，因此必须花费额外的代价解决死锁问题，常见的解决死锁问题的方法： 死锁的防止 死锁的避免
死锁的检测和恢复（解除）

97 死锁 死锁的防止 死锁产生的四个条件，1971年Coffman 破坏死锁的任一条件，可以防止死锁 常见的死锁防止方法 互斥条件
占有和等待条件 不剥夺条件 循环等待条件 破坏死锁的任一条件，可以防止死锁 常见的死锁防止方法 静态分配策略，破坏第二个条件，资源利用率低 层次分配策略，破坏第四个条件 死锁存在的必要条件

98 死锁 死锁的避免 破坏死锁条件能够防止死锁，但将导致低效的进程运行和资源使用率
死锁的避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配，从而避免死锁的发生 常见的方法： 资源轨迹图 银行家算法

99 死锁 死锁的避免 √ 资源轨迹图 A, B两个进程；打印机、绘图仪两种资源 t时刻，如何分配资源？ B I8 A,B进程同时拥有一个资源
╳ I6 打印机 ╳ I5 t 绘图仪 r s A,B进程同时拥有两个资源 A p q I1 I2 I3 I4 打印机 绘图仪

100 死锁 资源轨迹图的优缺点 优点： 比较直观和简单 缺点： 只适合在两个进程间进行判断 只适合描述只有单个实例的资源

101 死锁 死锁的避免 银行家算法 前提条件： 每个客户必须预先说明自己所要求的最大资金量； 每个客户每次提出部分资金量申请和获得分配； 如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还； 若一个所要求的最大资金量不超过其资金总量，则银行家一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。 关键问题是，对资金申请进行判断，又称“资源分配拒绝法”

102 死锁 银行家对资金申请的判断依据是，如果满足该申请，是否存在一个安全状态序列使所有客户均能得到所有的贷款（所有进程得到其所需的全部资源并执行终止） 例： 银行家有10个单位的资金，共有四个客户需要申请贷款，每个客户均提供了一个贷款额度，如下图所示： 客户 已贷款 最大 张三 1 6 李四 5 王五 2 4 赵六 7 ①是否可满足李四请求1个单位资金？ ②是否可满足王五请求1个单位资金？ 可用：2

103 如果分配1个单位的资金给李四，则资金分配状态如下：
死锁 ①判断是否可以满足李四一个单位的资金申请 如果分配1个单位的资金给李四，则资金分配状态如下： 客户 已贷款 最大 张三 1 6 李四 2 5 王五 4 赵六 7 可用：1 在该状态下，可用资金无法满足任何一个客户的最大贷款额度，因此该状态是不安全的，应拒绝李四的贷款申请，让李四等待。

104 如果分配1个单位的资金给王五，则资金分配状态如下：
死锁 ②判断是否可以满足王五一个单位的资金申请 如果分配1个单位的资金给王五，则资金分配状态如下： 客户 已贷款 最大 张三 1 6 李四 5 王五 3 4 赵六 7 可用：1 在该状态下，存在一个安全序列，“王五、李四、张三、赵六”。因此该状态是安全的，可以满足王五的资金申请。

105 死锁 多种资源的银行家算法 定义数据结构描述进程和资源的相关信息
系统每类资源的总数——m个元素的向量，每个分量对应一类资源的总数：Resource = (R1, R2, …, Rm)； 每类资源未分配数量——m个元素的向量，每个分量对应一类资源尚可分配的数量：Available = (V1, V2, …, Vm)； 最大需求矩阵——n*m，行代表n个进程，列代表m类资源，Claim，其中元素Cij表示进程Pi需要Rj类资源最大数； 分配矩阵——n*m，行代表n个进程，列代表m类资源，Allocation，其中元素Aij表示进程Pi已分得Rj类资源得数量；

106 死锁 安全性测试算法执行举例 设有五个进程{P0, P1, P2, P3, P4}和A, B, C三类资源，A类资源共有10个，B类资源共有5个，C类资源共有7个，在T0时刻系统的资源分配情况如下： Resource = (10, 5, ) Available = (3, 3, ) 0 1 0 0 0 0 2 1 1 0 0 2 Claim = 7 5 3 3 2 2 9 0 2 2 2 4 3 3 Allocation =

107 Currentavil+allocation
Available = (3, 3, 2) Claim = 7 5 3 3 2 2 9 0 2 2 2 4 3 3 死锁 安全性测试算法执行举例（续） 资源\进程 CurrentAvil Cki-Aki Allocation Currentavil+allocation Possible A B C P0 1 P1 2 P2 3 P3 P4 7 4 3 T 1 2 T 6 T 1 T 4 3 1 T Resource = (10, 5, 7)

108 死锁 银行家算法的缺点： 进程很难在运行前知道其所需资源的最大值 系统中各进程之间必须是无关的，即没有同步要求，无法处理有同步关系的进程
进程的数量和资源的数目是固定不变的，无法处理进程数量和资源数目动态变化的情况

109 死锁 死锁的检测和解除 资源分配图 死锁检测算法 死锁解除方法

110 死锁 死锁的检测和解除 资源分配图 描述进程和资源间申请及分配关系的一种有向图 节点集： 进程类集，P = {P1, P2, …, Pn}
资源类集，R = {R1, R2, …, Rm} 边集 E： 申请边，例 Pi→Rj 分配边，例 Ri→Pj

111 死锁 . . . . . . . 资源分配图例 设有P = {P1, P2, P3}, R = {R1, R2, R3, R4},
E = {P1→R1, P2→R3, R1→P2, R2→P2, R2→P1, R3→P3} R1 R3 . . P1 P2 P3 . . . . . R2 R4

112 死锁 死锁的检测 如果每个资源类型只有一个实例，那么资源分配图中出现环则意味着出现死锁
如果每个资源类型有多个实例，那么环并不意味着已经出现死锁 资源分配图中的环是死锁存在的必要条件，而非充分条件

113 死锁 死锁检测算法 如果资源分配图中无环，则没有发生死锁 如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生死锁
如果资源分配图中有环路，但涉及的资源类中有多个资源实例，则对该图进行简化，直至所有进程成为孤立点，称该有向图可完全化简。如果有向图可完全化简，则系统没有死锁发生，否则出现死锁。

114 死锁 死锁检测算法 完全化简实例 R1 . P1 P2 . . R2

115 死锁 死锁的解除 进程终止 资源抢占 终止所有死锁进程 一次终止一个进程，直至死锁解除 逐步从进程中抢占资源给其他进程使用，直到死锁被打破
每终止一个进程，都必须调用死锁检测算法以确定进程是否仍处于死锁状态 资源抢占 逐步从进程中抢占资源给其他进程使用，直到死锁被打破 选择被抢占进程 回滚问题 饥饿问题