OS 处理机调度

目录

处理机调度的层次

高级调度

作业

作业控制块 JCB

作业调度的主要任务

低级调度

中级调度

进程调度

进程调度时机

进程调度任务

进程调度机制

排队器

分派器

上下文切换器

进程调度方式

非抢占调度方式

抢占调度方式

调度算法

处理机调度算法的目标

处理机调度算法的共同目标

资源利用

公平性

平衡性

策略强制执行

批处理系统中处理机调度算法的目标

平均周转时间短

系统吞吐量高

处理机利用率高

分时系统中处理机调度算法的目标

保证响应时间快

保证均衡性

实时系统中处理机调度算法的目标

保证满足截止时间的要求

保证可预测性

先来先服务调度算法 FCFS

短作业优先调度算法 SJF

简介

优点

缺点

优先级调度算法

优先级调度算法的类型

非抢占式优先级调度算法

抢占式优先级调度算法

优先级的类型

静态优先级

动态优先级

高响应比优先调度算法 HRRN

轮转调度算法 RR

基本原理

进程切换时机

时间片大小的确定

多级队列调度算法

多级反馈队列调度算法

调度机制

性能

基于公平原则的调度算法

保证调度算法

公平分享调度算法

实时调度

实现实时调度的基本条件

提供必要的信息

系统处理能力强

采用抢占式调度机制

采用快速切换机制

实时调度算法分类

非抢占式调度算法

非抢占式轮转调度算法

非抢占式优先级调度算法

抢占式调度算法

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

立即抢占的优先级调度算法

最早截止时间优先算法 EDF

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

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

最低松弛度优先算法 LLF

优先级倒置

优先级倒置的形成

优先级倒置的解决方法

一种简单的解决方法

一种比较实用的解决方法

---

处理机调度的层次

高级调度

别称：长程调度、作业调度

调度对象：作用

PS：每个作用只调入一次，调出一次

主要功能：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为其创建进程【作业调入时会建立 PCB，调出时撤销 PCB】、分配必要的资源，并将其放入就绪队列

应用：主要用于多道批处理系统中，在分时系统和实时系统中，不设置高级调度

在多道批处理系统中，作业是用户提交给系统的一项相对独立的工作。操作员把用户提交的作业通过相应的输入设备输入磁盘存储器，并保存在一个后备作业队列中，再由作业调度程序将其从外存调入内存

作业

定义：一个具体的任务

作业是一个比程序更为广泛的概念，不仅包含了的程序和数据，而且配有一份作业说明书，系统根据该说明书对程序的运行进行控制。在多道批处理中，会将作业作为基本单位从外存调入内存

作业控制块 JCB

设置目的：管理和调度作业

地位：是作业在系统中存在的标准，保存了系统对作业进行管理和调度所需的全部信息

包含的内容：作业标志、用户名称、用户账号、作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）、作业状态、调度信息（优先级、作业运行时间）、资源需求情况（预计运行时间、要求内存大小）、资源使用情况……

执行过程：每当一个作业进入系统时，“作业注册”程序便会为该作业建立一个 JCB，然后根据作业类型将其放到相应的作业后备队列中等待调度。调度程序依据一定的调度算法调度它们，被调度到的作业将被装入内存。在作业运行期内，系统会按照 JCB 中的信息和作业说明书对作业进行控制。当一个作业执行结束并进入完成状态时，系统便会收回已分配给它的资源，并撤销其 JCB

作业调度的主要任务

作业调度的主要任务是，根据 JCB 中的信息，检查系统中的资源能否满足作业的需求，以及按照一定的调度算法从外存的作业后备队列中选取某些作业调入内存，并为其创建进程和分配必要的资源。然后，将新创建的进程排在就绪队列上等待调度。故，把作业调度称为接纳调度。在每次执行作业调度时，都须做出的决定：

1. 接纳多少个作业：在每次进行作业调度时，应从后备队列中选取多少作业调入内存，取决于多道程序度，表示允许多少个作业同时在内存中运行。对系统而言，希望装入内存较多的作业，有利于提高资源利用率和系统吞吐量。但若内存中同时运行的作业太多，进程在运行时因内存不足所发生的中断就会急剧增加，会使进程的平均周转时间显著延长，进而影响系统的服务质量。故，多道程序度的确定方法：综合考虑计算机系统规模、计算机运行速度、作业大小以及所能获得的系统性能好坏等情况后，做出适当的抉择
2. 接纳哪些作业：应选择后备队列中的哪些作业调入内存，取决于所采用的调度算法

