1 处理机调度流程

2 处理机调度的层次

高级调度

中级调度

低级调度

3 调度队列模型

1）仅有进程调度的调度队列模型

2）具有高级调度和低级调度的调度队列模型

3）同时具有高、中、低三级调度的调度队列模型

4 处理机调度的目标

5 作业与作业调度

1作业

2 作业调度

6 进程调度

1. 进程调度的任务

2. 进程调度的机制

3. 进程调度方法

4. 轮转调度算法（RR）

5. 优先级调度算法

6. 多队列调度算法

7. 多级反馈队列调度算法

8. 保证调度算法

9. 公平分享调度算法

7 实时调度

1. 实现实时调度的基本条件

2. 实时调度算法的分类

3. 最早截止时间优先算法(EDF)

4. 最低松弛度优先算法(LLF)

5. 优先级倒置

CPU是计算机系统中十分重要的资源，但在早期的计算机系统中，对它的管理十分简单，因为那时它和其他系统资源一样，为一个作业独占，不存在处理机分配和调度问题。随着多道程序设计技术和各种不同类型的操作系统出现，各种不同的CPU管理方法得到启用。不同的CPU管理方法将为用户提供不同性能的操作系统，如在多道批处理系统中，为了提高处理机的效率和增加作业吞吐率，当调度一批作业组织多道运行时，要尽可能使作业搭配合理，充分利用系统中的各种资源；在分时系统中，由于用户使用交互式会话的工作方式，系统必须要有较快的响应时间，使得每个用户都感到如同只有自己一人在使用这台计算机，因此系统在调度作业执行时首先考虑的是每个用户作业得到处理机的均等性；在实时系统中首先要考虑的是处理机的响应时间。由此可见，操作系统的要求不同，处理机管理的策略则不同 最常用的衡量调度策略的指标有周转时间，是指将一个作业提交给计算机系统后到该作业的结果返回给用户所需要的时间；吞吐率，在给定的时间内，计算机系统完成的工作总量；响应时间，从用户向计算机发出一个命令到计算机把响应的执行结果返回给用户所需要的时间；设备利用率，主要指输入输出设备的使用情况

在多道程序系统中，进程的数量往往多于处理机的个数，进程争用处理机的情况就在所难免。 处理机调度是对处理机进行分配，就是从就绪队列中，按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发地执行。

处理机调度是多道程序操作系统的基础，它是操作系统设计的核心问题。

流程图

流程说明

1，批量作业放入后备队列，通过作业调度进入就绪队列；

2，就绪队列中的元素通过进程调度依次获得CPU使用权，或是存入就绪、挂起队列；

3，若进程执行期间时间片用完，则重新进入就绪队列；

4，若发生等待事件则进程被阻塞，进而存入阻塞队列；

概念

特点

概念

 特点

概念

特点

调度方式——非抢占式

调度方式——抢占式

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

a.资源利用率:为了提高资源的利用率，应使系统中的处理机和其他所有资源尽可能保持忙碌状态。

**b.公平性:**公平性是指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象。但公平是相对的，对于相同类型的进程应获得相同的服务，对于不同类型的进程，由于其紧急程度和重要性不同，提供不同的服务。

**c.平衡性:**为使系统中CPU和各种外部设备都能经常处于忙碌状态，调度算法应保存系统资源使用的平衡性。

d.策略强制执行: 对所指定的策略其中也包括安全策略，只要需要，就必须提供。

2.批处理系统的目标

a.平均周转时间短:

b.系统吞吐量高： 吞吐量是指单位时间内系统完成的作业数，如果单纯为了获得高的系统吞吐量，那么就应该尽可能选择短作业运行。c.处理机利用率高: 如果单纯为获得处理机利用率高，那么应该尽可能选择长作业运行。

3.分时系统的目标

a.相应时间快: 响应时间是指，是从用户通过键盘提交一个请求开始，直到屏幕上显示处理结果为止那一段时间。b.均衡性: 用户对于响应时间的要求并非完全相同，用户对于简单的任务要求响应时间短，复杂任务时间允许较长。

4. 实时系统

**a.截止时间的保证:**截止时间是指：某任务必须开始执行的最迟时间，或者必须完成的最初时间。对于严格的实时系统，其调度方式和调度算法必须要保证这一点。 **b. 可预测性:**在实时系统中，这一点非常重要，。

1. 作业

作业(Job): 作业是一个比系统更广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存。

2. 作业步

