四、处理机调度

1、处理机调度层次

①高级调度(High Level Scheduling)：又称长程调度、作业调度，决定能否加入到执行的进程池中

②低级调度(Low Level Scheduling)：又称短程调度、进程调度，决定哪个可用进程占用处理器

③中级调度(Intermediate Scheduling)：又称为平衡负载调度，决定主存中的可用进程集合

2、调度准则

(1) 资源利用率。

(2) 公平性，诸进程获得合理的CPU 时间，不发生进程饥饿现象

(3) 平衡性，系统中的CPU和各种外部设备都能经常处于忙碌状态

(4) 响应时间短 (5)周转时间小 (6)吞吐量多

3、短程调度算法

■  先来先服务(first-come first-served，FCFS)调度算法

非抢夺式，平均等待时间比较长，不适合分时和实时系统。

■  短作业优先(short job first，SJF)调度算法

缺点：

(1)须预知作业运行时间(2)对长作业非常不利(3)无法实现人机交互

(4)完全未考虑作业紧迫程度,不能保证紧迫性作业能得到及时处理。

■ 轮转调度算法(RR)

高响应比优先调度算法(Highest Response Ratio Next，HRRN)

4、优先级调度算法，优先级的类型

（1）静态优先级：静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0～255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：进程类型、进程对资源的需求、用户要求

（2）动态优先级：动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。动态优先级根据进程占用CPU的长短、进程等待CPU的长短来确定。

■  优先级调度算法缺点与解决办法

缺点：无穷阻塞或饥饿现象，某个低优先级进程无穷等待CPU。

解决方法：老化技术，逐渐增加等待很长时间的进程的优先级。

5、多级反馈队列轮换调度算法

■  调度机制

多级反馈队列调度算法的调度机制可描述如下：

(1) 设置多个就绪队列。

(2) 每个队列都采用FCFS算法。

(3) 按队列优先级调度。

■  算法性能

如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要。

6、实时调度

■ 实现实时调度的基本条件：提供必要的信息、系统处理能力强、采用抢占式调度机制、具有快速切换机制

■  实时调度算法的分类：① 根据实时任务性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法；② 按调度方式，则可分为非抢占调度算法和抢占调度算法。

■  非抢占式调度算法有非抢占式轮转调度算法和优先调度算法

■  抢占式调度算法

可根据抢占发生时间的不同而进一步分成以下两种调度算法：

(1) 基于时钟中断的抢占式优先级调度算法。

(2) 立即抢占(Immediate Preemption)的优先级调度算法。

6.1最早截止时间优先EDF(Earliest Deadline First)算法

(1)非抢占式调度方式用于非周期实时任务

(2) 抢占式调度方式用于周期实时任务

6.2最低松弛度优先LLF(Least Laxity First)算法

该算法在确定任务的优先级时，根据的是任务的紧急(或松弛)程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。

图 1  A和B任务每次必须完成的时间

图 2  利用ELLF算法进行调度的情况