并发控制课件

TheCityCollegeOfJiLinArchitecturalAndCivilEngineeringInstituteDepartmentofComputerScience&Technology操作系统原理PrinciplesofOperatingSystem1第四章并发控制目的与要求：了解并行程序的高级语言表示与操作系统支持下的实现；了解同步与互斥问题。理解互斥问题的硬件实现方法；掌握信号量机制及使用它解决进程同步互斥问题的方法。掌握信号量解决进程同步互斥问题的方法；掌握进程通信的基本实现方法。了解死锁的定义，掌握死锁预防，了解死锁避免，死锁检测，死锁恢复的方法。重点与难点：并行程序中的同步与互斥，信号量实现及使用。信号量的典型应用，通讯实现。死锁预防法则的使用，死锁避免和检测算法。作业：1，2，3，4，6，11，13，14，15，21，23，28，3124.1并发进程4.1.1顺序程序及其特性顺序性内部顺序性：如：P1

:a=x+y;b=a-z;c=a+b;d=c+5;外部顺序性：输入，计算，打印特性连续性：一个程序的指令连续执行封闭性：P独占全部资料，不受外界影响可再现性：执行结果只与初始条件有关3例：图书借阅系统（x:某种书册数，设当前x:=1.）终端1：终端2：CYCLECYCLE等待借书者；等待借书者；IFx>=1ThenIFx>=1ThenBeginBeginx:=x-1;x:=x-1;借书借书EndEndElse无书Else无书EndEnd4.1.3与时间有关的错误1234中断中断54.1.3与时间有关的错误(Cont.)错误原因之1：进程执行交叉(interleave);错误原因之2：涉及公共变量(x)。Remarks:某些交叉结果不正确;必须去掉导致不正确结果的交叉。定义：并发进程的执行实际上是进程活动的某种交叉，某些交叉次序可能得到错误结果。由于具体交叉的形成与进程的推进速度有关，而速度是时间的函数，因而将这种错误称为与时间有关的错误。64.2同步与互斥4.2.1进程互斥互斥关系（亦称间接制约关系）即进程间因相互竞争使用独占型资源（互斥资源）所产生的制约关系。例2：P1、P2两进程使用同一打印机。如果不互斥使用会交叉输出Entrycodeexitcode使用打印机P1Entrycodeexitcode使用打印机P27……balance=balance+amountbalance=balance-amount……机器指令：A(amount)B(amount){R1=balance;{R1=balance;R2=amount;R2=amount;R1=R1+R2;R1=R1-R2;balance=R1;balance=R1;};};例3:进程P1处理存款业务，进程P2处理借贷业务。它们如何访问共享变量balance？互斥执行中断进程互斥的硬件实现1.硬件提供“测试并建立”(“读后置“1””)指令booleantest_and_set(boolean&target){booleanrv=target;/*读取参数传过来的地址中的值*/target=true;/*将参数值置“1”*/return(rv);}实现互斥的使用方法：1）对一组公共变量,设置一变量：booleanlock=false;

/*表示无进程在临界区*/2）Pi进入:While(test_and_set(&lock));

/*lock=true*/

临界区3）Pi离开：lock=false;10booleanlock=false;Pi进入:While(test_and_set(&lock));

/*lock=true*/

临界区Pi离开：lock=false;Pj进入:While(test_and_set(&lock));

/*lock=true*/

