并发进程控制讲义.ppt

《并发进程控制讲义.ppt》由会员分享，可在线阅读，更多相关《并发进程控制讲义.ppt（115页珍藏版）》请在三一办公上搜索。

1、*,操作系统（并发进程）,徐锋南京大学计算机科学与技术系,主要内容,并发进程概述临界区管理信号量与PV操作管程进程通信死锁,并发进程概述,顺序程序设计将一个程序设计成为一个顺序执行的程序模块，不同的程序也是按顺序执行。特点：（程序与程序的执行一一对应）执行的顺序性内部顺序性、外部顺序性环境的封闭性执行结果的确定性计算过程的可再现性,并发进程概述,顺序程序设计举例某程序需要循环执行输入、计算、输出三个过程while(TRUE)input;process;output;input 78ms,process 52ms,output 20ms,I1,P1,O1,I2,P2,O2,串行执行,并发进程概述

2、,顺序程序设计举例,处理器效率,处理器的利用率=52n/(78n+52n+20n)=52/150 35%,78,输入机,处理器,磁带机,130,150,228,280,300,378,430,450,时 间,并发进程概述,顺序程序设计优缺点：程序编制、调试方便计算机系统效率较低,并发进程概述,并发程序设计将一个程序分成若干个可同时执行的程序模块，每个程序模块和它执行时所处理的数据就组成了一个进程。特点：并发性共享性制约性交互性,并发进程概述,进程的并发性一组进程在执行时间上重叠，一个进程执行的第一条指令是在另一个进程执行的最后一条指令完成之前开始的宏观：在一个时间段中几个进程同时处于活动状态微

3、观：任一时刻仅有一个进程在处理器上运行实质：一个CPU在几个进程之间的多路复用,并发进程概述,并发程序设计举例一（相关进程）某程序需要循环执行输入、计算、输出三个过程设计为三个可并行执行的程序模块while(TRUE)input;send;78mswhile(TRUE)receive;process;send;52msWhile(TRUE)receive;output;20ms三个进程通过缓冲区交换信息,Ii,缓冲区1,Pi,缓冲区2,Oi,send,send,receive,receive,并发进程概述,并发程序设计举例一,I,P,O,t1,t2,t3,进程,时间,I1,I2,I3,P1,P

4、2,P3,O1,O2,O3,并发进程概述,并发程序设计举例一，处理器效率,78,输入机,处理器,磁带机,130,150,228,306,208,286,384,364,时 间,处理器的利用率=52n/(78n+52+20)67%,当n,并发进程概述,并发程序设计举例二（无关进程）进程A，由指令a1,a2,a3组成；进程B，由指令b1,b2,b3组成。A与B并发执行，则实际的指令执行序列？,a1a2a3b1b2b3,a1b1a2a3b2b3,b1a1b2a2b3a3,b1b2a1a2a3b3,并发进程概述,并发进程间的关系无关一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的

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=x+y;P2:b=z+1;P3:c=a b;P4:w=c+1;判断哪两个进程

6、可并发执行？解：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设备同时工作，发挥硬件的并行能力对于多处理器系统，可让各进程在不同的处理器上并行执行，加快计算速度简化程序设计任务,并发进程概述,采用并发程序设计的目的充分发挥硬件的并行工作能力，提高系统效率是多道程序设计的基础,并发进程概述,有交互关系的并发进程执行时带来的问题由于一组有交互关系的并发进程，其执行的相对速度无法控制，导致出现多种与时间有关的错误出现与时间有关错误的表现形式：结果不唯一永远等待,并发进程概述,结果不唯一错误举例，订票问题process Ti(i=1,2)var Xi:integ

8、er;begin按旅客定票要求找到Aj；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-B;修改主存分配表，申请进程获得主存资源 end;procedure return(var B:integer)begin x:=x+B;修改主存分配表 释放等主存资源的进程 end;,临界区管理,临界区：并发进程中与共享变量有关的程序段，称

9、为临界区(Critical Section)临界资源：共享变量代表的资源，称为临界资源(Critical Resource)临界区管理：保证一个进程在临界区执行时，不让另一各进程进入相关的临界区。（实现对共享变量的互斥访问）,临界区管理,临界区调度的原则一次至多一个进程能够进入它的临界区不能让一个进程无限地留在临界区不能强迫一个进程无限等待进入临界区“无空等待、有空让进、择一而入、算法可行”,临界区管理,临界区的描述临界资源（共享变量）shared 变量名临界区region 变量名 do 语句（复合语句）临界区的嵌套例，region X do;region Y do;嵌套可能导致进程无限地留在

