【操作系统】进程调度（低级调度）

客官°小女子只卖身不卖艺 2022-07-14 07:07 631阅读 0赞

# 进程调度的任务和机制 #

进程调度任务

*  保存处理机的现场信息
 *  按某种算法选取进程
 *  把处理器分配给进程

进程调度机制

![图解][20161201131136833]

# 进程调度方式 #

## 非抢占方式 ##

一旦把处理机分配给某进程，就让它一直运行下去，直至该进程完成或阻塞时，才把处理机分配给其它进程。

*  优点：是实现简单、系统开销小。
 *  缺点：但它不能用于分时系统和大多数实时系统。

## 抢占方式 ##

允许调度程序根据某种原则，将已分配给该进程的处理机，重新分配给另一进程。

“抢占”必须遵循的原则：

*  优先权原则
 *  短进程优先原则
 *  时间片原则

# 最短剩余时间调度算法（SRT） #

最短剩余时间调度算法(Shortest Remaining Time First,SRT) 是针对SPF 增加了抢占机制的一种调度算法。

它总是选择预期剩余时间最短的进程。只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程。

![注][20161201133031350]

![示例][20161201133045295]

SRT 不像 FCFS 偏向长进程，也不像轮转法（下个算法）产生额外的中断，从而减少了开销。

就此例而言，平均周转时间和带权平均周转时间说明了SRT 好于前面的任何一个算法（因为它具有抢占的特点） 。

![图解][20161201133210202]

缺点：必须记录过去的服务时间，从而增加了开销。

## 例题 ##

有如下四个进程，它们的到达时间和服务时间如下表所示，请分别计算在采用 FCFS、SPF 非抢占、SRT三种调度算法时的平均周转时间和平均等待时间。

![图解][20161201133433718]

![例题][20161201133509919]

![图解][20161201133547357]

![图解][20161201133613610]

SPF、SRT 与 FCFS 的比较

![图解][20161201133705313]

# 时间片轮转调度算法 (Round Robin, RR) #

时间片轮转调度算法：系统将所有就绪进程按FCFS的原则，排成一个队列依次调度，把 CPU 分配给队首进程，并令其执行一个时间片，通常为 10-100ms。时间片用完后，系统的计时器发出时钟中断，该进程将被剥  
夺 CPU并插入就绪队列末尾。

RR 是一种非常公平的算法。

进程切换时机

*  若一个时间片尚未用完进程便已经完成，就立即再调度就绪队列中队首进程运行，并启动一个新的时间片。
 *  如果在一个时间片用完时进程尚未运行完毕，则剥夺CPU，调度程序把它送往就绪队列的末尾。
    
    > 响应时间T = 时间片q × 就绪队列进程数n

例：一个分时 OS，10 个终端，时间片 100ms，每个用户的请求进程要 300ms 的时间处理，问终端用户提出二次请求的时间间隔最少是多少？

解：响应时间＝ 100ms×10 ＝ 1s，每个用户的请求要获得 3 个时间片才能处理完，要轮转 3 次，才能都处理完，所以终端用户的二次请求时间间隔最少应为 2.1∼3s。

时间片轮转调度算法保证了就绪队列中的所有进程在给定的时间内，均能获得一个时间片来执行，即系统在给定的时间内，可以响应所有用户的请求。

时间片的长短对系统性能有很大影响：

*  调度算法（时间片应该使大多数进程可以在一个时间片内完成。但是如果太长，则退化为 FCFS。 ）
 *  系统开销（太短，中断、上下文切换频繁）
 *  平均周转时间

时间片轮转调度算法的平均周转时间比 SPF 长，但响应时间要短一些。

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

## 例如 ##

![图解][20161201134546918]

![图解][20161201134611864]

# 优先级调度算法 #

优先级调度算法的类型

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

一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统  
方可将处理机重新分配给另一优先级最高的进程。

非抢占优先级调度算法 (设优先数越小优先级越高)

![图解][20161201135318444]

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

只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。

抢占式优先级调度算法 (设优先数越小优先级越高)

![图解][20161201135402476]

# 各种调度算法的比较 #

![图解][20161201135439898]

# 多级队列调度算法 #

SJF、SRT 都需要知道进程的运行时间，有局限性。

如果没有关于各个进程相对长度的任何信息，则可以用已经执行的时间进行衡量。

