📚 Operating System Process Scheduling | 操作系统进程调度
In a multitasking operating system, the CPU must be shared efficiently among many processes. Process scheduling is the mechanism that decides which ready process gets the CPU and for how long. Understanding scheduling algorithms is fundamental for A-Level computer science, as it directly affects system responsiveness, throughput, and fairness. This article explores the core concepts and classical algorithms used in modern operating systems, with clear comparisons and evaluation criteria.
在多任务操作系统中，CPU 必须在众多进程之间高效共享。进程调度就是决定哪个就绪进程获得 CPU 以及使用多长时间的一套机制。理解调度算法是 A-Level 计算机科学的基础，因为它直接影响系统的响应速度、吞吐量和公平性。本文深入探讨现代操作系统所运用的核心概念和经典算法，并给出清晰的对比及评价标准。
1. Introduction to Process Scheduling | 进程调度简介
The objective of CPU scheduling is to keep the CPU busy at all times and to provide acceptable response times for interactive users. A process alternates between CPU bursts and I/O bursts. CPU-bound processes tend to have long CPU bursts, while I/O-bound processes spend most of their time waiting for peripheral operations. The scheduler must balance these workloads to maximise resource utilisation without starving any process.
CPU 调度的目标是让 CPU 始终处于忙碌状态，同时为交互式用户提供可接受的响应时间。一个进程会在 CPU 执行期和 I/O 等待期之间交替。CPU 密集型进程往往具有较长的 CPU 执行期，而 I/O 密集型进程则把大部分时间花在等待外设操作上。调度器必须平衡这些负载，以最大限度提高资源利用率，同时避免任何进程被饿死。
2. Process States and the Process Control Block | 进程状态与进程控制块
A process can be in one of several states: New, Ready, Running, Blocked (or Waiting), and Terminated. Transitions occur when the process is created, dispatched, waits for I/O, or completes. The operating system maintains a Process Control Block (PCB) for each process. The PCB stores the program counter, register contents, memory limits, open file list, and process state. When a context switch occurs, the PCB of the old process is saved, and the PCB of the new process is loaded.
一个进程可以处于以下几种状态之一：新建、就绪、运行、阻塞（或等待）和终止。当进程被创建、调度执行、等待 I/O 或结束执行时，会发生状态转换。操作系统为每个进程维护一个进程控制块（PCB）。PCB 中保存了程序计数器、寄存器内容、内存界限、打开文件列表以及进程状态。当发生上下文切换时，旧进程的 PCB 被保存，新进程的 PCB 被加载。
3. Scheduling Queues and Schedulers | 调度队列与调度器
Several queues are maintained: the job queue (all processes), the ready queue (processes in main memory, ready to run), and device queues (processes waiting for a particular I/O device). Three types of schedulers are typically distinguished: the long-term scheduler (or job scheduler) controls the degree of multiprogramming by admitting processes from disk to memory; the short-term scheduler (CPU scheduler) selects from the ready queue for execution; and the medium-term scheduler swaps out partially executed processes to reduce contention for memory.
操作系统维护着多种队列：作业队列（所有进程）、就绪队列（在主存中等待运行的进程）以及设备队列（等待特定 I/O 设备的进程）。通常有三种调度器：长期调度器（作业调度器）通过将进程从磁盘调入内存来控制多道程序设计的道数；短期调度器（CPU 调度器）从就绪队列中挑选进程交给 CPU 运行；中期调度器则会将部分执行的进程换出，以减少对内存的争用。
4. Context Switching Overhead | 上下文切换开销
Switching the CPU from one process to another requires saving the state of the old process and loading the saved state for the new process. This context-switch time is pure overhead; the system does no useful work while switching. The speed of a context switch depends on hardware support, memory speed, and the number of registers to be saved. In real-time and interactive systems, frequent but short context switches are accepted to improve perceived responsiveness, whereas batch systems prefer long bursts and fewer switches to maximise throughput.
将 CPU 从一个进程切换到另一个进程需要保存旧进程的状态并加载新进程已保存的状态。这段上下文切换时间属于纯粹的开销，系统在切换期间不执行任何有用的工作。上下文切换的速度取决于硬件支持、内存速度以及需要保存的寄存器数量。在实时系统和交互式系统中，可以接受频繁但短暂的上下文切换以提升用户感知的响应速度，而批处理系统则倾向于使用较长的 CPU 执行期并减少切换，以最大化吞吐量。
5. Preemptive vs. Non-Preemptive Scheduling | 抢占式与非抢占式调度
Under non-preemptive scheduling, once the CPU has been allocated to a process, the process keeps the CPU until it voluntarily releases it, either by terminating or by switching to the waiting state. This model is simple but can lead to poor response times for other processes if a long CPU burst occupies the CPU. In preemptive scheduling, a running process can be interrupted and moved back to the ready queue, either at the end of a time quantum, when a higher-priority process becomes ready, or on a signal. Preemption is essential for time-sharing systems.
在非抢占式调度下，一旦 CPU 分配给某个进程，该进程将一直占有 CPU，直到它主动让出（通过终止或转入等待状态）。这种模型简单，但如果一个长 CPU 执行期占着 CPU，就会导致其他进程的响应时间变差。在抢占式调度中，正在运行的进程可以被中断并移回就绪队列，中断的原因可能是时间片用尽、有更高优先级的进程就绪或收到信号。抢占机制对于分时系统是不可或缺的。
6. First-Come, First-Served (FCFS) | 先来先服务
FCFS is the simplest non-preemptive scheduling algorithm. Processes are assigned the CPU in the order they arrive, managed by a FIFO ready queue. The average waiting time under FCFS is often high and varies greatly depending on the arrival order. A single CPU-bound process at the head of the queue can cause the “convoy effect”, where many I/O-bound processes queue up behind it, leading to device under-utilisation and poor overall performance.
FCFS 是最简单的非抢占式调度算法。进程按照到达顺序获得 CPU，由一个先进先出的就绪队列管理。FCFS 下的平均等待时间通常较长，且随到达顺序的不同而差异很大。如果队列头部是一个 CPU 密集型进程，就会引发“护航效应”——大量 I/O 密集型进程排在其后，导致设备利用率不足，整体性能下降。
7. Shortest Job First (SJF) and Shortest Remaining Time First (SRTF) | 最短作业优先与最短剩余时间优先
SJF associates each process with the length of its next CPU burst. The process with the shortest predicted CPU burst is scheduled next. It is provably optimal in terms of minimising average waiting time for a given set of processes. However, the main difficulty lies in accurately predicting burst lengths, which is usually done via exponential averaging of previous bursts. SRTF is the preemptive version: if a new process arrives with a shorter remaining burst than the current process’s remaining time, the CPU is preempted. SRTF delivers even lower average wait times but increases context switches.
SJF 为每个进程关联其下一次 CPU 执行期的长度，优先调度预测 CPU 执行期最短的进程。对于给定的一组进程，该方法在最小化平均等待时间方面已被证明是最优的。然而，主要困难在于准确预测执行期长度，通常通过对先前执行期进行指数平均来估算。SRTF 是 SJF 的抢占式版本：如果新到达进程的剩余执行时间比当前运行进程的更短，CPU 就会被抢占。SRTF 能进一步降低平均等待时间，但会增加上下文切换次数。
8. Priority Scheduling | 优先级调度
Each process is assigned a priority, and the CPU is given to the process with the highest priority (smallest integer typically denotes highest priority). Priorities can be static or dynamic, and the algorithm can be preemptive or non-preemptive. A major problem is starvation, where low-priority processes may never execute. Ageing is a common solution: gradually increase the priority of a process that has been waiting for a long time, ensuring that even the lowest-priority process eventually runs.
每个进程被分配一个优先级，CPU 将分配给具有最高优先级的进程（通常用最小的整数表示最高优先级）。优先级可以是静态的，也可以是动态的；同样地，调度可以是抢占式或非抢占式。一个严重的问题是饥饿现象，即低优先级进程可能永远无法执行。老化（ageing）是一种常见的解决方案：逐渐提升长时间等待进程的优先级，从而确保即使最低优先级的进程最终也能获得 CPU。
9. Round Robin (RR) Scheduling | 轮转调度
Round Robin is designed for time-sharing systems. A fixed time quantum (e.g., 10–100 ms) is defined. The ready queue is treated as a circular queue, and the scheduler goes around the queue, allocating the CPU to each process for up to one quantum. If a process’s CPU burst exceeds the quantum, it is preempted and placed at the tail of the queue. The choice of time quantum is critical: a very large quantum degenerates to FCFS; a very small quantum causes excessive context switching. The rule of thumb is that 80% of CPU bursts should be shorter than the quantum.
轮转调度专为分时系统设计。需要定义一个固定的时间片（例如 10–100 毫秒）。就绪队列被当作循环队列处理，调度器沿着队列依次为每个进程分配至多一个时间片的 CPU 时间。如果某个进程的 CPU 执行期超过时间片，它会被抢占并放回队尾。时间片大小的选择至关重要：太大的时间片会退化为 FCFS，太小的时间片则导致过多的上下文切换。经验法则是，应将 80% 的 CPU 执行期控制在时间片以内。
10. Multilevel Queue and Multilevel Feedback Queue | 多级队列与多级反馈队列
Multilevel queue scheduling partitions processes into separate queues based on their nature, e.g., foreground (interactive) and background (batch) queues. Each queue can have its own scheduling algorithm—round robin for the foreground, FCFS for the background. Fixed-priority preemptive scheduling between queues ensures that interactive processes receive the CPU first. Multilevel feedback queue (MLFQ) extends this by allowing processes to move between queues. A process that uses its entire quantum is demoted to a lower-priority queue, while one that releases the CPU early (I/O bound) stays or moves up. This dynamically adapts to process behaviour without explicit burst prediction.
多级队列调度根据进程的性质将其划分到不同的队列中，例如前台（交互式）队列和后台（批处理）队列。每个队列可以采用自己的调度算法——前台使用轮转，后台使用 FCFS。队列之间采用固定优先级抢占，保证交互式进程优先获得 CPU。多级反馈队列（MLFQ）进一步允许进程在队列之间迁移。耗尽其完整时间片的进程会被降级到更低优先级的队列，而提前释放 CPU（I/O 密集型）的进程则留在当前队列或予以升级。这种机制无需显式预测执行期，即可动态适应进程行为。
11. Evaluation Metrics and Comparison Summary | 评价指标与对比总结
To compare scheduling algorithms, we use several quantitative metrics: CPU utilisation (percentage of time the CPU is busy), throughput (number of processes completed per time unit), turnaround time (interval from submission to completion), waiting time (time spent in the ready queue), and response time (delay from submission until the first response). The table below summarises how the classic algorithms perform against these metrics under typical workloads.
为了比较调度算法，我们采用下列量化指标：CPU 利用率（CPU 处于忙碌状态的时间百分比）、吞吐量（单位时间内完成的进程数）、周转时间（从提交到完成的时间间隔）、等待时间（在就绪队列中花费的时间）以及响应时间（从提交到首次响应的延迟）。下表总结了经典算法在典型负载下对这些指标的表现。
| Algorithm | CPU Utilisation | Throughput | Turnaround | Waiting Time | Response Time |
|---|---|---|---|---|---|
| FCFS | High | Moderate | Poor (convoy) | High | Poor |
| SJF (non-preemptive) | High | High | Optimal | Minimum | Good |
| SRTF (preemptive SJF) | High | High | Better | Very low | Good |
| Priority (with ageing) | High | High | Variable | Variable | Good if interactive prioritised |
| Round Robin | High | Lower if quantum small | Depends on quantum | Higher for long jobs | Excellent |
| MLFQ | High | High | Good balance | Good | Good to excellent |
These metrics demonstrate that no single algorithm is perfect for all scenarios. The choice depends on the system’s objective: a batch system may favour SJF for maximum throughput, while a time-sharing desktop requires RR or MLFQ for low response times. Modern general-purpose operating systems like Linux and Windows use variants of MLFQ with dynamic priority adjustments.
这些指标表明，没有哪一种算法对所有场景都是完美无缺的。选择何种算法取决于系统的目标：批处理系统可能偏爱 SJF 以获得最大吞吐量，而分时桌面环境则需要 RR 或 MLFQ 来保证低响应时间。现代通用操作系统（如 Linux 和 Windows）均使用带动态优先级调整的 MLFQ 变体。
12. Real-World Examples and the Linux O(1) Scheduler | 实际案例与 Linux O(1) 调度器
The Linux kernel historically used an O(1) scheduler, which could select the next task in constant time regardless of the number of runnable processes. It maintained two arrays per CPU: an active array and an expired array, each containing priority-linked lists. Processes moved between arrays when their time quantum expired. Interactive processes received bonus priority to reduce latency. Although later replaced by the Completely Fair Scheduler (CFS), the O(1) scheduler illustrates how the principles of multilevel feedback queues are implemented in a production kernel.
Linux 内核曾使用过 O(1) 调度器，该调度器能够在常数时间内选出下一个任务，与可运行进程的数量无关。它为每个 CPU 维护两个数组：活跃数组和过期数组，每个数组均包含按优先级组织的链表。当进程的时间片用尽时，它会在数组之间移动。交互式进程获得额外的优先级加成以降低延迟。尽管后来被完全公平调度器（CFS）取代，O(1) 调度器仍很好地示范了生产内核中多级反馈队列原理的落地实现。
For students preparing for Edexcel A-Level Computer Science, it is essential to focus on the classification (preemptive/non-preemptive), the calculation of waiting and turnaround times for simple process sets, and the ability to explain how a given algorithm improves fairness or response time. Practice drawing Gantt charts for scenarios with arrival times and burst times to cement these concepts.
对于正在备考 Edexcel A-Level 计算机科学的学生来说，重点应聚焦于算法的分类（抢占/非抢占）、对简单进程集合计算等待时间和周转时间，以及能够说明某种算法如何提升公平性或响应速度。请反复练习为带有到达时间和执行时间的场景绘制甘特图，以巩固这些概念。
Published by TutorHao | Programming Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导