操作系统作业调度.ppt

《操作系统作业调度.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章处理机调度与死锁3.1处理机调度概述3.2调度算法3.3实时调度3.4死锁的概念3.5死锁的预防和避免3.6死锁的检测和解除3.1处理机调度概述处理机调度（CPU调度）要解决的问题：WHAT：按什么原则分配CPU—调度算法WHEN：何时分配CPU—调度的时机HOW：如何分配CPU—CPU调度过程（进程的上下文切换）3.1.1处理机调度的三个层次作业调度（高级调度）交换调度（中级调度）进程调度（低级调度）！进程调度频率最高，约10~100ms进行一次，因而进程调度算法不能太复杂，以免占用太多CPU时间（1）作

2、业程序+数据+作业说明书（2）作业步作业调度（4）作业控制块（JCB：JobControlBlock）作业控制块是作业存在的标志保存有系统进行作业管理所需要的全部信息位于磁盘区域中（5）作业调度1)接纳多少个作业2)接纳哪些作业FCFS、SJF、HPF、HRN一、进程调度的功能:在PCB中保存处理机的现场信息根据算法选取进程分派程序将处理机分配给进程附：调度方式非抢占方式：运行进程完成或阻塞时，才再分配处理机。抢占方式：将正运行进程强行撤下，处理机分配给其它进程。进程调度二、进程调度的时机：当前进程结束当前进

3、程调用阻塞原语将自己阻塞当前进程调用P()申请资源不能满足或调用V()唤醒了等待进程当前进程提出了I/O请求时间片到在抢占调度中，有一个优先权更高的进程进入就绪队列三、进程调度算法：就绪队列的两种组织：进程进入就绪队列时，插入到合适的优先位置。调度时取队首进程。进程进入就绪队列末尾，调度时扫描整个队列，选择最合适的进程。FCFS、SPF、HPF、RR3.1.2调度队列模型1.仅有进程调度的调度队列模型图3-1仅具有进程调度的调度队列模型2.具有高级和低级调度的调度队列模型图3-2具有高、低两级调度的调度队列模型3

4、.同时具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型3.1.3选择调度方式和调度算法的若干准则1.面向用户的准则(1)周转时间短。平均周转时间：作业的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS，称为带权周转时间，而平均带权周转时间则可表示为:(2)响应时间快。(3)截止时间的保证。(4)优先权准则。2.面向系统的准则系统吞吐量高。(2)处理机利用率好。(3)各类资源的平衡利用。3.2调度算法3.2.1先来先服务和短作业(进程)优先调度算法先来先服务调度算法FCFS：FirstCom

5、eFirstServe2.短作业(进程)优先调度算法SJF：ShortestJobFirst例假设在单道批处理环境下有四个作业，已知它们进入系统的时间、估计运行时间。应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间先来先服务调度算法计算结果最短作业优先作业算法计算结果3.2.2高优先权优先调度算法1.优先权调度算法的类型非抢占式优先权算法抢占式优先权调度算法把处理机分给优先权最高的就绪进程。（HPF—HighestPriorityFirst静态优先权：创

6、建进程时根据进程类型、资源需求、用户要求等因素确定优先级，并保持不变。动态优先权：创建进程时赋予进程一个优先权初值，但随着进程的等待时间及执行时间的延长，其优先级会增加或降低。例：线性优先级调度策略：享受服务进程队列新建进程队列CPU优先级P=P+a*t优先级P=P-b*t(a>b>0)2.优先权的类型3.高响应比优先调度算法由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。（HRRN：HighestResponseRatioNext）(1)如果作业的等待时间相同，则要求服务

7、的时间愈短，其优先权愈高，因而该算法有利于短作业。(2)当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。(3)对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机。最高响应比优先作业算法计算结果练习应用先来先服务、最短作业优先和最高响应比优先作业调度算法，分别计算出作业的平均周转时间和带权的平均周转时间作业提交时间运行时间开始时间完成时间周转时间带权周转时间18:0012028:304039:

8、00849:3012平均周转时间t=平均带权周转时间w=先来先服务作业提交时间运行时间开始时间完成时间周转时间带权周转时间18:001208:0010:00120128:304010:0010:401303.2539:00810:4010:4810813.549:301210:4811:00907.5平均周转时间t=112平均带权周转时间w=6.31短作业优先作业提交时间