Process Scheduling Algorithms in Operating Systems | 操作系统中的进程调度算法

📚 Process Scheduling Algorithms in Operating Systems | 操作系统中的进程调度算法

Process scheduling is a fundamental concept in operating systems that determines the order in which processes are executed by the CPU. It directly affects system performance, responsiveness, and fairness. Whether you are writing a simple script or building a complex multitasking application, understanding how the underlying scheduler works helps you write more efficient and predictable code. In this article, we explore the major CPU scheduling algorithms, their implementation, and their trade-offs, aligning with the Edexcel A‑level Computer Science specification.

进程调度是操作系统中的一个基本概念，它决定了 CPU 执行进程的顺序。调度策略直接影响系统性能、响应速度和公平性。无论你是在写简单脚本还是构建复杂的多任务应用，理解底层调度器的工作原理都有助于编写更高效、更可预测的代码。本文将探讨几种主要的 CPU 调度算法、它们的实现以及各自的权衡，内容与 Edexcel A‑level 计算机科学大纲保持一致。

1. The Role of the CPU Scheduler | CPU 调度器的角色

The CPU scheduler is a component of the operating system that selects one process from the ready queue and allocates the CPU to it. The scheduler runs whenever the CPU becomes idle, or when a running process voluntarily yields the CPU (e.g., waiting for I/O). There are two main types of scheduling: preemptive, where the OS can forcibly take the CPU away from a process, and non‑preemptive, where a process keeps the CPU until it voluntarily releases it.

CPU 调度器是操作系统的一个组件，它从就绪队列中选择一个进程并将 CPU 分配给它。每当 CPU 空闲，或者正在运行的进程主动让出 CPU（例如等待 I/O）时，调度器就会运行。调度主要分为两类：抢占式——操作系统可以强制从进程手中夺走 CPU，以及非抢占式——进程会一直占用 CPU 直到主动释放。

---

2. First‑Come, First‑Served (FCFS) | 先来先服务 (FCFS)

FCFS is the simplest scheduling algorithm: the process that arrives first gets the CPU first. It is implemented using a FIFO queue. While easy to understand, FCFS can lead to the “convoy effect”, where short processes get stuck behind long CPU‑bound processes, resulting in high average waiting time. FCFS is inherently non‑preemptive.

FCFS 是最简单的调度算法：最先到达的进程最先获得 CPU。它使用先进先出队列来实现。虽然容易理解，但 FCFS 会导致“护航效应”，即短进程被长 CPU 密集型进程阻塞，造成较高的平均等待时间。FCFS 本质上是一种非抢占式算法。

---

3. Shortest Job First (SJF) | 最短作业优先 (SJF)

SJF selects the process with the smallest CPU burst time from the ready queue. This algorithm can be either non‑preemptive (once a process starts, it runs to completion) or preemptive (if a new shorter job arrives, the current job is preempted). SJF theoretically minimises average waiting time, but it requires knowing the burst time of each process in advance, which is usually impossible in practice.

SJF 从就绪队列中选择 CPU 执行时间最短的进程。该算法可以是非抢占式的（一旦进程开始就运行到结束），也可以是抢占式的（如果有更短的作业到达，当前作业会被抢占）。理论上 SJF 可以最小化平均等待时间，但它需要提前知道每个进程的执行时间，这在实际中通常无法做到。

---

4. Shortest Remaining Time First (SRTF) | 最短剩余时间优先 (SRTF)

SRTF is the preemptive version of SJF. Whenever a new process arrives, the scheduler compares its remaining CPU burst with the remaining time of the currently executing process. If the new process has a shorter remaining time, the CPU is preempted. SRTF can provide even lower average waiting times than non‑preemptive SJF, but it increases context‑switching overhead and still requires burst‑time prediction.

SRTF 是 SJF 的抢占式版本。每当新进程到达时，调度器会比较其剩余 CPU 执行时间和当前执行进程的剩余时间。如果新进程剩余时间更短，CPU 就会被抢占。SRTF 的平均等待时间可能比非抢占式 SJF 更低，但它增加了上下文切换开销，并且仍然需要预测执行时间。

---

5. Round Robin (RR) | 轮转调度 (RR)

Round Robin is designed for time‑sharing systems. Each process gets a small unit of CPU time called a time quantum (or time slice); after that quantum expires, the process is preempted and placed at the end of the ready queue. RR is fair and prevents starvation, but performance heavily depends on the length of the time quantum. Too large a quantum makes RR behave like FCFS; too small a quantum leads to excessive context switches.

轮转调度是为分时系统设计的。每个进程获得一小段 CPU 时间，称为时间片；时间片用完后，进程被抢占并放到就绪队列末尾。RR 很公平，能防止饥饿，但性能高度依赖时间片的长度。时间片过大，RR 表现得像 FCFS；时间片过小，又会导致过多的上下文切换。

---

6. Priority Scheduling | 优先级调度

Each process is assigned a priority (often an integer); the CPU is allocated to the process with the highest priority. Priority scheduling can be preemptive or non‑preemptive. A major problem is starvation, where low‑priority processes may never execute if high‑priority processes keep arriving. This can be solved by aging, which gradually increases the priority of waiting processes.

