调度层次

这里的处理对象是作业，这时一个比较宽泛的概念，不仅仅包括程序和数据，还应包括对程序运行的控制信息。在批处理系统上，作业是最基本的调度单位，由后备队列中调入内存，在为其创建相应的进程，分配内存与相关的资源，之后根据相关的算法来分配cpu资源（以时间片作为单位），但是可能会有相关的事件发生，有些进程会被阻塞或者挂起，之后又重新就绪获得时间片进行运行，往复直至运行结束。根据各个阶段的资源调度特点，将其分为三个层次。

高级调度

就是最先的那一段，决定将后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，准备执行。
运行时调度的频率低（相关进程创建后的运行需要时间，内存有限），调度的算法可以很复杂（要确定相关调度的作业）

中级调度

之后就是中级调度了，之前创建的进程可能会由于相关事件或者没有请求到相关的资源，导致其无法立即运行，这时如果其还占用着内存资源的话会比较浪费，我们可以根据其状态将其移到外存中的相关队列中，等待其具备了运行条件，且内存又稍有空闲时，再由中级调度加载入内存中等待（就绪）继续运行。
其细分为内存就绪（表示进程在内存中就绪）和外存就绪（进程在外存中就绪），内存阻塞（运行后由于事件或者资源条件被撤到到内存）和外存阻塞（在内存中长期处于阻塞状态，将其换至外存中存储）。
中级调度的目的是为了提高内存利用率和系统吞吐量，调度频率介于高级调度和低级调度之间。
图中的阻塞，挂起队列与就绪挂起队列都是在外存中，就绪队列与阻塞队列位于内存中。

低级调度

这里就是具体决定是哪一个就绪进程获得处理机（cpu）的使用权（时间片）。主要分配的对象是cpu处理机。
调度方式有两种：一种是非抢占式，一种是抢占式。
非抢占式：故名思意，一旦获取到了cpu的使用权，就不会被抢占，即使是比它更为重要的进程对处理机提出请求，也不会剥夺当前cpu的使用权，直至当前进程运行完成或者由于事件进入阻塞状态时，才会把处理机分配给下一进程。
抢占式：抢占式就是当前进程运行时，如果有一个更重要的进程提出对处理机的请求时，就立即暂停对当前进程的执行，并将处理器分配给更紧迫的进程。
比较：非抢占式的系统开销小，实时性差，很多的耗时操作会占据太多的时间导致进程的等待时间增长。抢占式可以避免耗时进程对cpu资源的霸占。可以设置相关的优先级进行调度。

调度算法的性能衡量

周转时间

从作业提交给系统开始，到作业完成为止的时间间隔；
周转时间=后备队列等待时间（作业）+就绪队列等待时间（进程）+CPU上执行时间（进程）+等待I/O操作时间（进程）
平均周转时间=总的周转时间 / 进程数量
带权周转时间=总的周转时间 / 实际需要运行（服务）的时间
平均带权周转时间=总的带权周转时间 / 进程数量

面向用户

响应时间：用户从提交键盘命令开始，到系统首次给出响应为止的时间。
截止时间：作业（或进程）开始（或结束）的最晚时间
面向用户的准则要求响应时间快，截止时间保证。

面向系统

吞吐量：系统单位时间内完成的作业或进程的数量。
面向系统的准则要求系统吞吐量高，处理机利用率好，资源利用均衡。

调度算法

用于资源分配，根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。

先来先服务(FCFS)

既可用于作业调度，也可用于进程调度。
对于作业的调度，对应于高级调度中其总是取出后备作业队列中最先进入该队列中的作业，将其调入内存中，为其创建进程，放入就绪队列中。
对于进程的调度，可以对应与低级调度中，其总是选取最先进入就绪队列中的进程为之分配处理器使之运行。
特点是实现简单，仅考虑各个进程或作业的就绪时间（进入队列的时间先后），对于短作业的调度上会导致短作业的等待时间增加，从而加大其周转时间。