低级调度

别称：短程调度（运行频率最高，在分时chi中通常仅10ms~100ms便进行一次低级调度）、进程调度

调度对象：进程（或 LWP）

主要功能：根据某种算法，决定就绪队列中的哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程

地位：最基本的一种调度

应用：在多道批处理、分时和实时这 3 种系统中，都必须配置这种调度

中级调度

别称：内存调度

引入目的：提高内存利用率和系统吞吐量

描述：把暂时不能运行的进程调至外存等待，此时进程的状态称为就绪驻外存状态（或挂起状态）。当其已具备运行条件且内存稍有空闲时，由中级调度决定把外存上已具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待

PS：一个进程可能会被多次调出、调入内存，故中级调度发生的频率比高级调度更高

实质：存储器管理中的对换功能

进程调度

地位：进程调度是 OS 中必不可少的一种调度，也是对系统性能影响最大的一种处理机调度

“狭义的进程调度”与“进程切换”的区别：

• 狭义的进程调度：指的是从就绪队列中选中一个要运行的进程（此进程可以是刚被暂停执行的进程，也可以是另一个进程，后者需要进程切换）
• 进程切换：指一个进程让出处理机，由另一个进程占用处理机的过程

广义的进程调度包含选择一个进程和进程切换两个步骤

进程切换的过程主要完成了：

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复

PS：进程切换是有代价的，因此若过于频繁的进行进程调度、切换，会使整个系统的效率降低，使系统大部分时间都花在进程切换上，而真正用于执行进程的时间减少

调度程序决定：

• 让谁运行？——调度算法
• 运行多长时间？——时间片大小

闲逛进程：调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程

闲逛进程的特性：

• 优先级最低
• 可以是零地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
• 能耗低

进程调度时机

PS：有的系统中，只允许进程主动放弃处理机；有的系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机（被动放弃）

真题：

进程在操作系统内核程序程序临界区中不能进行调度与切换 √

进程处于临界区时不能进程处理机调度 ×

解析：

临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源

临界区：访问临界资源的代码

内核程序临界区：一般是用来访问某种内核数据结构的，比如进程的就绪队列

内核程序临界区访问的临界资源若不尽快释放，极有可能影响操作系统内核的其他管理工作，因此在访问内核程序临界区期内不能进行调度与切换

普通临界区访问的临界资源不会直接影响操作系统内核的管理工作，因此在访问普通临界区时可以进行调度与切换

进程调度任务

1. 保存 CPU 现场信息：在进行进程调度时，首先需要保存当前进程的 CPU 现场信息
2. 按某种算法选取进程：调度程序须按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把 CPU 分配给它
3. 把 CPU 分配给进程：有分派程序把 CPU 分配给该进程，此时需要将选中进程的 PCB 内有关 CPU 的现场信息装入 CPU 相应的各个寄存器内，并把 CPU 的控制权交给该进程，以使其能够从上次的断点处恢复运行

进程调度机制

为了实现进程调度，在进程调度机制中，应具有排队器、分派器、上下文切换器 3 个基本部分

排队器

为了提高进程调度的效率，应事先将系统中的所有就绪进程，按照一定的策略排成一个或多个队列，以便调度程序能最快地找到它们。以后每当有一个进程转变为就绪状态时，排队器便将其插入相应的就绪队列

分派器

将进程调度程序所选定的进程从就绪队列中取出，然后进行从分派器到新选进程间的上下文切换，将 CPU 分配给新选进程

上下文切换器

在对处理机进行切换时，会发生两对上下文的切换操作：

1. 第一对上下文切换时，OS 将保存当前进程的上下文，即把当前进程的 CPU 寄存器内容保存到该进程的 PCB 内的相应单元，而装入分派程序的上下文，可以方便分派程序运行
2. 第二对上下文切换是移出分派程序的上下文，把新选进程的 CPU 现场信息装入 CPU 的各个相应寄存器中，以便新选进程运行

