操作系统（7）----调度相关知识点（万字总结~）

一.调度的三个层次

1.高级调度

2.低级调度

3.中级调度

二.进程的挂起状态

三.进程调度的时机

四.进程调度方式

1.非剥夺调度方式

2.剥夺调度方式

五.进程的切换与过程

六.调度器/调度程序

1.调度程序

2.闲逛进程

七.评价调度算法的各个指标

1.CPU利用率

2.系统吞吐量

3.周转时间

4.等待时间

5.响应时间

八.调度算法

1.先来先服务算法（FCFS）

2.短作业优先（SJF）

3.高响应比优先（HRRN）

4.时间片轮转调度算法（RR）

5.优先级调度算法

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

7.多级队列调度算法

一.调度的三个层次

1.高级调度

高级调度也称为作业调度，作业即一个具体的任务，用户向系统提交一个作业就相当于用户让操作系统启动一个程序（来处理一个具体的任务），若用户想启动一个程序，那么这个程序所需的所有数据就要从外存调入到内存中。内存空间有限，有时无法将用户提交的作业全部放入内存。这时操作系统就要启动高级调度，决定到底先启动哪个程序：

高级调度会按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程，每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

2.低级调度

低级调度(进程调度/处理机调度) ，低级调度会按照某种策略从就绪队列中选取一个进程，将处理机分配给它（内存-->CPU）。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

3.中级调度

内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。

暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列。

中级调度(内存调度)--就是按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

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

三个调度的对比：

二.进程的挂起状态

暂时调到外存等待的进程状态为挂起状态 (挂起态，suspend)，挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。所以模型之前学习的五状态模型--->七状态模型

这里注意"挂起"和”阻塞“的区别：

两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

注：有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

三.进程调度的时机

进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

那么什么时候需要进行进程调度与切换

1.当前运行的进程主动放弃处理机

•进程正常终止

•运行过程中发生异常而终止

•进程主动请求阻塞（等待I/O）

2.当前运行的进程被动放弃处理机

例如:

•分给进程的时间片用完

•有更紧急的事需要处理（I/O中断）

•有更高优先级的进程进入就绪队列

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

什么时候不能进行进程调度与切换

1.在处理中断的过程中，中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。

2.进程在操作系统内核程序临界区中。

3.在原子操作过程中(原语) 。原子操作不可中断，要一气呵成如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)。

注：注意区分操作系统内核程序临界区与普通的临界区

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

临界区:访问临界资源的那段代码

对于内核程序临界区：

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)

当某个进程处于内核程序临界区，并且这个临界区需要访问就绪队列，在访问之前需要把这个就绪队列上锁，若当前进程还没退出临界区(还没解锁)就进行进程调度，但是进程调度相关的程序也需要访问就绪队列,但此时就绪队列被锁住了，因此又无法顺利进行进程调度

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

对于普通临界区：

进程在访问临界资源的时候会进行上锁，例如下图，打印机是临界资源，在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲（因为这个进程一直霸占着CPU）。进程在访问普通的临界资源时是应该进行进程调度的，因为临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

总结：

进程在操作系统内核程序临界区中不能进行调度与切换
进程处于临界区时能进行处理机调度

四.进程调度方式

前面看到，有些系统中，进程可以被强行剥夺处理机资源，而某些系统不能这样做，这是由于进程调度方式不同。

1.非剥夺调度方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

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

缺点：无法及时处理紧急任务，适合于早期的批处理系统

2.剥夺调度方式

剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

优点：可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能 (通过时钟中断)。适合于分时操作系统、实时操作系统

五.进程的切换与过程

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

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。 (这个进程可以是刚刚被暂停执行的进程也可能是另一个进程，后一种情况就需要进程切换)

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

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

进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存

2.对新的进程各种数据的恢复
(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块PCB中)

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

六.调度器/调度程序

1.调度程序

如下图所示，②，③由调度程序引起，调度程序决定:
让谁运行，这就涉及到调度算法（先来先服务，短作业优先等），而运行多长时间则由时间片大小决定。

调度时机----什么事件会触发“调度程序” ?

•创建新进程
•进程退出
•运行进程阻塞
•l/O中断发生(可能唤醒某些阻塞进程)
•非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
•抢占式调度策略，每个时钟中断或k个时钟中断会触发调度程序工作

注：

在不支持内核级线程的操作系统中，调度程序处理对象是进程

在支持内核级线程的操作系统中，调度程序处理对象是内核级线程

2.闲逛进程

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

闲逛进程的特性:
•优先级最低
•可以是0地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)，这个中断会周期性唤醒调度程序，让调度程序检查有没有其他就绪进程已经就绪，如果有就让闲逛进程下处理机，让其他进程上处理机器。
•能耗低，0地址指令表示不需要访存，也不需要访问CPU的寄存器，这就会使CPU能耗较低