短作业（进程）优先(SJF/SPF)

既可用于作业调度(SJF)，也可用于进程调度(SPF)。
对于作业的调度，对应于高级调度中其总是取出后备作业队列中要求服务时间（执行时间）最短 的作业，将其调入内存中，为其创建进程，放入就绪队列中。
对于进程的调度，可以对应与低级调度中，其总是选取执行时间最短的进程为之分配处理器使之运行。
但是这个算法很难实现，我们很难去推断每个作业或者进程运行时需要的时间，仅考虑了执行时间，加大了耗时作业的等待周期，进而增大了耗时作业的周转周期，但是平均周转时间会减少。

高优先权优先(FPF)

既可用于作业调度，也可用于进程调度。
用于作业调度时：系统将从后备队列中选择若干个优先权最高的作业，装入内存。
用于进程调度时：该算法是把处理机分配给就绪队列中优先权最高的进程。分为非抢占式优先权算法和抢占式优先权调度算法。

优先权

反映作业或进程执行时的迫切程度，是对调度所考虑的实际因素的算法抽象。通常用1个整型数来表示。
**进程的优先权(抢占式)**高优先权进程到达时，立刻停止低优先权进程的执行，让高优先权进程执行。
**进程的优先权(非抢占式)**高优先权作业进程到达时，要等待低优先权进程执行完毕或主动释放CPU之后才能执行。

优先权的确定

静态优先权：进程创建时确定（根据进程类型、资源需求和用户要求），直到进程执行结束，保持不变。
动态优先权：进程创建时确定（根据进程类型、资源需求和用户要求等）初始优先权，在进程执行过程中，可以发生变化。

高响应比优先

用于作业调度。系统将从后备队列中选择若干个响应比(优先权)最高的作业，装入内存，投入运行。

优先权确认

优先权=响应时间 / 要求服务时间 = （等待时间+要求服务时间）/ 要求服务时间=1 + 等待时间 / 要求服务时间
也就是上面的加权周转时间，但是注意这里的优先权是在变化的，因为随着作业的调度运行，等待时间时会不断增加的，所以优先权会不断的增大（要求服务时间不变），直至获得资源运行。在此期间等待的作业会以一定的速率a来提高其优先权。

如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，算法有利于短作业。
当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。
对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而获得处理机。避免了短作业一直占用处理机导致长作业无法及时运行。（改进短作业优先）
虽然这一算法综合了前几个算法的特点，但是其需要计算响应比，会增加系统开销。

时间片轮转(RR)

用于作业调度或进程调度。
在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。
保证响应时间：就绪队列中的所有进程，在给定时间内，均能获得一个时间片的处理机执行时间。换言之，系统能在给定的时间内，响应所有用户的请求。
时间片的大小从几毫秒到几百毫秒。

时间片

时间片选择：固定时间片，可变时间片。
不可太大：影响最大响应时间：
T=nq；其中，n为进程数量，q为时间片大小。
不可太小：调度开销，增加周转时间；

多级反馈队列(MFQ)

设置多个就绪队列

设置多个就绪队列，为各队列赋予不同的优先级。第1个队列的优先级最高，其余队列优先权逐个降低。赋予各个队列中进程执行时间片的大小各不相同：优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。仅当第1队列空闲时，调度程序才调度第2队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机（正在运行进程被放回原所在队列末尾）

实现

对新创建进程，首先将它放入第1队列末尾，按先来先服务原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，则结束; 如果未完成，调度程序便将该进程转入第2队列的末尾，再同样按先来先服务原则等待调度执行；如果它在第2队列中运行1个时间片后仍未完成，再依次将它放入第3队列…。如此下去，当1个长作业（进程）从第1队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式运行。
避免了事先计算各种进程所需的执行时间，适合各种需求。

实时调度

实时系统中都存在着若干个实时进程或任务，它们用来反应或控制某个（些）外部事件，往往带有某种程度的紧迫性。

