《操作系统原理》课程教案授课时间第6周周四第1-2节课次第12讲.doc

《操作系统原理》课程教案 授课时间 第6周 周四 第1-2节 课次 第12讲 授课方式 理论课√讨论课□实验课□习题课□其他□ 课时 安排 2课时 授课题目：第3章 进程调度与死锁（4）（3.7死锁的检测和解除） 教学目的、要求（分掌握、熟悉、了解三个层次）： 通过学习，要求掌握死锁的主要检测方法，掌握死锁的解除常用方法。重点掌握资源分配图及死锁解除的相关图例。 教学重点及难点： 1、死锁的主要检测方法； 2、死锁的解除方法。 教学环节及时间设计 教学方法及注意点 复习旧课（1分钟）： 提问：为什么会产生死锁？ 产生死锁的必要条件有哪些？ 讲授新课（约80分钟）： 一、银行家算法 1.安全状态的概念 2.安排状态与非安全状态 3.利用银行家算法避免死锁 银行家算法，例题。 银行家算法）假定系统中有五个进程｛P0,P1,P2,P3,P4｝和三类资源｛A,B,C｝,各种资源的数量分别为10、4、7，在T0时刻的资源分配情况如图所示。分析以下情况： T0时刻的安全性 P1请求资源Request1(1，0，2) P4请求资源Request4(3，3，0) P0请求资源Request0(0，2，0) 资源情况 进程 MAX A B C Allocation A B C Need A B C Availnble A B C P0 7 5 3 0 4 3 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 二、死锁的检测 当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段，为此，系统必须做到： (1) 保存有关资源的请求和分配信息； (2) 提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。 1．资源分配图(Resource Allocation Graph) 系统死锁可利用资源分配图来描述。该图是由一组结点N和一组边E所组成的一个对偶G=(N1E)，它具有下述形式的定义和限制： (1) 把N分为两个互斥的子集，即一组进程结点P={p1，p2，…，pn}和一组资源结点R={r1，r2，…，rn}，N=P∪R。在图3-20所示的例子中，P={p1，p2}，R={r1，r2}，N={r1，r2}∪{p1，p2}。 (2) 凡属于E中的一个边e∈E，都连接着P中的一个结点和R中的一个结点，e={pi，rj}是资源请求边，由进程pi指向资源rj，它表示进程pi请求一个单位的rj资源。e={rj，pi}是资源分配边，由资源rj指向进程pi，它表示把一个单位的资源rj分配给进程pi。图3-13中示出了两个请求边和两个分配边，即E={(p1，r2)，(r2，p2)，(p2，r1)，(r1，p1)}。 用圆圈代表一个进程，用方框代表一类资源。由于一种类型的资源可能有多个，我们用方框中的一个点代表一类资源中的一个资源。此时，请求边是由进程指向方框中的rj，而分配边则应始于方框中的一个点。下图示出了一个资源分配图。图中，p1进程已经分得了两个r1资源，并又请求一个r2资源；p2进程分得了一个r1和一个r2资源，并又请求r1资源。 2．死锁定理 可以利用把资源分配图加以简化的方法(图3-21)，来检测当系统处于S状态时是否为死锁状态。简化方法如下： (1) 在资源分配图中，找出一个既不阻塞又非独立的进程结点Pi。在顺利的情况下，Pi可获得所需资源而继续运行，直至运行完毕，再释放其所占有的全部资源，这相当于消去pi所求的请求边和分配边，使之成为孤立的结点。在图3-21(a)中，将p1的两个分配边和一个请求边消去，便形成图(b)所示的情况 (2) p1释放资源后，便可使p2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图(c)所示的情况。 (3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。 对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。同样可以证明：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。 二、死锁的解除 当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是： (1) 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死