在进行上下文切换时，需执行大量的 load 和 store 等操作指令，已保存寄存器的内容。通过硬件实现减少上下文切换时间，采用两组（或多组）寄存器，其中一组寄存器供处理机在内核态时使用，另一组寄存器供应用程序使用，此时，上下文切换只须改变指针使其指向当前寄存器组即可

进程调度方式

非抢占调度方式

描述：采用非抢占调度方式时，一旦把处理机分配给某进程，就会一直让其运行下去，决不会因为时钟中断或其他原因去抢占该进程的处理机，直至该进程完成或发生某事件被阻塞时，才会把分配给该进程的处理机分配给其他进程

引起进程调度的因素：

1. 正在执行的进程运行完毕，或因发生某事件而使其无法继续运行
2. 正在执行的进程因提出 I/O 请求而暂停执行
3. 在进程通信或同步过程中执行了某种原语操作

优点：实现简单、系统开销小

适用范围：适用于大多数批处理系统，但不能用于分时系统和大多数实时系统

抢占调度方式

描述：抢占调度方式允许调度程序根据某种原则去暂停某个正在执行的进程，并将已分配给该进程的处理机重新分配给另一进程

广泛使用的原因：对于批处理机系统，抢占调度方式可以防止一个长进程长时间占用处理机，以确保处理机能为所有进程提供更为公平的服务

应用：分时系统中采用抢占调度方式实现人机交互；实时系统中，抢占调度方式能满足实时任务的需求

缺点：抢占调度方式比较复杂，所须付出的开销较大

“抢占”原则：

1. 优先级原则：允许优先级高的新到进程抢占当前进程的处理机
2. 短进程优先原则：允许新到的短进程抢占当前长进程的处理机
3. 时间片原则：各进程按时间片轮转运行时，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度

调度算法

处理机调度算法的目标

处理机调度算法的共同目标

资源利用

最重要的资源 —— CPU 的利用率 = CPU 有效工作时间 / （CPU 有效工作时间 + CPU 空闲等待时间）

公平性

含义：各进程都获得合理的 CPU 时间，以防止发生进程饥饿现象

相对公平：

• 相同类型的进程应获得相同的服务
• 不同类型的进程，由于其紧急程度或重要性不同，为其提供不同的服务

平衡性

系统中可能具有多种类型的作业，有的属于 CPU 繁忙型作业，有的属于 I/O 繁忙型作业。为使系统中的 CPU 和各种 I/O 设备都能经常属于忙碌状态，调度算法应尽可能保证系统资源使用的平衡性

策略强制执行

对于所制定的策略（包括安全策略），只要有需要，就必须予以准确的执行，即使造成某些工作延迟也要执行

批处理系统中处理机调度算法的目标

以下目标的实现之间存在着一定的矛盾

平均周转时间短

周转时间（作业周转时间）：指从作业被提交给系统开始到作业完成为止的这段时间间隔，包括作业在外存后备队列上等待作业调度的时间，进程在就绪队列上等待进程调度的时间，进程在 CPU 上执行所耗费的时间，以及进程等待 I/O 操作完成的时间，后三项在一个作业的整个处理过程中可能会发生多次

（作业）周转时间 = 作业完成时间 - 作业提交时间

每个用户：希望自己作业的周转时间最短

计算机系统的管理者：希望作业的平均周转时间最短，不仅可以有效提高系统资源的利用率，还可以使大多数用户感到满意

平均周转时间：

带权周转时间：作业的周转时间 Ti 与系统为其提供服务的时间 Tsi之比，Wi = Ti / Tsi

平均带权周转时间：

等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低

• 进程：等待时间指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间进程是被服务的，故不计入等待时间
• 作业：不仅考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

系统吞吐量高

系统吞吐量：指单位时间内系统所完成的作业数，与批处理作业的平均长度有关

系统吞吐量 = 总共完成了多少道作业 / 总共花了多少时间

若仅为了获得高的系统吞吐量，则应尽量多选择短作业运行

处理机利用率高

若仅为了使处理机的利用率高，则应尽量多选择计算量大的作业运行