每个进程被赋予一个优先级（通常是一个整数）；CPU 分配给优先级最高的进程。优先级调度可以是抢占式或非抢占式。一个主要问题是饥饿——如果高优先级进程源源不断地到来，低优先级进程可能永远得不到执行。可以通过老化（aging）技术来解决，即逐渐增加等待进程的优先级。

---

7. Multilevel Queue Scheduling | 多级队列调度

Processes are partitioned into several separate queues, typically based on process type (e.g., interactive, batch, system). Each queue has its own scheduling algorithm, and there is also scheduling among the queues (e.g., fixed‑priority preemptive scheduling). This approach allows the system to give different treatment to different categories of processes, but it can be inflexible because a process is permanently assigned to a queue.

进程被划分到多个独立的队列中，通常根据进程类型（如交互式、批处理、系统）划分。每个队列有自己的调度算法，并且队列之间也有调度（例如固定优先级抢占式调度）。这种方法允许系统对不同类别的进程区别对待，但不够灵活，因为进程被永久分配到某个队列。

---

8. Multilevel Feedback Queue (MLFQ) | 多级反馈队列 (MLFQ)

MLFQ addresses the inflexibility of multilevel queues by allowing processes to move between queues. Typically, it gives shorter time quanta to higher‑priority queues and longer quanta to lower‑priority queues. Processes that use up their time quantum are demoted to a lower‑priority queue; processes that wait too long are promoted. MLFQ approximates SJF without requiring burst‑time knowledge, and it prevents starvation through aging. It is widely used in modern operating systems like Windows and macOS.

MLFQ 通过允许进程在队列之间移动解决了多级队列的不灵活性。通常，它为高优先级队列分配较短的时间片，为低优先级队列分配较长的时间片。用完时间片的进程会被降级到更低优先级的队列；等待过久的进程则会被提升。MLFQ 无需预知执行时间就能近似 SJF，并且通过老化防止饥饿。它被广泛应用于现代操作系统，如 Windows 和 macOS。

---

9. Real‑Time Scheduling | 实时调度

Real‑time systems require strict timing guarantees. Two common approaches are Rate Monotonic Scheduling (RMS), where static priorities are assigned based on the period of tasks (shorter period → higher priority), and Earliest Deadline First (EDF), where the task with the closest deadline gets the highest priority dynamically. These algorithms are essential in embedded systems, avionics, and industrial control.

实时系统要求严格的时间保证。两种常见的方法是：速率单调调度（RMS），它根据任务的周期分配静态优先级（周期越短优先级越高）；以及最早截止时间优先（EDF），它动态地将最高优先级赋予截止时间最近的任务。这些算法在嵌入式系统、航空电子和工业控制中至关重要。

---

10. Scheduling Algorithm Evaluation | 调度算法的评估

We compare scheduling algorithms using several criteria: CPU utilisation (keeping the CPU busy), throughput (number of processes completed per time unit), turnaround time (time from submission to completion), waiting time (time spent in the ready queue), and response time (time from submission to the first response). Deterministic modelling, queueing models, and simulations help evaluate algorithms under different workloads.

我们用若干标准来比较调度算法：CPU 利用率（保持 CPU 忙碌）、吞吐量（单位时间完成的进程数）、周转时间（从提交到完成的时间）、等待时间（在就绪队列里等待的时间）以及响应时间（从提交到首次响应的时间）。确定性建模、排队模型和仿真有助于在不同工作负载下评估算法。

---

11. Implementation in Code: A Simple Round Robin Simulator | 代码实现：一个简单的轮转调度模拟器

To solidify your understanding, consider a Python simulation of Round Robin. Represent each process as an object with attributes for arrival time, burst time, and remaining time. Use a queue to hold ready processes. The main loop increments time, enqueues newly arrived processes, and gives the current process a time slice. If the process completes, record its statistics; if not, re‑enqueue it. This hands‑on exercise reinforces the theoretical concepts and prepares you for the coding aspects of the A‑level exam.

为了巩固理解，可以用 Python 编写一个轮转调度的模拟程序。将每个进程表示为一个对象，包含到达时间、执行时间和剩余时间等属性。使用一个队列来存放就绪进程。主循环递增时间、将新到达的进程入队，并给当前进程一个时间片。如果进程完成，记录其统计信息；否则重新入队。这个动手练习能够强化理论概念，并为 A‑level 考试中的编程部分做好准备。

---

12. Common Pitfalls and Exam Tips | 常见误区与考试技巧

Students often confuse waiting time with response time, or forget that the average turnaround time includes the entire execution period plus all waiting. When drawing Gantt charts, clearly label process IDs and time stamps. In SRID analyses, be careful to check at every arrival whether preemption should occur. Practice with varied quantum values in RR to see why 80% of CPU bursts should typically be shorter than the time quantum for optimal performance.

学生常常混淆等待时间与响应时间，或者忘记平均周转时间包括整个执行周期加上所有等待时间。绘制甘特图时，要清楚地标注进程 ID 和时间戳。在分析 SRTF 时，要仔细在每个到达时刻检查是否应该发生抢占。多练习 RR 中不同时间片值的场景，以理解为什么通常 80% 的 CPU 执行时间应该短于时间片才能获得最佳性能。

Published by TutorHao | Programming Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）