进程调度算法

调度的基本概念

在多道程序系统中，进程的数量往往多于处理机的个数，因此进程争用处理机的情况在所难免。处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效）选择一个进程并将处理机分配给它运行，以实现进程并发执行。

在 Linux 中，有多种进程调度算法，以下是一些常见的调度算法：

先来先服务（FCFS，First - Come - First - Served）

基本原理：按照进程到达就绪队列的先后顺序来分配 CPU。先进入就绪队列的进程先获得 CPU 资源，直到它完成或者因为等待 I/O 等原因主动放弃 CPU。

示例：假设有进程 P1、P2 和 P3，它们到达就绪队列的时间分别是 0 时刻、1 时刻和 3 时刻。如果采用 FCFS 算法，那么 P1 先获得 CPU，当 P1 执行完或者阻塞后，P2 才能获得 CPU，接着是 P3。

优点：简单，易于理解和实现。

缺点：没有考虑进程的执行时间等因素，可能会导致短进程等待长进程的情况，平均周转时间可能较长。比如，如果一个长进程先到达，后面的短进程就需要等待很长时间才能执行。

常见使用场景： 批处理系统中的简单任务序列；打印机等独占设备的任务排队；简单的人工操作流程；

短作业优先（SJF，Short - Job - First）

基本原理：优先调度估计运行时间最短的进程。它可以分为非抢占式 SJF 和抢占式 SJF（也称为最短剩余时间优先，SRTF）。非抢占式 SJF 是当一个新进程进入就绪队列时，只有当前运行进程结束后，才会比较新进程和就绪队列中其他进程的运行时间，选择最短的运行；而抢占式 SRTF 会在新进程的剩余运行时间比当前正在运行的进程的剩余运行时间更短时，抢占 CPU。

示例：有进程 P1（估计运行时间为 5 个单位时间）、P2（3 个单位时间）和 P3（4 个单位时间）。如果是非抢占式 SJF，且 P1 先到达，当 P1 执行完后，会选择 P2 执行；如果是抢占式 SRTF，假设 P1 先执行了 2 个单位时间，此时 P2 到达，由于 P2 的剩余时间（3 个单位时间）小于 P1 的剩余时间（3 个单位时间），P2 会抢占 CPU。

优点：相比 FCFS，它能有效降低平均周转时间，提高系统的吞吐量，因为短进程可以更快地完成。

缺点：难以准确预估进程的运行时间。而且长进程可能会出现饥饿现象，即长进程因为不断有短进程进入而长时间得不到执行。

常见使用场景：分时系统中的短任务处理；数据处理中心的小数据量任务；小型服务器的日常请求处理

总的来说，短作业优先算法适用于存在大量不同执行时长任务的场景，尤其在短任务占比较大且对响应速度要求较高的情况下，能够有效提高系统对这些短任务的处理效率，提升整体性能和用户体验。

时间片轮转（RR，Round - Robin）

1、时间片轮转的基本概念

• 时间片轮转（Round - Robin，RR）是一种基于时间片的进程调度算法。其核心思想是将 CPU 的处理时间划分为一个个固定长度的时间片，所有就绪进程按照顺序轮流在 CPU 上运行一个时间片的时间。
• 例如，假设有 3 个就绪进程 P1、P2 和 P3，系统设定的时间片为 20 毫秒（ms）。开始时，P1 先获得 CPU 并运行 20ms，20ms 一到，无论 P1 是否完成任务，都会被操作系统暂停，将其放回就绪队列的末尾。然后调度程序会选择就绪队列中的下一个进程 P2，让 P2 运行 20ms，之后再暂停 P2 并将其放回队列末尾，接着是 P3 运行 20ms，如此循环往复。

2、时间片大小的重要性

• 时间片过小的情况
  • 当时间片设置得过小时，会导致频繁的进程上下文切换。进程上下文切换是指 CPU 从一个进程的执行环境切换到另一个进程的执行环境所需要的操作，包括保存当前进程的状态（如程序计数器、寄存器内容等）和恢复下一个进程的状态。
  • 例如，假设时间片为 1ms，对于一个简单的计算任务，进程可能刚加载数据到寄存器，还没来得及进行有效计算，时间片就用完了，然后就需要进行上下文切换。这种频繁的切换会增加系统的开销，因为上下文切换需要消耗 CPU 时间和内存资源，降低了系统的整体性能。
• 时间片过大的情况
  • 如果时间片设置得太大，就会退化成先来先服务（FCFS）算法。例如，如果时间片设置为比大多数进程的执行时间都长，那么每个进程在获得 CPU 后基本上都能完成自己的任务，就如同按照进程到达的先后顺序来执行一样。
  • 比如，有一些进程的执行时间大多在 100ms 左右，而时间片设置为 200ms，那么第一个获得 CPU 的进程很可能在这个时间片内就完成了任务，和 FCFS 的执行效果类似，不能很好地体现公平性和分时性。

