操作系统zxj-3处理机的调度和死锁.pptx

第三章

处理机的调度和死锁

处理机调度的基本概念高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。调度特性1.接纳作业数（内存驻留数）太多――― 周转时间T长太少――― 系统效率低2.接纳策略：即采用何种调度算法：FCFS、短作业优先等

处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。1.非抢占方式： 简单，实时性差(如win31)2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。3、中级调度（中程）为提高系统吞吐量和内存利用率而引入的一内------外存对换功能（换出时，进程为挂起或就绪驻外状态）运行频率：低中高。

0102三种调度被引发的事件？事件的表现方式？问？

仅有进程调度的队列模型01就绪队列02CPU03阻塞队列04交互用户05时间片完06进程调度07进程完成08等待事件09事件出现10调度的队列模型

具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度调度的队列模型

三、具有三级调度就绪队列CPU就绪、挂起队列时间片完进程调度进程完成后备队列阻塞、挂起队列事件出现作业调度阻塞队列等待事件挂起事件出现中级调度交互型作业

选择调度方式和算法的若干准则面向用户的准则周转时间短（常用于批处理系统）概念：作业从提交――完成的时间.分为：驻外等待调度时间驻内等待调度时间执行时间阻塞时间

平均周转时间平均带权可见带权w越小越好,Ts为实际服务时间。面向用户的准则选择调度方式和算法的若干准则

响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间输入传送时间处理时间响应传送时间截止时间的保证（特别于实时系统）优先权准则：（即需要抢占调度）面向用户的准则选择调度方式和算法的若干准则

面向系统的准则03各类资源的平衡利用。（？折算标准）吞吐量高（特别于批处理）：单位时间完成作业数0102处理机利用率好：（因CPU贵，特别于大中型多用户系统）选择调度方式和算法的若干准则

先来先服务和短作业（进程）优先调度算法调度算法——是一个资源分配问题先来先服务和短作业（进程）优先调度算法1.FCFS特点：简单，有利于长作业即CPU繁忙性作业2.短作业进程优先调度算法：SJ(P)F提高了平均周转时间和平均带权周转时间（从而提高了系统吞吐量）特点：对长作业不利，有可能得不到服务（饥饿）估计时间不易确定

例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.99

图3.4FCFS和SJF比较进程名ABCDE平均到达时间01234服务时间43524FCFS完成时间47121418周转时间461011149带权周转时间1225.53.52.8SJF完成时间4918613周转时间4816398带权周转时间12.673.11.52.252.1

高优先权优先调度算法1.优先权调度算法类型非抢占式优先权算法抢占式优先权算法，实时性更好。2.优先权类型：1．静态优先权：进程优先权在整个运行期不变。确定优先权依据（1）进程类型（2）进程对资源的需求；（3）根据用户需求。特点：简单，但低优先权作业可能长期不被调度。

高优先权优先调度算法(2)特点：响应比Rp=（tw+ts）/ts短作业RP大。ts（要求服务时间）相同的进程间相当于FCFS。长作业等待一段时间仍能得到服务。高响应比优先算法：动态优先权：如：优先权随执行时间而下降，随等待时间而升高。响应比Rp=（等待时间＋服务时间）/服务时间作为优先权优点：长短兼顾缺点：需计算Rp

时间片轮转基于时间片的轮转调度算法时间片大小的确定太大：退化为FCFS；太小：系统开销过大系统对响应时间的要求；T=nq就绪队列中进程的数目；系统的处理能力：（应保证一个时间片处理完常用命令）

多级反馈队列调度基于时间片的轮转调度算法大型作业不会长期不处理。中型作业周转时间不长；短作业一次完成；特点：长