处理机调度

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

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

调度的三个层次

高级调度(作业调度)

在早期的多道批处理操作系统中，用户首先会通过外围机或者外围设备，将多道作业输入到磁盘或者硬盘的外存空间上，但是由于内存的地址空间是有限的，并不能将所有作业全部放在内存当中，会装不下，出现了资源不够的问题。

这种情况下，就需要调度来解决

image-20220908174809571

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。

​ 高级调度（作业调度）：按一定的原则从外存上处于后备队列的作业中挑选一个(或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。

​ 高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。

  • 调入的时机需要操作系统来确定
  • 调出的时机必然是作业运行结束才调出。

因此，高级调度主要是指调入的问题

中级调度（内存调度)

引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。
这么做的目的是为了提高内存利用率和系统吞吐量。

image-20220908210050565

暂时调到外存等待的进程状态为挂起状态。

值得注意的是：

  • PCB【进程控制块】并不会一起调到外存，而是会常驻内存。

    PCB中会记录进程数据在外存中的存放位置，进程状态等信息。

    操作系统还需要通过内存中的PCB来保持对各个进程的监控、管理。

    被挂起的进程PCB会被放到的挂起队列中。

  • 进程的程序代码数据相关的会调到外存。

中级调度（内存调度)：就是要决定将哪个处于挂起状态的进程重新调入内存。

七状态模型

除了之前五种状态，与挂起有关的还有两个状态：

  • 阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
  • 就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

image-20220908210529729

导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

  • 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
  • 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程；

挂起和阻塞的区别：

两种状态都是暂时不能获得CPU的服务

  • 挂起态是将进程映像调到外存去了

  • 阻塞态下进程映像还在内存中。

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

低级调度（进程调度）

进程调度是实现并发的基础。

低级调度（进程调度)，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。

进程调度的频率很高，一般几十毫秒一次。

image-20220908211420064

三层调度对比

在谁之间进行调度 针对谁 发生频率 对进程状态影响
高级调度 内存 和 外存【后备队列 –》 内存】 作业 最低 无–>创建态–>就绪态
中级调度 内存 和 外存【挂起队列 –》 内存】 进程 中等 挂起态 –> 就绪态/阻塞态
低级调度 内存 和 处理机CPU【就绪队列 –》 CPU】 进程 最高 就绪态 –> 运行态

进程调度的时机

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

那什么时候需要进程调度呢？分为以下两种情况：

  • 当前运行的进程主动放弃处理机
    • 程序运行结束 或 程序因为异常终止 【运行态 -> 结束态】
    • 进程主动请求进入阻塞（如：等等IO） 【运行态 -> 阻塞态】
  • 当前运行的进程被动放弃处理机
    • 分给进程的时间片用完了
    • 有更紧急的事需要处理（如 IO处理）
    • 有更高优先级的进程进入队列。

不能进行调度和切换的情况：

  • 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  • 进程在操作系统内核程序临界区中。
  • 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)

什么是操作系统内核程序临界区？

临界资源：一次仅允许一个进程使用的资源，各进程需要互斥地访问临界资源。例如：物理设备中的打印机、输入机和进程之间共享的变量、数据。

临界区：每个进程中，访问临界资源的那段代码。

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

为什么进程在操作系统内核程序临界区不能进程调度？

image-20220908214508621

如果还没退出临界区（还没解锁)就进行进程调度，但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此
又无法顺利进行进程调度。

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

进程在内核临界区 —–> CPU空闲 ——> 内核临届资源被占用 ——> 其他内核管理工作极可能受影响【比如进程切换】

如果此时进行进程调度，就极可能受到影响，所以不能进行进程调度。

为什么进程在操作系统程序【非内核】临界区可以进程调度？

比如，访问打印机。

image-20220908215122123

在打印机打印完成之前,进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲

进程在普通临界区 —–> CPU空闲 ——> 临界资源被占用 ——> CPU一直空闲。

如果不允许进程调度的话，CPU会一直空闲

进程调度方式

  • 非抢占式调度算法：

    挑选一个进程，然后让该进程运行直到被阻塞，或者直到该进程退出，才会调用另外一个进程。

    特点：实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统

  • 抢占式调度算法：

    当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

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

进程切换

进程切换的过程主要完成了:

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

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

调度算法

调度算法的评价指标：

CPU利用率：CPU处于忙碌的时间 占 总时间的比例。

吞吐量：单位时间内完成作业的数量 $系统吞吐量 = \frac{总共完成了多少道作业}{总共花了多少时间}$

周转时间：

先来先服务算法

主要从“公平”的角度考虑（类似于我们生活中排队买饭）

规则：按照作业/进程到达的先后顺序进行服务。

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

image-20220909140754844

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

是一种非抢占式的调度算法。

  • 优点：公平、算法实现简单

  • 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。

    FCFS算法对长作业有利，对短作业不利。

适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

不会导致进程饥饿。

最短作业优先算法

追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间

规则：优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

image-20220909141357885

最短作业优先算法默认是非抢占式的，但也有抢占式的。

