chap3.6 死锁_.ppt

3.6.1 死锁产生若干死锁的例子(1) 例１进程推进顺序不当产生死锁 设系统有打印机、绘图仪各一台，被进程Ｐ和Ｑ共享。两个进程并发执行，按下列次序请求和释放资源： 进程Ｐ 进程Ｑ 请求绘图仪 请求打印机 请求打印机 请求绘图仪 释放绘图仪 释放绘图仪 释放打印机 释放打印机 ? 进程资源轨迹图 若干死锁的例子(2)例２PV操作使用不当产生死锁 进程Q1 进程Q2 ……… ……… P(S1); P(s2); P(s2); P(s1); 使用r1和r2; 使用r1和r2 V(S1); V(s2); V(S2); V(S1); 若干死锁的例子(3)例３资源分配不当引起死锁 若系统中有m个资源被n个进程共享，每个进程都要求Ｋ个资源，而m n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。 若干死锁的例子(4)例４对临时性资源使用不加限制引起死锁 进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。 进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待，产生死锁。 Bridge Crossing Example Traffic only in one direction. Each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possible. 死锁定义 操作系统中的死锁指：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。 例如，n个进程P1、P2，…，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。 产生死锁因素 不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。 The Conditions for Deadlock Three conditions must be present for a deadlock to be possible: Mutual exclusion: only one process may use a resource at a time Hold-and-wait : a process may hold allocated resources while awaiting assignment of others No preemption: no resource can be forcibly removed from a process holding it The Conditions for Deadlock We also need the occurrence of a particular sequence of events that result in: Circular wait: a closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain The Conditions for Deadlock Deadlock occurs if and only if the circular wait condition is unresolvable The circular wait condition is unresolvable when the first three conditions hold Thus the four conditions taken together constitute n