处理机调度及常用的几个调度算法

以你之姓@ 2022-12-18 06:56 243阅读 0赞

## 调度的基本概念 ##

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是 **“调度”** 研究的问题。

调度分为 3 个层级：

*  作业调度：创建新的进程；
 *  内存调度：恢复旧的进程；
 *  进程调度：选择就绪进程；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center][]  
其中频率最高的进程调度是我们要重点研究的。

## 进程调度的时机、方式 ##

进程调度就是按照某种规则，从就绪队列中选择一个进程为其分配处理机。

那什么时候需要进行进程调度呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 1][]  
有些时候是不能进行进程调度的：

*  **中断**的时候；
 *  进程在操作系统**内核程序**临界区中，但是在普通临界区中是可以进行调度或者切换的；
 *  **原子**操作时；

**进程调度的方式**

分为非抢占式和抢占式

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 2][]

狭义的进程调度是指仅从就绪队列中选择一个进程这个步骤；而广义的进程调度还包括进程切换这一步骤。

> 进程调度、切换是有代价的，并不是频率越高并发度就越高。

## 调度算法 ##

**FCFS 算法**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 3][]  
`FCFS` 算法 是一种先来先服务的的算法，根据先后顺序依次执行，它是一种非抢占式的调度算法，相对来说比较公平。

但是存在一个问题，就是如果前面有一个大作业，后面跟着一个小作业，那么小作业的带权周转时间很大，用户体验会非常不好。

比如你去排队买奶茶，你只想买一杯奶茶，但是你前面有一个要买 `20` 杯，你就要等很长时间，用户体验很差。

所以 `FCFS` 算法对长作业比较有利，但对短作业不利，它有利于 `CPU` 繁忙型作业，不利于 `IO` 繁忙型作业；所谓 CPU 繁忙型作业，是指该类作业需要大量的 CPU 时间进行计算，而很少请求 IO 操作，IO 繁忙型作业是指 CPU 处理时，需要频繁的请求 IO 操作，所以 CPU 繁忙型作业更接近于长作业。

**SJF 算法**

即短作业优先算法，可用于进程调度，称为短进程优先算法，`SPF`，也是非抢占式算法，但是他们也有抢占式的版本：最短剩余时间算法 `SRTN`。

简单地说就一句话：每次调度时选择当前已到达且运行时间最短的作业。

同样是上面的那一道题，我们使用 `SJF` 算法来解决：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 4][]

--------------------

下面来分析一下抢占式的 **最短剩余时间算法**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 5][]  
该算法对长作业不利，因为长作业一直让着短作业，导致长作业可能永远没机会执行，形成 **饥饿** 现象； 但 SJF 算法的平均等待时间和平均周转时间都是最少的。

**高响应比优先算法**

这是一个非抢占式的算法，只有当前运行的作业主动放弃处理机时才需要调度，才需要计算响应比。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 6][]  
一般来说，进程优先级的设置使用以下规则：

*  系统进程 优先于 用户进程；
 *  交互型进程 优先于 非交互型进程；
 *  `IO 型进程` 优先于 计算型进程；

**时间片轮转调度算法**

主要适用于分时系统，即分配给进程时间片，时间到了就重新进入就绪队列，然后再轮流使用，其中时间片大小的选取很重要，如果时间片很大，那么就会退化成为先来先服务算法，如果时间片很小，频繁的切换处理机，开销很大。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/08e1cbb24b924be98c64ddef012ab7b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/c76fd4e1264f48378b6009ba05c5c04f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/0b955b3daf7146a68b32dd93737e0790.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221122/a0fe0d7f001a4ab1bf37b2bd54932f17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221122/ed98d4dc75a34e50aa469e16f033583e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221122/7322ef2c8bcc497a9182895abb4e2930.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221122/906c160aa79b4389a50d2e04db5409e9.png