《处理机调度与死锁》PPT课件

《《处理机调度与死锁》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章处理机调度与死锁3.1处理机调度的基本概念3.2作业调度3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除3.1处理机调度的基本概念3.1.1高级、中级和低级调度处理器调度分为三级：高级调度（作业调度）（长程调度）中级调度（中期调度）低级调度（进程调度）（短程调度）按某种原则从后备状态挑选作业调入内存运行为作业创建进程为选中作业分配资源1.高级调度(LowLevelScheduling)2.中程调度决定哪些作业允许参于竞争处理机资源。作用：起到短期调整系统负荷，以平顺系统。方式：“挂起”，“解

2、挂”。3.低级调度按某种原则将处理机分配给就绪进程。进程调度属操作系统内核，执行频率很高。进程调度是最基本的一种调度，它可以采用非抢占方式或抢占方式。1)非抢占方式(Non-preemptiveMode)在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个：①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。2)抢

3、占方式(PreemptiveMode)抢占的原则有：优先权原则。(2)短作业(进程)优先原则。(3)时间片原则。4.处理机三级调度关系新建就绪挂起阻塞挂起就绪阻塞运行退出长程调度长程调度中程调度中程调度进程调度调度和进程状态转换3.1.2调度队列模型1.仅有进程调度的调度队列模型仅具有进程调度的调度队列模型2.具有高级和低级调度的调度队列模型具有高、低两级调度的调度队列模型就绪队列的形式。(2)设置多个阻塞队列。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个方面。3.同时具有三级调度的调度队列模型具有三级调

4、度时的调度队列模型就绪队列进程调度CPU就绪挂起队列中级调度阻塞挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2.1作业调度的职能记录已进入系统的作业情况JCB调度算法：按照某种调度算法从后备状态挑选作业运行。运行准备：为选中作业创建进程，分配主存和外设。结束善后处理：收回资源，输出必要信息。作业进入后备状态建立作业退出系统时撤消3.2作业调度3.2.2作业控制块作业存在唯一标志作业调度的依据记录作业的有关信息，反映作业运行情况内容进入系统时建立退出系统时撤消作业名资源要求资源使用情况类型说明状态

5、3.2.3调度性能的衡量平均周转时间：作业kTk=Tck-Tsk=T等待+T运行平均周转时间T=1/nTk带权周转时间：作业kWk=Tk/TRk平均带权周转时间W=1/nWkK=1nK=1nTck：作业K完成时间Tsk：作业K提交时间TRk：作业K运行时间3.2.4选择调度方式和调度算法的若干准则1.面向用户的准则周转时间短。响应时间快。(3)截止时间的保证。(4)优先权准则。2.面向系统的准则系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。3.3调度算法先进先服务调度算法短作业优先调度算法高优先权优先调度算法最高响应比优先时间

6、片轮转调度算法最短剩余时间优先调度算法均衡法多级反馈队列调度算法3.3.1先来先服务调度算法其原则按照作业到达系统或进程进入就绪队列先后次序来选择。FIFO是一种非抢占算法。例题进程到达时间服务时间优先数10322265344346565821作业1作业2作业3作业4作业5039131820T=1/5（3+7+9+12+12）=8.60W=1/5（1+1.17+2.25+2.40+6.00）=2.56特点:吞吐量不定、耗费最小、无饥饿、对偏重于I/O进程不利，响应时间很高，尤其是进程执行时间变化很大时3.3.2短作业(进程)优先调度算法短作业(进程

7、)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。作业1作业2作业5作业3作业4039111520T=1/5（3+7+11+14+3）=7.60W=1/5（1+1.17+2.75+2.80+1.50）=1.84SJ(P)F调

8、度算法也存在不容忽视的缺点：(1)该算法对长作业不利，更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，