3、时间片轮转的适用场景

• 时间片轮转算法主要适用于分时操作系统。在分时系统中，多个用户通过终端同时使用计算机系统，每个用户的进程都需要在短时间内获得 CPU 资源，以保证用户的交互体验。
• 例如，在一个多用户的服务器环境中，多个用户通过远程终端连接到服务器，运行自己的程序。时间片轮转算法可以让每个用户的进程都能快速地获得 CPU 服务，使用户感觉自己独占了计算机系统，不会因为某个进程长时间占用 CPU 而导致其他用户的进程无法执行。

4、时间片轮转与其他调度算法的比较

• 与先来先服务（FCFS）算法相比，时间片轮转更加公平。FCFS 是按照进程到达的先后顺序执行，一旦一个长进程先到达并开始执行，后面的进程就需要等待很长时间才能获得 CPU。而时间片轮转可以让每个进程都有机会在较短时间内运行。
• 与短作业优先（SJF）算法相比，时间片轮转不依赖于对进程执行时间的预估。SJF 需要知道进程的执行时间来优先调度短进程，但在实际系统中，准确预估进程执行时间是比较困难的。时间片轮转不需要这种预估，它只是按照固定的时间片轮流执行进程。

5、特点

1. 时间片划分机制保证响应及时性
   • 分时操作系统将 CPU 时间划分成很小的时间片。例如，通常时间片长度在 10 - 100 毫秒之间。当多个用户同时请求资源时，系统会按照顺序为每个用户分配时间片。
   • 假设用户 A、B、C 同时请求资源，系统可能先给用户 A 分配一个时间片。在这个时间片内，A 的程序开始执行相关操作。由于时间片长度相对较短，在经过几个时间片的轮转后，每个用户的请求都能很快地得到处理。即使每个用户的程序执行过程可能被频繁中断（时间片用完时），但由于 CPU 速度很快，用户几乎感觉不到这种中断，并且能在较短时间内看到自己请求的响应结果。
2. 高效的进程切换机制
   • 分时操作系统有高效的进程切换机制。当一个用户的时间片用完后，操作系统会快速地保存当前进程（用户程序）的状态。这个状态包括程序计数器（记录程序执行到哪里）、寄存器内容（存储临时数据）、内存中的数据等。
   • 例如，当用户 A 的时间片结束时，操作系统会将 A 程序的这些状态信息保存到特定的内存区域（如进程控制块）。然后，系统会快速地恢复下一个用户（如用户 B）程序的状态，使 B 的程序可以在之前中断的地方继续执行。这种快速的切换使得系统能够在多个用户之间快速地分配 CPU 时间，保证每个用户的请求都能及时得到处理。
3. 优先级和缓冲机制辅助响应
   • 有些分时操作系统会设置优先级。对于一些比较紧急的用户请求（如系统管理员的操作或者涉及系统关键功能的操作），可以赋予较高的优先级。这样，当这些高优先级请求和普通请求同时存在时，高优先级请求会先得到处理。
   • 同时，系统也可能采用缓冲机制。例如，对于用户的输入操作（如键盘输入），系统会先将这些输入存储在缓冲区。当轮到该用户程序的时间片时，就可以直接从缓冲区获取输入信息并进行处理，而不是等待用户实时输入，这样也有助于提高响应速度。

6、适用场景

1. 分时操作系统
2. 多任务处理且对公平性要求较高的系统
3. 实时性要求不高的多用户环境
4. 测试与调试环境

优先级调度（Priority Scheduling）

1、基本概念

• 优先级调度是一种进程调度算法，它为每个进程分配一个优先级。优先级可以是一个整数值，数字越大优先级越高（或者反之，具体规则由系统定义）。在进行进程调度时，系统会优先选择优先级高的进程来分配 CPU 资源。例如，在一个多任务操作系统中，系统进程可能被赋予较高的优先级，因为它们负责系统的关键功能，如内存管理、设备驱动等，而用户进程的优先级可能相对较低。

2、优先级的类型

• 静态优先级：进程的优先级在创建时就确定了，并且在整个生命周期内保持不变。这种方式简单，但缺乏灵活性。例如，一些实时控制系统中，关键的控制进程被赋予最高优先级，并且一直保持这个优先级，因为这些进程的重要性和紧急程度从始至终都是最高的。
• 动态优先级：进程的优先级在运行过程中可以根据多种因素进行调整。例如，一个进程等待 CPU 的时间越长，它的优先级可能会越高，这是为了避免进程饥饿现象（某些进程一直无法获得 CPU 资源）。或者，如果一个进程占用 CPU 的时间过长，其优先级可能会降低，以便让其他进程有机会运行。