七.评价调度算法的各个指标

1.CPU利用率

由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作

CPU利用率:指CPU“忙碌”的时间占总时间的比例

有些题目还要求计算某种设备的利用率，例如：

某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少?

CPU利用率：

打印机利用率：

通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算

2.系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业，所以设置了系统吞吐量来记录单位时间内完成作业的数量。

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

例如：

某计算机系统处理完10道作业，总共花费100s，则系统吞吐量为：

10/100=0.1道/秒

3.周转时间

对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间，周转时间是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

它包括四个部分:

•作业在外存后备队列上等待作业调度(高级调度)的时间

•进程在就绪队列上等待进程调度(低级调度)的时间

•进程在CPU上执行的时间

•进程等待I/O操作完成的时间。

后三项在一个作业的整个处理过程中，可能发生多次。

周转时间的计算：

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

对于用户来说，更关心自己的单个作业的周转时间

平均周转时间=各作业周转时间之和/作业数

对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值

带权周转时间：

带权周转时间=作业周转时间/作业实际运行的时间=作业完成时间-作业提交时间/作业实际运行时间

带权周转时间必然≥1（因为周转时间包含了作业的实际运行时间）
带权周转时间与周转时间都是越小越好

对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。
对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。

平均带权周转时间：

平均带权周转时间=各作业带权周转时间之和/作业数

与平均周转时间类似，平均带权周转时间是系统更看重的。

4.等待时间

计算机的用户希望自己的作业尽可能少的等待处理机。而等待时间就是指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

作业刚开始提交时，被放在外存中作业后被队列，等待被服务（调度），当作业被调度后，就会被放在内存中，并且建立相应的进程。这个进程会被CPU服务，会被I/O设备服务，当然也会有等待被服务的时候，当进程结束，作业被移出内存。

注：对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

但对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

5.响应时间

对于计算机用户来说，会希望自己的提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。而响应时间就是指从用户提交请求到首次产生响应所用的时间。

八.调度算法

1.先来先服务算法（FCFS）

按照作业/进程到达的先后顺序进行服务，主要从“公平”的角度考虑。

可用于进程调度和作业调度

用于作业调度时，考虑的是哪个作业先到达后备队列;用于进程调度时，考虑的是哪个进程先到达就绪队列

是否可抢占

其是非抢占算法

例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

先来先服务调度算法:按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。

因此，调度顺序为:P1-->P2-->P3-->P4

我们可以看到P3的带权周转时间=8/1=8，也就是他运行时间很少，等待的时间却很长，所以p3进程的用户体验是很不好的。

注：本例中的进程都是纯计算型的进程，一个进程到达后要么在等待，要么在运行。如果是又有计算、又有I/O 操作的进程，其等待时间就是周转时间-运行时间-I/O操作的时间

平均周转时间=(7+9+8+11)/4=8.75

平均带权周转时间=(1+2.25+8+2.75)/4=3.5

平均等待时间=(0+5+7+7)/4=4.75

优点:公平、算法实现简单

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

是否会导致饥饿（饥饿表示某进程/作业长期得不到服务）：

不会

2.短作业优先（SJF）

最短的作业/进程优先得到服务(所谓“最短”，是指要求服务时间最短)。即追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间。

用于作业调度，也用于进程调度

即可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先(SPF,Shortest Process First)算法”

是否可抢占

SJF和SPF是非抢占式的算法。但是也有抢占式的版本一最短剩余时间优先算法(SRTN,Shortest Remaining Time Next)

非抢占的例子：

各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式的短作业优先调度算法（短进程优先调度算法（SPF）），计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

短作业/进程优先调度算法:每次调度时选择当前已到达且运行时间最短的作业/进程。因此，调度顺序为:P1->P3->P2->P4

对比FCFS算法的结果，显然SPF算法的平均等待/周转/带权周转时间都要更低

抢占的例子：

各进程到达就绪队列的时间、需要的运行时间如下表所示。使用抢占式的短作业优先调度算法（最短剩余时间优先算法(SRTN)）计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

如上图所示，P1运行了2个时间后，处理机就被P2抢占了，所以2时刻

P1剩余5个时间未运行--P1（5）

P2需要运行4个时间--P2（4）

其他同理，每个进程运行的具体时间如下图所示:

进而得到：

对比非抢占式的短作业优先算法，显然抢占式的这几个指标又要更低

注：

1.如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
2.很多书上都会说“SIF 调度算法的平均等待时间、平均周转时间最少”

严格来说，这个表述是错误的，不严谨的。