分时系统中处理机调度算法的目标

保证响应时间快

响应时间快是选择分时系统中进程调度算法的重要准则

响应时间：指用户通过键盘提交一个请求开始，到屏幕上显示出处理结果为止的这段时间间隔，包括请求信息从键盘输入开始直至传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间

保证均衡性

均衡性：系统响应时间的快慢应与用户所请求服务的复杂性相适应

实时系统中处理机调度算法的目标

保证满足截止时间的要求

截止时间：某任务必须开始执行的最迟时间，或必须完成的最迟时间

对于实时系统而言，调度算法的一个主要目标是保证实时任务满足截止时间的要求

保证可预测性

在实时系统中，可预测性非常重要

先来先服务调度算法 FCFS

地位：最简单的调度算法

使用：既可用于作业调度，也可用于进程调度

描述：

• 作业调度：当在作业调度中采用该算法时，系统将按照作业到达的先后次序进行调度，或者说会考虑在系统中等待时间最长的作业，而不管该作业执行时间的长短。FCFS 调度算法会从后备作业队列中选择几个最先进入该队列的作用，将其调入内存，并为其分配资源和创建进程，最后将其放入就绪队列
• 进程调度：当在进程调度中采用 FCFS 调度算法时，每次调度都是从就绪的进程队列中选择一个最先进入该队列的进程，并为之分配处理机，使之投入运行。在该进程一直运行到完成或发生某事件而阻塞后，进程调度程序才会将处理机分配给其他进程

调度方式：非抢占式调度

周转时间 = 完成时间 - 到达时间

带权周转时间 = 周转时间 / 运行时间

等待时间 = 周转时间 - 运行时间

有 I/O 操作的进程：等待时间 = 周转时间 - 运行时间 - I/O 操作时间

优点：公平，算法实现简单

缺点：排在长作业（进程）后面的短作业需要等待很长的时间，带权周转时间很大，对短作业说用户体验不好，即 FCFS 算法对长作业有利，对短作业不利

饥饿现象（某进程/作业长期得不到服务）：不会出现饥饿现象

短作业优先调度算法 SJF

简介

SJF 调度算法是以作业的长短计算优先级的，作业越短，其优先级越高

作业的长短以作业所要求的运行时间衡量

使用：可分别用于作业调度和进程调度

描述：

• 作业调度：从外存的作业后备队列中选择估计运行时间最短的作业，并优先将其调入内存运行
• 进程调度：短进程优先算法 SPF，从就绪队列中选择估计运行时间最短的进程，并为之分配 CPU 运行

调度方式：非抢占式调度、抢占式调度

非抢占式短作业优先调度算法：

• 周转时间 = 完成时间 - 到达时间
• 带权周转是时间 = 周转时间 / 运行时间
• 等待时间 = 周转时间 - 运行时间

抢占式短作业优先调度算法（最短剩余时间优先算法 SRTN）：

• 描述：每当有进程加入就绪队列改变时就需要调度，若新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列，且当一个进程完成时也需要调度
• 周转时间 = 完成时间 - 到达时间
• 带权周转时间 = 周转时间 / 运行时间
• 等待时间 = 周转时间 - 运行时间

饥饿现象（某进程/作业长期得不到服务）：会出现饥饿现象

优点

“最短的”平均等待时间、平均周转时间 【不太严谨】

在所有进程同时可运行时，采用 SJF 调度算法的平均等待时间、平均周转时间最少

在所有进程都几乎同时到达时，采用 SJF 调度算法的平均等待时间、平均周转时间最少

抢占式的短作业/进程优先调度算法的平均等待时间、平均周转时间最短

缺点

1. 必须预先知道作业的运行时间
2. 对长作业非常不利，长作业的周转时间会明显增长
3. 当采用 FCFS 调度算法时，无法实现人机交互
4. SJF 调度算法完全没有考虑作业的紧迫程度，故不能保证紧迫性作业得到及时处理

优先级调度算法

优先级调度算法基于进程的紧迫程度，由外部赋予进程相应的优先级，根据该优先级进行调度

使用：可用于作业调度，也可用于进程调度

描述：

