操作系统处理机调度与死锁.ppt

第三章 处理机调度与死锁 3.1 处理机调度的基本概念 在多道程序环境下，内存中有多个进程，其数目往往多余处理机数目，这要求系统需要按照某种算法，将处理机分配给就绪队列中的一个进程，分配处理机的任务是由处理机调度程序完成的。 处理机调度是操作系统设计的中心问题之一。 3.1.1 高级、中级和低级调度 1. 高级调度(High Scheduling) 2. 低级调度(Low Level Scheduling) 3. 中级调度(Intermediate-Level Scheduling) 1. 仅有进程调度的调度队列模型 2. 具有高级和低级调度的调度队列模型 3. 同时具有三级调度的调度队列模型 3.3 调度算法 3.3.1 先来先服务（FCFS）和短作业优先调度算法（SJF） 3.3.2 高优先权优先调度算法（HRF） 3.3.3 时间片轮转调度算法 3.3.2 高响应比优先调度算法 3.3.2 高响应比优先调度算法 3.3.2最高优先权优先调度算法（优先数的确定） 2、动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可 以随进程的推进或随其等待时间的增加而改变的，以便 获得更好的调度性能。 例如，可以规定，在就绪队列中的进程，随其等待时间 的增长，其优先权以速率a提高。 那么对于优先权初值低的进程，在等待了足够的时间后， 其优先权便可能升为最高，从而可以获得处理机。 高响应比优先调度算法 高响应比优先调度算法 (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权(响应比)愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权(响应比)决定于其等待时间，等待时间愈长，其优先权(响应比)愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级(响应比)可以随等待时间的增加而提高，当其等待时间足够长时，其优先级(响应比)便可升到很高， 从而也可获得处理机。 高响应比优先调度算法 每次调度时，计算每个后备作业的响应比Rpi，然后挑选响应比最高者，使其投入运行。 练习 高响应比优先调度算法 3.3.3 基于时间片的轮转调度算法 1) 时间片轮转法（Round Robin） 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行进程的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片的处理机执行时间。 3.3 实时调度 3.3.1 实现实时调度的基本条件 3.3.2 实时调度算法的分类 3.3.3 常用的几种实时调度算法 3.3.1 实现实时调度的基本条件 在实时操作系统中存在若干个实时进程，这种进程带有某种程度的紧迫性，因而对实时系统中的调度提出了某些特殊要求，前面介绍的调度算法并不能很好地满足系统对调度的要求，为此引入一种新的调度，即实时调度。 3.3.1 实现实时调度 3.3.3 常用的几种实时调度算法 1. 最早截止时间优先即EDF(Earliest Deadline First)算法 3.3.3 常用的几种实时调度算法 1. 非抢占式最早截止时间优先算法 3.3.3 常用的几种实时调度算法 2. 抢占式最早截止时间优先算法 周期任务是指计算机系统按一定周期到达并请求运行，下例中A,B在0秒同时到达。 3.3.3 常用的几种实时调度算法(续) 最低松弛度优先即LLF(Least Laxity First)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。任务的紧急程度愈高，为该任务所赋予的优先级就愈高， 以使之优先执行。 例如，一个任务在200ms时必须完成，而它本身所需的运行时间就有100ms，因此，调度程序必须在100 ms之前调度执行，该任务的紧急程度(松弛程度)为100 ms。 又如，另一任务在400 ms时必须完成，它本身需要运行 150 ms，则其松弛程度为 250 ms。在实现该算法时要求系统中有一个按松弛度排序的实时任务就绪队列，松弛度最低的任务排在队列最前面，调度程序总是选择就绪队列中的队首任务执行。 该算法主要用于可抢占调度方式中。 练习 对于下面的5个非周期