之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少

应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最小”

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

如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法(最短剩余时间优先,SRNT算法)的平均等待时间、平均周转时间最少”

3.虽然严格来说，SIF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法(如FCFS)3.SIF依然可以获得较少的平均等待时间、平均周转时间

优点:“最短的”平均等待时间、平均周转时间

缺点:不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

是否会导致饥饿

会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象。如果一直得不到服务，则称为"饿死"。

3.高响应比优先（HRRN）

对于之前讲的FCFS与SJF算法：

FCFS 算法是在每次调度的时候选择一个等待时间最长的作业(进程)为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。
SIF 算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。

能不能设计一个算法，即考虑到各个作业的等待时间，也能兼顾还行时间呢?这就是高响应比优先算法。

高响应比优先算法在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。综合考虑了作业/进程的等待时间和要求服务的时间。

响应比=等待时间+要求服务时间/要求服务时间

响应比>=1

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

是否可抢占

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。

例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

高响应比优先算法:非抢占式的调度算法，只有当前运行的进程主动放弃CPU时(正常/异常完成，或主动阻塞)，才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。

响应比=等待时间+要求服务时间/要求服务时间

因此每个进程运行的具体时间如下图所示:

优点：

综合考虑了等待时间和运行时间(要求服务时间)。

等待时间相同时，要求服务时间短的优先(SJF的优点)

要求服务时间相同时，等待时间长的优先(FCFS的优点)

对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题

是否会导致饥饿

不会

各种调度算法的总结如下：

注:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色。

接下来介绍适用于交互式系统的调度算法：

4.时间片轮转调度算法（RR）

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。这样就可以公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

一般由于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）

是否可抢占

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到

例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小分别是2、!5时的进程运行情况。

注：常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间。

时间片大小为2(注:以下括号内表示当前时刻就绪队列中的进程、进程的剩余运行时间)

0时刻（P1（5））：0时刻只有P1到达就绪队列，让P1上处理及运行一个时间片

2时刻（P2（4）-->P1（3））:

2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。此时P2排在队头，因此让P2上处理机。(注意:2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列，所以将P2排在前，P1排在后)

4时刻（P1(3)-->P3(1)-->P2(2)）:4时刻，P3到达，先插到就绪队尾，紧接着，P2下处理机也插到队尾，P1上处理机运行

5时刻(P3(1)→P2(2)→P4(6)):

5时刻，P4到达插到就绪队尾

注意:由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中

6时刻(P3(1)→P2(2)→P4(6)→P1(1)):

6时刻，P1时间片用完，下处理机，重新放回就绪队尾，P3上处理机，发生调度

7时刻(P2(2)→P4(6)→P1(1)):

虽然P3的时间片没用完，但是由于P3只需运行1个单位的时间，运行完了会主动放弃处理机，因此也会发生调度。队头进程P2上处理机。

9时刻(P4(6)-->P1(1)):

进程P2时间片用完，并刚好运行完，发生调度，P4上处理机

11时刻(P1(1)-->P4(4)):

P4时间片用完，重新回到就绪队列。

P1上处理机。

12时刻(P4(4)):

P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机

14时刻():就绪队列为空，因此让P4接着运行一个时间片。
16时刻:所有进程运行结束。

所以每个进程运行的具体实践如下：

若时间片为5

0时刻(P1(5)):只有P1到达，P1上处理机。

2时刻(P2(4)):P2到达，但P1时间片尚未结束，因此暂不调度

4时刻(P2(4)-->P3(1)):P3到达，但P1时间片尚未结束，因此暂不调度

5时刻(P2(4)-->P3(1)-->P4(6)):P4到达，同时，P1运行结束。发生调度，P2上处理机

9时刻(P3(1)-->P4(6)):P2运行结束，虽然时间片没用完，但是会主动放弃处理机。发生调度10时刻(P4(6)):P3运行结束，虽然时间片没用完，但是会主动放弃处理机。发生调度。

15时刻():P4时间片用完，但就绪队列为空，因此会让P4继续执行一个时间片。

16时刻():P4运行完，主动放弃处理机。所有进程运行完。

若按照先来先服务调度算法，我们可以发现，与时间片为5每个进程执行的时间是一样的。所以如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

注：一般来说，设计时间片时要让切换进程的开销占比不超过1%

优点：公平，响应快，适用于分时操作系统

缺点：由于高频率的进程切换，因此有一定开销;不区分任务的紧急程度。

是否会导致饥饿

不会，因为时间片轮转算法会按照各进程到达就绪队列的顺序，轮流让CPU为各个进程服务。

5.优先级调度算法

优先级调度算法会为每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程。随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序，这就可以使用优先级调度算法。

