操作系统3调度n精品.pptVIP

TechEd 2002 第三章 处理机调度 一、处理机的3级调度 二、作业的状态与处理流程 一、先来先服务(FCFS)调度算法 二、时间片轮转(RR)调度算法 三、优先级调度算法 四、多级队列调度算法 作业调度程序 二、选择调度算法时应考虑问题 如系统各类资源的均衡使用；对用户公平并使用户满意；用户作业到达系统的时间；作业的优先数；对主存和外设的要求；以及整个系统的效率等。 设计时应将那些对系统运行影响较大的关键因素作为调度算法考虑的主要依据。 (2)公平对待后备队列中每一个作业，顾及各种类型作业的情况。 例如:个别用户可能要求使用系统中的几乎全部外设，却只要求很少的主存。系统若满足这类用户的愿望，势必影响主存利用率，从而降低系统效率，所以一般都不得不推迟这种作业的运行时间，等到有要求内存多而外设少的作业与之搭配运行。但是我们选择的算法也不应使一个作业的运行被无限制地推迟。 (3) 均衡使用系统资源，克服资源忙闲不均情况出现。 在考虑设计目标的前提下应充分发挥各种资源的效能，最大限度地使它们忙碌。科学计算型作业和数据处理型作业搭配运行就是一种方法。 (4) 在使用优先级的系统中，每个进程都有一个优先数，调度算法应优先运行高优先级进程。 (5) 在使用优先数的系统中，调度策略还分为“可抢占 ” 和“不可抢占 ” 两种方式。抢占策略通常使用于需要迅速响应高优先级进程的系统中。 一、先来先服务调度算法 二、短作业优先调度算法 三、最短剩余时间优先调度算法 四、高响应比优先调度算法 §3.3 作业的调度 在批处理系统中，系统吞吐能力是衡量算法的主要着眼点，通常用作业的“周转时间”来定量判断。 周转时间：作业提交?作业完成之间的时间 Ti = Wi - Si Si ：作业i 提交给系统的时间 Wi ：作业i完成的时间 带权周转时间： Wi’’‘=Ti / 运行时间 平均周转时间： n个作业的平均周转时间 T = （T1+T2+. . .+Tn）/ n 平均带权周转时间: W = （W1+W2+. . .+Wn）/ n §3.4 作业调度算法 基本思想：以作业进入后备队列的先后为依据。 →从后备队列选一个或多个最先进入队列的作业 →将作业调入内存、分配资源、创建进程 →放入进程就绪队列 §3.4 调度算法 例：三个作业按表中顺序同时提交系统，采用先来先服务作业调度算法。求出每个作业的周转时间和它们的平均周转时间。 分析：三作业同时提交系统，可看作到达时间都为0，Si =0 解: T1=W1-S1=24-0=24 T2=W2-S2=(24+3)-0=27 T3=W3-S3=(24+3+3)-0=30 T =(T1+T2+T3 ) /3 =(24+27+30)/3=27 3 3 3 2 24 1 所需CPU时间 作业提交顺序 0 24 27 30 §3.4 调度算法 1.6 12.3 0.2 10.7 5 1.5 12.1 0.4 10.6 4 1.2 11.7 0.4 10.5 3 1 11.3 0.5 10.3 2 0.7 10.8 0.7 10.1 1 周转时间 完成时间 所需CPU时间 到达时间 作业 例：5个作业提交系统，采用先来先服务作业调度算法。求出每个作业的周转时间和它们的平均周转时间。 解:T=(T1+T2+T3 +T4+T5) /5 =(0.7+1+1.2+1.5+1.6)/5=1.2 .1 10 10.8 .3 .5 .7 .6 11.3 11.7 12.1 12.3 §3.4 调度算法 合计 0.20 9.50 4 0.10 9.00 3 0.50 8.50 2 2.00 8.00 1 Wi(Z) ti(时) tC(时) tB(时) tR(时) ts(时) 带权周转时间 周转时间 完成时间 开始时间 运行时间 提交时间 作业 例： §3.4 调度算法 27.50 6.90 合计 6.50 1.30 10.80 10.60 0.20 9.50 4 16.00 1.60 10.60 10.50 0.10 9.00 3 4.00 2.00 10.50 10.00 0.50 8.50 2 1.00 2.00 10.00 8.00 2.00 8.00 1 Wi(Z) ti(时) tC(时) tB(时) tR(时) ts(时) 带权周转时间 周转时间 完成时间 开始时间 运行时间 提交时间 作业 平均周转时间 T=6.90/4=1.725(小时) 平均带权时间 W=27.5/4=6.