可调度条件

对于m个实时任务，处理时间为Ci,周期时间为Pi，系统是可调度的，则需满足下列条件：

∑

i

=

1

m

C

i

P

i

≤

1

\sum_{i=1}^m\frac {Ci}{Pi}\le1

∑i=1m​PiCi​≤1

算法分类

任务性质
硬实时调度算法：严格实时
软实时调度算法：非严格实时
调度方式
非抢占调度算法
抢占调度算法
调度时间
静态调度：在进程执行前，调度程序便已经决定了各进程间的执行顺序。
动态调度：在进程的执行过程中，由调度程序届时根据情况临时决定将哪一进程投入运行。

非抢占式调度算法

非抢占式轮转调度：将所有实时任务排列成队列，轮流投入运行；当任务完成，就重新排到队列末尾；调度时选择队首进程；
实时响应时间：数秒-数十秒

非抢占式优先调度：为所有实时任务设定优先权；高优先权进程到达队列，排到队首，以待当前任务执行完毕；调度时选择队首进程；
实时响应时间：数百毫秒-数秒

抢占式调度算法

基于时钟中断的抢占式优先权调度：为所有实时任务设定优先权；高优先权进程到达队列，排到队首，以待时钟中断到达时，调度到CPU上执行；调度时选择队首进程；
实时响应时间：数毫秒-数十毫秒

立即抢占的优先权调度：为所有实时任务设定优先权；高优先权进程到达队列，只要当前进程不在临界区，则立刻抢占CPU；调度时选择队首进程；
实时响应时间：数百微秒-数毫秒

最早截止时间优先调度(EDF)

根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。该算法要求在系统中保持一个实时任务就绪队列，该队列按各任务截止时间的早晚排序，具有最早截止时间的任务排在队列的最前面。调度程序在选择任务时，总是选择就绪队列中的第一个任务，为之分配处理机，使之投入运行。
这里的开始时间最早是指最早可以开始运行的时间。

最低松弛度优先调度(LLF)

根据任务的紧急程度（松弛度）来确定任务的优先级。
松弛度 = 必须完成时间 – 本身运行时间 – 当前时间
调度程序在选择任务时，总是选择就绪队列中紧急程度（松弛度）最大任务，为之分配处理机，使之投入运行。
抢占时机为松弛度为0的时候。
例如：周期性任务A和B，执行时间分别为10ms和25ms，周期分别为20ms和50ms。

对于A来说，每20ms内要运行10ms，对于B来说每50ms内要运行25ms，抢占发生的时机为松弛度为0的时候。刚开始
A的松弛度=20(20ms内必须完成)-10(运行时间)-当前时间(0)=10
B的松弛度=50(50ms内必须完成)-25(运行时间)-当前时间(0)=25
所以A任务先运行，运行10ms后A的第一次循环结束。
A的松弛度=40(40ms内必须完成)-10(运行时间)-当前时间(10)=20
B的松弛度=50(50ms内必须完成)-25(运行时间)-当前时间(10)=15
以此循环进行，但是当出现松弛度为0的情况时就抢占cpu，让松弛度为0的进程运行。
不足是当多个任务的松弛度相近时就要不断的切换运行，增大了调度的开销。

优先级倒置

正常：高优先级进程先执行，低优先级进程后执行
特殊情况：低优先级进程先执行，高优先级进程后执行；
比如：当低优先级的进程请求到了高优先级进程所需的相关资源，高优先级进程的资源被占用了，只有等到低优先级的进程运行完后释放资源后才能运行，但是当其用完释放后，可能会被比起优先级稍高一点进程占据运行权。
后果：高优先级进程执行被延迟。（优先级倒置）

解决方法

当低优先级进程阻塞高优先级进程，将低优先级进程的优先级提高到被它被阻塞进程的最高优先级进程的优先级。这样当其运行完了之后其不会被优先级稍高一点进程剥夺运行权，可以保证高优先权的进程的顺利运行。