10、临界区,临界区管理,临界区管理的尝试引入进程标志，分别指示进程进入临界区的情况第一种尝试，先测试，后置位不能保证同一时间只有一个进程进入临界区第二种尝试，先置位，后测试会出现死循环的情况，永远等待,临界区管理,临界区管理的尝试(1)inside1,inside2:Booleaninside1:=false;/*P1不在其临界区内*/inside2:=false;/*P2不在其临界区内*/cobeginprocess P1Begin while inside2 do begin end;inside1:=true;临界区;inside1:=false;end;process P2 Begin w

11、hile inside1 do begin end;inside2=true;临界区;inside2:=false;end;coend,临界区管理,临界区管理的尝试(2)inside1,inside2:Booleaninside1:=false;/*P1不在其临界区内*/inside2:=false;/*P2不在其临界区内*/cobeginprocess P1Begin inside1:=true;while inside2 do begin end;临界区;inside1:=false;end;process P2 Begin inside2=true;while inside1 do be

12、gin end;临界区;inside2:=false;end;coend,临界区管理,实现临界区管理的软件方法Dekker算法Peterson算法,临界区管理,Dekker算法，采用指示器变量turn来指示该由哪个进程进入临界区具体实现：/变量定义及初始化var inside:array1.2 of boolean;turn:integer;turn:=1 or 2;inside1:=false;inside2:=false;,临界区管理,Dekker算法（续）,cobegin process P1begin inside1:=true;while inside2 do if turn=2 t

13、hen begin inside1:=false;while turn=2 do begin 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)进入自己的

14、临界区时，把自己的标志位insidei置为true，并检查对方标志位如果对方不在也不想进入临界区，进程Pi可立即进入临界区；如果双方都想进入，咨询指示器turn，若turn为1(或为2)，P1(或P2)知道应该自己进入缺点：算法复杂难以理解,临界区管理,Peterson算法基本思想：用对turn的置值和while语句来限制每次只有一个进程进入临界区；进程执行完临界区程序后，修改insidei状态使等待进入临界区的进程可在有限时间内进入。算法满足临界区管理的三个条件。,临界区管理,Peterson算法算法描述（1）/变量定义及初始化var inside:array1.2 of boolean;t

15、urn:integer;turn:=1 or 2;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.,临界区管理,实

16、现临界区管理的硬件方法关中断（阻止进程交替执行）测试并建立指令，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 lock:boolean;lock:=false;process

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

18、V操作,生产者-消费者问题示意,P1,Pn,C1,Cm,Buffer,1,2,3,0,4,5,6,k-1,k-2,k-3,send,send,receive,receive,缓冲区指针：in，生产者进程投入产品指针out,消费者进程取产品指针缓冲区计数器：counter,in,out,信号量与PV操作,生产者-消费者问题算法描述,var k:integer;type item:any;buffer:array0.k-1 of item;in,out:integer:=0;counter:integer:=0;process producer while(TRUE)begin produce a

19、n 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:=counter 1;if(counter=k-1)wakeup(producer)consume the item in nextc;end;,信号量与PV操

20、作,生产者-消费者算法存在的问题由于生产者和消费者进程执行速度的不一致导致：缓冲器计数器出错错过等待唤醒解决方法：交互进程之间通过交换信号或消息来达到调整相互执行速度，从而保证进程协调运行的目的,信号量与PV操作,进程同步机制：操作系统实现进程同步的机制，通常由同步原语组成常见的同步机制：信号量与PV操作管程消息传递,信号量与PV操作,信号量与PV操作前述临界区管理方法存在的问题软件方法：复杂度高、效率低，将测试能否进入临界区的责任推给用户，降低系统的可靠性，加重用户编程负担硬件方法：虽然简单，但硬件设施采用忙式等待测试、浪费CPU时间1965，Dijkstra提出了新的同步机制信号量与PV操

21、作同步原语：P(Proberen,测试)原语,V(Verhogen,增量)原语除赋初值外，信号量仅能由同步原语操作,信号量与PV操作,信号量的分类按用途可分为：公用信号量（进程互斥）私有信号量（进程同步）按取值可分为：二元信号量（0/1，互斥）一般信号量（非负整数，同步）按信号量的结构：（简单数据类型）整型信号量记录型信号量,信号量与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

22、;,信号量与PV操作,记录型信号量（系统内核实现）s为一个记录型变量，包括两个分量value，整型量，非负初值queue，进程队列，初值为空P(s)：将信号量s的value值减去1，若结果小于0，则调用P(s)的进程被置为等待信号量s的状态，并加入queue队列V(s)：将信号量s的value值加1，若结果不大于0，则唤醒queue队列中某个等待信号量s的进程,信号量与PV操作,记录型信号量，描述：type semaphore=record value:integer;queue:list of process;end;procedure P(var s:semaphore);begin s.

