大家可以看下我使用幕布软件画的思维导图，如果大家想使用幕布可以通过我的邀请链接注册，可免费获得一个月高级会员https://mubu.com/inv/477598

在多道程序中，调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。

5.1 处理机调度的层次和调度算法的目标

在多道批处理系统中，一个作业从提交到获得处理机执行，直至作业运行完成，可能需要经历多次处理机调度。

5.1.1 处理机调度的层次

高级调度
高级调度又称为长程调度或作业调度，他的调度对象是作业。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存、为他们创建进程，分配必要的资源，并将他们放入就绪队列。
低级调度
低级调度又称为短程调度或作业调度，他的调度对象是进程。主要功能是根据某种算法，决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。
中级调度
中级调度又称为内存调度。主要功能是将那些暂时不能运行的进程，调至外存等待，当他们具备运行条件且内存又稍有空闲时再调入内存。

5.1.2 处理机调度算法的目标

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

资源利用率
系统中的处理机和其它所有资源应尽可能保持忙碌状态，其中最重要的处理机利用率可用以下方式计算： $CPU的利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$
公平性
系统中的所有的进程都应该获得合理的CPU时间，不会发生进程饥饿现象。，对同类型的进程获得相同的服务；不同类型的进程，由于紧急程度不同或者重要性不同，应提供不同的服务。
平衡性
系统中可能具有多种类型的进程，有的是计算型作业，有的是I/O型作业。为了使CPU和资源尽可能的处于忙碌状态，调度算法应尽可能的保持系统资源使用的平衡性。
策略强制执行
对所定制的策略，只要需要，就必须准确的执行。

5.1.2.2 批处理系统的目标

平均周转时间段
周转时间，是指从作业被提交给系统，直到作业执行完毕所花费的时间。
对于每个用户来言，都希望自己的周转时间最短；但是对于系统来言，他要求的是平均周转时间最短，这不仅可以提高系统资源的利用率，而且还可使大多数用户都感到满意。
可把周转时间描述为： $T=\frac{1}{n}[\sum_{i=1}^{n}{T_i}]$ 为了进一步反应调度的性能，更清楚的描述各进程在其周转时间中，等待和执行时间的具体分配情况，往往使用带权周转时间，即作业周转时间T与系统为他提供的时间Ts之比，即$ W=\frac{T}{T_s} $，平均带权周转时间可表示为： $W = \frac{1}{n}\sum_{i=1}^{n}\frac{T_i}{T_s}$
系统吞吐量高
处理机利用率高

5.1.2.3 分时系统的目标

相应事时间快
响应时间是指从用户通过键盘提交一个请求开始，直到屏幕上显示出处理结果为之的一段时间间隔，它包括三部分时间：一是请求信息从键盘输入开始，直至将其传送到处理机的时间；二是处理机对请求信息进行处理的时间；三是将所形成的的响应信息回送到终端显示器的时间。
均衡性
用户对响应时间的要求并非完全相同。通常，用户对于复杂的的作业，响应时间允许较长；对于简单的作业，响应时间则要短。

5.1.2.4 实时系统的目标

截止时间的保证
截止时间是指某任务必须开始执行的最迟时间，或者必须完成的最迟时间。
可预测性

5.2 作业与作业调度

我们前面讲到过，在多道批处理系统中，作业由用户提交给系统操作员，再由系统操作员把作业输入给相应的输入设备，并保存在一个后备队列中，然后就由作业调度程序将其从外存调入内存再来进行处理。

5.2.1 作业

5.2.1.1 作业和作业步

作业
作业一般包括程序还数据，还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。
作业步
在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果。我们把其中的每一个加工步骤称为一个作业步。

5.2.1.2 作业控制块JCB

为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，她是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
通常内容有作业标识、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等。

5.2.1.3 作业运行的三个阶段和三种状态

收容阶段
操作员把用户提交的作业通过某种输入方式或SPOOLing系统输入到硬盘上，再为改作业建立PCB，并把它放入作业后备队列中。作业此时的状态为后备状态
运行阶段
当作业被作业调度选中后，变为它分配必要的资源和建立进程，并将它放入就绪队列。一个作业从第一次进入就绪状态开始，知道他运行结束前，都处于运行状态
完成阶段
当作业运行完成，或者发生异常情况提前结束时，作业便进入完成阶段，相应的作业状态为“完成状态”。

5.2.2 作业调度的主要任务

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

接纳多少个作业
在每一次作业调度时，应当从后备队列中选取多少作业调入内存，取决于多道程序度，即允许多少个作业同时在内存中运行。
接纳哪些作业
选择哪些作业取决于，作业调度采用哪种算法。

5.3 作业调度算法

5.3.1 先来先服务（FCFS）算法算法

对于这个算法，八个字——简单粗暴，没啥可讲。你来的早我就先服务你，其他人不管再牛逼你来晚了你就是弟弟，你得等我先把前面这位服务好了再来服务你。