多级队列调度算法（MQ-Multilevel Queue）

根据作业的性质或类型，把就绪队列划分成若干个独立的队列，每个作业固定地分属一个队列。不同的队列可以采用不同的调度算法。

## 多级反馈队列调度算法 MFQ ##

多级反馈队列调度算法

*  是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间。
 *  FCFS + 优先级 + RR + 抢占
 *  多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。

## 多级反馈队列调度算法调度机制 ##

*  设置多个就绪队列，并为每个队列赋予不同的优先级。队列 1 的优先级最高，其余队列逐个降低。
 *  每个队列中进程执行时间片的大小各不相同，进程所在队列的优先级越高，其相应的时间片就越短。
 *  新进程进入系统时，先放入队列 1 的末尾，按FCFS等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列 2 的末尾，按 FCFS 再次等待调度，如此下去，最后进入队列 n 按RR算法调度执行。
 *  仅当队列 1 为空时，才调度队列 2 中的进程运行。若一个队列中的进程正执行，此时有新进程进入高级队列，则新进程抢占运行，原进程转移至本队列队尾。

![图解][20161201135942963]

## 多级反馈队列调度算法的优点 ##

*  短作业优先处理。运行时间短的进程在经过前面几个队列之后便可以执行完毕。
 *  设备资源利用率高。I/O 繁忙类型的进程可能经常会由于所申请的资源被占用或启动了 I/O 传输的原因而进入等待状态。当进程得到所等待的资源或 I/O 传输完成时，它将进入第一级就绪队列，尽快获得处理机并使用  
    资源。
 *  系统开销小。因为运行时间长的进程最后会进入低优先级的队列，这些队列的时间片较长，因而进程的调度频率较低。

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

以上介绍的调度算法只是保证一些进程（或作业）可以优先运行（如优先级算法） ，但是不能保证占用处理机的时间。另外也没有考虑调度的公平性。

## 保证调度算法 ##

保证处理机分配的公平性。如果 n 个进程同时运行，公平的情况下每进程应该获得处理机时间的 1/n。

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

## 公平分享调度算法 ##

针对用户而不是进程，使得每用户获得相同的处理机时间。

*  时间片轮转算法让每个进程轮流运行一个时间片，对进程很公平，但如果每个用户拥有的进程数不同，则可能对用户不公平。
 *  公平分享调度算法调度的公平性主要是针对用户而不是进程，目标是使所有用户能获得相同的处理机时间。
 *  调度是以进程为基本单位的，所以必须考虑到每一个用户所拥有的进程数目。
 *  例如，用户 1 有 4 个进程 A、B、C、D，用户 2 只有一个进程 X。为保证两个用户能获得相同的处理机时间，需要强制执行如下的调度顺序：  
    A X B X C X D X A X ···

[20161201131136833]: /images/20220714/2087d2a1560c4e119cf45008fc63e28d.png
[20161201133031350]: /images/20220714/c5f4b352d1ee4f8b9b279ef0d3e66380.png
[20161201133045295]: /images/20220714/aaa4c0aadc3845ceb592ac1fc0576997.png
[20161201133210202]: /images/20220714/cb8fbf9d83354f3dbf59bcfdac92d761.png
[20161201133433718]: /images/20220714/e4c3fb71c0344ac2a44c589f8a0517e8.png
[20161201133509919]: /images/20220714/8f09d5ac3f8842d09622e4e9afa7231e.png
[20161201133547357]: /images/20220714/04ecd12e96234b9d9437717addb83982.png
[20161201133613610]: /images/20220714/d84b3727cc1c49f3b4c0aafdcd10bef3.png
[20161201133705313]: /images/20220714/3be5a71893a44329a90e6c9c9c0b1e33.png
[20161201134546918]: /images/20220714/58378d48c05e4afe9c77187c5b3069c6.png
[20161201134611864]: /images/20220714/a8adbfb6aa904615a8a60e4cc65871f0.png
[20161201135318444]: /images/20220714/0a444ce1bd034fdb8b32c2992a03c26a.png
[20161201135402476]: /images/20220714/f2c59f28dd404b5a892f79990715c120.png
[20161201135439898]: /images/20220714/c2bc25becf36445782531b6bd7b8d604.png
[20161201135942963]: /images/20220714/61533d8727d14473ad1140e7bcba80e9.png