23、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=0 then R(s.queue);end;,信号量与PV操作,当信号量代表某个物理资源时，关于记录型信号量和PV操作的三个推论若s.value为正，则该值代表实际还可以使用的物理资源数量若s.value为负，则其绝对值代表s.queue队列中等待该物理资源的进程数目P操作意味着请求一个资源（可能被阻塞），V操作意味着释放一个资源（唤醒被阻塞的进程）,信号量与PV操作

24、,二元信号量记录型信号量的一个特例，其value分量仅能取值为0或1BP(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);表达能力等同与一般的记录型信号量（稍有差别）,信号量与PV操作,采用记录型信号量实现互斥与硬件指令实现的区别，P,V操作只对信号量测试一次（等待），而TS指令需要反复测试（忙等待）实现互斥的一般形式：var mutex:semaphore;mutex:=1;cobegin process Pi begin P(mu

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

26、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(sj);提示票已售完；end;goto L1;end;coend.,信号量与PV操作,五个哲学家吃通心面（面条）问题有五个哲学家围坐在一圆桌旁，桌子中央有一盘通心面，每人面前有一只空盘子

27、，每两人之间放一把叉子。每个哲学家思考、饥饿，然后想吃通心面。为了吃面，每个哲学家必须获得两把叉子，规定每人只能直接从其左边或右边去取叉子,信号量与PV操作,五个哲学家吃通心面（面条）问题解决叉子是共享资源，需要互斥访问引入五个记录型互斥信号量每个哲学家吃之前，先对其左右两个叉子所对应的信号量P操作，吃完后，对其进行V操作上述解决方法，将有可能出现所有哲学家都吃不到通心面而饿死的问题（相互等待）至多允许四个哲学家同时吃奇数号先取左手边叉子，偶数号先取右手边叉子每个哲学家取到手边得两把叉子才吃，否则，一把也不取,信号量与PV操作,记录型信号量解决生产者-消费者问题单个生产者和单个消费者问题单一产

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

29、针的问题多个消费者之间互斥访问out指针的问题引入mutex信号量，解决互斥问题既有同步又有互斥信号量的情况下，原则上，用于互斥信号量上的P操作总在后面执行,信号量与PV操作,多类产品的多生产者和多消费者问题一个缓冲区长度为1的多类产品的多生产者和多消费者问题引入3个信号量sp，允许放入盘子，初值是缓冲器长度sg1,初值为0，允许消费第一类产品sg2,初值为0，允许消费第二类产品,信号量与PV操作,读者-写者问题有两类并发进程，读进程与写进程，共享一个文件，为防止出错，要求：1）允许多个读进程同时对文件读；2）只允许一个写进程写信息；3）写进程在没有写完成之前不允许读；4）写之前应该让所有已经

30、在读或写的进程操作完成。引入一个计数器和两个信号量解决此问题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 then P(W);V(mutex);读文件；P(mutex);rc:=rc 1;if rc=0 then V(w);V(mutex);end;,procedure witebegin P(w);写文件；V(w);en

31、d;,读者-写者问题的进一步思考,读者优先的解决方法，可能会出现写进程无限期被推迟的情况，为解决此问题，可考虑：公平的读者-写者问题写者优先的读者-写者问题pthread提供了读写锁pthread_rwlock_t，对应哪种实现？,读者-写者近似公平的解决方法,二元信号量实现一般信号量（错误）,二元信号量实现一般信号量（正确）,信号量与PV操作(理发师问题),理发师问题理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师就在理发椅上睡觉。当一个顾客到来后，他必须叫醒理发师。如果理发师正在理发时又有顾客到来，那么，如果有空椅子可坐，顾客就坐下来等待，否则离开理发店

32、。引入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(mutex);waiting:=waiting 1;V(b

33、arbers);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操作实现同步时，对共享资源的管理分散在各进程中，进程能够直接对共享变量进行修改，这很可能导致：不利于系统对临界资源的管理难以防止进程有意或无意的违法同步操作容易造成程序设计错误,管程,什么是管程？基本思想：把

34、分散在各进程中的临界区集中起来进行管理，并把系统中的共享资源用数据结构抽象地表示出来。代表共享资源的数据结构及其上操作的一组过程构成了管程管程是一种程序设计语言结构成分，和信号量有同等的表达能力,管程,管程的基本结构TYPE=MONITOR;define;移出部分use;procedure();begin;end;begin;end.,管程,管程的工作流程,condition c1,wait(c1),condition cn,wait(cn),urgent queue,signal,局部数据,条件变量,过程1,过程k,出口,初始化代码,入口,管程,等待调用的进程队列,管程等待区域,管程,条件变

35、量：当调用管程过程的进程无法继续运行时，用于阻塞进程的一种信号量wait同步原语：当一个管程过程无法继续时，它在某个条件变量上执行wait原语，将使调用该管程过程的进程阻塞signal同步原语：另一个进程可以通过对其伙伴进程在等待同一个条件变量上执行signal原语，以唤醒该等待进程,管程,使用signal原语释放等待进程时，将有可能出现两个进程同时停留在管程中的情况，这与管程的互斥性相违背，解决方法：执行signal的进程等待，直到唤醒的进程退出管程或等待另一条件被释放的进程等待，直到执行signal的进程退出管程或等待另一条件,管程,管程实现：Hoare方法，采用第一种方法解决signal

36、原语导致两个进程同时在管程中的情况采用PV操作实现进程互斥进入管程，以及对共享资源的互斥访问Hanson方法，对signal原语进行了限制，仅允许在过程体的最后调用signal原语。,Hoare方法实现管程,每个管程需要引入两个信号量和一个计数器TYPE interf=RECORDsemaphore mutex=1，用于互斥方式调用管程过程semaphore next=0,用于发出signal的进程挂起自己int next_count=0,在next上等待的进程数 END;实现wait操作和signal操作，用于进程间在某个特定条件上的同步semaphore x_sem=0，用于在某个特定条件

37、上的同步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_count+;V(x_sem);P(IM.next);IM.next_count-;,Hoare方法实现管

38、程,任何外部过程必须采用如下形式，才能保证互斥进入管程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 of condition;define pickup,putdown;use wait,signal;produce

39、 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 eating)then wait(selfi,s-counti,IM);end;procedure putdown(i:0.4)beginstatei:=

