OS 进程调度

当多个进程在系统并发执行时，所有进程共享 CPU。当某一 CPU 上运行的进程因阻塞和进程运行结束而使 CPU 可以分配给其它进程使用时，如何从众多就绪的可运行进程中选择一个进程，将 CPU 分配给该进程，使系统有效运行，是多任务操作系统需要解决的问题。

进程调度的功能和时机

进程调度的功能

进程调度的功能是按照某种策略和算法从就绪态进程中为当前空闲的 CPU 选择在其上运行的新进程。

进程调度的时机

当一个进程运行结束、进程阻塞、中断返回、在支持抢占式调度的系统中有比当前运行进程优先级更高的进程到来、当前运行进程的时间片用完时，系统都会通过执行进程调度程序重新进行进程调度。

进程调度算法

选择调度方式和算法的若干准则

• 周转时间短。

周转时间：指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

• 响应时间快。
• 截止时间有保证。
• 系统吞吐量高。
• 处理机利用率好。

调度算法

1. 先来先服务调度算法（FCFS - First Come First Served）

调度算法：FCFS 就是从就绪队列的队首选择最先到达就绪队列的进程，为该进程分配 CPU。

性能分析：FCFS 适合 长 进程，不利于 短 进程，短进程等待时间相对运行时间而言太长。

假设有 3 个进程 p1、p2、p3 分别在 0、1、2 时刻进入系统，需要的运行时长分别为 24、3、3，如果按 FCFS 调度算法，3 个进程的等待时间和周转时间如下表所示：

• 系统的平均周转时间：T=(24+26+28)/3=26
• 平均的带权周转时间：T=(24/24+26/3+28/3)≈6.33

2. 短进程优先调度算法（SPF - Shortest Process First）

调度算法：SPF 是从就绪队列中选择估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行完成，或发生某事件而被阻塞放弃处理机时，再重新调度。

算法优点：有效降低进程的平均等待时间，提高系统的吞吐量。

算法缺点：

• 对长进程不利。如果系统中不断有短进程到来，长进程可能长时间得不到调度。
• 不能保证紧迫进程的及时处理，因为该算法不考虑进程的紧迫程度。
• 进程的长短根据用户的估计而定，故不一定能真正做到短进程优先。

假设有 3 个进程 p3、p2、p1 分别在 0、1、2 时刻进入系统，需要的运行时长分别为 24、3、3，如果按 SPF 调度算法，3 个进程的等待时间和周转时间如下表所示：

• 周转时间=服务时间+等待时间。
• 开始运行时间=上一次开始运行时间+上一次服务时间。
• 等待时间=开始运行时间-进入系统时间。

或者

• 系统的平均周转时间：T=(3+5+28)/3=12
• 平均的带权周转时间：T=()≈6.33

1. 优先权调度算法（Priority Scheduling Algorithm）

调度算法：每个进程都有一个与之关联的优先权。优先权值通常是固定区间的数字（如：0~127）。

优先权调度算法的类型：

• 非抢占式（Nonpreemptive）优先权调度算法：
• 抢占式（Preemptive）优先权调度算法：

优先权的类型：

• 静态优先权：在进程创建时刻确定，在进程的整个运行期间保持不变。
• 动态优先权：在进程创建时被赋予优先权，随进程的推进或随其等待时间的增加而改变。

优先权调度算法存在的问题和解决方案：

• 存在问题：无穷阻塞，或称为饥饿（Starving）问题。
• 解决方案：老化（Aging）技术，以逐渐增加在系统中等待时间很长的进程的优先权，使低优先权进程在等待时间很长的情况下，优先权变高而获得 CPU 的执行。

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

时间片轮转调度算法是现代分时系统中广泛使用的进程调度算法，Unix、Linux 和 Windows 操作系统都采用基于时间片轮转、支持优先权和抢占式调度的混合式进程调度算法。