作业步(Job Step)：在作业运行期间，每个作业都必须经过若干相互独立又相互关联的顺序加工步骤才能得到结果。我们把其中每一步称为一个作业步。例如，一个典型的作业步可以分为：“编译”作业步，“链接装配”作业步，和“运行”作业步。

3. 作业控制块（JCB）

和进程线程类似，作业中也包含一个作业控制块（JCB）。通常JCB包含：作业标识，用户名称，用户账号，作业类型，作业专业，调度信息，资源需求，资源使用情况。

4. 作业运行的阶段和状态

作业从进入系统到运行，通常要经历收容，运行和完成阶段，相应的也就有了“收容状态” “运行状态” “完成状态”。

a.收容状态: 操作员把用户提交的作业通过某种方式或SPOOLing系统输入到硬盘上，在为该作业建立JCB，并把它放入作业后备对列中。

**b.运行状态:**当作业被作业调度选中后，边为它分配必要的资源和建立进程，并把他放入就绪队列。

c.完成状态: 当作业运行完成，或发生异常情况而提前结束时，作业便进入了完成阶段。

1. 作业调度的目标

作业调度的主要任务就是根据JCB中的信息，检查系统中的资源能否满足作业队资源的要求，以及按照一定的调度算法，从外存的后备对列选取某些作业调入内存。在每次执行作业调度时，都需要做出以下两个决定: **a.接纳多少个作业:**接纳多少作业取决于多道程序度。而多道程序度取决于：计算机系统规模，运行速度，作业大小，以及能否获得较好的系统性能.b.接纳哪些作业: 选择哪些作业取决于，作业调度采用哪种算法，常见的算法如下

2. 先来先服务(FCFS)

先来先服务算法，既可以用于作业调度，也可以用于进程调度。当作业调度中采取该算法时，系统将按照作业到达的先后次序来进行调度。

在系统调度中采用FCFS算法时，每次调度是从就绪的进程队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或者阻塞时，进程调度程序才会将处理机分配给其他进程。

FCFS算法在单处理机系统中以及很少作为主调度算法，但经常把它和其他调度算法结合使用，形成一种更为有效的调度算法。例如，可以在系统中按进程的优先级设置多个队列，每一个优先级一个队列，其中每一个队列的调度都基于FCFS。

3. 短作业优先(SJF)

SJF算法是以作业的短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的时间来衡量的。SJF也可以分别用于作业调度和进程调度。但用于进程调度时优于作业调度。

缺点： SJF相比FCFS算法，有很大的改进，但依然有以下缺点

4. 优先级调度算法(PSA)

优先级调度算法也是既可以用于作业调度，也可以用于进程调度。FSFC和SJF算法都无法使紧迫性的作业得到尽快的处理，而PSA正是基于作业的紧迫程度，由外部赋予的作业优先级，进行作业调度。

5. 高响应比优先算法(HRRN)

FSFC算法值考虑的作业的等待时间，SJF只考虑的作业的需要运行时间。而HRRN则既考虑了作业的等待时间，又考虑的作业的紧迫时间，从而改善了处理机调度的性能。

HRRN为每一个作业引入了一个动态优先权。该优先权的变化规律如下: 优 先 权 = 等 待 时 间 + 要 求 服 务 的 时 间 要 求 服 务 的 时 间 优先权= \frac{等待时间+要求服务的时间}{要求服务的时间} 优先权=要求服务的时间等待时间+要求服务的时间​

同时等待时间+要求服务的时间 = 相应时间。所以优先权也可以表示为 优 先 权 = R p = 响 应 时 间 要 求 服 务 的 时 间 优先权=R_p= \frac{响应时间}{要求服务的时间} 优先权=Rp​=要求服务的时间响应时间​

从上式可以看出

进程调度的任务有以下几点

为了实现进程调度，在进程调度中应该有以下三个部分：

进程调度的方法大概分为非抢占式和抢占式。a.非抢占式 采用这种调度方式时，一旦把处理机分配给某进程后，就一直让他运行下去，绝不会因为时钟中断或者其他原因抢占当前处理机，直到该进程完成或者阻塞，才把处理机分配给其他进程。这种方式的好处就是实现简单，系统开销小，适用于大部分法批处理系统。但是无法适应于分时系统和大部分的实数系统。

这种方式下，会引起调度的原因:

b. 抢占式 这种调度方式允调度程序根据某种原则，去暂停某个正在执行的进程，将已经分给该进程的处理机重新分给另一进程。广泛采用抢占式，是因为对于批处理系统，可以防止一个长进程长时间的占用处理机，以确保处理机能够为所有进程提供更为公平的服务。 在分时系统中，只有采用抢占式才能实现人机交互，在实时系统中，抢占式能满足实时任务的要求。但同时抢占式比较复杂，所需要的系统开销也比较大。

