第三章处理机调度与死锁2

第三章 处理机调度与死锁内容提要n处理机调度及调度算法n产生死锁的原因和必要条件n预防死锁的方法，死锁的检测与解除 n银行家算法第三章 处理机调度与死锁处理机调度： 按一定方法 动态地 把处理机 分配给 就绪队列中的一个进程WHAT ： 按什么原则分配 CPU 进程调度算法WHEN ： 何时分配 CPU 进程调度的时机HOW ： 如何分配 CPU CPU 调度过程（进程的上下文切换）第三章 处理机调度与死锁3.1 处理机调度的基本概念1)调度类型 高级调度 ：即作业调度，选择后备作业进入内存，为其建立进程 ,分配资源并排在就绪队列。 中级调度 ：即对换调度，将暂不运行的进程调到外存等待，从而提高内存利用率和系统吞吐量 低级调度 ：即 进程调度 ，决定哪个进程可以占用 CPU， 进入运行状态。输入程序就绪阻塞就绪运行 完成阻塞后备外存中级调度对换低级调度作业调度2)进程调度方式调度方式是指但某一个进程正在处理机上执行时如果有个更重要更紧迫的进程需要处理此时应该如何分配处理机。n 非抢占方式进程一旦被调度执行，除非进程完成或发生某事件被阻塞，否则不允许其他进程抢夺其执行权。n 抢占方式允许按某种策略（原则）剥夺正在执行的进程的执行权-优先权原则-短作业 (进程 )优先原则-时间片原则3)调度类型与 O.S类型的关系 多道批处理系统：存在作业调度、进程调度 分时 /实时系统：只有进程调度共同点：均存在进程调度（分配 CPU）4) 调度队列模型 (三种 )n 仅有进程调度的调度队列模型仅有进程调度的调度队列模型n 具有高级和低级的调度队列模型n 具有三级调度的调度队列模型调度队列模型n 仅有进程调度的调度队列模型就 绪 队 列阻 塞 队 列进程调度 CPU 进程完成等待事件交互用户事件出现时间片完进程调度 CPU 进程完成时间片完就 绪 队 列12等待事件等待事件等待事件 n12n事件 出现事件 出现事件 出现后 备 队 列作业调度 与上一模型的 主要区别：就绪队列的形式；设置多个阻塞队列阻 队 列塞 2阻 队 列塞 n阻 队 列塞 1n 具有高级和低级的调度队列模型n 同时具有三级调度的调度队列模型就绪队列 进程调度就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现事件出现CPU5) 调度性能评价 作业调度算法的评价因素 CPU利用率 ：越高越好 吞吐量 ：单位时间内 CPU完成作业的数量 周转时间 ：通常与带权周转时间一起作为评价批处理系统的性能指标，定义如下：其中：作业其中：作业 Ji的提交时间为的提交时间为 tsi，执行时间为执行时间为 tri，完成时间为，完成时间为 toin个作业的平均周转时间 T和平均周转系数 W分别为n 对于每个用户来说，总是希望作业提交后立即执行，这样周转时间等于执行时间；而对于一个计算机系统来说，不可能满足每个用户的这种要求，只能使系统的平均周转时间最短。n 对于分时系统常把响应时间的长短作为评价标准；对于实时系统常把截止时间作为评价标准。3.2 调度算法l 先来先服务调度算法l 短作业（进程）优先调度算法l 高优先权者优先调度算法l 时间片轮转调度算法l 多队列反馈轮转调度算法l 实时调度算法相关术语n 调度算法：根据系统的资源分配策略所规定的资源分配算法n 几个术语 到达时间、服务时间、开始时间 完成时间、等待时间 周转时间：完成时间 -到达时间 带权周转时间：周转时间 /服务时间1）先来先服务调度算法 策略： 先进入后备队列（就绪队列）的作业（进程）先被调度 优点： 算法简单易实现 缺点： 不分轻重缓急，对短作业（进程）不利2）短作业（进程）优先调度算法 策略： 启动要求运行时间最短的作业。 优点： 有效降低作业平均等待时间 提高系统的吞吐量 缺点： 长作业（进程）可能长期得不到服务进程名 到达时 间 服务时 间 开始时 间 完成时 间 周转时 间 带权周转时间平均0 4A1 3B2 5C3 2D4 4E0 4 44 7 6例：先 来 先服务算法（ FCFS） 7 12 1012 14 1114 18 141225.53.59 2.8A A A A B B B C C C C C D D E E E E0 5 10 15 18t进程名 到达时 间 服务时 间 开始时 间 完成时 间 周转时 间 带权周转时间平均0 4A1 3B2 5C3 2D4 4E0 4 4 1例：短作业 /短进程优先（ SJF/SPF）4 6 3 3/26 9 8 8/39 13 9 9/413 18 16 16/540/5 2.1A A A A B B B C C C C CD D E E E E0 5 10 15 18t3）高优先权者优先调度算法 优先权： 反映作业（进程）重要性和调度级别的权值，又称优先数。通常分为：静态优先数 ：进程创建时确定运行过程中 保持不变 。一般根据进程的类型，资源需求情况，估计的运行时间等因素确定。一般用一整数进行表示（如 0至 32）动态优先数 ：创建进程时确定一个优先级，进程运行过程中可以根据情况的变化调整优先级，调整一般是根据进程占用的 CPU的时间长短、进程等待 CPU时间长短来进行（如高响应比优先）。 调度类型非抢占式优先权调度 ：处理机一旦分配给就绪队列中优先权最高的进程后，该进程就一直运行下去直到自动放弃或完成，这时才可把处理机分配给另一优先级最高的进程。抢占式优先权调度 ：进程在运行时一旦出现了另一个优先级更高的进程，调度程序就停止该进程而把处理机分配给新出现的高优先权进程。进程名到达时间服务时间静态优先权开始时间完成时间周转时间带权周转时间平均例：静态优先权，非抢占式（ 1为高优先权）0 4A 41 3B 22 5C 33 2D 54 4E 10 4 4 14 8 4 18 11 10 10/311 16 14 14/516 18 15 15/29.4 2.93考虑一下 抢占式 ，情况如何？ 高响应比优先调度算法（ HRP）： 优先调度响应比高的作业对短作业有利是先来先服务对长作业有利缺点：要进行响应比计算，增加了系统开销小结：等待时间相同的作业，则要求服务的时间愈短，其优先权愈高要求服务的时间相同的作业，则等待时间愈长，其优先权愈高长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机4）时间片轮转调度算法（适合于分时系统） 策略 系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把 CPU分配给队首进程，并令其执行一个时间片 当执行的时间片用完时，由一个计时器发出 时钟中断 请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首 优、缺点： 简单易实现，但不分轻重缓急 关键： 时间片大小的选择例：基于时间片的轮转调度算法进程名 到达时 间 服务时 间 开始时 间 完成时 间 周转时 间 带权周转时间平均 A B C D E A B C D E A B C E A C E C0 5 10 15 18t0 4A0 3B0 5C0 2D0 4E0123491215171815 15/411 11/316 16/56 6/213 13/412.2 2.12若 到达时间为 0、 1、 2、3、 4，又如何？5）多级队列反馈轮转调度算法 策略：将时间片 与 优先级 调度相结合。-设置多个就绪队列，分别赋予不同的优先级。优先级越低则时间片越长-新进程进入内存后，先投入第一队列的末尾，按 FCFS算法调度；若按第一队列一个时间片未能执行完，则降低投入到第二队列的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按 “ 时间片轮转 ” 算法调度直到完成-仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾就绪队列 1就绪队列 2就绪队列 3就绪队列 nS1S2S3至 CPU至 CPU至 CPU至 CPU(时间片： S1 S2 S3)高低优先级时间片小大Sn按 FIFO原则排队等待调度尚未完成转入第二队列的末尾，按FIFO原则等待调度采取按时间片轮转的方式运行因等待而放弃 CPU后，进入阻塞队列，一旦等待的事件发生，则回到原来的就绪队列调度算法性能分析设有四个作业，其提交时刻、执行时间如下表所示，分别采用FCFS、 SJF、 FPF调度方法，计算平均周转时间 T和平均周转系数 W。 作业号 提交时刻 运行时间1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.20 先来先服务调度算法：顺序为 1 2 3 4，平均周转时间和平均周转系数的计算结果如下表所示：作业 提交时间 执行时间 开始时间 完成时间 周转时间 周转系数1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.208.00 10.00 2.00 1.0010.00 10.50 2.00 4.0010.50 10.60 1.60 16.0010.60 10.80 1.30 6.506.90 27.50 平均周转时间 T 1.725小时，平均周转系数 W 6.875 最短作业优先调度算法 ：由于在 8.00开始执行作业，当时仅有 1，而作业 2， 3， 4尚未到达，故作业 1是最短作业。 作业 1执行完成后是 10.00，此时作业 2， 3， 4均已经到达，故选最短作业 3，然后是4， 2。所以 顺序为 1,3,4,2。 平均周转时间和平均周转系数的计算结果如下表所示： 作业 提交时间 执行时间 开始时间 完成时间 周转时间 周转系数1 8.00 2.002 8.50 0.503 9.00 0.104 9.50 0.208.00 10.00 2.00 1.0010.00 10.10 1.10 11.0010.10 10.30 0.80 4.0010.30 10.80 2.30 4.606.20 20.60 平均周转时间 T 1.55小时，平均周转系数 W 5.15 响应比高者优先算法：在作业 1执行完成，计算作业 2， 3， 4的响应比分别为： 4，11， 3.5，因此作业 1执行完成后选中作业 3完成。执行顺序为 1， 3， 2， 4。按此算法求得的平均周转时间和平均周转系数如下表所示：作业 提交时间 执行时间 开始时间 完成时间 周转时