第三章 处理机调度与死锁2017.ppt

第三章 处理机调度与死锁 处理机调度：处理机调度程序动态的把处理机分配给就绪队列中的一个进程，使之执行。 3.1 处理机调度的基本概念 3.1.1 高级、中级和低级调度 一个批处理作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历三级调度。 1.高级调度（High Scheduling） 按照一定的算法在外存上处于后备作业队列中选择满足条件的作业，分配一定资源，创建PCB，进入主存就绪队列中，准备执行。 2.低级调度（Low Level Scheduling） 按照一定的算法从就绪队列中选择满足条件的进程，分配CPU运行。 3.中级调度(Intermediate-Level Scheduling) 将在内存中长期得不到执行的进程，按照一定的算法调至外存上去等待；满足执行条件后再重新调入主存,进入就绪队列。 3.1.2 调度队列模型 每一种调度,都涉及到进程队列,由此形成了三种类型的调度队列模型。 1.仅有进程调度的调度队列模型 2.具有高级和低级调度的调度队列模型 3.同时具有三级调度的调度队列模型 3.1.3 选择调度方式和调度算法的若干准则 如何选择调度方式和调度算法？ 1.面向用户准则 (1)周转时间短 平均周转时间:T=[T1+T2+T3+…+Tn]*1/n 带权周转时间:Wi=T周转时间/T系统提供的服务时间（cpu） 平均带权周转时间:W平均=(W1+W2+W3+W…+Wn)/n (2)响应时间快 (3)截止时间的保证 截止时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。 对于严格的实时系统，其调度方式和调度算法必须能保证这一点。 (4)优先权准则 2.面向系统的准则 (1)系统吞吐量高 (2)处理机利用率好 (3)各类资源的平衡利用 3.2 调度算法 调度算法：根据系统的资源分配策略所规定的资源分配算法（CPU、内存）。 批处理系统中，短作业优先的调度算法。 分时系统中，轮转法进行调度。 … 3.2.1 先来先服务和短作业（进程）优先调度算法 1.先来先服务(FCFS) FCFS算法有利于长作业(进程),而不利于短作业(进程) 。 2.短作业(进程)优先调度算法 短作业(进程)优先调度算法SJ(P)F,是指对短作业或短进程优先调度的算法。 SJ(P)F调度算法的缺点： （1）该算法对长作业不利。 （2）该算法完全未考虑作业的紧迫程度。 （3）估算的执行时间并不一定准确，所以不一定能真正做到短作业优先调度。 3.2.2 高优先权调度算法 1.优先权调度算法的类型 （1）非抢占式优先权算法 常用于批处理系统中， 也可用于某些对实时 性要求不严的实时系统中。 （2）抢占式优先权调度算法 能更好的满足紧迫作业的要求， 故而常用于要求比较严格的实 时系统中，以及对性能要求较 高的批处理和分时系统中。 2.优先权的类型 （1）静态优先权 创建进程时确定的，且在进程的整个运行周期间保持不变。一般的，优先权是利用某一范围内的一个整数来表示的，如，0~255中的某一个整数。确定优先权的依据有如下三个方面： 进程类型 进程对资源的要求 用户要求 （2）动态优先权 在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的。 3.高响应比优先调度算法 在批处理系统中，短作业优先算法的不足之处是长作业的运行得不到保证，如果为每一个作业引入前面的动态优先权，可使作业的优先级随着等待时间的增加而以速率a提高。 优先权=（等待时间+要求服务时间）/ 要求服务时间 = 响应时间 / 要求服务时间 3.2.3 基于时间片的轮转调度算法 在分时系统中，为保证能及时响应用户的请求，必须采用时间片的轮转式进程调度算法。 1.时间片轮转法 按照先来先服务的原则，排成一个队列。 时间片：S1S2S3 3.多级反馈队列调度算法的性能 （1）终端型作业用户，通常在第一队列所规定的时间片内完成。 （2）短批处理作业用户，通常前几个队列各执行一个时间片即可完成。 （3）长批处理作业用户，依次在1~n个队列中运行，然后再按轮转方式运行，用户不必担心作业长期得不到运行。 复习 1、高级、中级、低级调度 2、调度算法： 先来先服务FCFS 短作业（进程）优先 高优先权优先调度算法：高响应比优先调度算法 基于时间片的轮转调度算法：时间片轮转法 多级反馈队列调度算法 3.3