5. 多级队列调度算法（Multilevel Queue Scheduling）

多级队列调度算法将就绪队列分成多个独立队列，根据进程的某些属性，如需要占用的存在大小、进程优先权或进程类型，进程会被永久地分配到一个队列。每个队列有自己的调度算法。不同的队列优先权不同，调度算法也可能不同。

对于低优先权的进程会存在无穷阻塞（饥饿）问题，而多级反馈队列调度算法可以弥补这些不足。

6. 多级反馈队列调度（Multilevel Feedback Queue Scheduling）

多级反馈队列调度算法的设计需要考虑的几个方面的问题：

• 就绪队列的数量。
• 根据进程优先权确定进程应该进入哪个就绪队列的算法。
• 用以确定进程何时转移到较高优先权队列的算法。
• 用以确定进程何时转移到较低优先权队列的算法。
• 用以确定进程在需要服务时应该进入哪个队列的算法。

实时系统中的调度

常用的几种实时调度算法

1. 最早截止时间优先算法（EDF - Earliest Deadline First）。
2. 最低松弛度优先算法（LLF - Least Laxity First）。

松弛度：来用表示一个实时进程的紧迫程度。如果一个进程的完成截止时间为 T，当前时间为 T_c，处理完该任务还需要的时间为 T_s，则松弛度 L 的计算式表示为：L=T-T_c-T_s。

假设在一个实时系统中，有两个周期性实时进程 A 和 B，要求进程 A 每 20ms 执行一次，执行时间为 10ms。要求进程 B 每 50ms 执行一次，执行时间为 25ms。由此可知进程 A 和 B 每次必须完成的时间分别为：A1、A2、A3… 和 B1、B2、B3…，如下图所示：

1
2
3
4
5
6
7
8

    A1        A2        A3        A4        A5        A6        A7        A8
    |         |         |         |         |         |         |         |
    |         |         |         |         |         |         |         |
----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----+----> t
         20        40   |    60        80        100       120       140  |    160
                        |                        |                        |
                        |                        |                        |
                        B1                       B2                       B3

对进程 A 和进程 B 采用最低松弛度优先算法，保证两个进程在每个周期都能执行一次。

采用最低松弛度优先算法的调度时机和调度过程如下图，图中 A1、A2、A3、A4 分别表示进程 A 在第一、二、三、四个周期内的一次连续执行时间，B1、B2 分别表示进程 B 在第一、二个周期内的一次连续执行时间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

  A1(10)                       A2(10)          A3(10)                   A4(10)
+--------+                   +---------+    +---------+              +---------+
|        |                   |         |    |         |              |         |
|        |                   |         |    |         |              |         |
T1       T2                  T3        T4   T5        T6             T7        T8
---------+---------+---------+---------+----+----+----+----+---------+---------+---------> t
         10        20        30        40   |    50   |    60        70        80
         |                   |         |    |         |              |         |
         |                   |         |    |         |              |         |
         +-------------------+         +----+         +--------------+         +----------
                 B1(20)                 B1(5)              B2(15)                 B2(10)

上图的调度过程如下：

进程切换

进程切换的步骤：

1. 保存包括程序计数器和其它寄存器在内的 CPU 上下文环境。
2. 更新被替换进程的进程控制块。
3. 修改进程状态，把执行态改为就绪态或者阻塞态。
4. 将被替换进程的进程控制块移到就绪队列或阻塞队列。
5. 执行通过进程调度程序选择的新进程，并更新该进程的进程控制块。
6. 更新内存管理的数据结构。
7. 恢复被调度程序选中的进程的硬件上下文。

多处理器调度

多处理器系统的类型

1. 紧密耦合的多处理器系统和松弛耦合的多处理器系统。