40、thinking;test(i 1)mod 5);test(i+1)mod 5);end;beginfor i:=0 to 4 do statei:=thinking;end,管程,管程与进程的区别管程定义公共数据结构；进程定义私有数据结构管程把共享变量上的同步操作集中在一起；而临界区则分散在各进程中管程为管理共享资源而建立；进程为占有资源和实现系统并发而存在管程与调用它的进程串行工作；而进程之间可并行工作管程是语言和操作系统的成分，具有静态性；进程是动态的，存在生命周期，需要创建和撤消,进程通信,为什么需要进程通信？进程间的交互需要进程间存在通信机制竞争互斥（特殊的同步）协作同步交换数据,进

41、程通信,常见的通信机制信号通信共享文件共享存储区消息传递,进程通信,信号通信机制,signal,Minix中sigaction系统调用信号通信又称软中断，是一种简单的通信机制，通过发送一个特定的信号来通知进程某个异常事件发生信号可以是内核发送给进程，也可以是一个进程发送给另一个进程例：SIGLD、SIGHUP、SIGKILL、SIGCHLD等信号用于进程的终止,进程通信,共享文件通信机制又称管道通信，引入一个特殊的称之为管道的共享文件连接两个读写进程管道(pipeline)，允许进程按先进先出的方式传送数据，也能使进程同步执行操作,P1写进程,共享文件,P2读进程,字节流,字节流,进程通信,共

42、享文件通信机制的实现可借助于文件系统的机制实现，包括管道文件的创建、打开、关闭和读写。进程对共享文件互斥使用，即一个进程正在读或写时，另一个进程必须等待。由于共享文件有大小限制，因此通信进程之间必须能够正确的同步通信双方必须知道对方是否存在,进程通信,有名管道或FIFO通信机制(UNIX)普通管道机制的缺陷仅能连接具有共同祖先的进程管道具有临时性，难以提供全局服务一种永久性通信机制，具有Unix文件名、访问权限，并且性能与普通的管道相同,进程通信,共享存储区通信机制是进程通信中最快捷和有效的方法具体过程：向系统共享存储区申请一个分区段，并指定关键字；若系统已为其他进程分配了该分区，则返回对应的

43、关键字给申请者。分区段连接到进程的虚地址空间，进程可通过对该区段的读、写来直接通信,进程通信,共享存储区通信机制示例,A进程,B进程,共享存储区,内核,进程通信,消息传递机制（基本概念）信号消息，低级高级，信息的规模扩大消息，是一组信息，由消息头和消息体组成。两个基本的消息传递原语：send,receivesend,receive可以实现为同步操作也可实现为异步操作（一般实现为异步send，同步receive）,死锁,死锁的产生死锁的定义死锁的防止死锁的避免死锁的检测和解除,死锁,死锁的产生计算机系统中存在许多独占资源，如硬件资源：磁带机、绘图仪等软件资源：进程表、临界区等为保证有效管理，独占

