📚 Understanding Process Scheduling in Operating Systems | 理解操作系统中的进程调度
In the study of operating systems, one of the most crucial functions managed by the kernel is process scheduling. This mechanism determines which process runs on the CPU at any given moment, aiming to maximise CPU utilisation, minimise response time, and achieve fairness. For A-Level programmers, understanding scheduling algorithms not only clarifies how multitasking works but also influences the design of efficient software that interacts with the OS. We will explore preemptive and non‑preemptive strategies, examine classic algorithms like Round Robin and Shortest Job First, and consider real‑world implications such as context switching overhead and priority inversion.
在学习操作系统的过程中，内核管理的最关键功能之一就是进程调度。这一机制决定了在任何时刻哪个进程在 CPU 上运行，目标是最大化 CPU 利用率、最小化响应时间并实现公平。对于 A-Level 编程学习者而言，理解调度算法不仅能阐明多任务处理的工作原理，还会影响与操作系统交互的高效软件设计。我们将探讨抢占式和非抢占式策略，研究轮转调度、最短作业优先等经典算法，并思考上下文切换开销和优先级反转等实际影响。
1. The Role of the Scheduler | 调度器的角色
The scheduler is a component of the OS kernel that decides the order in which processes are executed on the CPU. It maintains one or more queues of processes in various states (ready, waiting) and selects the next process when the CPU becomes idle. In modern multiprogramming environments, the scheduler must quickly make decisions to keep the CPU busy while providing a responsive user experience. The scheduler’s design directly impacts system throughput, latency, and energy consumption.
调度器是操作系统内核的一个组件，它决定进程在 CPU 上的执行顺序。它维护一个或多个不同状态（就绪、等待）的进程队列，并在 CPU 空闲时选择下一个进程。在现代多道程序设计环境中，调度器必须迅速做出决策以保持 CPU 繁忙，同时提供及时的用户体验。调度器的设计直接影响系统的吞吐量、延迟和能耗。
2. Preemptive vs Non‑Preemptive Scheduling | 抢占式与非抢占式调度
In preemptive scheduling, the OS can forcibly remove the CPU from a running process before it finishes its burst, typically based on a timer interrupt or a higher‑priority process becoming ready. This approach prevents a single process from monopolising the CPU and is essential for time‑sharing systems. In contrast, non‑preemptive scheduling allows a process to hold the CPU until it voluntarily yields, either by completing its task or by blocking for I/O. Non‑preemptive algorithms are simpler but can lead to poor response times for interactive applications.
在抢占式调度中，操作系统可以在某个进程完成其 CPU 脉冲之前强制剥夺 CPU 使用权，通常基于定时器中断或更高优先级的进程变为就绪。这种方法可以防止单个进程独占 CPU，对于分时系统至关重要。相反，非抢占式调度允许进程一直占用 CPU，直到它主动放弃——要么完成任务，要么因 I/O 而阻塞。非抢占式算法较简单，但可能导致交互式应用程序的响应时间不佳。
3. Context Switching and Its Overhead | 上下文切换及其开销
Switching the CPU from one process to another requires a context switch, where the state of the current process (program counter, registers, memory mappings) is saved and the state of the next process is restored. This operation is pure overhead because no useful work is done during the switch. Frequent context switches can degrade system performance, so schedulers aim to balance responsiveness against the cost of switching. Typical context switch times range from a few microseconds to tens of microseconds, which must be factored into scheduling decisions.
将 CPU 从一个进程切换到另一个进程需要进行上下文切换，当前进程的状态（程序计数器、寄存器、内存映射）被保存，下一个进程的状态被恢复。此操作属于纯开销，因为在切换期间没有完成任何有用的工作。频繁的上下文切换会降低系统性能，因此调度器需要在响应性和切换成本之间取得平衡。典型的上下文切换时间从几微秒到几十微秒不等，在调度决策中必须加以考虑。
4. First‑Come, First‑Served (FCFS) | 先来先服务
FCFS is the simplest non‑preemptive scheduling algorithm. Processes are placed in a ready queue in the order they arrive; when the CPU is free, it is assigned to the process at the front of the queue. The process runs to completion or until it blocks. While easy to implement, FCFS can suffer from the “convoy effect,” where a long CPU‑bound process holds up many shorter I/O‑bound processes, leading to high average waiting times.
FCFS 是最简单的非抢占式调度算法。进程按到达顺序放入就绪队列；当 CPU 空闲时，分配给队首的进程。该进程一直运行到结束或阻塞。虽然实现简单，但 FCFS 可能会出现“护航效应”，即一个长时间的 CPU 密集型进程阻塞了许多较短的 I/O 密集型进程，导致平均等待时间很长。
5. Shortest Job First (SJF) and Shortest Remaining Time (SRT) | 最短作业优先与最短剩余时间
SJF is an optimal non‑preemptive algorithm when all burst times are known in advance, as it minimises average waiting time. It selects the process with the shortest next CPU burst. However, predicting burst lengths is difficult, and starvation of long processes can occur. Its preemptive counterpart, Shortest Remaining Time (SRT), picks the process with the smallest remaining execution time and can preempt the current process if a new one arrives with a shorter remaining time. Both algorithms rely on estimates of future CPU bursts, often using exponential averaging.
SJF 是一种在提前知道所有脉冲时间时的最佳非抢占式算法，因为它使平均等待时间最小化。它选择具有最短下一次 CPU 脉冲的进程。然而，预测脉冲长度很困难，且可能导致长进程饥饿。其抢占式版本——最短剩余时间（SRT）会选择剩余执行时间最短的进程，并且如果有剩余时间更短的新进程到来，可以抢占当前进程。这两种算法都依赖于对未来 CPU 脉冲的估计，通常使用指数平均法。
6. Round Robin (RR) Scheduling | 轮转调度
Round Robin is a preemptive algorithm designed for time‑sharing systems. Each process gets a fixed time quantum (e.g., 10–100 ms). The ready queue is treated as circular; a process is allowed to run for one quantum, after which it is preempted and placed at the back of the queue if it has not finished. The choice of quantum is critical: too small causes excessive context switches, too large degenerates into FCFS. RR guarantees fairness and reasonable response times for short interactive tasks.
轮转调度是一种专为分时系统设计的抢占式算法。每个进程获得一个固定的时间片（如 10–100 毫秒）。就绪队列被视作循环队列；进程可以运行一个时间片，如果未完成，之后会被抢占并放到队尾。时间片的选择至关重要：太小会导致过多的上下文切换，太大则退化为 FCFS。RR 保证了公平性，并为短交互任务提供了合理的响应时间。
7. Priority Scheduling and Starvation | 优先级调度与饥饿
Priority scheduling assigns each process a priority value (often an integer) and selects the highest‑priority ready process. Priorities can be static or dynamic. A major problem is starvation, where low‑priority processes may never execute. A common solution is aging, where the priority of a waiting process gradually increases over time. Preemptive priority scheduling will preempt the CPU if a higher‑priority process becomes ready, making it suitable for real‑time systems.
优先级调度为每个进程分配一个优先级值（通常为整数），并选择优先级最高的就绪进程。优先级可以是静态的或动态的。一个主要问题是饥饿，即低优先级进程可能永远得不到执行。常见的解决方案是老化，即等待进程的优先级随时间逐渐提高。抢占式优先级调度会在更高优先级的进程就绪时抢占 CPU，使其适用于实时系统。
8. Multilevel Queue and Multilevel Feedback Queue | 多级队列与多级反馈队列
Multilevel queue scheduling partitions processes into separate queues based on attributes such as foreground/background or process type, each with its own scheduling algorithm. For instance, interactive processes might use RR, while batch processes use FCFS. Scheduling among queues is typically based on fixed priority preemption. The multilevel feedback queue extends this by allowing processes to move between queues based on their behaviour; CPU‑bound processes are demoted to lower‑priority queues, while I/O‑bound processes remain in high‑priority queues, optimising overall responsiveness.
多级队列调度根据进程属性（如前台/后台或进程类型）将进程划分到不同的队列中，每个队列有自己的调度算法。例如，交互式进程可能使用 RR，而批处理进程使用 FCFS。队列之间的调度通常基于固定优先级的抢占。多级反馈队列在此基础上扩展，允许进程根据其行为在队列之间移动；CPU 密集型进程会被降级到低优先级队列，而 I/O 密集型进程则保留在高优先级队列，从而优化整体响应能力。
9. Real‑Time Scheduling | 实时调度
Real‑time systems require that tasks meet strict timing deadlines. Hard real‑time systems must guarantee deadline completion, whereas soft real‑time systems aim to minimise tardiness. Rate‑monotonic (RM) scheduling assigns static priorities based on the period of periodic tasks: shorter periods get higher priority. Earliest Deadline First (EDF) is a dynamic priority algorithm where the task closest to its deadline gets the CPU. Both methods rely on admission control to ensure schedulability.
实时系统要求任务满足严格的时间期限。硬实时系统必须保证在截止时间前完成，而软实时系统则力求最小化延迟。速率单调（RM）调度根据周期性任务的周期分配静态优先级：周期越短，优先级越高。最早截止时间优先（EDF）是一种动态优先级算法，最接近截止时间的任务获得 CPU。这两种方法都依赖准入控制来确保可调度性。
10. Scheduling in Practice: Linux and Windows | 实践中的调度：Linux 与 Windows
Modern OSs implement sophisticated schedulers that blend multiple algorithms. Linux’s Completely Fair Scheduler (CFS) uses a red‑black tree to track process virtual runtime and aims to give each task a fair share of CPU time. Windows employs a priority‑driven, preemptive scheduler with 32 priority levels and uses boosting to temporarily raise the priority of threads that have been starved. Both kernels incorporate support for multicore and energy‑aware scheduling, adapting to diverse hardware environments.
现代操作系统实现了融合多种算法的复杂调度器。Linux 的完全公平调度器（CFS）使用红黑树跟踪进程的虚拟运行时间，旨在让每个任务获得公平的 CPU 时间份额。Windows 采用优先级驱动、抢占式的调度器，具有 32 个优先级级别，并使用优先级提升来暂时提高被阻塞线程的优先级。两个内核都包含对多核和节能调度的支持，以适应多样的硬件环境。
11. Programming Considerations for Scheduling | 编程中的调度考虑
Programmers can influence scheduling behaviour through careful design. Using threads and setting appropriate priorities can improve responsiveness, but misuse can cause priority inversion, where a high‑priority thread waits for a low‑priority thread holding a lock. Techniques such as priority inheritance help mitigate this. Moreover, I/O‑bound programs should aim to release the CPU promptly to allow interactive processes to run, while CPU‑heavy tasks can use nice values or background threads to avoid hogging resources.
编程者可以通过精心设计来影响调度行为。使用线程并设置适当的优先级可以提高响应性，但误用可能导致优先级反转，即高优先级线程等待持有锁的低优先级线程。优先级继承等技术有助于缓解此问题。此外，I/O 密集型程序应尽快释放 CPU，以便交互式进程运行；而 CPU 繁重任务则可以使用 nice 值或后台线程，避免占用资源。
12. Key Formulas and Metrics | 关键公式与指标
To evaluate scheduling algorithms, we commonly compute:
Turnaround Time = Completion Time − Arrival Time
Waiting Time = Turnaround Time − Burst Time
Response Time = Time of First CPU Allocation − Arrival Time
Average values are then derived from the sum of all processes. CPU utilisation is measured as the percentage of time the CPU is busy. Throughput is the number of processes completed per unit time.
为了评估调度算法，我们通常计算：
周转时间 = 完成时间 − 到达时间
等待时间 = 周转时间 − CPU 脉冲时间
响应时间 = 首次分配 CPU 的时间 − 到达时间
然后根据所有进程的总和得出平均值。CPU 利用率以 CPU 繁忙的时间百分比衡量。吞吐量是单位时间内完成的进程数。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导