• 作业调度：从后备队列中选择优先级最高的作业装入内存
• 进程调度：从就绪队列中选择具有最高优先级的进程在 CPU 上运行

饥饿现象（某进程/作业长期得不到服务）：会出现饥饿现象

优先级调度算法的类型

非抢占式优先级调度算法

抢占式优先级调度算法

应用：常用于对实时性要求较高的系统

优先级的类型

静态优先级

定义：静态优先级在创建进程时确定，在进程的整个运行期间保存不变

表示：利用某一范围内的一个整数表示，称为优先数

确定进程优先级大小的依据：

1. 进程类型：通常系统进程（如接收进程、对换进程……）的优先级要高于一般用户进程的优先级
2. 进程对资源的需求：对资源要求少的进程应被赋予较高的优先级
3. 用户要求：根据进程的紧迫程度以及用户所付费用的多少，确定优先级
4. 前台进程优先级高于后台进程
5. OS 更偏好 I/O 型进程（I/O 繁忙型进程）

优点：简单易行，系统开销小

缺点：不够精确，可能出现优先级低的进程长期未被调用的情况

动态优先级

定义：指在创建进程之初，先赋予进程一个优先级，然后优先级会随进程的推进或等待时间的增加而改变，以便获得更好的调度性能

高响应比优先调度算法 HRRN

地位：优先级调度算法的一个特例

使用：通常用于作业调度

描述：既考虑作业的等待时间，又考虑作业的运行时间，因此既照顾了短作业，又不会致使长作业的等待时间过长，从而改善了处理机调度的性能

优先级的变化规律：优先级 = （等待时间 + 要求服务时间）/ 要求服务时间 = 响应时间 / 要求服务时间 = 响应比 Rp

• 若作业的等待时间相同，则要求服务时间越短，优先级越高，此时 HRRN 调度算法类似于 SJF 算法，有利于短作业
• 当作业的要求服务时间相同时，其优先级取决于等待时间，此时 HRRN 调度算法类似于 FCFS 调度算法
• 对于长作业的优先级，可随等待时间得到增加而提高，当作业的等待时间足够长时，可获得处理机

调度方式：非抢占式调度

优点：实现了较好的折中

缺点：每次调度之前都需要先计算响应比，增加系统开销

轮转调度算法 RR

描述：采取非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片，若就绪队列上有 n 个进程，则每个进程每次大约可获得 1/n 的处理机时间

地位：分时系统中最简单、最常用的进程调度算法

饥饿现象（某进程/作业长期得不到服务）：不会出现饥饿现象

基本原理

在 RR 调度算法中，系统将所有的就绪进程按 FCFS 策略排成一个就绪队列。系统可设置每隔一定时间便产生一次中断，去激活进程调度程序进行调度，把处理机分配给队首进程，并令其执行一个时间片。当其运行完后，再把处理机分配给就绪队列中新的队首进程，同时让其也执行一个时间片。保证就绪队列中的所有进程，在确定的时间段内，都能获得一个时间片的处理机时间

进程切换时机

1. 若一个时间片尚未用完而正在运行的进程便已经完成，则立即激活调度程序，将已经运行完成的进程从就绪队列中删除，再调度就绪队列中新的队首进程运行，并启动一个新的时间片
2. 当一个时间片用完时，计时器中断处理程序会被激活，此时若进程尚未运行完毕，调度程序就把它送往就绪队列的末尾

时间片大小的确定

一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间

时间片太大：退化为先来先服务调度算法

时间片太小：进程切换过于频繁，系统花费大量的时间处理进程切换，导致实际用于进程执行的时间比例减少

多级队列调度算法

描述：多级队列调度算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级

优点：在多处理机系统中，多级队列调度算法由于安排了多个就绪队列，因此可以很方便地为每个处理机设置一个单独的就绪队列。不仅对每个处理机的调度可以实施各自不同的调度策略，而且对于一个含有多个线程的进程而言，可以根据其要求将所有线程分配在一个就绪队列上，并全部在一个处理机上运行；再者，对于一组需要相互合作的进程或线程而言，可将其分配到一组处理机所对应的多个就绪队列上，使其能同时获得处理机并行执行

多级反馈队列调度算法

饥饿现象（某进程/作业长期得不到服务）：会出现饥饿现象