3、优先级调度的实现方式

• 非抢占式优先级调度：当一个进程开始运行后，它会一直运行直到结束或者主动放弃 CPU（如等待 I/O 操作），即使在这个过程中有更高优先级的进程进入就绪队列。例如，假设有进程 P1（优先级为 3）正在运行，此时有一个优先级为 4 的进程 P2 进入就绪队列。在非抢占式优先级调度下，P1 会继续运行直到完成或者阻塞，然后 P2 才有机会运行。
• 抢占式优先级调度：当一个更高优先级的进程进入就绪队列时，当前正在运行的进程如果优先级较低，就会被抢占 CPU 资源，高优先级进程立即获得 CPU 开始运行。例如，还是上述的 P1 和 P2，在抢占式优先级调度下，一旦 P2 进入就绪队列，P1 会立即停止运行，P2 获得 CPU 开始运行。

4、优点

• 灵活性：通过设置不同的优先级，可以根据进程的重要性、紧急程度等因素灵活地分配 CPU 资源。例如，在一个多媒体播放系统中，音频和视频播放进程可以被赋予较高的优先级，以确保播放的流畅性，而一些后台下载进程可以设置为较低的优先级。
• 对关键任务的保障：可以保证关键任务（如系统监控、安全防护等进程）能够优先获得 CPU 资源，从而保障系统的安全和稳定运行。例如，在一个网络服务器中，负责处理安全认证的进程优先级较高，这样在有大量用户请求和其他进程竞争 CPU 时，安全认证进程能够及时处理，防止安全漏洞。

5、缺点

• 可能导致进程饥饿：低优先级的进程可能长时间得不到 CPU 资源，特别是在静态优先级且高优先级进程不断产生的情况下。例如，在一个工厂自动化控制系统中，如果一些非关键的设备监测进程被赋予很低的优先级，而关键的生产控制进程优先级很高且持续运行，那么这些监测进程可能会因为一直无法获得 CPU 而无法正常工作。
• 确定优先级的复杂性：确定合理的优先级是比较复杂的，需要考虑进程的性质、重要性、紧急程度等多种因素。如果优先级设置不合理，可能会导致系统性能下降或者某些任务无法正常完成。例如，在一个复杂的软件开发环境中，要准确判断每个开发工具进程和用户代码进程的优先级是很困难的。

6、适用场景

实时系统

​ 在硬实时系统中，如航空航天、工业控制等领域，某些任务必须在严格的时间限制内完成。例如，飞机的自动驾驶系统中的飞行控制进程，这些进程需要在规定的极短时间内接收传感器数据、进行计算并发出控制指令。通过优先级调度，将这些关键的飞行控制进程设置为最高优先级，可以确保它们优先获取 CPU 资源，从而保证飞行安全。

​ 在软实时系统，像多媒体播放系统中，音频和视频播放进程需要保证一定的实时性，以提供流畅的视听体验。优先级调度可以使这些进程获得较高优先级，优先于其他非实时性要求高的进程（如后台文件下载），避免播放卡顿。

系统资源管理

​ 操作系统本身的一些关键进程，如内存管理进程、设备驱动进程等，需要优先执行，以确保系统的正常运转。例如，内存管理进程负责分配和回收内存，当系统内存紧张时，它需要快速响应以避免系统崩溃。通过优先级调度，将这些系统管理进程设置为高优先级，可以保障系统资源的有效管理。

​ 在服务器环境中，对于处理用户请求的关键进程（如处理高价值客户订单的进程、安全认证进程）可以设置较高优先级。例如，在金融交易服务器中，处理大额交易的进程优先级可以高于普通交易进程，确保重要交易能够快速处理。

多用户环境下的任务区分

​ 在多用户分时系统中，系统管理员可能需要执行一些紧急的系统维护任务，如修复系统漏洞、安装重要软件更新等。通过优先级调度，将管理员任务的进程设置为高优先级，这样可以在众多用户任务竞争 CPU 资源时，优先完成管理员的操作，保障系统整体安全和稳定。

7、如何实现适用的优先级调度

合理设置优先级

• 对于系统进程，根据其对系统运行的重要性来设置优先级。例如，内核调度进程、中断处理进程等通常设置为最高优先级，因为它们直接关系到系统的基本运行。对于用户进程，可以根据用户的重要性（如管理员用户、普通用户）、任务的性质（如实时任务、非实时任务）等因素来设置优先级。
• 可以采用分级的方式设置优先级。例如，将优先级分为 0 - 9 共 10 个等级，0 为最高优先级，9 为最低优先级。对于关键的实时任务设置为 0 - 2 级，系统管理进程设置为 3 - 4 级，普通用户的重要任务设置为 5 - 6 级，一般用户任务设置为 7 - 9 级。

