第三章处理机调度

第三章 处理机调度与死锁 3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 第三章 处理机调度与死锁 3.1 处理机调度的层次 3.1.1 高级调度（作业调度、长程调度）按照某种算法，决定把外存上处于后备队列中的那些作业调入内存。第三章 处理机调度与死锁 作业步 (Job Step)： 通常，在作业运行期间，把其中的每一个加工步骤称为一个作业步1作业和作业步作业 (Job)： 作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。2作业控制块 JCB(Job Control Block)在多道批处理系统中为每个作业设置了一个作业控制块（ JCB),它是作业在系统中存在的标志 .当作业进入系统时， OS为其建立 JCB.3作业调度作业调度的主要功能是根据 JCB，审查系统能否 满足用户作业的资源需求，以及按照一定的 算法 ，从外存的后备队列中选取 某些作业调入 内存 ，并为它们 创建进程 、 分配 必要的资源。然后再将新创建的进程插入 就绪 队列，准备执行。因此，有时也把作业调度称为接纳调度 (Admission Scheduling) 。 周转时间3.1.2. 低级调度 (Low Level Scheduling)-进程调度决定就绪队列中的哪个进程应获得处理机，由分派程序执行把处理机分配给该进程的具体操作 1) 非抢占方式 (Non-preemptive Mode) :自愿放弃2) 抢占方式 (Preemptive Mode) ：时间片；优先级第三章 处理机调度与死锁 引入的主要目的：为了提高内存利用率和系统吞吐量使暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上暂时等待（就绪驻外存状态或挂起状态），当这些进程重又具备运行条件、且内存又有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上3.1.3. 中级调度 (Intermediate-Level Scheduling) 中程调度第三章 处理机调度与死锁 3. 2 调度队列模型 和调度准则3.2.1. 调度队列模型 图 3 - 1 仅具有进程调度的调度队列模型 第三章 处理机调度与死锁 就 绪 队 列阻 塞 队 列进程调度 CPU 进程完成等待事件交互用户事件出现时间片完1.仅有进程调度的调度队列模型CPU进程 i进程调度进程 j进程 k进程 p就绪队列时间片完进程 f进程 b进程 n进程 l 阻塞队列等待事件事件出现进程完成进程 X第三章 处理机调度与死锁 2. 具有高级和低级调度的调度队列模型 图 3-2 具有高、低两级调度的调度队列模型 第三章 处理机调度与死锁 就 绪 队 列进程调度 CPU 进程完成等待事件 1作业调度事件 1出现时间片完等待事件 2事件 2出现 等待事件 n事件 n出现后 备 队 列 作业3作业2作业1作业调度 进程2 就绪队列CPU阻 塞 队 列 1阻 塞 队 列 n阻 塞 队 列 2进程调度等待事件1进程1等待事件2等待事件n 事件 1出现事件 2出现事件 n出现第三章 处理机调度与死锁 3. 同时具有三级调度的调度队列模型 图 3-3 具有三级调度时的调度队列模型 第三章 处理机调度与死锁 就绪队列进程调度 CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现3.2.2 选择调度方式和调度算法的若干准则 1. 面向用户的准则 (1) 周转时间短。 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔 作业的周转时间 T与系统为它提供服务的时间 TS之比，即W=T/TS，称为带权周转时间第三章 处理机调度与死锁 作业在外存后备队列上的等待时间进程在就绪队列上等待进程调度的时间进程在 CPU上执行的时间进程等待 I/O操作完成的时间(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。 第三章 处理机调度与死锁 平均周转时间 平均带权周转时间2. 面向系统的准则 (1) 系统吞吐量高。 ?(2) 处理机利用率好。 (3) 各类资源的平衡利用。 第三章 处理机调度与死锁 第三章 处理机调度与死锁 3.3 调 度 算 法 先来先服务调度算法 FCFS 短作业 (进程 )优先调度算法 SJ(P)F 高优先权优先调度算法 基于时间片的轮转调度算法3.3.1 先来先服务和短作业 (进程 )优先调度算法 第三章 处理机调度与死锁 1 先来先服务（ FCFS）调度算法作业调度：从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存运行；进程调度：就绪队列按进入的先后次序排列，调度时，选队首进程投入运行。 进 程名 A B C D就 绪时间 0 5 10 15要求服 务时间 10 25 5 10先来先服务FCFS到达 时间 0完成 时间 10周 转时间 10带权 周 转时间1535301.210403061550353.5105/4=26.2511.7/4=2.925例： FCFS算法比较有利于长作业 (进程 )，而不利于短作业 (进程 )。下表列出了 A、 B、 C、 D四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。2、短作业（进程）优先调度算法（ SJ(P)F） 短作业优先 SJF调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。 短进程 SPF优先调度算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。进 程名 A B C D 平均就 绪时间 0 5 10 15要求服 务时间10 25 5 10先来先服 务（ FCFS）周 转时间 10 30 30 35 26.25带权 周 转时间1 1.2 6 3.5 2.925短 进 程 优 先（ SPF）周 转时间 10 45 5 10 17.5带权 周 转时间1 1.8 1 1 1.2FCFS和 SPF调度算法的性能比较3.3.2 高优先权优先调度算法1. 优先权调度算法的类型 非抢占式优先权算法 抢占式优先权调度算法2. 优先权的类型 1) 静态优先权 第三章 处理机调度与死锁 确定进程优先权的依据有如下三个方面： (1) 进程类型。 (2) 进程对资源的需求。 (3) 用户要求。 进 程名 A B C D就 绪时间 0 5 10 15要求服 务时间 10 25 5 10优 先 权 0 1 3 2开始 时间完成 时间周 转时间带权 周 转时间高优先权优先(静态)非抢占式优先权调度0 25 10 1510 50 15 2510 45 5 101 1.8 1 1A0 t10 20 5030 40BC5 15 3525 45D进 程名 A B C D就 绪时间 0 5 10 15要求服 务时间 10 25 5 10优 先 权 0 1 3 2高优先权优先(静态)抢占式优先权调度2) 动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定，在就绪队列中的进程，随其等待时间的增长，其优先权以速率 a提高。当采用抢占式优先权调度算法时，如果再规定当前进程的优先权以速率 b下降，则可防止一个长作业长期地垄断处理机。 第三章 处理机调度与死锁 3) 高响应比优先调度算法 优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比 RP。据此，又可表示为： 第三章 处理机调度与死锁 要求服务时间要求服务时间等待时间R +=要求服务时间等待时间要求服务时间要求服务时间等待时间R =+=3.3.3 基于时间片的轮转调度算法 1. 时间片轮转法 RR在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把 CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百 ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。第三章 处理机调度与死锁 A0 t10 20 5030 40BC5 15 3525 45D进 程名 A B C D就 绪时间 0 5 10 15要求服 务时间 10 25 5 10