• 紧密耦合的多处理器系统通常通过高速总线或调整交叉开关实现多个处理器之间的互连，它们共享主存储器系统和 IO 设备，并要求将主存储器划分为若干个独立访问的存储器模块，以便多个处理器能同时对主存进程访问。
• 松弛耦合的多处理器系统通常通过通道或通信线路来实现多台计算机之间的互连。每台计算机都有自己的存储器和 IO 设备，并配置了操作系统来管理本地资源和在本地运行的进程。因此，每一台计算机都能独立工作。

2. 对称多处理器系统和非对称多处理器系统：只有一个主处理器，有多个从处理器。

多处理器系统中的进程分配方式

1. 对称多处理器系统中的进程分配方式。
2. 非对称多处理器系统中的进程分配方式。

进程调度方式

1. 自调度。
2. 成组调度。
3. 专用处理器分配。

死锁

产生死锁的主要原因和必要条件

1. 死锁产生的主要原因：竞争共享资源且分配资源的顺序不当。

2. 死锁产生的必要条件：

注意：只有当以下 4 个条件同时满足时才会发生死锁。

• 互斥条件。
• 请求和保持条件。
• 不剥夺条件。
• 环路等待条件。

处理死锁的基本方法

1. 死锁的预防。
2. 死锁的避免。

银行家算法

1965 年 Dijkstra 提出了一种能够避免死锁的资源分配算法。其思想是一个进程提出资源请求后，系统先进行资源的试分配。然后检测本次的试分配是否使系统处理安全状态，若安全则按试分配方案分配资源，否则不分配资源。

1. 数据结构。

• available[] 是一个一维数组。表示系统中某种资源的可用数量，也就是这种资源可分配的数量。
• max[] 是一个 n*m 的二维数组。表示各进程需要各类资源的最大数量。
• allocation[] 是二维数组。表示某时刻已分配给进程的某类资源数。
• need[] 是二维数组。表示某个进程还需要某类资源的数量。

2. 算法说明。

银行家算法分为两个过程：一是进行资源的试分配过程；二是对试分配后系统的状态做安全性检测的过程。经过安全性检测，若试分配后系统安全状态是安全的，则分配资源。若不安全，则阻塞申请资源的进程，暂不为它分配资源。

资源试分配算法：

安全性检测算法：安全性检测算法用来判断系统的资源分配状态是否安全。

1. 实例。

假设系统中有 5 个进程 p0、p1、p2、p3、p4，有 3 种类型的资源 A、B 和 C。A 类资源有 10 个，B 类资源有 5 个，C 类资源有 7 个。假定在 T0 时刻，系统的资源分配状态如表所示：

在 T0 时刻，可以找到一个安全序列 <p1,p3,p4,p0>，系统在 T0 时刻处于安全状态。

若此时进程 pi 提出资源请求 request_i = (1,0,2)，通过银行家算法，先进行资源试分配，然后检测试分配后系统在 T1 时刻的状态是否安全。

• 对 p1 的请求进行试分配：T0 时刻 request_i = (1,0,2)，available = (3,3,2)，need_i = (1,2,2) 可见满足 request_i <= need_i 并且 request_i <= available。所以进行进一步试分配。

死锁的检测和解除

1. 何时调用检测算法。

取决于两个因素：一是死锁可能发生的频率；二是当死锁发生时受影响的进程数量。

2. 资源分配图。

3. 死锁定理。

定理作用：用于检测系统所处的资源分配状态 S 是否为死锁状态。

死锁定理：S 为死锁状态的 充分条件 是当且仅当 S 状态的资源分配图是不可完全简化的。

4. 死锁的解除。

解除死锁的途径：一是终止处于死锁的进程；二是抢占死锁进程占有的资源。

进程终止：

• 终止所有死锁进程。
• 一次只终止一个处于死锁的进程，直到死锁解除。

资源抢占：逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。

抢占来处理死锁，需要处理三个问题：

• 抢占哪个进程和哪些资源。
• 回滚。
• 饥饿：进程因长时间不能获得所需要的资源而无限等待的状态。