“抢占式”抢占时也需要按照一定的原则，主要原则有：

在分时系统中，最简单也是教常用的是基于时间片的轮转算法(RR).该算法采用了非常公平的处理机分配方法，即让每个进程每次仅运行一个时间片。如果就绪队列上有n个进程，则每个进程大约获得1/n的处理机时间。

a.轮转法的基本原理 在RR中，系统将所有的就绪进程按照FCFS策略排成一个就绪队列，系统可设置每个一定时间便产生一次中断， 去激活进程调度进行激活，把CPU分配队首进程，并令其执行一个时间片。运行完毕后，又把处理机分配给就绪队列的新的队首。b.进程切换时机 在RR算法中，切换时机有两种情况：

下图是时间片略大于典型交互的时间 下图是时间片小于典型交互的时间 下图是时间片分别为q=1和q=4对于平均周转时间的影响

a.优先级调度算法的类型 优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。同时又可以进一步把该算法分为：

b.优先级类型

之前所述的各种调度算法，在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度的算法是单一的，固定的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制缺点更加明显。因此多级队列算法能够在一定程度上弥补这一缺点。

多级队列算法将进程就绪队列拆分成若干个，不同的就绪队列采用不同的调度算算法，所以可以很好的满足不同用户对进程调度策略的不同需求，同时也可以满足多处理机系统的需求。

多级反馈队列不同与之前的调度算法，他可以不需确定各进程运行的时间，还可以较好的满足各种类型进程的需求。调度机制 多级反馈进程调度算法机制可以描述如下

保证调度算法是另一种类型的调度算法，它想用户所作出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易的性能保证是处理机的公平性，如果在系统中有n个类型相同的进程同时运行，为了公平期间，每个进程都获得相同的处理机时间1/n。

在实施保证调度算法时，系统必须具备这样一些功能：

分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。 在该算法中，调度的公平性是体针对于用户而言。使所有的用户获得相同的处理机时间，或要求的时间比例。

·　在实时系统中，可能存在着两类不同性质的实时任务，即HRT任务和SRT任务，它们都联系着一个截止时间。为保证系统能正常工作，实时调度必须能满足实时任务对截止时间的要求。为此，实现实时调度应具备一定的条件。

a.提供必要的信息 为了实现实时调度，系统应向调度程序提供以下信息：

b.系统处理能力强 在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。假定系统中有m个周期性的硬实时任务HRT，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的： ∑ i = 1 n C i P i ≤ 1 \sum_{i=1} ^ {n} \frac{C_i}{P_i} \leq 1 i=1∑n​Pi​Ci​​≤1

提高系统处理能力的途径有二：一是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为： ∑ i = 1 n C i P i ≤ N \sum_{i=1} ^ {n} \frac{C_i}{P_i} \leq N i=1∑n​Pi​Ci​​≤N

c.采用抢占式调度机制 　　在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。 对于一些小的实时系统，如果能够预知任务法开始截止时间，则对于实时任务的调度可以采用非抢占式调度。d.具有快速切换的机制 为保证硬实时任务能及时运行，在系统中还应具有快速切换机制，使之能进行任务的快速切换。该机制应具有如下两方面的能力：

实时调度算法按照调度方式可分为：a.抢占式

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

该算法是根据任务的截止时间确定任务的优先级，任务的截止时间越早，其优先级越高，具有最高优先级的排在队首。EDF既可以用于抢占式也可以用于非抢占式。

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

b.抢占式用于周期实时任务 下图有两个周期任务，任务A和任务B的周期时间分别为20 ms和50 ms，每个周期的处理时间分别为10 ms和25 ms。

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

假如在一个实时系统中有两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms，任务B要求每50 ms执行一次，执行时间为25 ms。由此可知，任务A和B每次必须完成的时间分别为：A1、A2、A3、…和B1、B2、B3、…，如下图

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

a.优先级倒置是什么 系统中存在着影响进程运行的资源而可能产生“优先级倒置”的现象，即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。

b.优先级倒置的解决 一种较简单的解决方法就是，规定进程进入临界区后，该进程占用的处理机不允许被抢占

另一个比较实用的方法建立在动态优先级基础的基础上：该方法规定，当高优先级进程要进入临界区时，去使用临界资源R时，如果已有一个低优先级进程正在使用该资源。此时高优先进程被阻塞，另一方面低优先级进程继承高优先进程的优先级，直到低优先进程退出临界区。