临界区Pj离开：lock=false;Lock=falsePj的时间片到Lock=truePi忙式等待存在忙式等待现象：不进入等待状态的等待称为~。即空耗处理机资源。11为何开关中断进程互斥方法仅在单CPU系统中是有效的？答：关中断方法不适用于多CPU系统，因为关中断只能保证CPU不由一个进程切换到另外一个进程，从而防止多个进程并发地进入公共临界区域。但即使关中断后，不同进程仍可以在不同CPU上并行执行关于同一组共享变量的临界区代码。13例：司机-售票员问题P1：司机活动：P2：售票员活动：do{do{关车门启动车辆正常行驶售票到站停车开车门}while(1)}while(1)12344.2.2进程同步14同步关系（亦称直接制约关系）指完成同一任务的伙伴进程间，因需要在某些位置上协调它们的工作而等待、传递信息所产生的制约关系。4.2.2进程同步15信号量机构的组成：“信号量”、“P、V操作”。信号量S：一整型变量，只能被两个原语访问。P操作(原语)：P(S){While（S≤0） ；空操作S=S-1；}V操作(原语)：V(S){S=S＋1；}P、V操作是两条原语，即保证P、V操作对变量S的访问是互斥操作。4.2.3信号量申请资源释放资源17一.原语概念与实现原语定义：指完成某种功能且不被分割或不被中断执行的操作序列。原语可通过硬件实现不可中断性；或通过实现临界段的元方法达到不被中断。实现临界段的元方法:屏蔽中断(只用于单机)利用“test-and-set”指令18下面我们用屏蔽中断方法实现P（s）和V（s）的原子性。 P（s）V（s）{{

disableInterrupt();

disableInterrupt(); while（s≤0）{

enableInterrupt();

disableInterrupt();

}； s=s-1；s=s+1；

enableInterrupt();enableInterrupt(); }}循环忙等时可响应中断19解决互斥问题：有n个进程均要访问的临界段。设n进程共享一个信号量mutex,初值为1，semaphoremutex;任一进程Pi的结构为：P(mutex)V(mutex)临界段非临界段do{}while（1）进入临界段前执行P操作；离开临界段后执行V操作；关于同一个信号量的P、V操作处理同一个进程中！21semaphoremutex=1;Pi进入:P(mutex){While(mutex≤0)；

mutex=mutex-1；}

临界区Pi离开:V(mutex){mutex=mutex+1;}Pj进入:P(mutex){While(mutex≤0);

mutex=mutex-1；}

临界区Pj离开：V(mutex);mutex=1mutex=022解决同步问题：例1：有P1、P2两进程，必须在P1执行完S1语句后，P2才能执行S2。设同步的两进程共享信号量synch，初值为0。semaphoresynch=0;S1S2P1：P2：P2():{P1():{……S1;V(synch);……};……P(synch);S2;……};申请资源执行P；释放资源执行V；P、V在不同进程中！23例2：两个进程P1和P2，其中，进程P1依次运行S1，S2，S4，S5，S7子任务，进程P2依次运行S3，S6子任务。Semaphores13,s46,s67;s13=0;s46=0;s67=0;S1S2S3S4S5S6S7P1:……S1;V(s13);S2;S4;V(s46);S5;P(s67);S7;……P2:……P(s13);S3;P(s46);S6;V(s67);

