Skip to content
Notes

2.2. 进程调度

2.2.1 处理机调度

1. 调度的基本概念

当有一堆任务要处理，但由于资源有限，无法同时处理。需要确定某种规则来决定处理这些任务的顺序，即“调度”要研究的问题。从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。

例如先到先服务，时间短优先服务等。

2. 调度的三个层次

2.1 高级调度（作业调度）

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

高级调度时外存与内存之间的调度，每个作业只调入一次，调出一次。 调入时建立对应 PCB，调出时撤销 PCB。 高级调度主要指作业调入的问题。

2.2 中级调度（内存调度）

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

暂时调到外存等待的进程状态为挂起状态。PCB 并不会一起调到外存，而是常驻内存，被放到挂起队列中。

中级调度就是要决定将哪个处于挂起状态的进程重新调入内存。可以被调入调出多次。

Note

挂起态进一步细分为就绪挂起态、阻塞挂起态。

“挂起”和“阻塞”都暂时不能获得 CPU 的服务，挂起态将进程映像调到外存中，阻塞态下进程映像还在内存中。

2.3 低级调度（进程调度）

按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是 OS 中最基本的一种调度。进程调度的频率很高一般几十毫秒一次。

要做什么调度发生在发生频率对进程状态的影响
高级调度
作业调度		按照某种规则，从后备队列中选择合适
的作业将其调入内存，并为其创建进程		外存→内存
（面向作业）		最低无→创建态→就绪态
中级调度
内存调度		按照某种规则，从挂起队列中选择合适
的进程将其数据调回内存		外存→内存
（面向进程）		中等挂起态→就绪态
（阻塞挂起→阻塞态）
低级调度
进程调度		按照某种规则，从就绪队列中选择一个
进程为其分配处理机		内存→CPU最高就绪态→运行态

2.2.2 进程调度的时机、切换与过程、方式

1. 进程调度的时机

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

  • 需要进行进程调度与切换的情况
    • 当前运行的进程主动放弃处理机
      • 进程正常终止
      • 运行过程中发生异常而终止
      • 进程主动请求阻塞（如等待 I/O）
    • 当前运行的进程被动放弃处理机
      • 分给进程的时间片用完
      • 有更紧急的事需要处理（如 I/O 中断）
      • 有更高优先级的进程进入就绪队列
  • 不能进行进程调度与切换的情况
    • 在处理中断的过程中
    • 进程在 OS 内核程序临界区中
      • 普通临界区可以调度
    • 在 原子操作（原语） 过程中

2. 进程调度的方式

2.1 非剥夺式调度方式（非抢占方式）

只允许进程主动放弃处理机，进入阻塞态。

实现简单，开销小，但无法处理紧急任务。

2.2 剥夺调度方式（抢占方式）

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

可以优先处理紧急的进程，也可以实现各进程按时间片轮流执行的功能。适合于分时操作系统、实时操作系统。

3. 进程的切换与过程

  • 狭义的进程调度
    • 指从就绪队列中选中一个要运行的进程。可以是刚刚暂停的进程，也可以是另一个，若是另一个则需要进程切换。
    • 进程切换指一个进程让出处理机，由另一个进程占用处理机的过程。
  • 广义的进程调度
    • 包含了选择一个进程和进程切换两个步骤

进程切换完成了

  • 对原来运行进程各种数据的保存
  • 对新的进程各种数据的恢复
    • 信息一般保存到 PCB 中

进程切换有代价，过于频繁的进行调度和切换，必然导致整个系统的效率降低。

2.2.3 调度算法评价标准

1. CPU 利用率

CPU 利用率指 CPU 忙碌的时间占总时间的比例。

CPU 利用率 = CPU 实际工作时间 ÷ 总时间

2. 系统吞吐量

单位时间内完成作业的数量。

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

3. 周转时间

指从作业被提交给系统开始到作业做完为止的时间。

包括四个部分

  • 作业在后备队列上等待作业调度（高级调度）的时间
  • 进程在就绪队列上等待进程调度（低级调度）的时间
  • 进程在 CPU 上执行的时间
  • 进程等待 I/O 操作完成的时间

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

带权周转时间 = 作业周转时间 ÷ 作业实际运行时间

带权周转时间越小，用户满意度越高。

4. 等待时间

指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

  • 进程等待时间
    • 进程建立后等待被服务的时间之和。在等待 I/O 完成的期间其实进程也在被服务，不计入等待时间
  • 作业等待时间
    • 建立进程后等待时间，作业在外存后备队列中等待的时间

5. 响应时间

指用户从首次提交到首次产生相应所用的时间

2.2.4 调度算法

考虑的方面
  1. 算法思想
  2. 算法规则
  3. 这种算法是用于【作业调度】还是【进程调度】
  4. 抢占式 or 非抢占式
  5. 优点和缺点
  6. 是否会导致饥饿

1. 先来先服务 FCFS

  1. 主要从“公平”的角度考虑
  2. 按照作业/进程到达的先后顺序进行服务
  3. 调度
    • 用于作业调度时，考虑哪个作业先到达后备队列
    • 用于进程调度时，考虑哪个进程先到达就绪队列
  4. 非抢占式
  5. 优劣
    • 优点：公平、算法实现简单
    • 缺点：对长作业有利，对短作业不利
  6. 不会导致饥饿