5.3.2 短作业优先（SJF）调度算法

对于这个算法，他也是基于先来先服务，只是多了个考虑范围，就是原则上还是先到先服务，但是当服务完一个之后并且还有很多个再等着被服务时，就从中找一个需要服务时间最短的先来服务，服务完他了，在从剩下的找一个最短的来服务。
这个算法有几个缺点：

必须预知作业的运行时间
对长作业很不利
人机无法交互
没有考虑作业执行的紧迫感，对急需服务的作业不管

5.3.3 优先级调度算法（PSA）

在优先级算法中，基于作业的紧迫程度，外部会赋予进程的优先级，然后优先级算法就根据算法的优先级，进行调度。算法实质上类似于短作业优先，你甚至可以把短作业优先级算法也看做是优先级算法，只不过他的优先级是作业长短，而优先级调度算法的优先级是进程的紧迫程度。

5.3.4 高响应比优先调度算法（HRRN）

FCFS算法是考虑了作业的等待时间，却忽略的作业的运行时间；而SJF算法是只考虑了作业的运行时间，却忽略了作业的等待时间。高响应比算法是又考虑运行时间又考虑等待时间，因此既能照顾短作业，又不致使长作业的等待时间过长。

他为每个作业引入了一个动态优先级，即优先级是可以改变的，它随着等待时间的延长而增加，这使得长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。这个变化规律可描述为：

$优先级=\frac{等待时间+要求服务时间}{要求服务时间}$

由于等待时间与服务时间之和就是系统对该作业的响应时间，故该优先级又相当于响应比$R_p$。所以，优先级又可表示为： $R_p=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$

从上面可以看出

如果作业的等待时间相同，则要求服务的时间越短，优先级越高
当要求服务时间相同时，作业的优先级决定于其等待时间
对于长作业的优先级，可以随等待时间的增加而提高

5.4 进程调度

5.4.1 进程调度的任务、机制和方式

5.4.1.1 进程调度的任务

保存处理机的现场信息
在进行调度时首先需要保存当前进程处理机的现场信息。
按某种算法选取进程
调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给他。
把处理机分配给进程
由分派程序把处理器分配给该进程，此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。

5.4.1.2 进程调度机制

为了实现进程调度，在进程调度机制中，应具有如下三个基本部分：

排队器
为了提高进程调度的效率，应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列，以便调度程序能最快的找到它。
分派器
分派器依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行从分派器到新选出进程间的上下文切换，将处理机分配给新选出的进程。
上下文切换器
在对处理机进行切换时，会发生两对上下文的切换操作
1. 对上下文切换时，OS将保存当前进程的上下文，即把当前进程的处理机寄存器的内容保存到该进程的进程控制块中的相应单元，再装入分派程序的上下文，以便分派程序运行
2. 对上下文切换是移除分派程序的上下文，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中，以便新选进程运行

5.4.1.3 进程调度方式

非抢占方式
在这种方式下，一旦处理机分派给一个进程后，就一次性一直处理下去，直到该进程被处理完。
抢占方式
这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的程序，将已分配给该进程的处理机重新分配给另一进程。
它遵循的主要原则有：
1. 优先权原则，优先级高的新到进程抢占正在运行的优先级低的进程
2. 短进程优先原则，需要运行时间更短的新到进程抢占正在运行的需要运行时间更长的进程
3. 时间片原则，各进程按时间片轮转运行，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度

5.4.2 轮转调度算法

在分时系统中，最常用也是最简单的就是基于时间片的轮转调度算法。该算法采取了非常公平的处理机分配方式，即让就绪队列上每个进程每次仅运行一个时间片。n个进程每个都运行$\frac{1}{n}$的处理机时间。

5.4.2.1 基本原理

在RR算法中，系统根据FCFS策略，将所有的就绪进程排成一个就绪队列，并可设置每隔一定时间间隔即产生一次中断，激活系统中的进程调度程序，完成一次调度，将CPU分配给队首进程，令其执行。

5.4.2.2 进程切换时机

如果一个时间片尚未用完但是正在运行的进程已经完成，此时可以切换
在一个时间片用完，正在执行的进程还未执行完成，这时也可以切换

5.4.2.3 时间片大小的确定

在RR算法中，时间片的大小对系统性能有很大的影响。
如果选择很小的时间片，有利于短作业，因为他能在该时间片内完成，但时间片小，意味着会频繁调度，这无疑会增加系统开销。
时间片小于交互时间

如果时间片选择太长，这样的话RR可能会退化成FCFS，无法满足短作业和交互式用户的需求。
时间片大于交互时间

5.4.3 优先级调度算法

在RR算法中，我们假设了所有进程的紧迫性是相同的，但是实际情况并非如此。我们为了满足实际情况，在进程调度算法中引入了优先级，而形成的优先级调度算法。

5.4.3.1 优先级调度算法的类型

非抢占式优先级调度算法
抢占式优先级调度算法

这块和前面调度算法方式一样，在此就不多说。