调度机制

1. 设置多个就绪队列：在系统中设置多个就绪队列，为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余队列的优先级依次降低。为不同队列中的进程所赋予的执行时间片的大小不同，优先级越高的队列的时间片越小
2. 每个队列都采用 FCFS 调度算法：当新进程进入内存后，首先将其放入第一个队列的末尾，按 FCFS 策略等待调度。当轮到该进程执行时，若其能在该时间片内完成，则可撤离系统，否则，调度程序将其转入第二个队列的末尾等待调度；若其在第二个队列中运行一个时间片后仍未完成，则将其放入第三个队列，依次类推。当进程最后被降到第 n 队列后，在第 n 队列中便采取 RR 方式运行
3. 按队列优先级调度：调度程序首先调度最高优先级队列中的各进程运行，仅当第一队列空闲时，才调度第二队列中的进程运行；换而言之，仅当第 1~（i-1）队列均空时，才会调度第 i 队列中的进程运行。若处理机在第 i 队列中为某进程服务时，又有新进程进入任一优先级较高的队列，则必须把正在运行的进程放回到第 i 队列的末尾，并把处理机分配给新到的高优先级进程

调度方式：抢占式调度

性能

在多级反馈队列调度算法中，若规定第一个队列的时间片略大于多数人机交互所需的处理时间，则能较好地满足各类用户的需要

• 终端型用户：由于终端型用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列规定的时间片内完成，便可使终端型用户感到满意
• 短批处理作业用户：对于这类作业，若可在第一队列中执行完成，则能获得与终端型作业一样的响应时间；对于稍长的短作业，也只须在第二和第三队列各执行一个时间片即可完成，其周转时间仍然较短
• 长批处理作业用户：对于这类作业，将其依次在第 1，2，...，n 个队列中运行，然后再按 RR 方式运行，用户不必担心其作业长期得不到处理

基于公平原则的调度算法

保证调度算法

向用户做出明确的性能保证，可以做到调度的公平性

一种比较容易实现的性能保证措施：公平分配处理机，若在系统中有 n 个相同类型的进程同时运行，则为了公平起见，须保证每个进程都能获得相同的处理机时间

在实施公平调度算法时，系统必须具备的功能：

1. 跟踪计算每个进程自创建以来已经执行的处理时间
2. 计算每个进程应获得的处理机时间，即自创建以来的时间除以 n
3. 计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比
4. 比较各进程获得处理机时间的比率
5. 调度程序应选择比率最小的进程，将处理机分配给它，并让它一直运行，直到它的比率超过最接近它的进程的比率为止

公平分享调度算法

描述：分配给每个进程相同的处理机时间

在公平分享调度算法中，调度的公平性主要是针对用户的，即所有用户能获得相同的处理机时间或所要求的时间比例。因为调度是以进程为基本单位的，所以必须考虑每个用户所拥有的进程数目

实时调度

实现实时调度的基本条件

提供必要的信息

1. 就绪时间：指某任务的状态转换为就绪状态的起始时间，在周期任务的情况下，就绪时间是事先预知的一串时间序列
2. 开始截止时间和完成截止时间：对于典型的实时应用，只须知道开始截止时间或完成截止时间
3. 处理时间：一个任务从开始执行直至完成所需的时间
4. 资源要求：任务执行时所需的一组资源
5. 优先级：若某任务的开始截止时间被错过了（势必引起故障），则应赋予任务“绝对”优先级；若其开始截止时间的错过对任务的继续执行无重大影响，则可赋予其“相对”优先级以供调度程序参考

系统处理能力强

假定系统中有 m 个周期性的 HRT 任务，它们的处理时间表示为 Ci，周期时间表示为 Pi，则在单处理机情况下，必须满足

的限制条件，系统才可以调度。因该限制条件并未考虑任务切换所花费的时间，故当利用该限制条件时，应适当留有余地

提高处理机能力的途径：

1. 采用单处理机系统：须增强其处理能力，以显著减少对每个任务的处理时间
2. 采用多处理机系统：假定系统中的处理机个数为 N，则限制条件应为

   

采用抢占式调度机制

