操作系统-第3章-处理机调度与死锁讲述.ppt

* * 图3-21　资源分配图的简化 * * 　　(2) p1释放资源后，便可使p2获得资源而继续运行，直至p2完成后又释放出它所占有的全部资源，形成图(c)所示的情况。 　　(3) 在进行一系列的简化后，若能消去图中所有的边，使所有的进程结点都成为孤立结点，则称该图是可完全简化的；若不能通过任何过程使该图完全简化，则称该图是不可完全简化的。 　　对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。同样可以证明：S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。 * * 　3．死锁检测中的数据结构 　　死锁检测中的数据结构类似于银行家算法中的数据结构： 　　(1) 可利用资源向量Available，它表示了m类资源中每一类资源的可用数目。 　　(2) 把不占用资源的进程(向量Allocationi:=0)记入L表中，即Li∪L。 　　(3) 从进程集合中找到一个Requesti≤Work的进程，做如下处理： 　　① 将其资源分配图简化，释放出资源，增加工作向量Work:=Work + Allocation i。 　　② 将它记入L表中。 * * 　　(4) 若不能把所有进程都记入L表中，便表明系统状态S的资源分配图是不可完全简化的。 因此，该系统状态将发生死锁。 　　Work:=Available； 　　　L:={Li |Allocation i=0∩Request i=0} 　　　for all Li　　 　L do 　　　　　begin 　　　　　　　for all Request i≤Work do 　　　　　　　　　begin 　　　　　　　　　　Work?:=Work + Allocation i； 　　　　　　　　　　Li∪L； 　　　　　　　　　end 　　　　　　　end 　　　　　deadlock?:=┓(L={p1，p2，…，pn})； * * 3.7.2　死锁的解除 　　当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是： 　　(1) 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。 　　(2) 撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。 　　在出现死锁时，可采用各种策略来撤消进程。例如，为解除死锁状态所需撤消的进程数目最小；或者，撤消进程所付出的代价最小等。一种付出最小代价的方法如图3-22所示。 * * 图 3-22　付出代价最小的死锁解除方法 * * 　　假定在死锁状态时，有死锁进程P1，P2，…，Pk。首先，撤消进程P1，使系统状态由S→U1，付出的代价为CU1，然后，仍然从S状态中撤消进程P2，使状态由S→U2，其代价为CU2，…，如此下去可得到状态U1，U2，…，Un。若此时系统仍处于死锁状态，需再进一步撤消进程，如此下去，直至解除死锁状态为止。这种方法为解除死锁状态可能付出的代价将是k(k-1)(k-2)…/2C。显然，所花费的代价很大，因此，这是一种很不实际的方法。 * * 　　一个比较有效的方法是对死锁状态S做如下处理：从死锁状态S中先撤消一个死锁进程P1，使系统状态由S演变成U1，将P1记入被撤消进程的集合d(T)中，并把所付出的代价C1加入到rc(T)中；对死锁进程P2、P3等重复上述过程，得到状态U1，U2，…，Ui，Un，然后，再按撤消进程时所花费代价的大小，把它插入到由S状态所演变的新状态的队列L中。显然，队列L中的第一个状态U1是由S状态花最小代价撤消一个进程所演变成的状态。在撤消一个进程后，若系统仍处于死锁状态，则再从U1状态按照上述处理方式再依次地撤消一个进程，得到， 　　，状态，再从状态中选取一个代价最小的，如此下去，直到死锁状态解除为止。为把系统从死锁状态中解脱出来，所花费的代价可表示为： R(S)min?=?min{CUi}?+?min{CUj}?+?min{CUk}?+?… * * * P33： 7,12,14,15,16,17 课程作业 * * * 　　这种预防死锁的方法其优点是简单、易于实现且很安全。但其缺点却也极其明显： （1）首先表现为资源被严重浪费，因为一个进程是一次性地获得其整个运行过程所需的全部资源的，且独占资源，其中可能有些资源很少使用，甚至在整个运行期间都未使用，这就严重地降低了系统资源的利用率； （2）其次是使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行，但可能因有些资源已长期被其它进程占用而致使