5.4.3.2 优先级类型

5.4.3.2.1 静态优先级

静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的。确定进程优先级大小的依据有如下三个：

进程类型，通常系统进程的优先级一般高于用户进程。
进程对资源的需求，对资源要求较少的进程应赋予较高的优先级。
用户要求，根据进程的紧迫程度及用户所付费用的多少确定优先级。

静态优先级法简单易行，系统开销小，但是不够精确，可能会出现优先级低的进程长期没有被调度的情况。

5.4.3.2.2 动态优先级

动态优先级是指进程创建之初，先赋予一个优先级，然后根据进程的推进或等待时间的增加而改变，以便获得更好的调度性能。

5.4.4 多队列调度算法

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

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

5.4.5 多级反馈队列调度算法

前面的算法都有一定的局限性，如果未指明进程长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而下述的多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，还可以很好地满足各种类型进程的需要，因而他是目前公认的一种较好的进程调度算法。

5.4.5.1 调度机制

设置多个就绪队列。在系统中设置多个就绪队列，并未每个队列赋予不同的优先级。第一个队列的优先级最高，第二次之，其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也不同，在优先级越高的队列中时间片越小。
每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程时，如他能在时间片内完成，便可撤离系统，否则，他在一个时间片结束还未完成时，转入第二队列末尾等待，依次类推。
按队列优先级调度，首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列。

5.4.5.2 调度算法的性能

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

5.4.6 基于公平原则的调度算法

5.4.6.1 保证调度算法

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

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

跟踪计算每个进程自创建以来已经执行的处理时间。
计算每个进程应获得的处理机时间，即自创建以来的时间除以n。
计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。
比较各进程获得处理机时间的比率。如进程A的比率最低，为0.5，而进程B的比率为0.8，进程C的比率为1.2等。
调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

5.4.6.2 公平分享调度算法

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

5.5 实时调度

5.5.1 实现实时调度的基本条件

提供必要的信息
1. 就绪时间，是指某任务称为就绪状态的时间，在周期任务的情况下，她是实现预知的一串时间序列。
2. 开始截止时间和完成截止时间，对于典型的实时应用，只需知道开始截止时间或者完成截止时间
3. 处理时间，一个任务从开始执行，直至完成时所需的时间
4. 资源要求，任务执行时所需要的一组资源
5. 优先级，如果某任务的开始截止时间错过，势必引起故障，则应为该任务赋予“绝对”优先级；如果其开始截止时间的错过，对任务的继续运行无重大影响，则可为其赋予“相对优先级”，供调度程序参考
系统处理能力强
在实时系统中，若处理机的处理能力不够强，则有可能因处理机忙不过，而致使某些实时任务不能得到及时处理，从而导致发生难以预料的后果。
假定系统中有m个周期性的硬实时任务HRT，他们的处理时间可表示为$Ci$，周期时间表示为$P_i$，则在单处理机情况下，必须满足下面的限制条件系统才是可调度的：$$ \sum{i=1}^{m}\frac{Ci}{P_i}\le1 $提高系统处理能力的途径有二：一是采用单处理机系统，但须增强其处理能力，以显著地减少对每一个任务的处理时间；二是采用多处理机系统。假定系统中的处理机数为N，则应将上述的限制条件改为：$ \sum{i=1}^{m}\frac{C_i}{P_i}\le N $$
采用抢占式调度机制
在含有HRT任务的实时系统中，广泛采用抢占机制。这样便可满足HRT任务对截止时间的要求。但这种调度机制比较复杂。对于一些小的实时系统，如果能够预知任务法开始截止时间，则对于实时任务的调度可以采用非抢占式调度。
具有快速切换机制
为保证硬实时任务能及时运行，在系统中还应具有快速切换机制，使之能进行任务的快速切换。该机制应具有如下两方面的能力：
1. 对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)。
2. 快速的任务分派能力。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。

5.5.2 实时调度算法的分类

5.5.2.1 非抢占式调度算法

非抢占式轮转调度算法
由一台计算机控制若干个相同的对象，为每个被控对象建立一个实时任务。并将他们排成一个轮转队列。调度程序每次选择队列中的第一个任务投入运行，当该任务完成后，便把它挂在轮转队列的末尾等待，调度程序再选择下一个队首任务运行。
非抢占式优先调度算法
如果在系统中还含有少数具有一定要求的实时任务，则可采用非抢占式优先调度算法，系统为这些任务赋予了较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，便可去调度执行队首的高优先级进程。

5.5.2.2 抢占式调度算法

基于时钟中断的抢占式优先级调度算法。
在某实时任务到达后，如果他的优先级高于当前任务的优先级，这是并不立即抢占当前任务的处理机，而是等到时钟中断发生时，调度程序才剥夺大年任务的执行，把处理机分配给新到的高优先级的任务。
立即抢占的优先级调度算法。
在这种调度策略中，要求操作系统具有快速响应外部事件中断的能力，一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。