2. 短作业优先 SJF

  1. 追求最少的平均等待时间，最少的平均周转时间。最少的平均带权周转时间
  2. 最短作业/进程优先得到服务
  3. 可用于作业调度，也可用于进程调度。用于进程调度时称为“短进程优先 SPF”算法
  4. SJF 和 SPF 时非抢占式。但也有抢占式版本——最短剩余时间优先算法 SRTN
  5. 优劣
    • 优点：“最短的”平均等待时间、平均周转时间
    • 缺点：对短作业有利，对长作业不利
  6. 可能导致饥饿

3. 高响应比优先 HRRF

  1. 综合考虑作业/进程的等待时间和要求服务的时间
  2. 在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务，响应比 = (等待时间 + 要求服务时间) ÷ 要求服务时间
  3. 可用于作业/进程调度
  4. 非抢占式。只有当前运行的作业/进程主动放弃处理机，才需要调度，需要计算响应比
  5. 优点
    • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
    • 要求服务时间相同时，等待时间长的优先（FCFS 的优点）
  6. 不会导致饥饿

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

  1. 公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都能得到响应
  2. 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片
  3. 用于进程调度（只有作业放入内存建立相应进程后才能被分配处理机时间片）
  4. 抢占式，由时钟装置发出时钟中断来通知 CPU 时间片已到
    • 公平，响应快，适用于分时操作系统
    • 如果时间片太大，会退化为 FCFS，并且会增大进程响应时间
    • 如果时间片太小，导致进程切换过于频繁，系统花费大量时间来处理进程切换
  6. 不会导致饥饿

5. 优先级调度算法

  1. 需要根据任务的紧急程度来决定处理顺序
  2. 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
  3. 可以用于作业/进程调度，还会用于 I/O 调度
  4. 抢占式（就绪队列变化时检查）/非抢占式（进程主动放弃）
  5. 用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活的调整各种作业/进程的偏好程度
  6. 若源源不断地有高优先级进程到来，可能导致饥饿
Note

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

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

通常

  • 系统进程优先级高于用户进程
  • 前台进程优先级高于后台进程
  • OS 更偏好 I/O 型进程（或称 I/O 繁忙型进程）
    • I/O 设备和 CPU 可以并行工作，可以通过方法使资源利用率、系统吞吐量提升

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

  1. 对其他调度算法的折中权衡
  2. 算法见下表
  3. 用于进程调度
  4. 抢占式
  5. 对各类进程相对公平；每个新到达的进程都可以很快得到响应；短进程只用较少的时间；不必实现估计进程的运行时间；灵活的调整对各类进程的偏好程度（例如 CPU 密集型进程，I/O 密集型进程）
  6. 会造成饥饿
算法
  • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  • 新进程到达时先进入第一级队列，按 FCFS 排队等待被分配时间片。若用还时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级队列，则重新放回最下级队尾
  • 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
  • 被抢占处理机的进程重新放回原队列队尾

P1(1)→P2(1)→P1(2)→P2(1)→P3(1)→P2(2)→P1(4)→P1(1)P_1(1)\rightarrow P_2(1)\rightarrow P_1(2)\rightarrow P_2(1)\rightarrow P_3(1)\rightarrow P_2(2)\rightarrow P_1(4)\rightarrow P_1(1)

2.2.5. 进程切换

对于通常的进程而言，其创建、撤销及要求由系统设备完成的 I/O 操作，都是利用系统调用而进入内核，再由内核中的相应处理程序予以完成的。进程切换同样是在内核支持下实现的，因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。

上下文切换

切换 CPU 到另一个进程需要保存当前进程状态并恢复另一个进程的状态，这个任务称为上下文切换。上下文是指某一时刻 CPU 寄存器和程序计数器的内容。进行上下文切换时，内核会将旧进程状态保存在其 PCB 中，然后加载经调度而要执行的新进程的上下文。

实质上是处理机从一个进程的运行转到另一个进程运行，这一过程中，运行环境发生了实质性的变化，流程如下：

  1. 挂起一个进程，保存 CPU 上下文，包括程序计数器和其他寄存器
  2. 更新 PCB 信息
  3. 把进程的 PCB 移入相应的队列，如就绪、在某事件阻塞等队列
  4. 选择另一个进程执行，并更新其 PCB
  5. 跳转到新进程 PCB 中的程序计数器所指向的位置执行
  6. 恢复处理机上下文

上下文切换的消耗

上下文切换通常是计算密集型的，即它需要相当可观的 CPU 时间，在每秒几十上百次切换中，每次切换都需要纳秒量级的时间，所以上下文切换对系统来说意味着消耗大量的 CPU 时间。有些处理器提供多个寄存器组，上下文切换只需简单地改变当前寄存器组的指针。

上下文切换与模式切换

模式切换与上下文切换是不同的，模式切换时，CPU 逻辑上可能还在执行同一进程。用户进程最开始都运行在用户态，若进程因中断或异常进入核心态运行，执行完后又回到用户态刚被中断的进程运行。

用户态和内核态之间的切换称为模式切换，而不是上下文切换，因为没有改变当前的进程。上下文切换只能发生在内核态，它是多任务操作系统中的一个必需的特性。