第二章 操作系统 4、处理机.ppt

死锁检测的方法 Work:=Available; L:= {Pi |Allocationi=0∩ Needi =0}; for all Pi?L do begin for all Needi ≤Work do begin Work:=Work + Allocationi; L:= Pi∪L; end end deadlock:=(L≠{P1, P2 , … , Pn}); 死锁解除 发现进程死锁后，应立即把它从死锁状态中解脱出来，常采用的方法有： 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态； 撤消进程：直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止。 终止进程的方法 终止所有死锁进程：代价大，部分进程可能已接近结束。 逐个终止进程：选择终止的依据是“代价最小”，包括进程优先级、已运行时间和剩余时间、已使用资源和需求资源、进程是交互式还是批处理式。 付出代价最小的死锁解除算法 作业 证明对于给定的一组进程，使用非抢占的短作业优先调度算法时，进程的平均完成时间最短。 实时系统中有2个周期任务。第一个任务每隔m1秒需要进行n1次运算；第二个任务每隔m2秒需要进行n2次运算。现有2种CPU可供选择，第一种CPU每秒能运算r1次运算，价格为c1；第二种CPU每秒能运算r2次，价格为c2。问如何配置最省钱。 课件第81页银行家算法案例中，如果把P0请求从Request0(0,2,0)改为Request0(0,1,0)，系统是否安全？ 证明同一个资源分配图按不同的简化顺序都将得到相同的不可简化图。 证明死锁定理是正确的。 写死锁解除算法，使用撤消进程的方法，通过撤销权值（表示撤销代价）总和最小的n个进程，使系统脱离死锁状态。 设n个进程的处理顺序是P1、P2、…、Pn，执行时间是t1、t2、…、tn，进程的平均完成时间为 若进程不全按短作业优先原则，即存在Pj和Pk进程，满足jk且tjtk，则将Pj和Pk进程的交换，形成新的处理顺序P1、…、Pj-1、Pk 、Pj+1 …、Pk-1、Pj 、Pk+1、…、Pn ，进程的平均完成时间为 两个周期任务平均每秒运算次数L=n1/m1+n2/m2 ，设 For i=0 to k //i表示第一种CPU数量 //j表示第二种CPU数量 c=c1*i+c2*j //c表示总成本 将最小的c对应的i和j作为第一种和第二种CPU的配置数量 P1、P3、P4、P2、P0 对于进程P1、P2、…、Pn，若资源分配图的两种简化方法涉及的进程（Pj1、Pj2、…、Pjm）相同，仅简化的顺序不同。由于资源简化的方法是将与进程节点有关的边都删除形成孤立节点，与执行顺序无关。资源分配图的初始值相同，故简化后也相同。 若方法一与方法二涉及不同的进程，不妨设方法一中有Pjk进程，而方法二中没有，则将Pjk进程补到方法二最后一个进程后。方法一在处理Pjk进程时仅回收了Pj1、Pj2、…、Pjk-1的资源，而方法二已回收了除Pjk外Pj1、Pj2、…、Pjm的资源，故有足够资源供Pjk完成，因此方法二不是不可简化图，与已知矛盾。 不同的简化方法涉及的进程相同，顺序可能不同，故得到相同的不可简化图。 若资源分配图可完全简化，则必然存在一个简化顺序P1、P2、…、Pn ，该顺序即为进程能够顺序执行完毕的一种方法。故存在死锁时，资源分配图是不可完全简化的。 同理，当进程能够顺序执行完毕时，必然存在一个执行顺序P1、P2、…、Pn ，该顺序即为资源分配图的完全简化顺序。故若资源分配图是不可完全简化的，则存在死锁。 将空集以及对应的代价0作为第一个元素放入队列中 循环执行 取队列首个元素A 若终止A中进程可解除死锁状态，则退出循环，A包含的进程为需终止进程，对应最小代价 分别在A中添加一个不在A中的其他进程，计算代价，并根据代价大小，与队列中已有的元素按从小到大的顺序排序，重新放入队列中 计算机、软件 软件 计算机 软件 计算机 软件 计算机 软件 处理死锁的方法 预防死锁：属于事先预防策略。通过设置某些限制条件，破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。 避免死锁：属于事先预防策略，在资源的动态分配过程中，用某种方法防止系统进入不安全状态，避免发生死锁。 处理死锁的方法 检测和解除死锁：不事先采取任何限制性措施，允许进程在运行过程中发生死锁。通过检测机构及时检测死锁，撤消一些进程，回收资源，并分配给其他阻塞状态的进程，使其能继续运行。 处理机调度和反死锁策略 处理机调度的层次和调度算法的目标 作业与作业调度 进程调度 实时调度 死锁概述 预防死锁 避免死锁 死锁的检测与解