第3章-调度与死锁.pptVIP

　2．银行家算法 　　设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程P i需要K个R j类型的资源。当P i发出资源请求后，系统按下述步骤进行检查： 　　(1) 如果Request i[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 　　(2) 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。 　　(3) 系统试探着把资源分配给进程P i，并修改下面数据结构中的数值： Available[j] := Available[j]-Requesti[j]； Allocation[i,j] := Allocation[i,j]+Requesti[j]； Need[i,j] := Need[i,j]-Request i[j]； 　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 　　3．安全性算法 　　系统所执行的安全性算法可描述如下： 　　(1) 设置两个向量： 　　① 工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work:=Available。 　　② Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]:=false；当有足够资源分配给进程时，再令Finish[i]:=true。 　　(2) 从进程集合中找到一个能满足下述条件的进程： 　　① Finish[i]=false； 　　② Need[i,j]≤Work[j]；若找到，执行步骤(3)，否则，执行步骤(4)。 　　(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work[j]:= Work[j]+Allocation[i,j]； Finish[i]:=true； go to step 2； (4) 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。 2.多级反馈队列调度算法 多级队列调度算法把就绪队列划分成多个队列，为各个队列赋予不同的优先级，且各个队列中进程执行的时间片也不同（优先级越高，时间片越短）。 图3-7 多级反馈队列调度算法 几种常用调度算法的比较 w —— 至今在系统中用于等待和执行所花 费的时间。 e —— 至今在CPU上执行用去的时间。 s —— 进程所需的总体运行时间（包括e） 比较项目算法 FCFS RR SJF SRTF HRRF MFQ 选择依据 max[w] 常量 min[s] min[s-e] max((w+s)/s) 见3.3.3节 调度方式 非抢占式 抢占式（按时间片） 非抢占式 抢占式（进程到达时） 非抢占式 抢占式（按时间片） 吞吐量 不突出 如果时间片太小，可能变低 高 高 高 不突出 响应时间 可能很高，特别在进程执行时间有很大变化时 对于短进程提供良好的响应时间 对于短作业（进程）提供良好的响应时间 提供良好的响应时间 提供良好的响应时间 不突出 开销 最小 低 可能高 可能高 可能高 可能高 对进程的 作用 不利于短作业（进程）和I/O繁忙型作业（进程） 公平对待 不利于长作业（进程） 不利于长进程 良好的均衡 可能偏爱I/O繁忙型作业（进程） “饥饿”问题 无 无 可能 可能 无 可能 几种常用调度算法的比较 3.4 实时调度 什么是实时任务？ 对截止时间有严格要求的任务 截止时间可分为“开始时间”和“完成时间” 实现实时调度的基本条件 提供必要的信息 系统处理能力强，须满足以下公式： 其中，Ci为任务处理时间；Pi为任务周期 采用抢占式调度机制 具有快速切换机制 3.4.3　常用的几种实时调度算法 　　1．最早截止时间优先即EDF(Earliest Deadline First)算法 　　该算法是根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，每次调度时均选择队首。最早截止时间优先算法既可用于抢占式调度，也可用于非抢占式调度方式中。 　　1) 非抢占式调度方式用于非周期实时任务 　　图3-9示出了将该算法用于非抢占调度方式之例。该例中具有四个非周期任务，它们先后到达。 1 3 4 2 开始截止时间 任务执行 任务到达 1 2 3 4 1 3 4 2 t 图 3-