在含有 HRT 任务的实时系统中，广泛采用抢占式调度机制可以满足 HRT 任务对截止时间的要求，这种调度机制比较复杂

对于一些小的实时系统，若能预知任务的开始截止时间，则对实时任务的调度可采用非抢占式调度机制，以简化调度程序和任务调度时所花费的系统开销

在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界代码后能及时地将自己阻塞起来，以便释放处理机并供调度程序去调度开始截止时间即将到达的任务

采用快速切换机制

为保证 HRT 任务能及时运行，在系统中应采用快速切换机制，使之能进行任务的快速切换，该机制应具有以下两方面的能力：

1. 对中断的快速响应能力：对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机（影响其他紧迫任务的执行）
2. 快速的任务分派能力：为了提高分派程序的任务切换速度，应使系统中的每个运行功能单位适当地小，以减少任务切换的开销

实时调度算法分类

非抢占式调度算法

非抢占式轮转调度算法

描述：由一台计算机控制若干个相同的或类似的对象，为每个被控对象建立一个实时任务，并将其排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾进行等待，调度程序再选择下一个队首任务运行

响应时间：数秒至数十秒

应用：可用于要求不太严格的实时控制系统

非抢占式优先级调度算法

描述：若在系统中还含有少数具有一定要求的实时任务，则可采用非抢占式优先级调度算法，系统会为这些任务赋予较高的优先级。当这些实时任务到达时，系统会把其安排在就绪队列的队首，等待当前任务自我终止或运行完成后，再通过调度执行队首的高优先级进程

响应时间：数百毫秒至数秒

应用：可用于有一定要求的实时控制系统

抢占式调度算法

根据抢占发生时间的不同，将抢占式调度算法分为 基于时钟中断的抢占式优先级调度算法 和 立即抢占的优先级调度算法

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

描述：在某实时任务到达后，若其优先级高于当前任务的优先级，则此时并不立即抢占当前任务的处理机，而是等到时钟中断发生后，调度程序才会剥夺当前任务的执行，将处理机分配给新到的高优先级任务

调度时延：几毫秒至几十毫秒

应用：用于大多数的实时系统

立即抢占的优先级调度算法

描述：此调度算法要求 OS 具有快速响应外部中断事件的能力。一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务

调度时延：几百微秒至几毫秒

最早截止时间优先算法 EDF

描述：根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最早的截止时间的任务排在队列的前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，并为之分配处理机

使用：即可用于抢占式调度方式中，又可用于非抢占式调度方式中

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

解析：4 个非周期实时任务先后到达。系统先调度任务 1 执行，在任务 1 执行期间，任务 2、任务 3 又先后到达。由于任务 3 的开始截止时间早于任务 2 的，故系统在执行完任务 1 后先调度任务 3 执行。在此期间任务 4 又到达了，其开始截止时间仍早于任务 2 的，故在任务 3 执行完后，系统又会先调度任务 4 执行，最后才调度任务 2 执行

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

最低松弛度优先算法 LLF

描述：最低松弛度优先算法在确定任务的优先级时，根据的是任务的紧急程度或松弛度。任务紧急程度越高，赋予该任务的优先级就越高，使其可被优先执行

松弛度=必须完成时间 - 其本身的运行时长 - 当前时间

解析：任务 A 每 20ms 执行一次，执行时长为 10ms，任务 B 每 50ms 执行一次，执行时长为 25ms，任务 A 和任务 B 每次必须完成的子任务 A1、A2、A3、……和 B1、B2、B3、……的时间情况

优先级倒置

优先级倒置的形成

高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞

优先级倒置的解决方法

一种简单的解决方法

规定：在进程进入临界区后，其所占用的处理机就不允许被抢占

适用情况：系统中的临界区都较短且不多时适用

一种比较实用的解决方法

建立在动态优先级基础的基础上

规定：当高优先级进程要进入临界区去使用临界资源时，若已有一个低优先级进程正在使用该资源，则此时一方面高优先级进程会被阻塞，另一方面会由低优先级进程继承高优先级进程的优先级，并一直保持到低优先级进程推出临界区

目的：不让比低优先级进程的优先级稍高但比高优先级进程的优先级稍低的进程插进来，导致延缓低优先级进程退出临界区