《并发进程控制讲义》由会员分享，可在线阅读，更多相关《并发进程控制讲义（115页珍藏版）》请在金锄头文库上搜索。
1、*操作系统（并发进程）徐锋南京大学计算机科学与技术系主要内容并发进程概述临界区管理信号量与PV操作管程进程通信死锁并发进程概述顺序程序设计将一个程序设计成为一个顺序执行的程序模块，不同的程序也是按顺序执行。特点： （程序与程序的执行一一对应）执行的顺序性内部顺序性、外部顺序性环境的封闭性执行结果的确定性计算过程的可再现性并发进程概述顺序程序设计举例某程序需要循环执行输入、计算、输出三个过程while(TRUE) input; process; output;input 78ms, process 52ms, output 20msI1P1O1I2P2O2串行执行并发进程概述顺序程序设计举例,处
2、理器效率处理器的利用率 = 52n/(78n + 52n + 20n) = 52/150 35% 7878输入机输入机处理器处理器磁带机磁带机130130150150228228280280300300378378430430450450时时 间间并发进程概述顺序程序设计优缺点：程序编制、调试方便计算机系统效率较低并发进程概述并发程序设计将一个程序分成若干个可同时执行的程序模块，每个程序模块和它执行时所处理的数据就组成了一个进程。特点：并发性共享性制约性交互性并发进程概述进程的并发性一组进程在执行时间上重叠，一个进程执行的第一条指令是在另一个进程执行的最后一条指令完成之前开始的宏观：在一个时间
3、段中几个进程同时处于活动状态微观：任一时刻仅有一个进程在处理器上运行实质：一个CPU在几个进程之间的多路复用并发进程概述并发程序设计举例一（相关进程）某程序需要循环执行输入、计算、输出三个过程设计为三个可并行执行的程序模块while(TRUE) input; send; 78mswhile(TRUE) receive; process; send; 52msWhile(TRUE) receive; output; 20ms三个进程通过缓冲区交换信息Ii缓冲区1Pi缓冲区2Oisendsendreceivereceive并发进程概述并发程序设计举例一IPOt1t2t3进程时间I1I2I3P1P2
4、P3O1O2O3并发进程概述并发程序设计举例一，处理器效率7878输入机输入机处理器处理器磁带机磁带机130130150150228228306306208208286286384384364364时时 间间处理器的利用率 = 52n/(78n + 52 + 20) 67%, 当n 并发进程概述并发程序设计举例二（无关进程）进程A，由指令a1, a2, a3组成；进程B，由指令b1, b2, b3组成。A与B并发执行，则实际的指令执行序列？a1a2a3b1b2b3a1b1a2a3b2b3b1a1b2a2b3a3b1b2a1a2a3b3并发进程概述并发进程间的关系无关一组并发进程分别在不同的变量
5、集合上操作，一个进程的执行与其他并发进程的执行进度无关交互（往）一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果并发进程概述无关的并发进程判断并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为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) = 则并发进程的执行与时间无关并发进程概述无关的并发进程判断举例有如下四个进程：P1: a
6、= 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) = cW(P1) = a, W(P2) = b, W(P3) = c, W(P4) = wP1和P2的上述集合满足Bernstein条件，可并发执行。并发进程概述并发进程间的交互（往）竞争关系（间接制约关系）解决手段，进程互斥访问若干个进程要访问同一共享资源时，任何时刻最多允许一个进程访问，其他进程必须等待，直到占有资源的进程释放该资源协作关系（直接制约关系）解决手段，进程同
7、步两个以上的进程基于某个条件来协调它们的活动。一个进程的执行依赖于其协作进程的消息或信号，当没有得到该消息或信号时需要等待，直到消息或信号到达时被唤醒进程的互斥关系是一种特殊的进程同步关系并发进程概述并发程序设计的优点：对于单处理器系统，可让处理器和个I/O设备同时工作，发挥硬件的并行能力对于多处理器系统，可让各进程在不同的处理器上并行执行，加快计算速度简化程序设计任务并发进程概述采用并发程序设计的目的充分发挥硬件的并行工作能力，提高系统效率是多道程序设计的基础并发进程概述有交互关系的并发进程执行时带来的问题由于一组有交互关系的并发进程，其执行的相对速度无法控制，导致出现多种与时间有关的错误出
8、现与时间有关错误的表现形式：结果不唯一永远等待并发进程概述结果不唯一错误举例，订票问题process Ti ( i = 1, 2 ) var Xi:integer;begin按旅客定票要求找到按旅客定票要求找到A Aj j；Xi := Aj;if Xi=1 then begin Xi:=Xi-1; Aj:=Xi; 输出一张票输出一张票；endelse 输出票已售完输出票已售完；end;并发进程概述永远等待错误举例，内存管理问题procedure borrow (var B:integer) begin if Bx then 申请进程进入等待队列等主存资源申请进程进入等待队列等主存资源 x:=x
9、-B; 修改主存分配表，申请进程获得主存资源修改主存分配表，申请进程获得主存资源 end;procedure return (var B:integer) begin x:=x+B; 修改主存分配表修改主存分配表 释放等主存资源的进程释放等主存资源的进程 end;临界区管理临界区：并发进程中与共享变量有关的程序段，称为临界区(Critical Section)临界资源：共享变量代表的资源，称为临界资源(Critical Resource)临界区管理：保证一个进程在临界区执行时，不让另一各进程进入相关的临界区。（实现对共享变量的互斥访问）临界区管理临界区调度的原则一次至多一个进程能够进入它的临界
10、区不能让一个进程无限地留在临界区不能强迫一个进程无限等待进入临界区“无空等待、有空让进、择一而入、算法可行”临界区管理临界区的描述临界资源（共享变量）shared 变量名临界区region 变量名 do 语句（复合语句）临界区的嵌套例，region X do ; region Y do ; 嵌套可能导致进程无限地留在临界区临界区管理临界区管理的尝试引入进程标志，分别指示进程进入临界区的情况第一种尝试，先测试，后置位不能保证同一时间只有一个进程进入临界区第二种尝试，先置位，后测试会出现死循环的情况，永远等待临界区管理临界区管理的尝试(1)inside1,inside2:Booleaninside
11、1,inside2:Booleaninside1 := false; /* P1inside1 := false; /* P1不在其临界区内不在其临界区内 */ */inside2 := false; /* P2inside2 := false; /* P2不在其临界区内不在其临界区内 */ */cobegincobeginprocess P1process P1BeginBegin while inside2 do begin end;while inside2 do begin end; inside1 := true;inside1 := true; 临界区临界区; ; inside1
12、:= false;inside1 := false; end; end; process P2 process P2 Begin Begin while inside1 do begin end;while inside1 do begin end; inside2 = true;inside2 = true; 临界区临界区; ; inside2 := false;inside2 := false; end; end;coendcoend临界区管理临界区管理的尝试(2)inside1,inside2:Booleaninside1,inside2:Booleaninside1 := false;
13、 /* P1inside1 := false; /* P1不在其临界区内不在其临界区内 */ */inside2 := false; /* P2inside2 := false; /* P2不在其临界区内不在其临界区内 */ */cobegincobeginprocess P1process P1BeginBegin inside1 := true;inside1 := true; while inside2 do begin end;while inside2 do begin end; 临界区临界区; ; inside1 := false;inside1 := false; end; en
14、d; process P2 process P2 Begin Begin inside2 = true;inside2 = true; while inside1 do begin end;while inside1 do begin end; 临界区临界区; ; inside2 := false;inside2 := false; end; end;coendcoend临界区管理实现临界区管理的软件方法Dekker算法Peterson算法临界区管理Dekker算法，采用指示器变量turn来指示该由哪个进程进入临界区具体实现：/ / 变量定义及初始化变量定义及初始化var inside : a
15、rray1.2 of var inside : array1.2 of boolean;boolean;turn :integer;turn :integer;turn := 1 or 2; turn := 1 or 2; inside1:=false;inside1:=false;inside2:=false;inside2:=false;临界区管理Dekker算法（续）cobegin process P1begin inside1:=true; while inside2 do if turn=2 then begin inside1:=false; while turn=2 do beg
16、in end; inside1:=true; end 临界区临界区; turn = 2； inside1:=false;end;process P2begin inside2:=true; while inside1 do if turn=1 then begin inside2:=false; while turn=1 do begin end; inside2:=true; end 临界区临界区; turn = 1； inside2:=false;end;coend.临界区管理Dekker算法（续）基本思想：进程P1(或P2)进入自己的临界区时，把自己的标志位insidei置为true，并
17、检查对方标志位如果对方不在也不想进入临界区，进程Pi可立即进入临界区；如果双方都想进入，咨询指示器turn，若turn为1(或为2)，P1(或P2)知道应该自己进入缺点：算法复杂难以理解临界区管理Peterson算法基本思想：用对turn的置值和while语句来限制每次只有一个进程进入临界区；进程执行完临界区程序后，修改insidei状态使等待进入临界区的进程可在有限时间内进入。算法满足临界区管理的三个条件。临界区管理Peterson算法算法描述（1）/ 变量定义及初始化var inside: array1.2 of boolean;turn : integer;turn := 1 or 2;
18、inside1 := false;inside2 := false;临界区管理Peterson算法算法描述（2）cobeginprocess P1begin inside1 := true; turn := 2; while (inside2 and turn = 2) do begin end; 临界区； inside1 := false;end;process P2begin inside2 := true; turn := 1; while (inside1 and turn = 1) do begin end; 临界区； inside2 := false;end;coend.临界区管理
19、实现临界区管理的硬件方法关中断（阻止进程交替执行）测试并建立指令，TS （测试与上锁不能分离）TS(x): 若x = true, 则x := false; return true; 否则return false;实现：var s: boolean; s := true;process Pivar pi : boolean;begin repeat pi := TS(s) until pi; 临界区； s := true;end; 临界区管理实现临界区管理的硬件方法对换指令，SwapSwap(a,b): temp := a; a := b; b := temp; 例如：XCHG指令实现：var
20、lock : boolean; lock := false;process Pivar pi : boolean;begin pi := true; repeat Swap(lock, pi ) until pi = false; 临界区； lock := false;end;信号量与PV操作同步问题生产者-消费者问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题生产者（如，计算进程、发送进程）消费者（如，打印进程、接收进程）问题描述（有界缓冲问题）有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界环形缓冲上。其中，pi和ci都是并发进程，只要缓冲区未满，生产者pi
21、生产的产品就可投入缓冲区；类似，只要缓冲区不空，消费者ci就可从缓冲区取走并消耗产品。信号量与PV操作生产者-消费者问题示意P1PnC1CmBuffer1230456k-1k-2k-3sendsendreceivereceive缓冲区指针：in，生产者进程投入产品指针out, 消费者进程取产品指针缓冲区计数器：counterinout信号量与PV操作生产者-消费者问题算法描述var k: integer; type item: any; buffer: array0.k-1 of item; in, out: integer := 0; counter: integer := 0;proces
22、s producer while (TRUE) begin produce an item in nextp; if (counter = k) sleep(); bufferin := nextp; in := (in + 1) mod k; counter := counter + 1; if (counter = 1) wakeup (consumer) end;process consumer while (TRUE) begin if (counter = 0) sleep(); nextc := bufferout; out := (out + 1) mod k; counter
23、:= counter 1; if (counter = k-1) wakeup (producer) consume the item in nextc; end;信号量与PV操作生产者-消费者算法存在的问题由于生产者和消费者进程执行速度的不一致导致：缓冲器计数器出错错过等待唤醒解决方法：交互进程之间通过交换信号或消息来达到调整相互执行速度，从而保证进程协调运行的目的信号量与PV操作进程同步机制：操作系统实现进程同步的机制，通常由同步原语组成常见的同步机制：信号量与PV操作管程消息传递信号量与PV操作信号量与PV操作前述临界区管理方法存在的问题软件方法：软件方法：复杂度高、效率低，将测试能否进
24、入临界区的责任推给用户，降低系统的可靠性，加重用户编程负担硬件方法硬件方法：虽然简单，但硬件设施采用忙式等待测试、浪费CPU时间1965，Dijkstra提出了新的同步机制信号量与PV操作同步原语：P(Proberen, 测试)原语, V(Verhogen, 增量)原语除赋初值外，信号量仅能由同步原语操作信号量与PV操作信号量的分类按用途可分为：公用信号量（进程互斥）私有信号量（进程同步）按取值可分为：二元信号量（0/1，互斥）一般信号量（非负整数，同步）按信号量的结构：（简单数据类型）整型信号量记录型信号量信号量与PV操作整型信号量（初步）设s为一正整型量P(s)：当信号量s大于0时，将信号
25、量s减一，否则调用P(s)的进程等待直至信号量s大于0。描述： while s = 0 do null operation /忙式等待 s := s - 1;V(s)：将信号量s加一描述： s := s + 1;信号量与PV操作记录型信号量（系统内核实现）s为一个记录型变量，包括两个分量value，整型量，非负初值queue，进程队列，初值为空P(s)：将信号量s的value值减去1，若结果小于0，则调用P(s)的进程被置为等待信号量s的状态，并加入queue队列V(s)：将信号量s的value值加1，若结果不大于0，则唤醒queue队列中某个等待信号量s的进程信号量与PV操作记录型信号量，描
26、述： 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); end; procedure V (var s: semaphore); begin s.value := s.value + 1; if s.value = 1 then begin Xi := Xi - 1; Aj := Xi; V(mutex); 输出一张票； end
27、 else begin V(mutex); 提示票已售完； end; goto L1;end; coend.信号量与PV操作记录型信号量与PV操作解决售票问题(改进方案)var A: Array1.m of integer; s: Array1.m of semaphore;sj := 1;cobegin process Pi var Xi : integer; begin L1: 按旅客要求找到对应的Aj; P(sj); Xi := Aj; if Xi = 1 then begin Xi := Xi - 1; Aj := Xi; V(sj); 输出一张票； end else begin V(
28、sj); 提示票已售完； end; goto L1;end; coend.信号量与PV操作五个哲学家吃通心面（面条）问题有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。每个哲学家思考、饥饿，然后想吃通心面。为了吃面，每个哲学家必须获得两把叉子，规定每人只能直接从其左边或右边去取叉子信号量与PV操作五个哲学家吃通心面（面条）问题解决叉子是共享资源，需要互斥访问引入五个记录型互斥信号量每个哲学家吃之前，先对其左右两个叉子所对应的信号量P操作，吃完后，对其进行V操作上述解决方法，将有可能出现所有哲学家都吃不到通心面而饿死的问题（相互等待）至多允许四个哲学
29、家同时吃奇数号先取左手边叉子，偶数号先取右手边叉子每个哲学家取到手边得两把叉子才吃，否则，一把也不取信号量与PV操作记录型信号量解决生产者-消费者问题单个生产者和单个消费者问题单一产品的多个生产者和多个消费者问题多类产品的多个生产者和多个消费者问题信号量与PV操作单个生产者和单个消费者问题生产者与消费者的同步问题引如两个信号量，empty, full解决进程间同步问题，取代counter计数器empty指示生产者是否可以向缓冲区放入产品full指示消费者是否可从缓冲区获得产品先生产，后消费，empty.value = k, full.value = 0生产者，P(empty) 、生产、V(fu
30、ll)消费者，P(full)、消费、V(empty)信号量与PV操作单一产品的多个生产者和多个消费者问题生产者与消费者之间的同步问题同单个生产者和单个消费者问题多个生产者之间互斥访问in指针的问题多个消费者之间互斥访问out指针的问题引入mutex信号量，解决互斥问题既有同步又有互斥信号量的情况下，原则上，用于互斥信号量上的P操作总在后面执行信号量与PV操作多类产品的多生产者和多消费者问题一个缓冲区长度为1的多类产品的多生产者和多消费者问题引入3个信号量sp，允许放入盘子，初值是缓冲器长度sg1, 初值为0，允许消费第一类产品sg2, 初值为0，允许消费第二类产品信号量与PV操作读者-写者问题
31、有两类并发进程，读进程与写进程，共享一个文件，为防止出错，要求：1）允许多个读进程同时对文件读；2）只允许一个写进程写信息；3）写进程在没有写完成之前不允许读；4）写之前应该让所有已经在读或写的进程操作完成。引入一个计数器和两个信号量解决此问题int rc, 读进程计数器W，允许写信号量，初值为1mutex，互斥访问rc计数器信号量，初值为1 读者优先的读者-写者问题var rc: integer;w, mutex: semaphore;rc := 0;w := 1;mutex := 1;procedure readbeginP(mutex);rc := rc +1;if rc = 1 the
32、n P(W);V(mutex);读文件； P(mutex);rc := rc 1;if rc = 0 then V(w);V(mutex);end;procedure witebegin P(w); 写文件； V(w);end;读者-写者问题的进一步思考读者优先的解决方法，可能会出现写进程无限期被推迟的情况，为解决此问题，可考虑：公平的读者-写者问题写者优先的读者-写者问题pthread提供了读写锁pthread_rwlock_t，对应哪种实现？读者-写者近似公平的解决方法二元信号量实现一般信号量（错误）typedef struct semaphore int value; binary_se
33、maphore 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): BP(S.mutex); S.value + ; if (S.value = 0) BV(S.wait); BV(S.mutex);二元信号量实现一般信号量（正确）typedef struct semaphore int value; binary_semaphore wait, mutex;wait =
34、0; mutex = 1;Semaphore S;P(S):BP(S.mutex);S.value - ;if (S.value 0) BV(S.mutex);BP(S.wait); BV(S.mutex);V(S):BP(S.mutex);S.value + ;if (S.value = 0) BV(S.wait); else BV(S.mutex);信号量与PV操作(理发师问题)理发师问题理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师就在理发椅上睡觉。当一个顾客到来后，他必须叫醒理发师。如果理发师正在理发时又有顾客到来，那么，如果有空椅子可坐，顾客就坐
35、下来等待，否则离开理发店。引入3个信号量和一个控制变量int waiting, 等候理发师的顾客数，初值为0customer, 是否有人需要理发，初值为0barbers，是否有理发师可以理发，初值为0mutex，互斥信号量，初值为1信号量与PV操作(理发师问题)var waiting: integer;customers, barbers, mutex: semaphore;customers := 0; barbers := 0; mutex := 1; waiting := 0;procedure barberbegin while (TRUE) begin P(customers); P
36、(mutex); waiting := waiting 1; V(barbers); V(mutex);理发； end;end; procedure customerbegin P(mutex); if (waiting n) then begin waiting := waiting + 1; V(customer); V(mutex); P(barbers); 理发； end else V(mutex);end;管程为什么引入管程？信号量与PV操作存在的问题：使用信号量与PV操作实现同步时，对共享资源的管理分散在各进程中，进程能够直接对共享变量进行修改，这很可能导致：不利于系统对临界资源的
37、管理难以防止进程有意或无意的违法同步操作容易造成程序设计错误管程什么是管程？基本思想：把分散在各进程中的临界区集中起来进行管理，并把系统中的共享资源用数据结构抽象地表示出来。代表共享资源的数据结构及其上操作的一组过程构成了管程管程是一种程序设计语言结构成分，和信号量有同等的表达能力管程管程的基本结构TYPE = MONITOR;define ; 移出部分use ;procedure (); begin ; end; begin ;end.管程管程的工作流程condition c1wait(c1)condition cn wait(cn)urgent queue signal局部数据条件变量过程
38、1过程k出口初始化代码入口管程等待调用的进程队列管程等待区域管程条件变量：当调用管程过程的进程无法继续运行时，用于阻塞进程的一种信号量wait同步原语：当一个管程过程无法继续时，它在某个条件变量上执行wait原语，将使调用该管程过程的进程阻塞signal同步原语：另一个进程可以通过对其伙伴进程在等待同一个条件变量上执行signal原语，以唤醒该等待进程管程使用signal原语释放等待进程时，将有可能出现两个进程同时停留在管程中的情况，这与管程的互斥性相违背，解决方法：执行signal的进程等待，直到唤醒的进程退出管程或等待另一条件被释放的进程等待，直到执行signal的进程退出管程或等待另一条
39、件管程管程实现：Hoare方法，采用第一种方法解决signal原语导致两个进程同时在管程中的情况采用PV操作实现进程互斥进入管程，以及对共享资源的互斥访问Hanson方法，对signal原语进行了限制，仅允许在过程体的最后调用signal原语。Hoare方法实现管程每个管程需要引入两个信号量和一个计数器TYPE interf = RECORDsemaphore mutex = 1，用于互斥方式调用管程过程semaphore next = 0, 用于发出signal的进程挂起自己int next_count = 0, 在next上等待的进程数 END;实现wait操作和signal操作，用于进程
40、间在某个特定条件上的同步semaphore x_sem = 0，用于在某个特定条件上的同步int x_count = 0, 在特定条件上等待的进程数外部过程确保互斥进入管程Hoare方法实现管程void wait(semaphore x_sem, int x_count, interf IM)x_count+;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_c
41、ount +;V(x_sem);P(IM.next);IM.next_count -;Hoare方法实现管程 任何外部过程必须采用如下形式，才能保证互斥进入管程P(IM.mutex) /过程体if (IM.next_count 0) V(IM.next);elseV(IM.mutex);管程实现生产者消费者问题pthread-mutex,condition实现生产者消费者问题管程方式实现哲学家进餐问题TYPE dining-philosophers = MONITORvar state:array0.4 of (thinking, hungry, eating); self:array0.4
42、of condition;define pickup, putdown;use wait, signal;produce test(k:0.4)beginif (state(k-1) mod 5 eating) and (statek = hungry) and (state(k+1) mod 5 eating) then beginstatek := eating;signal(selfk, s-countk, IM);end;end;管程方式实现哲学家进餐问题procedure pickup(i:0.4)beginstatei := hungry;test(i);if (statei ea
43、ting) then wait(selfi, s-counti, IM);end;procedure putdown(i:0.4)beginstatei := thinking;test(i 1) mod 5);test(i + 1) mod 5);end;beginfor i:=0 to 4 do statei := thinking;end管程管程与进程的区别管程定义公共数据结构；进程定义私有数据结构管程把共享变量上的同步操作集中在一起；而临界区则分散在各进程中管程为管理共享资源而建立；进程为占有资源和实现系统并发而存在管程与调用它的进程串行工作；而进程之间可并行工作管程是语言和操作系统的
44、成分，具有静态性；进程是动态的，存在生命周期，需要创建和撤消进程通信为什么需要进程通信？进程间的交互需要进程间存在通信机制竞争互斥（特殊的同步）协作同步交换数据进程通信常见的通信机制信号通信共享文件共享存储区消息传递进程通信信号通信机制, signal,Minix中sigaction系统调用信号通信又称软中断，是一种简单的通信机制，通过发送一个特定的信号来通知进程某个异常事件发生信号可以是内核发送给进程，也可以是一个进程发送给另一个进程例：SIGLD、SIGHUP、SIGKILL、SIGCHLD等信号用于进程的终止进程通信共享文件通信机制又称管道通信，引入一个特殊的称之为管道的共享文件连接两个
45、读写进程管道(pipeline)，允许进程按先进先出的方式传送数据，也能使进程同步执行操作P1写进程共享文件P2读进程字节流字节流进程通信共享文件通信机制的实现可借助于文件系统的机制实现，包括管道文件的创建、打开、关闭和读写。进程对共享文件互斥使用，即一个进程正在读或写时，另一个进程必须等待。由于共享文件有大小限制，因此通信进程之间必须能够正确的同步通信双方必须知道对方是否存在进程通信有名管道或FIFO通信机制(UNIX)普通管道机制的缺陷仅能连接具有共同祖先的进程管道具有临时性，难以提供全局服务一种永久性通信机制，具有Unix文件名、访问权限，并且性能与普通的管道相同进程通信共享存储区通信机
46、制是进程通信中最快捷和有效的方法具体过程：向系统共享存储区申请一个分区段，并指定关键字；若系统已为其他进程分配了该分区，则返回对应的关键字给申请者。分区段连接到进程的虚地址空间，进程可通过对该区段的读、写来直接通信进程通信共享存储区通信机制示例A进程B进程共享存储区内核进程通信消息传递机制（基本概念）信号消息，低级高级，信息的规模扩大消息，是一组信息，由消息头和消息体组成。两个基本的消息传递原语：send, receivesend, receive可以实现为同步操作也可实现为异步操作（一般实现为异步send，同步receive）死锁死锁的产生死锁的定义死锁的防止死锁的避免死锁的检测和解除死锁死
47、锁的产生计算机系统中存在许多独占资源，如硬件资源：磁带机、绘图仪等软件资源：进程表、临界区等为保证有效管理，独占资源的使用必须经历：申请资源，若资源不可用，则申请者进入等待状态使用资源归还资源当一个进程需要独占多个资源，而操作系统允许多个进程并发执行共享系统资源时，可能会出现进程永远处于等待状态的现象（死锁）死锁死锁举例进程推进顺序不当产生死锁进程P请求读卡机请求打印机释放读卡机释放打印机进程Q请求打印机请求读卡机释放读卡机释放打印机产生死锁的执行序列PQPQ死锁死锁举例PV操作使用不当产生死锁（与前例类似）死锁也可能在不包括资源的情况下产生同类资源分配不当引起死锁5个同类资源，5个请求进程，
48、每个进程需要请求2个资源才能继续执行，并最终运行结束按照轮流分配，每次分配一个资源的分配方式将导致死锁对临时性资源使用不加限制引起死锁进程通信中，信件是临时性资源，使用不当出现死锁P1等P3的信件S3到达后向P2发送信件S1P2等P1的信件S1到达后向P3发送信件S2P3等P2的信件S2到达后向P1发送信件S3P1P3P2S1S2S3死锁死锁产生的因素系统拥有资源的数量资源分配策略进程对资源的要求并发进程的推进顺序死锁死锁的定义为避免与硬件故障以及其他程序性错误混淆，在定义死锁前给定六个假设：任意一个进程要求资源的最大数量不超过系统能提供的最大量如果一个进程要求的资源均得到满足，那么，它一定能
49、够在有限时间内结束一个资源在任何时间最多只被一个进程所占有一个进程一次申请一个资源，且只有在申请资源得不到满足时才处于等待状态一个进程结束时释放它占有的全部资源系统具有有限个进程和有限个资源一组进程处于死锁状态是指：如果在一个进程集合中得每个进程都在等待只能由该集合中其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。死锁由于死锁会造成很大的损失，因此必须花费额外的代价解决死锁问题，常见的解决死锁问题的方法：死锁的防止死锁的避免死锁的检测和恢复（解除）死锁死锁的防止死锁产生的四个条件，1971年Coffman互斥条件占有和等待条件不剥夺条件循环等待条件破坏死锁的任一条件，可以防止死锁
50、常见的死锁防止方法静态分配策略，破坏第二个条件，资源利用率低层次分配策略，破坏第四个条件死锁存在的必要条件死锁死锁的避免破坏死锁条件能够防止死锁，但将导致低效的进程运行和资源使用率死锁的避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配，从而避免死锁的发生常见的方法：资源轨迹图银行家算法死锁死锁的避免资源轨迹图A, B两个进程；打印机、绘图仪两种资源t时刻，如何分配资源？BAI8I7I6I5I1I2I3I4绘图仪打印机打印机绘图仪pqrstA,B进程同时拥有一个资源A,B进程同时拥有两个资源死锁资源轨迹图的优缺点优点：比较直观和简单缺点：只适合
51、在两个进程间进行判断只适合描述只有单个实例的资源死锁死锁的避免银行家算法前提条件：每个客户必须预先说明自己所要求的最大资金量；每个客户每次提出部分资金量申请和获得分配；如果银行满足了客户对资金的最大需求量，那么，客户在资金运作后，应在有限时间内全部归还；若一个所要求的最大资金量不超过其资金总量，则银行家一定接纳该客户，并可处理他的资金需求；银行在收到一个客户的资金申请时，可能因资金不足而让客户等待，但保证在有限时间内让客户获得资金。关键问题是，对资金申请进行判断，又称“资源分配拒绝法”死锁银行家对资金申请的判断依据是，如果满足该申请，是否存在一个安全状态序列使所有客户均能得到所有的贷款（所有进
52、程得到其所需的全部资源并执行终止）例：银行家有10个单位的资金，共有四个客户需要申请贷款，每个客户均提供了一个贷款额度，如下图所示：客户已贷款最大张三16李四15王五24赵六47可用：2是否可满足李四请求1个单位资金？是否可满足王五请求1个单位资金？客户已贷款最大张三16李四25王五24赵六47可用：1死锁判断是否可以满足李四一个单位的资金申请如果分配1个单位的资金给李四，则资金分配状态如下：在该状态下，可用资金无法满足任何一个客户的最大贷款额度，因此该状态是不安全的，应拒绝李四的贷款申请，让李四等待。客户已贷款最大张三16李四15王五34赵六47可用：1死锁判断是否可以满足王五一个单位的资金
53、申请如果分配1个单位的资金给王五，则资金分配状态如下：在该状态下，存在一个安全序列，“王五、李四、张三、赵六”。因此该状态是安全的，可以满足王五的资金申请。死锁多种资源的银行家算法定义数据结构描述进程和资源的相关信息系统每类资源的总数m个元素的向量，每个分量对应一类资源的总数：Resource = (R1, R2, , Rm)；每类资源未分配数量m个元素的向量，每个分量对应一类资源尚可分配的数量：Available = (V1, V2, , Vm)；最大需求矩阵n*m，行代表n个进程，列代表m类资源，Claim，其中元素Cij表示进程Pi需要Rj类资源最大数；分配矩阵n*m，行代表n个进程，列
54、代表m类资源，Allocation，其中元素Aij表示进程Pi已分得Rj类资源得数量；死锁安全性测试算法执行举例设有五个进程P0, P1, P2, P3, P4和A, B, C三类资源，A类资源共有10个，B类资源共有5个，C类资源共有7个，在T0时刻系统的资源分配情况如下：Resource = (10,5, 7)Available = (3,3, 2)010200302211002Claim = 753322902222433Allocation = 死锁安全性测试算法执行举例（续）资源进程CurrentAvilCki-AkiAllocationCurrentavil+allocationP
55、ossibleABCABCABCABCP0010P1200P2302P3211P4002743122600011431Claim = 753322902222433Available = (3, 3, 2)3 3 2 5 3 2T5 3 2T 7 4 3T7 4 3 7 5 3T7 5 3 10 5 5T10 5 5 10 5 7Resource = (10, 5, 7)死锁银行家算法的缺点：进程很难在运行前知道其所需资源的最大值系统中各进程之间必须是无关的，即没有同步要求，无法处理有同步关系的进程进程的数量和资源的数目是固定不变的，无法处理进程数量和资源数目动态变化的情况死锁死锁的检测和解除
56、资源分配图死锁检测算法死锁解除方法死锁死锁的检测和解除资源分配图描述进程和资源间申请及分配关系的一种有向图节点集：进程类集，P = P1, P2, , Pn 资源类集，R = R1, R2, , Rm边集 E：申请边，例 PiRj分配边，例 RiPj死锁资源分配图例设有P = P1, P2, P3, R = R1, R2, R3, R4,E = P1R1, P2R3, R1P2, R2P2, R2P1, R3P3 R1.R3.P1R2. .P2P3R4. . .死锁死锁的检测如果每个资源类型只有一个实例，那么资源分配图中出现环则意味着出现死锁如果每个资源类型有多个实例，那么环并不意味着已经出现
57、死锁资源分配图中的环是死锁存在的必要条件，而非充分条件死锁死锁检测算法如果资源分配图中无环，则没有发生死锁如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生死锁如果资源分配图中有环路，但涉及的资源类中有多个资源实例，则对该图进行简化，直至所有进程成为孤立点，称该有向图可完全化简。如果有向图可完全化简，则系统没有死锁发生，否则出现死锁。死锁死锁检测算法完全化简实例R1.P1R2. .P2死锁死锁的解除进程终止终止所有死锁进程一次终止一个进程，直至死锁解除每终止一个进程，都必须调用死锁检测算法以确定进程是否仍处于死锁状态资源抢占逐步从进程中抢占资源给其他进程使用，直到死锁被打破选择被抢占进程回滚问题饥饿问题