……25三.信号量的具体实现及P、V操作的改进改进原因：硬件方法和原有的P、V操作存在“忙等”现象。26无忙等的信号量的P、V操作1、信号量定义（E.W.Dijkstra,1965.） typedefstruct{ intvalue；

structprocess*L;/*等待队列*/}semaphore；S.valueS.LsemaphoreS;29无忙等的信号量的P、V操作2、P操作voidP(Semaphores){S.Value=S.value–1;if(S.value<0){保存现场，将执行该P操作的进程挂入S.L队列；block();}}S.valueS.LPCB1PCB2PCBnFIFO若s.value=1，执行P(S)的进程p1是否等待？S.value=?若s.value=0，执行P(S)的进程p1是否等待？S.value=?0-1注意：当s.value<0时，则s.L队列中有等待状态的进程！30无忙等的信号量的P、V操作3、V操作voidV(Semaphores){S.value=S.value+1ifS.value≤0then{从S.L队列取一进程，挂入就绪队列。wakeup();}}S.valueS.LPCBPCBPCBs.value=-1s.value=-2s.value=-ns.value=0若s.value=-1，执行v(S)的进程p是否进行唤醒操作？S.value=?031信号量和P、V操作的规定P(S):表示申请一个资源V(S):表示释放一个资源。信号量的初值必须且只能置一次初值，且应该大于等于0P.V操作必须成对出现，有一个P操作就一定有一个V操作对信号量只能执行P操作和V操作，所有其它操作非法。32规定和结论几个有用的结论：当s.value>=0时，有s.values个资源可用，且s.L队列为空；当s.value<0时，|s.value|为队列s.L的长度(即队列中等待状态的进程的个数)；当s->value初=1时，可以实现进程互斥；当s->value初=0时，可以实现进程同步；当s->value初=正整数时，表示系统中资源的个数，可用来管理同种类组合资源。334.2.4进程同步与互斥举例互斥举例：进入临界段前执行P操作；离开临界段后执行V操作；关于同一个信号量的P、V操作处理同一个进程中！34例2：P1、P2两进程使用同一打印机。设一个信号量：semaphores;s.value=1;Entrycodeexitcode使用打印机P1Entrycodeexitcode使用打印机P2P(s)P(s)V(s)V(s)互斥举例35Pj进入:P(s){S.value=S.value-1；if(s.value<0){入等待队列；block();}

临界区Pi离开：V(S){S.value=S.value+1;if(s.value<=0){出等待队列；wakeup(Pj);}semaphores.value=1;Pi进入:P(s){S.value=S.value-1；if(s.value<0){入等待队列；block();}

临界区Pi离开：V(S){S.value=S.value+1;if(s.value<=0){

出等待队列；wakeup(Pj);}S.value=1S.value=0S.value=-1S.valueS.LnullPCBjnull36

balance=balance+amountbalance=balance-amountA(amount)B(amount){R1=balance;{R1=balance;R2=amount;R2=amount;R1=R1+R2;R1=R1-R2;balance=R1;balance=R1;};};例3:进程P1处理存款业务，进程P2处理借贷业务。它们如何访问共享变量balance？互斥执行P(mutex)P(mutex)V(mutex)V(mutex)semaphoremutex.value=1;37互斥例子：借书系统(revisited)semaphoremutex;mutex.value=1;终端1：终端2：while(1){while(1){等待借书者；等待借书者；

P(mutex);P(mutex);if(x>=1)if(x>=1){{x=x-1;x=x-1;V(mutex);V(mutex);

借书借书}}elseV(mutex);无书;elseV(mutex);无书;}}38同步举例：司机-售票员问题申请资源执行P；释放资源执行V；P、V在不同进程中！39用信号灯实现进程同步例子：司机-售票员问题：semaphores1.value=0,s2.value=0;司机活动：售票员活动：while(1)while(1){P(S1){关车门启动车辆V(S1)正常行驶售票到站停车P(S2)

V(S2)开车门}}是否关门了是否停车了40Classicalsynchronizationproblems1.Producersandconsumersproblem2.Readersandwritersproblem3.Diningphilosophersproblem4.Cigarettesmokersproblem5.Sleepybarbersproblemetc.41例1.生产者/消费者问题1箱子，容量1intb;1个生产者1个消费者生产物品放入b中b中取物品消费之42问题分析生产者活动：消费者活动：do{do{

加工一件物品箱中取一物品物品放入箱中消耗这件物品}while(1)}while(1)资源：箱子(同种组合)

资源：物品(同种组合)semaphoreempty;semaphorefull;

empty.value=1;full.value=0;放前：P（empty）取前：P（full）放后：V（full）取后：V（empty）43同步生产者活动：消费者活动：do{do{

加工一件物品P(full)

P(empty)

箱中取一物品物品放入箱中V(empty)

V(full)

消耗这件物品}while(1)}while(1)44例1.生产者/消费者问题01……k-1箱子，容量kintb[k]m个生产者n个消费者生产物品放入b中b中取物品消费之45互斥生产者活动：消费者活动：do{do{

加工一件物品P(full)

P(empty)

P(mutex)

P(mutex)

箱中取一物品物品放入箱中V(mutex)

V(mutex)

V(empty)

V(full)

消耗这件物品}while(1)}while(1)46semaphoreempty.value=k,full.value=0,mutex.value=1;voidproducer(){while(1){加工一个产品

P(empty);

P(mutex);

获得一个缓冲区;产品放入缓冲区;

V(mutex);

V(full);}}voidconsumer(){while(1){P(full);

P(mutex);

获得一个满缓冲区;取缓冲区中的产品;

V(mutex);V(empty);}}P(mutex);

P(empty);

47voidproducer(){while(1){加工一个产品

P(empty);

P(mutex);

获得一个缓冲区;产品放入缓冲区;

V(mutex);

V(full);}}voidconsumer(){while(1){P(full);

P(mutex);

获得一个满缓冲区;取缓冲区中的产品;

V(mutex);V(empty);}}P(mutex);

P(empty);

若，当前缓冲区满，则empty.value=0,full.value=k,mutex.value=1生产者：mutex.value=0,empty.value=-1消费者：full.value=k-1,mutex.value=-1死锁48注意注意：如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前而两个V操作无关紧要49并发性提高策略生产者和消费者：关注不同的缓冲区生产者关注：空的缓冲区消费者关注：满的缓冲区semaphoremutex1,mutex2;mutex1.value=1;mutex2.value=1;？50互斥生产者活动：消费者活动：do{do{

加工一件物品P(full)

P(empty)

P(mutex2)

P(mutex1)

箱中取一物品物品放入箱中V(mutex2)

V(mutex1)

V(empty)

V(full)

消耗这件物品}while(1)}while(1)51例2.读者/写者问题P.T.Courtois1971CommunicationoftheACM,Vol.14,667-669.ACM:AssociationforComputingMachinery解法1：写者可能饿死解法2：写者优先52例2.读者/写者问题ProblemStatement:一组公共数据DBR1……RmW1…...Wn要求：（1）R-R可以同时（2）R-W不可同时（3）W-W不可同时accessing53Solution1:不考虑R-R不互斥semaphorer_w_w.value=1;Reader：Writer:

P(r_w_w);P(r_w_w)

{读操作}{写操作}V(r_w_w);V(r_w_w)分析：(1)写者活动正确；(2)R-R不能同时。改进：最先进入的R执行P；最后离开的R执行V；54Solution2:考虑R-R不互斥intreadercount=0;Reader:readercount=readercount+1;if(readercount==1)P(r_w_w);{读操作}readercount=readercount-1;if(readercount==0)V(r_w_w);问题：对Readercount操作的互斥问题。55Solution3:正确解法semaphorereadercount_mutex.value=1;

Reader:

P(readercount_mutex);readercount=readercount+1;if(readercount==1)P(r_w_w);

V(readercount_mutex);{读操作}

P(readercount_mutex);readercount=readercount-1;if(readercount==0)V(r_w_w);

V(readercount_mutex);读者等待在何处？读者如何被唤醒？56程序intreadercount=0;semaphorer_w_w.value=1;semaphorereadercount_mutex.value=1;writer(){while(1){……

P(r_w_w);<写操作>

V(r_w_w)}}57程序（Cont.）reader(){while(1){……

P(readercount_mutex);readercount=readercount+1;if(readercount==1)P(r_w_w);

V(readercount_mutex);

<读操作>

P(readercount_mutex);readercount=readercount-1;if(readercount==0)V(r_w_w);

V(readercount_mutex);}}58分析（w1,w2,r1,w3,r2,r3）①初始状态readercount_mutex

1NULLreadercount=0r_w_w1NULL访问文件者：无图4-1②w1请求readercount_mutex1NULLreadercount=0r_w_w0NULL访问文件者：w1图4-259请求序列：w1,w2,r1,w3,r2,r3③w2请求readercount_mutex1NULLreadercount=0r_w_w-1w2访问文件者：w1图4-3④r1请求readercount_mutex0NULLreadercount=1r_w_w-2w2,r1访问文件者：w1图4-460⑤w3请求readercount_mutex0NULLreadercount=1r_w_w-3w2,r1,w3访问文件者：w1图4-5⑥r2请求readercount_mutex-1r2readercount=1r_w_w-3w2,r1,w3访问文件者：w1图4-6请求序列：w1,w2,r1,w3,r2,r361⑦r3请求readercount_mutex-2r2,r3readercount=1r_w_w-3w2,r1,w3访问文件者：w1图4-7⑧w1结束，唤醒w2readercount_mutex-2r2,r3readercount=1r_w_w-2r1,w3访问文件者：w2图4-8请求序列：w1,w2,r1,w3,r2,r362readercount_mutex-1r3readercount=1r_w_w-1w3访问文件者：r1图4-9readercount_mutex0NULL

readercount=2r_w_w-1w3访问文件者：r1,r2图4-10⑨w2结束唤醒r1,r1唤醒r2,r2入就绪队列⑩r2运行,r2唤醒r3,r3入就绪队列请求序列：w1,w2,r1,w3,r2,r363⑩r3运行readercount_mutex1NULL

readercount=3r_w_w-1w3访问文件者：r1,r2,r3图4-11⑩r1,r2,r3结束,唤醒w3readercount_mutex1NULL

readercount=0r_w_w0NULL

访问文件者：w3图4-12请求序列：w1,w2,r1,w3,r2,r364⑩w3结束readercount_mutex1NULL

readercount=0r_w_w1NULL

访问文件者：无图4-13请求序列：w1,w2,r1,w3,r2,r365分析：问题：读者源源不断，readcount不归0，写者会被饿死。初始:w1,w2,r1,w3,r2,r3实际:w1,w2,r1,r2,r3,w3策略：一旦有写者等待，新到达读者等待，正在读的读者都结束后，写者进入。Furtherimprovementislefttointerestedstudents.66写者优先算法semaphorer_w_w.value=1;semaphorereader_wait.value=1;semaphorefirst_reader_wait.value=1;semaphorereadercount_mutex.value=1;semaphorewritercount_mutex.value=1;intwritercount=0;intreadercount=0;67reader(){

P(reader_wait);P(first_reader_wait);

P(readercount_mutex);readercount++;if(readercount==1)P(r_w_w);

V(readercount_mutex);

V(reader_wait);

V(first_reader_wait);读文件;68

P(readercount_mutex);readercount--;if(readercount==0)V(r_w_w);

V(readercount_mutex);}69writer(){

P(writercount_mutex);

writercount++;if(writercount==1)

P(first_reader_wait);

V(writercount_mutex);

P(r_w_w);写文件;70

V(r_w_w);

P(writercount_mutex);writercount--;if(writercount==0)

V(first_reader_wait);

V(writercount_mutex);}71无优先算法semaphorer_w_w.value=1;semaphorewait.value=1;

semaphorereadercount_mutex.value=1;intreadercount=0;72reader(){

P(wait);P(readercount_mutex);if(readercount==0)

P(r_w_w);readercount++;

V(readercount_mutex);

V(wait);读文件;73

P(readercount_mutex);readercount--;if(readercount==0)

V(r_w_w);

V(readercount_mutex);}74writer(){

P(wait);

P(r_w_w);写文件;

V(r_w_w);

V(wait);}75例3.哲学家就餐问题DiningPhilosophersProblemProposedandsolvedbyE.W.Dijkstra,in196576例3.哲学家就餐问题Roomph0ph4ph3ph2ph1f0f4f3f2f177例3.哲学家就餐问题哲学家活动：while(1){思考进食}进食：需要“筷子”筷子：不同种组合资源为每个筷子设置一个信号量fork[i],0<=i<=4哲学家活动（包含资源活动）while(1){思考取左筷取右筷进食放左筷放右筷}78例3.哲学家就餐问题Semaphorefork[i].value=1哲学家活动（包含资源活动）while(1){思考p(&fork[i]);取左筷，

p(&fork[(i+1)%5]);取右筷进食放左筷，v(&fork[i]);放右筷v(&fork[(i+1)%5]);}死锁情况：每位哲学家拿到左叉，等待右叉。79习题1.设有一个售票大厅，可容纳200人购票。如果厅内不足200人，则允许进入，超过则在厅外等候；售票员某时只能给一个购票者服务，购票者习完票后就离开。试问：购票者之间是同步关系还是互斥关系？用P、V操作描述购票者的工作过程。80答（1）购票者间是互斥关系。（2）semaphoreempty.value=200;semaphoremutex.value=1;购票者{p(empty);p(mutex);购票；v(empty);v(mutex);}81例4理发师睡觉问题理发师问题的描述：

一个理发店接待室有n张椅子，工作室有1张椅子；

没有顾客时，理发师睡觉；

第一个顾客来到时，必须将理发师唤醒；

顾客来时如果还有空座的话，他就坐在一个座位上等待；

如果顾客来时没有空座位了，他就离开，不理发了；

当理发师处理完所有顾客，而又没有新顾客来时，他又开始睡觉。

82顾客的活动{如果没有空椅子，离开；否则，坐在椅子上等候；从椅子上起来；坐在理发椅上；}资源：理发师的活动{睡觉；理发；

}资源：有没有等待的顾客；83Windows2000/XP互斥同步机制CRITICAL_SECTION类型InitializeCriticalSection:初始化EnterCriticalSection:等待进入TryEnterCriticalSection:非等待，失败返回0LeaveCriticalSection:离开DeleteCriticalSection:清除844.3进程高级通讯进程通讯：进程之间的相互作用。低级通讯（简单信号）进程互斥进程同步高级通讯（大宗信息）高级通讯memorysharingvs.messagepassingdirectvs.indirectsymmetricvs.non-symmetricbufferingvs.non-buffering4.3.1进程通讯概念85P14.3.2进程通讯模式1.共享内存模式(sharedmemory)：2.消息传递模式(messagepassing)：P2OS提供：（1）公共内存（2）互斥同步机制P1P2Msendreceive直接：进程-进程间接：进程-信箱-进程原语系统调用命令864.3.3消息传递模式(messagepassing)对称形式(senderandreceivernameeachother)send(R,message)receive(S,message)…Send(R,M)...…Receive(S,N)...S:R:1.消息传递原语形式：一对一87非对称形式(onlysendernamesreceiver)send(R,message)receive(pid,message)…receive(pid,N)...…send(R,M1)...…send(R,M2)...C/SmodelR:S1:S2:多对一信息是如何传送的？4.3.3消息传递模式(messagepassing)882.消息传递方法直接通信法基本思想：进程在发送和接收消息时直接指明接收者或发送者进程ID。缺点：必须指定接收进程ID。（UNIX的信号机制类似这种形式）分类无缓冲途径有缓冲途径4.3.3消息传递模式(messagepassing)89间接通讯法（信箱命名法〕基本思想：设立一个通信参与者共享的逻辑实体，如信箱。系统为每个信箱设一个消息队列，发送者只向信箱发消息，接收者只从信箱取消息。4.3.3消息传递模式(messagepassing)MailboxSend(mb,m)Receive(mb,n)...90有缓冲途径消息传递过程PCB…send(R,M)…sizetext...PCB…receive(pid,N)…

...M:发送区N:msgmsg...发送者S:接收者R:bufbufbuf...bufbuf...bufmsgmsgmsgbufbufmsg91Send(R,M)

根据R找接收者；

P(Sb);//是否有空buf

P(b_mutex);//互斥用buf

取一空buf;

V(b_mutex);text,size,sender=>buf

P(m_mutex);//互斥用消息链

消息入链尾；

V(m_mutex);

V(Sm);

//消息数量加1

发送-接收原语PCB…send(R,M)…sizetext...M:发送区发送者S:bufbufbuf...PCB…receive(pid,N)…

...N:msgmsgmsg...接收者R:semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;92发送-接收原语PCB…send(R,M)…sizetext...M:发送区发送者S:bufbufbuf...PCB…receive(pid,N)…

...N:msgmsgmsg...接收者R:Receive(pid,N)P(Sm);//是否有消息

P(m_mutex);//互斥用消息链

头消息出链;

V(m_mutex);text,size=>Nsender=>pid

P(b_mutex);//互斥用buf

空buf入链；

V(b_mutex);V(Sb);//空buf数量加1semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;93Send(R,M)根据R找接收者；

P(Sb);P(b_mutex);取一空buf;

V(b_mutex);text,size,sender=>buf

P(m_mutex);

消息入链尾；

V(m_mutex);

V(Sm);

Receive(pid,N)

P(Sm);

P(m_mutex);头消息出链;

V(m_mutex);text,size=>Nsender=>pid

P(b_mutex);

空buf入链；

V(b_mutex);V(Sb);semaphoreSb.value=k，b_mutex.value=1,

Sm.value=0,m_mutex.value=1;申请缓冲区释放缓冲区入消息队列从消息队列取消息94Remarks：Send/receive为高级通讯原语，可用低级原语实现；Send/receive不是真正意义的原语，可以被中断。954.4死锁

4.4.1死锁示例日常生活中的例子进程死锁的例子竞争外部设备竞争辅存空间编程错的例子964.4.2死锁定义定义：一组进程中的每一个进程，均无限期地等待此组进程中某个其他进程占有的，因而永远无法得到的资源，这种现象称为进程死锁。定义死锁时刻：无限等待发生时；等待发生前（已注定死锁）。97由定义得到的结论几个有用的结论：参与死琐的进程至少有二个；每个参与死锁的进程均等待资源；参与死锁的进程中至少有两个进程占有资源；死锁进程是系统中当前进程集合的一个子集。984.4.3死锁类型DBACW:直行E:左转S:左转1.竞争资源引起的死锁（1）不同种资源（2）同种资源4台打印机，申请:a,释放aP1:aaaaaaaaP2:aaaa994.4.3死锁类型(Cont.)2.进程通讯引起的死锁P1：receive(P2,M1);P2:receive(P3,M2);P3:receive(P1,M3);其它原因引起的死锁Afteryou/afteryou1004.4.4死锁的条件Coffman条件（必要条件）资源独占（mutualexclusion互斥）同一时刻，一个资源只能分配给一个进程不可抢占（nonpreemption非剥夺）申请者不能强行抢夺别人的资源保持申请（holdandwait占有等待）P占有资源又申请资源循环等待（circularwait）第四个条件是前三个同时存在的结果。破坏上述任意一个条件可以消除死锁。1014.4.5资源分配图资源分配图的定义定义:G=(V,E),V是点的集合

V=PR,P={p1,p2,…,pn},R={r1,r2,…,rm},E是边的集合

E={(pi,rj)}{(rj,pi)},piP,rjR.

申请边(pi,rj):pi申请rj；

分配边(rj,pi):rj分配pi;102例子（无环路，无死锁）例1.P={p1,p2,p3},R={r1(1),r2(2),r3(1),r4(3)}E={(p1,r1),(p2,r3),(r1,p2),(r2,p1),(r2,p2),(r3,p3),(r4,p3)}p1p2p3r1r3r2r4103例子（有环路，有死锁）增加边（p3,r2)p1p2p3r1r3r2r4104例子（有环路，无死锁）r1r2p1p2p31054.4.5资源分配图结论:无环路,一定无死锁有环路,且每个资源类中均只有唯一的一个资源实例,则死锁有环路,且存一个所有资源类所构成集合子集,该子集中每一个资源类均只有唯一的一个资源实例,则死锁1064.4.5资源分配图资源分配图的约简步骤:（1）寻找非孤立且无请求边的进程节点Pi,若无结束;（2）去除所有Pi的分配边使Pi成为一个孤立节点；（3）寻找所有请求边均可满足的进程Pj,将Pj的请求边全部改为分配边；（4）转（1）。判断系统是否死锁10资源分配图的约简p1p2p3r1r3r2r4定理：S为死锁状态的充分必要条件是S的资源分配图不可完全约简。10资源分配图的约简p1p2p3r1r3r2r41094.4.6死锁的处理不让死锁发生：死锁预防（deadlockprevention）-静态所有进程都遵守某种资源使用协议死锁避免（deadlockavoidance）--动态实时检测资源申请命令，拒绝不安全请求允许死锁发生再处理：死锁检测（deadlockdetection）死锁恢复（deadlockrecovery）1104.4.7死锁预防主要思想：破坏死锁的四个必要条件逻辑公式：D→C1∧C2∧C3∧C4

C1∨C2∨C3∨C4→D其中：D：死锁Ci：死锁的必要条件111破坏互斥占用条件 让资源共享使用（但有些资源必须互斥）破坏占有等待条件将进程所要资源一次性分给进程，要么没分到一个资源，要么全部满足（适合廉价资源的分配,如外存空间分配）进程在提出申请资源前，必须释放所占的所有资源(用完一个再用下一个)112破坏非剥夺条件(用于内存管理、CPU管理等)当进程Pi申请ri类资源时，若有则分配，若没有则剥夺（释放）Pi占有的所有资源；当进程Pi申请ri类资源时，若有则分配，若无则剥夺（淘汰）占有ri类资源进程所占的ri类资源分配给Pi；或看占用ri类资源的Pk处于什么状态，若处于等资源状态，则剥夺其资源，否则让Pi等待,等于剥夺Pi的资源。113破坏循环等待条件 采用资源顺序分配方法：给每类资源编号，进程只能按序号由小到大的顺序申请资源，若不满足则拒绝分配。反证：若出现循环等待，则必会有小序号资源序号>大序号资源序号。114死锁预防：对进程有关资源的申请命令施加限制。死锁避免：对进程发出的每一个系统能够满足的资源申请命令实施动态检查。4.4.8死锁避免(动态的)检测可满足请求分配不分配安全不安全1154.4.8死锁避免1.银行家算法的提出依据：116例：设银行家有10万贷款，P,Q,R分别需要8,3,9万元搞项目(假设任何人满足资金总额后都会归还所有贷款)。描述格式：P(已拥有的)：申请的第一种情况：存在安全的贷款序列：QPR102P(4):4Q(2):1R(2):71P(4):4Q(3)R(2):74P(4):4R(2):70P(8)R(2):7P:4Q:2R:28R(2):71R(9)10Q(2):1Q归还P(4):4P归还R(2):7R归还返回117分析银行家考虑：当顾客申请资金时，能否给予满足的关键是－－这次提供的资金会不会给今后其它贷款造成障碍。算法实质：通过确保系统随时处于安全状态来避免死锁。如：上例方法中，存在安全的贷款序列：QPR，所以系统处于安全状态。118第二种情况:不存在安全的贷款序列，所以系统不安全。101P(4):4Q(2):1R(3):60P(4):4Q(3)R(3):63P(4):4R(3):6P:4Q:2R:3Q(2):1Q归还死锁1194.4.8死锁避免(动态的)定义：系统处于安全状态：存在安全进程序列<p1,p2,…,pn>设系统中有n个进程，若存在一个序列〈P1，P2…Pn〉使得Pi(i＝1，2…n)以后还需要的资源可以通过系统现有资源加上所有Pj(j＜i)占有的资源来满足，则称这个系统处于安全状态,序列<P1，P2…Pn〉称为安全序列。安全不安全死锁2.安全状态与安全进程序列p1,p2,…,pn可依次进行完。例1203.银行家算法的提出Banker’salgorithm,E.W.Dijkstra.进程：事先申明所需资源最大量（并不分配）系统：对每个可满足的资源申请命令进行安全性检查。

P={p1,p2,…,pn};R={r1(k1),r2(k2),…,rm(km)};121银行家算法(Cont.)数据结构：intAvailable[m]//系统可用资源intClaim[n,m]//进程最大需求intAllocation[n,m]//当前分配intNeed[n,m]//尚需资源intRequest[n,m]//当前请求临时变量：intWork[m]//记录可用资源intFinish[n]//进程是否完成其中:Claim[n,m]=Allocation[n,m]+Need[n,m]122银行家算法(Cont.)设X,Y为下标1..l的一维数组：XYj(1jl),X[j]Y[j]X=Yj(1jl),X[j]:=Y[j]X=cj(1jl),X[j]:=cX±Yj(1jl),X[j]±Y[j]123算法1银行家算法--资源分配算法Pi请求资源请求超量，错返Request[i]Available不满足，等待Available=Available-Request[i]

Allocation[i]=Allocation[i]+Request[i]Need[i]=Need[i]-Request[i]安全确认，pi继续FTFTTFRequest[i]Need[i]Available=Available+Request[i]

Allocation[i]=Allocation[i]-Request[i]Need[i]=Need[i]+Request[i]pi等待124算法2银行家算法--安全性检测算法Work=Available;Finish=false;Finish[i]=true;Work=Work+Allocation[i]有满足条件的i:Finish[i]=falseNeed[i]WorkTi,finish[i]=trueFTF安全不安全125银行家算法例子例1R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Claim

Allocation

Need

Available

Work

FinishABCABCABCABCABC753010743332322200122902302600222211011433002431P0:p1:p2:p3:p4:问：(1)系统是安全的吗？

(2)若p1请求：Request[1]=(1,0,2)，可否满足？332<532<743<745(1)运行安全性检测算法，令Work=Available=(3,3,2)Finish[1]=false，并且Need[1]=(1,2,2)<Work,则Work=Work+Allocation[1]=(3,3,2)+(2,0,0)=(5,3,2);Finish[1]=true；Finish[3]=false，并且Need[3]=(0,1,1)<Work,则Work=Work+Allocation[3]=(5,3,2)+(2,1,1)=(7,4,3);Finish[3]=true；

；Finish[4]=false，并且Need[4]=(4,3,1)<Work,则Work=Work+Allocation[4]=(7,4,3)+(0,0,2)=(7,4,5)；Finish[4]=true；Finish[2]=false，并且Need[2]=(6,0,0)<Work,则Work=Work+Allocation[2]=(7,4,5)+(3,0,2)=(10,4,7)；Finish[2]=true；1047<Finish[0]=false,并且Need[0]=(7,4,3)<Work,则Work=Work+Allocation[0]=(10,4,7)+(0,1,0)=(10,5,7)；Finish[0]=true；126解：(1)运行安全性检测算法，令Work=Available=(3,3,2)Finish[1]=false并且Need[1]=(1,2,2)<Work,则Work=Work+Allocation[1]=(3,3,2)+(2,0,0)=(5,3,2);

Finish[1]=true；Finish[3]=false并且Need[3]=(0,1,1)<Work,则Work=Work+Allocation[3]=(5,3,2)+(2,1,1)=(7,4,3);

Finish[3]=true；127Finish[4]=false并且Need[4]=(4,3,1)<Work,则Work=Work+Allocation[4]=(7,4,3)+(0,0,2)=(7,4,5)；Finish[4]=true；Finish[2]=false并且Need[2]=(6,0,0)<Work,则Work=Work+Allocation[2]=(7,4,5)+(3,0,2)=(10,4,7)；

Finish[2]=true；Finish[0]=false并且Need[0]=(7,4,3)<Work,则Work=Work+Allocation[0]=(10,4,7)+(0,1,0)=(10,5,7)；

Finish[0]=true；128可以找到一个安全进程序列<p1,p3,p4,p2,p0>，它使Finish[i]=true，对于所有0≤i≤4，因而可以断言系统当前处于安全状态．129银行家算法例子例1R={A(10),B(5),C(7)}P={p0,p1,p2,p3,p4}Claim

Allocation