44、资源的使用必须经历：申请资源，若资源不可用，则申请者进入等待状态使用资源归还资源当一个进程需要独占多个资源，而操作系统允许多个进程并发执行共享系统资源时，可能会出现进程永远处于等待状态的现象（死锁）,死锁,死锁举例进程推进顺序不当产生死锁,进程P请求读卡机请求打印机释放读卡机释放打印机,进程Q请求打印机请求读卡机释放读卡机释放打印机,产生死锁的执行序列PQPQ,死锁,死锁举例PV操作使用不当产生死锁（与前例类似）死锁也可能在不包括资源的情况下产生同类资源分配不当引起死锁5个同类资源，5个请求进程，每个进程需要请求2个资源才能继续执行，并最终运行结束按照轮流分配，每次分配一个资源的分配方式将导致

45、死锁对临时性资源使用不加限制引起死锁进程通信中，信件是临时性资源，使用不当出现死锁P1等P3的信件S3到达后向P2发送信件S1P2等P1的信件S1到达后向P3发送信件S2P3等P2的信件S2到达后向P1发送信件S3,死锁,死锁产生的因素系统拥有资源的数量资源分配策略进程对资源的要求并发进程的推进顺序,死锁,死锁的定义为避免与硬件故障以及其他程序性错误混淆，在定义死锁前给定六个假设：任意一个进程要求资源的最大数量不超过系统能提供的最大量如果一个进程要求的资源均得到满足，那么，它一定能够在有限时间内结束一个资源在任何时间最多只被一个进程所占有一个进程一次申请一个资源，且只有在申请资源得不到满足时才

46、处于等待状态一个进程结束时释放它占有的全部资源系统具有有限个进程和有限个资源一组进程处于死锁状态是指：如果在一个进程集合中得每个进程都在等待只能由该集合中其他一个进程才能引发的事件，则称一组进程或系统此时发生了死锁。,死锁,由于死锁会造成很大的损失，因此必须花费额外的代价解决死锁问题，常见的解决死锁问题的方法：死锁的防止死锁的避免死锁的检测和恢复（解除）,死锁,死锁的防止死锁产生的四个条件，1971年Coffman互斥条件占有和等待条件不剥夺条件循环等待条件破坏死锁的任一条件，可以防止死锁常见的死锁防止方法静态分配策略，破坏第二个条件，资源利用率低层次分配策略，破坏第四个条件,死锁存在的必要条

47、件,死锁,死锁的避免破坏死锁条件能够防止死锁，但将导致低效的进程运行和资源使用率死锁的避免不是通过对进程随意强加一些规则，而是通过对每一次资源申请进行认真的分析来判断它是否能够完全的分配，从而避免死锁的发生常见的方法：资源轨迹图银行家算法,死锁,死锁的避免资源轨迹图A,B两个进程；打印机、绘图仪两种资源t时刻，如何分配资源？,B,A,I8,I7,I6,I5,I1,I2,I3,I4,绘图仪,打印机,打印机,绘图仪,p,q,r,s,t,A,B进程同时拥有一个资源,A,B进程同时拥有两个资源,死锁,资源轨迹图的优缺点优点：比较直观和简单缺点：只适合在两个进程间进行判断只适合描述只有单个实例的资源,死

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

49、有10个单位的资金，共有四个客户需要申请贷款，每个客户均提供了一个贷款额度，如下图所示：,可用：2,是否可满足李四请求1个单位资金？,是否可满足王五请求1个单位资金？,可用：1,死锁,判断是否可以满足李四一个单位的资金申请,如果分配1个单位的资金给李四，则资金分配状态如下：,在该状态下，可用资金无法满足任何一个客户的最大贷款额度，因此该状态是不安全的，应拒绝李四的贷款申请，让李四等待。,可用：1,死锁,判断是否可以满足王五一个单位的资金申请,如果分配1个单位的资金给王五，则资金分配状态如下：,在该状态下，存在一个安全序列，“王五、李四、张三、赵六”。因此该状态是安全的，可以满足王五的资金申请。

50、,死锁,多种资源的银行家算法定义数据结构描述进程和资源的相关信息系统每类资源的总数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类资源得数量；,死锁,安全性测试算法执行举例设有五个进程P0,P1,P2,P3,P4和A,B,C三类资源