操作系统作业调度.ppt

1、第3章处理器调度和死锁、3.1处理器调度概述3.2调度算法3.3实时调度3.4死锁概念3.5预防和避免死锁3.6死锁处理器调度(c 要解决的问题： what :如何分配CPU调度算法when:CPU调度时间how :如何分配CPU CPU调度进程(进程上下文切换)， 3.1.1处理器调度的三阶段进程调度频率最高，大约在10100 ms内进行一次，从而使得进程调度算法不太复杂，CPU时间不太多(1)工作程序数据工作说明书作业控制块(JCB:Job Control Block )作业控制块中，系统进行作业管理所需的全部信息被存储在盘区域中，(5)作业调度1 )接受多少作业2 )哪个作业进程调度功能

2、：将处理器的现场信息保存在PCB中，并基于算法选择进程调度程序以将处理器分配给进程：基于调度的非优先级方法：完成或阻止进程执行时抢占、进程调度、2、进程调度计时：当前进程终止当前进程调用基元阻断自己当前进程调用p ()资源未满足或等待v ()进程当前进程I/O请求时间进程进入就绪队列的末尾，在调度时扫描整个队列并选择最佳进程。 FCFS、SPF、HPF、RR、3.1.2调度队列模型、1 .仅进程调度调度队列模型、图3-1仅进程调度调度队列模型、2 .高级和低级调度平均换向时间：这是工作的换向时间t与系统提供服务的时间TS的比，即W=T/TS可以称为频带权重换向时间，平均频带权重换向时间可以表示

3、为：其中，(2)响应时间快； (三)截止时间的保证。 (4)优先顺序的指导方针。 2 .面向系统的指导方针，系统吞吐量高。 (2)处理器利用率好。 (3)平衡利用各种资源。 3.2调度算法，3.2.1先服务和短作业(进程)优先调度算法，3.2.1先服务调度算法FCFS :第一个服务，2 .短作业(进程) 优先调度算法sjf:shortt先行服务，应用最短作业优先级和最高响应速率优先作业调度算法，分别校正作业的平均换向时间和加权平均换向时间，并校正先行服务调度算法最短作业优先级作业算法修改结果、3.2.2高优先级调度算法类型、非优先级算法优先级调度算法、(HPF高优先级第一，静态优先级：创建进程

4、时的进程类型、资源动态优先级-创建进程时为进程提供初始优先级值，但优先级随着进程等待时间和执行时间的增加而增加或减少。 例如，由于等待时间和服务时间之和是系统针对作业的响应时间，因此线性优先级调度策略：2 .优先级类型，3 .快速响应速率优先级调度算法等于响应速率RP。(HRRN:Highest Response Ratio Next )、(1)作业的等待时间越相同，请求服务的时间越短则优先级越高，因此该算法对短作业有利。 (2)在请求服务的时间相同的情况下，作业的优先度决定为该等待时间，等待时间越长优先度越高，因此实现先到顺序的服务。 (3)对于长的作业，能够随着等待时间的增加而提高作业的优

5、先级，在等待时间充分长的情况下，能够提高其优先级，从而能够获得处理器。 应用最高响应比优先作业算法的修正结果、练习、先到服务、最短作业优先和最高响应比优先作业调度算法，分别修正作业的平均旋转时间和加权的平均旋转时间，将先到服务、短作业优先、最高响应比优先、各进程按顺序排列在准备队列中占用处理器，确定运行某个时间的时间片：时间片q=响应时间T /进程数n开销：时间片100ms，进程切换需要5ms时，开销所占比例：5/(100 5 )=4.8%可变时间片：在一个循环的调度开始时，根据现有的准备进程数重新计算q；1、时间片循环法(RR:Round Robin )、3.2.3基于时间片的循环调度2、多

6、级反馈队列算法：设置多个就绪队列，越是优先级越高的队列，如果要运行的时间片越小的进程没有在一个时间片内运行，则下一级别的队列下降到本地队列，进程准备就绪调度子队列中的进程新进程可以切断低优先级的当前进程一个队列中的进程用FCFS方法进行调度，最终队列用时间分片轮转方法进行调度。 3.4实时调度，1 )实时系统，实时指示“实时”，系统响应外部事件请求，在规定时间内完成对该事件的处理用于工业过程、军事、金融等实时控制、实时信息处理领域，按任务执行时是否呈周期性进行分类：周期性实时任务：每隔一定时间发生一次非周期性实时任务：发生在不可预测的时间。 截止时间(deadline ) :开始截止时间(最大

7、延迟开始时间)完成截止时间(最大延迟完成时间)根据截止时间的要求进行分类。 硬实时任务：有必要满足的时间限制。 软实时任务：有时可允许超过时间限制。实时任务类型：2 )对于提供实现实时调度的基本条件、所需信息(准备时间、截止时间、处理时间、资源请求、资源优先级)的系统处理能力足够强的：单处理器：有m个周期事件，事件其中的每个事件或Ci秒的可调度实时系统是采用C1/P1 C2/P2 Cm/Pm 1优先调度机制的快速调度机制，3 )实时调度算法的分类，1 ) 非优先调度算法3360非优先循环调度算法(算法不严格，s )非优先调度算法数百ms) 2)优先级调度算法基于：时钟中断的优先级调度算法抢占调

8、度算法(紧迫的任务，几毫秒到百微秒)，图3-8实时进程调度，4 )中常用的一些实时调度算法1 )用于非抢占调度非周期性实时任务图3-9 EDF算法用于非优先权调度方式，2 )用于优先权调度周期实时任务：最早完成截止时间优先，II .最低松弛度优先，LLF(Least Laxity First )算法主要用于可抢占的调度方式。 松弛度：即，每个进程的剩馀时间(剩馀度)松弛度=必须完成的时间-其自身的执行时间-当前时间，如果使用图3-12llf算法进行调度，则图3-11 A和b的任务每次必须完成的时间是一个实时对于练习1、接下来的5个非周期性实时任务，如果以最早的开始截止时间优先调度算法如何进行CPU调度(非抢占式/抢占式)、到达时间、开始截止时间、练习2、周期性任务有3个，则各任务、时间、每个过程的到达时间、总是完成时间、假设一个系统有五个过程，I/O其它开销时间被忽略，如下表所示。 分别按照先行服务FCFS、非优先及优先短的处理优先SPF和最高响应比优先HRRN、时间片RR法进行CPU调度，并将各处理的运行