📚 Process Scheduling in Operating Systems | 操作系统中的进程调度
In any multitasking operating system, the CPU must switch between processes rapidly to create the illusion of parallelism. Process scheduling is the mechanism that decides which process gets the CPU, when, and for how long. It is a core topic in A‑Level Computer Science, directly influencing system performance, responsiveness, and fairness.
在任何多任务操作系统中，CPU 必须在各个进程之间快速切换，以营造并行处理的错觉。进程调度正是决定哪个进程获得 CPU、何时获得以及获得多长时间的核心机制。这是 A‑Level 计算机科学中的关键主题，直接影响系统性能、响应速度和公平性。
1. The Role of the Scheduler | 调度器的角色
The scheduler is a component of the operating system kernel that selects the next process to run from the ready queue. Its main objectives are to keep the CPU busy, minimise waiting time, maximise throughput, and ensure fair access for all processes.
调度器是操作系统内核的一个组件，负责从就绪队列中选择下一个要运行的进程。其主要目标是保持 CPU 忙碌、最小化等待时间、最大化吞吐量，并确保所有进程公平访问 CPU。
2. Preemptive vs Non‑preemptive Scheduling | 抢占式与非抢占式调度
Non‑preemptive scheduling allows a process to run until it voluntarily yields the CPU, either by terminating or entering a waiting state. Preemptive scheduling can interrupt a running process and force a context switch, typically triggered by a timer interrupt or a higher‑priority process becoming ready.
非抢占式调度允许进程一直运行，直到它主动放弃 CPU（例如终止或进入等待状态）。抢占式调度可以中断正在运行的进程并强制进行上下文切换，这通常由定时器中断或更高优先级的进程变为就绪状态触发。
3. First Come First Served (FCFS) | 先来先服务
FCFS is the simplest scheduling algorithm: processes are executed in the order they arrive in the ready queue. It is non‑preemptive and easy to implement with a FIFO data structure. However, it suffers from the “convoy effect”, where short processes get stuck behind long CPU‑bound processes.
FCFS 是最简单的调度算法：进程按其到达就绪队列的顺序执行。它是非抢占式的，使用 FIFO 数据结构即可实现。但其存在“护航效应”，即短进程被长 CPU 密集型进程阻挡，导致平均等待时间变长。
4. Shortest Job First (SJF) | 最短作业优先
SJF selects the process with the smallest estimated CPU burst time next. It is provably optimal in minimising average waiting time. Preemptive SJF (also called Shortest Remaining Time First, SRTF) further reduces waiting time. The main challenge is predicting burst lengths, which can be done using exponential averaging.
SJF 选择下一个预计 CPU 执行时间最短的进程。它在最小化平均等待时间上是可证明最优的。抢占式 SJF（又称最短剩余时间优先，SRTF）能进一步缩短等待时间。主要难点在于预测执行时长，可借助指数平均法进行估算。
5. Priority Scheduling | 优先级调度
Each process is assigned a priority, and the CPU is allocated to the highest‑priority process in the ready queue. Priority scheduling can be preemptive or non‑preemptive. A major risk is starvation, where low‑priority processes may never execute. Ageing (gradually increasing priority over time) solves this problem.
每个进程被分配一个优先级，CPU 分配给就绪队列中优先级最高的进程。优先级调度可以是抢占式也可以是非抢占式。一个主要风险是饥饿现象，即低优先级进程可能永远得不到执行。老化机制（随时间逐渐提升优先级）可以解决此问题。
6. Round Robin (RR) Scheduling | 轮转调度
Round Robin is a preemptive algorithm designed for time‑sharing systems. Each process is given a small time quantum (typically 10–100 ms). The CPU cycles through the ready queue, allowing each process to run for at most one quantum. If a process does not finish, it is returned to the tail of the queue.
轮转调度是一种为分时系统设计的抢占式算法。每个进程获得一小段的时间片（通常为 10–100 毫秒）。CPU 循环遍历就绪队列，每个进程最多运行一个时间片。若进程未完成，则被放回队列尾部。
7. Performance Trade‑offs of RR | 轮转调度的性能权衡
The choice of time quantum critically impacts performance. Too large a quantum makes RR behave like FCFS; too small a quantum causes excessive context‑switching overhead. A common guideline is that 80% of CPU bursts should be shorter than the quantum to maintain good response times and efficiency.
时间片的选择对性能至关重要。时间片过大，RR 会退化为 FCFS；时间片过小，上下文切换开销会过高。常见的指导原则是让 80% 的 CPU 突发时间短于时间片，以保持良好的响应时间和效率。
8. Multilevel Queue Scheduling | 多级队列调度
The ready queue is partitioned into separate queues based on process type (e.g., foreground interactive, background batch). Each queue has its own scheduling algorithm, and there is fixed priority scheduling between queues. This allows the system to prioritise interactive tasks while still serving batch jobs.
就绪队列根据进程类型（例如前台交互式、后台批处理）被划分为多个独立队列。每个队列可以使用自己的调度算法，队列之间采用固定优先级调度。这样系统可以优先处理交互式任务，同时仍能为批处理作业服务。
9. Multilevel Feedback Queue (MLFQ) | 多级反馈队列
MLFQ adds the ability to move processes between queues based on their CPU‑use history. A process that uses too much CPU time in a high‑priority queue is demoted to a lower‑priority queue; a process that waits too long can be promoted. This adaptive scheme balances responsiveness and throughput without prior knowledge of process behaviour.
MLFQ 增加了根据 CPU 使用历史在队列间移动进程的能力。在高优先级队列中使用过多 CPU 时间的进程会被降级到更低优先级的队列；等待过久的进程可以被提升。这种自适应方案在无需预先了解进程行为的情况下，能很好地平衡响应性和吞吐量。
10. Comparison of Scheduling Algorithms | 调度算法对比
| Algorithm | Type | Avg Waiting Time | Starvation | Overhead |
|---|---|---|---|---|
| FCFS | Non‑preemptive | High (convoy effect) | No | Low |
| SJF/SRTF | Both | Minimal | Possible (long jobs) | Medium |
| Priority | Both | Depends on priorities | Yes (no ageing) | Medium |
| Round Robin | Preemptive | Low (tuned q) | No | Context switches |
| MLFQ | Preemptive | Good (adaptive) | Mitigated by ageing | High |
This table highlights that no single algorithm is universally best; the choice depends on system goals, workload characteristics, and the balance between fairness and efficiency.
上表说明没有哪一种算法是普遍最优的；选择取决于系统目标、工作负载特征以及公平性与效率之间的平衡。
11. Real‑World Implementations | 实际应用中的实现
Modern operating systems use hybrid approaches. Linux employs a Completely Fair Scheduler (CFS) based on red‑black trees, approximating ideal fair scheduling. Windows uses a priority‑based scheme with 32 levels and automatic priority boosting. These real‑world schedulers incorporate MLFQ concepts to serve interactive, batch, and real‑time processes.
现代操作系统采用混合式方法。Linux 使用基于红黑树的完全公平调度器 (CFS)，试图逼近理想的公平调度。Windows 使用基于 32 级优先级并自动提升优先级的方案。这些实际调度器都融入了 MLFQ 的思想，以同时服务交互式、批处理和实时进程。
12. Summary and Exam Tips | 总结与备考提示
Process scheduling is a fundamental OS responsibility. Be prepared to calculate average waiting times and turnaround times for FCFS, SJF, Priority, and RR given a set of processes with arrival and burst times. Remember to distinguish between preemptive and non‑preemptive versions and to explain starvation/ageing clearly.
进程调度是操作系统的基本职责。考试中，能够针对一组给定到达时间和执行时间的进程，计算 FCFS、SJF、优先级调度和 RR 的平均等待时间和周转时间。记住区分抢占式与非抢占式版本，并能清晰地解释饥饿和老化机制。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导