抢占式的最短作业优先算法，也称“最短剩余时间优先算法”：

当有进程加入 –> 导致就绪队列改变 —> 然后需要进行调度。

如果新到达的进程剩余时间比当前运行的进程剩余时间更短

则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

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

  • 缺点：

    • 不公平。对短作业有利，对长作业不利。

    • 可能产生饥饿现象。

      一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。如果一直得不到服务，则称为”饿死“

    • 作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先

高响应比优先调度算法

综合考虑作业/进程的等待时间和要求服务的时间。

前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。

那么，高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。

「响应比优先级」的计算公式：
$$
优先级 = \frac{等待时间+要求服务时间}{要求服务时间}{(优先级\geq1)}
$$
每次进行进程调度时

  1. 先计算「响应比优先级」
  2. 然后把「响应比优先级」最高的进程投入运行

现实中，进程要求服务的时间是不可预估的。所以，高响应比优先调度算法是「理想型」的调度算法，现实中是实现不了的。

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

优点：

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

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

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

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

时间片轮转调度算法

按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。

若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

image-20220909145213669

是一种抢占式调度算法，

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

时间片的长度就是一个很关键的点：

  • 时间片设得太短：会导致过多的进程上下文切换，降低了 CPU 效率；
  • 时间片设得太长：使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

优先级调度算法

每个作业/进程有各自的优先级，调度时从就绪队列选择优先级最高的作业/进程。

进程的优先级可以分为，静态优先级和动态优先级：

  • 静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；

  • 动态优先级：

    根据进程的动态变化调整优先级

    比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

  • 非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
  • 抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

优点和缺点：

  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿

多级反馈队列调度算法

多级反馈队列（*Multilevel Feedback Queue*）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

  • 「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
  • 「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列；
image-20220909151926863

用一个例子来进行说明：

如下进程：

进程 到达时间 运行时间
P1 0 8
P2 1 4
P3 5 1

多级反馈队列

image-20220909152139158
  • 第一级就绪队列的时间片大小为1
  • 第二级就绪队列的时间片大小为2
  • 第三级就绪队列的时间片大小为4

0时刻

P1到达，先放入第一级队列，此时也没有别的进程，由于它在第一级队列，所以它被分配 1 个时间片。

image-20220909152420743

当过了 1 个时间的时候，P1的时间片用完了。所以它会进入下一级队列的队尾【第2级队列】

image-20220909152544695

1时刻

P2到达，进入第一级队列，P1执行完了，P2紧随其后。

image-20220909152731253

此时第 1 级队列不是空的，所以不会处理第2级队列的进程。因此这个时刻会调度P2这个进程，来进行处理。

image-20220909152912292

同样的，P2只运行一个单位时间的时间片。运行完后，会放入下一级队列的队尾。

image-20220909153027084

2时刻

没有进程到达，且第一级队列为空，所以才会处理第二级队列的进程。为第二级队列的队头【即P1】分配一个2个时间单位的时间片。

P1被处理机调度。

image-20220909153317696

P1执行两个单位时间的时间片后结束。P1的运行时间没有结束，还会放入下一级队列的队尾。

image-20220909153439751

4时刻

没有进程到达，第一级队列为空，第二级队列不为空，为第二级队列的队头分配一个2个时间单位的时间片。

image-20220909153616819

5时刻

P3进程到达，进入第一级队列。

image-20220909153851875

此时P3所在队列的优先级更高，P2还没有运行完，此时P2被剥夺处理机。

但是，P2的时间片还没有用完，它没有放入下一级队列，而是放回当前队列的队尾。P3被调度，分配一个单位的时间片。

image-20220909154328959

P3运行一个单位时间后，P3运行完成。然后被调出内存。

image-20220909154426952

6时刻

第一级队列为空，第二级队列的队头，被调度，P2继续运行，P2运行两个单位的时间片。【不是运行上次剩余的一个单位的时间片】

image-20220909155131054

然后，P2运行结束【总共运行了4个单位的时间片】，被调离内存。

image-20220909155233794

8时刻

此时，第1级队列 和 第二级队列 都是空的，此时调度第三级队列的队头元素【P1】。给P1分配 4 个单位时间的时间片。

image-20220909155357725

12时刻

P1,运行结束，但它所处的队列以及是最低级队列，没法再放入在低一级的了。所以，又放回第三级队列。

image-20220909155634897

然后只剩它一个了，再次被调度，分配 4 个单位时间的时间片。

用了一个单位时间就结束了。被调离内存。

规则

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

  2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片

    若用完时间片进程还未结束，则进程进入下一级队列队尾。

    若此时已经是在最下级的队列，则重新放回该队列队尾

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

  4. 抢占式的算法。

    在k级队列的进程运行过程中

    若更上级的队列(1 ~ k-1级）中进入了一个新进程

    则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。

对于短作业可能可以在第一级队列很快被处理完。

对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

但该算法，如果遇到有源源不断的短进程到达，会引起长进程的饥饿

__END__