这个算法既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中

是否可抢占

抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

非抢占式：

例题:各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先优先级越高)级调度算法，分析进程运行情况。(注:优先数越大，优先级越高）

非抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

注:以下括号内表示当前处于就绪队列的进程

0时刻(P1):只有P1到达，P1上处理机。

7时刻(P2、P3、P4):P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机。

8时刻(P2、P4):P3完成，P2、P4优先级相同，由于P2先到达，因此P2优先上处理机

12时刻(P4):P2完成，就绪队列只剩P4，P4上处理机。

16时刻():P4完成，所有进程都结束

抢占式：

例题:各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用抢占式的优先级调度算法，分析进程运行情况。(注:优先数越大，优先级越高)

抢占式的优先级调度算法:每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。

注:以下括号内表示当前处于就绪队列的进程

0时刻(P1):只有P1到达，P1上处理机。

2时刻(P2):P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机。4时刻(P1、P3):P3到达，优先级比P2更高，P2回到就绪队列，P3抢占处理机。

5时刻(P1、P2、P4):P3完成，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机。
7时刻(P1、P4):P2完成，就绪队列只剩P1、P4，P4上处理机。

11时刻(P1):P4完成，P1上处理机

补充:就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置

根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种。

静态优先级:创建进程时确定，之后一直不变。

动态优先级:创建进程时有一个初始值，之后会根据情况动态地调整优先级。

如何合理地设置各类进程的优先级？

•系统进程优先级高于用户进程

前台进程优先级高于后台进程

操作系统更偏好 IO型进程(或称 //O繁忙型进程)

注:与I/O型进程相对的是计算型进程(或称CPU繁忙型进程)

也就是说：I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程优先运行的话，则越有可能让I/O设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。

如果采用的是动态优先级，什么时候应该调整?

可以从追求公平、提升资源利用率等角度考虑

如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级

如果某进程占用处理机运行了很长时间，则可适当降低其优先级

如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级

其实高响应比优先中的响应比就可以类比这里的优先级

优点:用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点:若源源不断地有高优先级进程到来，则可能导致饥饿。

是否会产生饥饿

会

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

FCFS算法的优点是公平。SJF 算法的优点是能尽快处理完短作业，平均等待/周转时间等参数很优秀。时间片轮转调度算法可以让各个进程得到及时的响应。优先级调度算法可以灵活地调整各种进程被服务的机会。能否对其他算法做个折中权衡?得到一个综合表现优秀平衡的算法呢?这就是多级反馈队列调度算法。

这个算法的规则如下：

1.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

2.新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾

3.只有第k级队列为空时，才会为k+1级队头的进程分配时间片

这个算法用于进程调度，不能用于作业调度

是否可抢占

抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用多级反馈队列调度算法，分析进程运行的过程。

设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。

流程如下：

1.0时刻，P1进程到达，放入第一级队列，P1被分配给处理机

但是第一级队列的时间片为1，所以P1进入下一级队列的队尾，并且P2到达第1级队列，如下图所示，由于第1级队列还没有处理完，所以不会处理P1，先处理P2

由于第1级队列时间片为1，所以P2处理时间为1，进入2级队列

由于第1级队列为空，所以可以处理第2级队列，由于P1在对头，所以P1被分配处理机

P1执行完后还剩余时间，所以P1进入下一个队列

由于还有进程在2级队列中，所以P2上处理机

在P2上处理机运行的时候，第5时间P3到达第1队列

此时因为有更高优先级的进程到达，所以此时会发生抢占处理机的情况，所以P2会被剥夺处理机，并且放回原来的队列，即2级队列，P3上处理机处理。

刚好P3运行时间为1，所以P3运行完后，就结束进程

接下来是P2进程上处理机处理，并且P2运行完2个时间后，结束进程了

高优先级的进程都运行完后，P1就可以上处理机处理，继续运行4个单元的时间，但是P1的运行时间还不足8，并且P1已经在最下面1级队列，所以P1只能被放到这一级队列的队尾，继续上处理机运行，P1完成，调出内存

各个进程运行时刻具体如下（括号内为各进程运行时间）：

多级反馈队列的优点:

1.对各类型进程相对公平(FCFS的优点);

2.每个新到达的进程都可以很快就得到响应(RR的优点);

3.短进程只用较少的时间就可完成(SPF的优点);

4.不必实现估计进程的运行时间(避免用户作假,即被识别为短进程但是其实本身为长进程)可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展:可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级)

是否会导致饥饿

会导致饥饿，若有源源不断的进程到达1级队列，并且都是短进程，在第1级队列就能被处理完，那么已经被降级为低优先级的进程就有可能长期得不到服务。

总结如下：

比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)