操作系统处理死锁

第三章处理机调度和死锁作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历下述三级调度。1.高级调度/作业调度(jobscheduling)2.低级调度/进程调度(processscheduling)1）非抢占方式(Non-PreemptiveMode)2）抢占方式(PreemptiveMode)3.中级调度(Intermediate-LevelScheduling)存储器的对换功能一、调度的类型和层次二、调度算法1.先来先服务（FCFS）调度算法(作业调度、进程调度)2.短作业（进程）优先(SJF/SPF)调度算法（作业调度、进程调度）3.高优先权调度（HPF）算法（作业调度、进程调度）4.高响应比优先(HRRF)调度算法(作业调度)5.时间片轮转（RR）算法（进程调度）6.多级反馈队列(MFQ)调度算法（进程调度）几种常见调度算法比较见下表所示：FCFSRRSJ(P)FHPFHRRFMFQ选择依据Max[w]常量Min[s]优先数Max[w＋s/s]调度方式非抢占抢占非抢占抢占非抢占抢占非抢占抢占应用系统批处理分时系统批处理批处理/分时批处理/分时分时吞吐量不突出时间片小，可能变低高不强调高不突出响应时间不突出好短进程响应时间好较好较好较好开销最小较小较高较高较高较高对进程作用不利于短作业公平对待不利于长作业(进程)良好的均衡良好的均衡可能偏爱I/o繁忙型作业“饥饿”无无可能可能无可能几种常见调度算法的比较三、常用的几种实时调度算法根据确定实时任务优先权方法的不同，可形成以下两种常用的实时调度算法：•1.最早截止时间（EDF）优先算法。EDF算法如何确定任务的优先权？或者说它是如何保证满足各任务对截止时间的要求的。•2.最低松弛度优先（LLF）算法。LLF算法如何确定任务的优先权？在什么情况下，一个进程应抢占被另一个进程占用的CPU。四、死锁的基本概念1.死锁的定义：多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，这些进程都将无法向前推进。2.产生死锁的原因（1）竞争资源（2）进程推进顺序非法3.产生死锁的必要条件(1)互斥条件(MutualExclusioncondition)(2)请求和保持条件(Requestandholdcondition)(3)不剥夺条件(Nonpreemptivecondition)(4)环路等待条件(Loopwaitingcondition)五、处理死锁的基本方法1.预防死锁摒弃“请求和保持”条件摒弃“不剥夺”条件摒弃“环路等待”条件2.避免死锁银行家算法避免死锁3.死锁的检测与解除当系统资源都为单体资源类时，若图中出现环路，则必存在死锁。在系统资源为多体资源类时，图中出现环路，系统不一定死锁。系统存在死锁，则资源分配图中一定出现环路。4.鸵鸟策略利用资源分配图，死锁定理进行死锁判定。资源分配策略死锁预防死锁避免死锁检测和解除很保守；对资源不做调配使用介于预防和检测间，安全状态非常开放；申请资源就分配，但定期检测采用的方式一次性分配所有资源抢占式资源分配资源编号，按序分配至少找一个安全序列定期调用检测算法，是否出现死锁主要优点•适用单一突发进程•无需抢占•最容易实现适用资源状态便于保存和恢复的情况•适用于编译时强行检查•运行无需计算无需抢占从来不延误进程的开始执行，便于联机处理主要缺点•设备利用率低，效率低•延误进程开始时间抢占动作比实际需要次数多•占用没有太多用处的资源•不允许增加对资源的申请•须知道以后对资源申请情况，实现困难•进程可能被阻塞很长时间丧失固有的抢占性。执行检测算法需要一定的CPU开销。几种处理死锁方法的比较典型问题分析1.n个进程共享m个同类资源，若每个进程都需要用该资源，而且每个进程对该类资源的最大需求量之和小于m+n。说明该系统不会因竞争该类资源而阻塞。2.当前运行的进程（），将引发系统进行进程调度。A.执行了一条转移指令B.要求增加主存空间，经系统调用银行家算法进行测算认为是安全的C.执行了一条I/O指令D.执行程序期间发生了I/O完成中断证明：设每个进程最多申请资源x个（1≤x≤m），最坏情况下，为进程分配资源数为n（x-1）。系统剩余资源为m-n（x-1）。只要m-n（x-1）≥1；则系统不会出现死锁。整理得：nx≤m+n-1，所以nx≤m+n时，不会引起死锁3、下列选项中，降低进程优先权级的合理时机是（）A：进程的时间片用完B：进程刚完成I/O，进入就绪队列C：进程长期处于就绪队列中D：进程从就绪状态转为运行态A3、下列关于死锁的说法中，正确的是？1）有环必死锁;2）死锁必有环;3）有环无死锁;4）死锁也无环4、不安全状态是否必然导致系统进入死锁状态？5、一台计算机有8台磁带机，它们由N个进程竞争使用，每个进程可能需要3台磁带机，请问N为多少时，系统没有死锁的危险？6、系统中有4个并发进程，都需要某类资源3个。试问该类资源最少为多少时，不会因竞争该资源而发生死锁。7、资源有序分配法的目的是？1）死锁预防;2）死锁避免;3）死锁检测;4）死锁解除8、Banker算法是（）算法?1）死锁预防;2）死锁检测；3）死锁避免；4）安全性判定9注意：系统处于不安全状态可能发生死锁，并非一定发生死锁。因为进程活动期间对资源的请求是动态的，时而申请，时而释放。因此，当系统处于不安全状态时，若某些进程释放了一些资源，则可能系统又进入了安全状态。9、三个进程P1、P2和P3并发工作。进程P1需要资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3，请回答：（1）若对资源分配不加限制，会发生什么情况？为什么？（2）为保证进程正确工作，应采用何种资源分配策略？为什么？解答：(1)若对进程间的资源分配不加限制，可能会发生死锁。若进程P1、P2和P3分别获得资源S3、S1和S2，后再继续申请资源时会导致进程间的“循环等待”，并且这种状态将永远持续下去。(2)为保证系统处于安全状态，应采用下面列举3种资源分配策略：1)采用静态资源分配：由于执行前已获得所需全部资源，故不会出现占有资源又等待资源的现象，从而避免资源的循环等待。2)采用资源按序分配，避免出现循环等待资源的现象。3)采用银行家算法进行分配资源前的检测。10、在银行家算法中，若出现下述的资源分配情况问：1）该状态是否安全？2）若进程p2提出request(1，2，2，2)后，系统能否将资源分配？为什么？ProcessAllocationNeedavaliableP0003200121622P110001750P213542356P303320652P40014065611、有一个具有两道作业的批处理系统，作业调度采用短作业优先调度算法，进程调度采用以优先数为基础的抢占式调度算法，如表所示的作业序列（表中所列作业优先数即为进程优先数，数值越小优先级越高）作业执行时间作业名到达时间估计运行时间优先数A10：0040分5B10：2030分3C10：3050分4D10：5020分61）列出所有作业进入内存时间及结束时间。2）计算平均周转时间解答：各作业进入内存的时间和结束时间见表：作业名进入内存时间结束时间A10：0011：10B10：2010：50C11：1012：00D10：5012：20各作业执行时的周转时间为：A：70分钟B：30分钟C：90分钟D：90分钟平均周转时间：70分钟12、设系统有三种类型的资源，数量为（4，2，2）。系统进程P1、P2、P3按如下顺序请求资源；进程P1申请（2，2，1）进程P2申请（1，0，1）进程P1申请（0，0，1）进程P3申请（2，0，0）该系统按照死锁预防中破坏“不可剥夺”条件，对上述申请序列，给出资源分配过程。指出哪些进程需要等待资源，哪些资源被剥夺。进程可能进入无限等待状态吗？解答：（1）资源分配过程：P1申请（2，2，1），分配，可用资源（2，0，1）；P2申请（1，0，1），分配，可用资源（1，0，0）；P1再申请（0，0，1），不分配，且缺少的资源没被等待进程占有，无法剥夺，因此P1等待，可用资源不变；P3申请（2，0，0），资源不够，但缺少的资源被等待进程P1占有，因此P3剥夺P1资源（1，0，0），P1剩余（1，2，1）等待第1类和第3类资源，可用资源（0，0，0）；（2）这种方法会导致某些进程无限期的等待如果再创建的进程总是只申请第1和第3类资源，总是占有系统所剩下的第1和第3类资源的全部且不阻塞，那么进程P1将会无限期等待。