习题课处理机的调度与死锁.ppt

选择调度方式和调度算法的若干准则,一、面向用户的准则1周转时间短2响应时间快3截止时间的保证4优先权准则,二、面向系统的准则1系统吞吐量高2处理机利用率好3各类资源的平衡利用,衡量标准,作业周转时间如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts它是作业在系统里的等待时间与运行时间之和。,平均作业周转时间为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间 T=(ti)/n,衡量标准,作业带权周转时间如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，带权周转时间总大于1。平均作业带权周转时间平均作业带权周转时间W=(wi)/n,衡量标准,响应比作业进入系统后的等待时间与估计运行时间之比称作响应比，现定义；响应比 1+已等待时间/估计运行时间,调度算法,先来先服务算法最短作业优先算法高优先权优先调度算法时间片轮转法高响应比优先调度算法,调度算法,例：有五个批处理作业A，B，C，D，E几乎同时到达一个计算中心，估计的运行时间分别为2，4，6，8，10min，它们的优先权分别为1，2，3，4，5（5为最高优先级）。请用下面的调度算法，分别计算作业的平均周转时间（忽略作业的切换开销）：优先级调度时间片轮转（时间片为2min）FIFO（作业的到达顺序为C，D，B，E，A）最短作业优先,调度算法,优先级：10 18 24 28 30=22时间片轮转 2 12 20 26 30=18FIFO 6 14 18 28 30=19.2短作业 2 6 12 20 30=14,调度算法,例：如下表所示，把作业交给单道批处理系统，采用最高响应比优先调度算法，分别计算其周转时间T和平均带权周转时间W。,调度算法例：假设一个系统中有5个进程，它们的到达时间和服务时间如下表所示，忽略I/O以及其他开销时间，若分别按照先来先服务（FCFS）、非抢占及抢占的短进程优先(SPF)、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)以及立即抢占的多级反馈队列调度算法(FB，第i级队列的时间片=2i-1)进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。,先来先服务FCFS First Come First Served短进程优先SPF(SPN)Shortest Process First(Next)短作业优先SJF Shortest Job First 高响应比优先HRRF(HRRN)Highest Response Ratio First(next),SJF算法是非抢占式的，可以改进成抢占式的调度算法。当一个作业正在执行时，一个新作业进入就绪状态，如果新作业所需CPU时间比当前正在执行的作业剩余下来还需要的CPU时间短，抢占式短作业优先算法强行赶走当前正在执行的作业，这种方式叫最短剩余时间优先（Shortest Remaining Time First,SRTF）算法。,死锁,在银行家算法中，若出现下述资源分配情况：试问：该状态是否安全？若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？,