结合其他调度算法

• 与时间片轮转相结合。在优先级相同的情况下，采用时间片轮转来分配 CPU。例如，在一个多用户分时系统中，对于同一优先级的用户进程，通过时间片轮转让每个进程都有机会获得 CPU，这样既保证了优先级高的进程优先执行，又避免了同优先级进程之间的不公平。
• 与多级反馈队列调度结合。将优先级调度融入多级反馈队列调度中，不同优先级的进程可以放在不同的队列中。例如，高优先级进程放在高优先级队列，且时间片较小，低优先级进程放在低优先级队列，时间片较大。这样可以根据优先级和进程的运行特性进行综合调度。

动态调整优先级

• 根据进程的等待时间来调整优先级。例如，一个进程等待 CPU 的时间越长，其优先级可以适当提高。可以设定一个规则，如每等待 100 毫秒，优先级提高一级（在合理范围内），以避免进程饥饿。
• 根据进程的执行情况来调整优先级。如果一个进程占用 CPU 时间过长，可以降低其优先级。例如，当一个用户进程连续占用 CPU 超过一定时间（如 1 秒），将其优先级降低一级，让其他进程有机会获得 CPU。

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

1、基本原理

• 多队列设置：该算法设置了多个就绪队列，每个队列具有不同的优先级，一般来说，优先级从高到低依次排列。不同优先级的队列用于处理不同类型或状态的进程。
• 时间片差异：各个队列的时间片大小也不相同，通常高优先级队列的时间片相对较小，低优先级队列的时间片相对较大。例如，最高优先级队列的时间片可能只有 5 毫秒，而最低优先级队列的时间片可能达到 50 毫秒。
• 进程进入与移动规则：新进程进入系统时，一般会先被放入最高优先级的队列。当一个进程在其所在队列用完时间片后，如果还未完成任务，它会根据一定规则被移动到下一个较低优先级的队列。并且，只有当高优先级队列中没有进程时，低优先级队列中的进程才有机会获得 CPU 资源。

2、具体示例

假设系统设置了三个就绪队列 Q1、Q2、Q3，优先级 Q1 > Q2 > Q3，时间片大小分别为 10 毫秒、20 毫秒、40 毫秒。

• 当一个新进程 P1 进入系统时，它首先被放入 Q1 队列。P1 在 Q1 队列中获得一个 10 毫秒的时间片开始运行。
• 如果 P1 在 10 毫秒内未完成任务，那么它会被移动到 Q2 队列。此时，当 Q1 队列中没有其他进程时，P1 才能在 Q2 队列中获得一个 20 毫秒的时间片继续运行。
• 假如 P1 在 Q2 队列的 20 毫秒时间片用完后仍未完成任务，它又会被移动到 Q2 队列。只有当 Q1 和 Q2 队列中都没有进程时，P1 才能在 Q3 队列中获得一个 40 毫秒的时间片继续运行。

3、优点

• 综合多种算法优点：它巧妙地融合了多种经典调度算法的优点。对于短进程，由于新进程首先进入高优先级且时间片较小的队列，所以短进程有很大机会在高优先级队列中快速完成，就如同短作业优先（SJF）算法的效果，能够快速得到处理，提高系统的吞吐量。
• 适应不同进程特性：可以很好地适应不同类型的进程。比如对于 I/O 密集型进程，这类进程在等待 I/O 操作完成后，往往会重新进入高优先级队列（因为等待 I/O 后可视为新进程的一种情况），从而能够得到及时处理，就像又获得了一次优先执行的机会，保证了这类进程的高效运行。而对于长进程，虽然开始在高优先级队列，但随着时间片用完会逐渐下移到低优先级队列，在低优先级队列中可以慢慢执行，不至于长时间占用高优先级队列资源，影响其他进程。
• 公平性保障：从整体上看，通过多级队列和不同的时间片设置以及进程的动态移动规则，实现了对不同进程的相对公平对待。每个进程都有机会根据自身的执行情况在合适的队列中获得 CPU 资源，不会出现某些进程一直被忽视或某些进程过度占用资源的情况。

4、缺点

实现相对复杂，需要维护多个队列和相关的调度策略。

5、适用场景

• 通用操作系统环境：在像 Linux 这样的通用操作系统中应用广泛，因为操作系统需要处理各种各样的进程，包括 CPU 密集型、I/O 密集型、短进程、长进程等不同类型的进程。多级反馈队列调度能够根据这些进程的不同特性进行合理调度，保障系统的高效运行和资源的公平分配。
• 服务器环境：在服务器环境中，同样会面临多种类型的客户端请求，这些请求对应的进程特性各不相同。采用多级反馈队列调度可以有效地处理这些请求，确保服务器资源能够合理分配给不同需求的客户端，提高服务器的响应速度和处理效率。