📚 Operating System Scheduling Algorithms and Memory Management | 操作系统调度算法与内存管理
In A-Level Computer Science, understanding how an operating system manages processes and memory is fundamental. This article explores key scheduling algorithms – FCFS, Round-Robin, SJF, and priority-based – alongside memory management techniques including paging, segmentation, and page replacement policies, all crucial for Edexcel Paper 1.
在A-Level计算机科学中，理解操作系统如何管理进程和内存是基础。本文探讨了关键的调度算法——先来先服务、轮转、最短作业优先和基于优先级的调度，以及包括分页、分段和页面置换策略在内的内存管理技术，这些都是Edexcel试卷一的重点。
1. Introduction to Operating Systems and Their Roles | 操作系统及其作用介绍
An operating system (OS) acts as an intermediary between computer hardware and user applications. Its core responsibilities include process management, memory management, file system handling, and I/O device control. The OS aims to maximize resource utilization while ensuring fairness and responsiveness.
操作系统充当计算机硬件与用户应用程序之间的中介。其核心职责包括进程管理、内存管理、文件系统处理和I/O设备控制。操作系统的目标是在确保公平性和响应性的同时最大化资源利用率。
In a multi-programming environment, several processes reside in main memory simultaneously. The OS must decide which process gets the CPU, for how long, and how to allocate memory efficiently. This decision-making is implemented via scheduling algorithms and memory allocation strategies, which directly impact system performance metrics such as throughput, turnaround time, and waiting time.
在多道程序环境中，多个进程同时驻留在主存中。操作系统必须决定哪个进程获得CPU、使用多长时间以及如何高效地分配内存。这些决策通过调度算法和内存分配策略实现，直接影响吞吐量、周转时间和等待时间等系统性能指标。
2. Process States and the Process Control Block | 进程状态与进程控制块
A process transitions through several states during its lifetime: New, Ready, Running, Waiting (blocked), and Terminated. The CPU scheduler selects a process from the ready queue and dispatches it to the running state. When a process needs I/O, it moves to the waiting state until the event completes.
进程在其生命周期中经历多个状态：新建、就绪、运行、等待（阻塞）和终止。CPU调度器从就绪队列中选择一个进程并将其分派到运行状态。当进程需要I/O时，它会转移到等待状态，直到事件完成。
Each process is represented in the OS by a Process Control Block (PCB), which stores essential information: process ID, program counter, CPU registers, memory limits, list of open files, and scheduling parameters such as priority. The PCB allows the OS to save and restore the context of a process during a context switch, enabling preemptive multitasking.
每个进程在操作系统中由一个进程控制块表示，它存储了关键信息：进程ID、程序计数器、CPU寄存器、内存界限、打开文件列表以及优先级等调度参数。PCB允许操作系统在上下文切换期间保存和恢复进程的上下文，从而实现抢占式多任务处理。
3. Preemptive vs Non-preemptive Scheduling | 抢占式与非抢占式调度
Scheduling algorithms can be classified as preemptive or non-preemptive. In non-preemptive scheduling, once a process is allocated the CPU, it keeps it until it voluntarily releases it by terminating or switching to the waiting state. This approach is simple but can lead to long waiting times for short processes if a long one is executing.
调度算法可以分为抢占式和非抢占式。在非抢占式调度中，一旦进程被分配到CPU，它将一直保持直到通过终止或切换到等待状态而自愿释放CPU。这种方法简单，但如果有长进程在执行，可能导致短进程等待时间过长。
Preemptive scheduling allows the OS to forcibly remove a running process from the CPU, typically after a time slice expires or when a higher-priority process becomes ready. This improves responsiveness and prevents starvation, but incurs context-switching overhead. Modern general-purpose operating systems like Windows, Linux, and macOS all use preemptive scheduling.
抢占式调度允许操作系统强制将正在运行的进程从CPU中移除，通常在时间片到期或有更高优先级进程就绪时。这提高了响应性并防止饥饿，但会带来上下文切换开销。现代通用操作系统如Windows、Linux和macOS都使用抢占式调度。
4. First-Come, First-Served (FCFS) Scheduling | 先来先服务调度
FCFS is the simplest non-preemptive scheduling algorithm. Processes are executed in the order they arrive in the ready queue. The CPU is allocated to the process at the head of the queue, and it runs to completion without interruption. The average waiting time under FCFS can be high and varies significantly with the arrival order.
FCFS是最简单的非抢占式调度算法。进程按照它们到达就绪队列的顺序执行。CPU分配给队列头部的进程，该进程不间断地运行直至完成。在FCFS下，平均等待时间可能很高，并且随到达顺序的不同而显著变化。
Consider three processes arriving at time 0 with burst times: P1 = 24 ms, P2 = 3 ms, P3 = 3 ms. If they arrive in order P1, P2, P3, the waiting times are: P1 = 0, P2 = 24, P3 = 27, giving an average of 17 ms. The main drawback is the convoy effect, where short processes get stuck behind long ones, reducing CPU and I/O device utilization.
考虑三个在时间0到达且爆发时间分别为：P1 = 24毫秒，P2 = 3毫秒，P3 = 3毫秒的进程。如果它们按P1、P2、P3的顺序到达，等待时间为：P1 = 0，P2 = 24，P3 = 27，平均值为17毫秒。主要缺点是护航效应，即短进程被挡在长进程后面，降低了CPU和I/O设备的利用率。
5. Round-Robin (RR) Scheduling | 轮转调度
Round-Robin is a preemptive scheduling algorithm designed for time-sharing systems. Each process gets a small unit of CPU time called a time quantum (q), typically 10–100 ms. The ready queue is treated as a circular queue. The CPU cycles through processes, allocating the quantum, and moves to the next process if the current one hasn’t finished.
轮转调度是一种为分时系统设计的抢占式调度算法。每个进程获得一个称为时间片（q）的小单位CPU时间，通常为10–100毫秒。就绪队列被当作循环队列处理。CPU轮转遍历进程，分配时间片，如果当前进程未完成则移至下一个进程。
The choice of quantum is critical: too small causes too many context switches, wasting CPU time; too large degrades to FCFS. If the time quantum is 4 ms and we have the same processes as before, the execution order becomes P1(4), P2(3), P3(3), P1(4), P1(4)… waiting times improve dramatically. RR provides good response time but may increase average turnaround time compared to SJF.
时间片的选择至关重要：太小时造成过多的上下文切换，浪费CPU时间；太大时则退化为FCFS。如果时间片为4毫秒且采用相同的进程，执行顺序变为P1(4)、P2(3)、P3(3)、P1(4)、P1(4)……等待时间大幅改善。RR提供良好的响应时间，但与SJF相比可能增加平均周转时间。
6. Shortest Job First (SJF) Scheduling | 最短作业优先调度
SJF schedules the process with the shortest predicted CPU burst time next. When implemented non-preemptively, once a process starts, it runs to completion. Preemptive SJF, also called Shortest Remaining Time First (SRTF), preempts the current process if a new process arrives with a shorter remaining burst time.
SJF将具有最短预测CPU爆发时间的进程安排为下一个执行。当以非抢占式实现时，一旦进程开始，它将运行到完成。抢占式SJF，也称为最短剩余时间优先，如果新进程到达时剩余爆发时间更短，则抢占当前进程。
SJF is provably optimal in terms of minimizing average waiting time for a given set of processes. However, it requires knowledge of future burst lengths, which is usually estimated using exponential averaging. Starvation of long processes can occur if short processes keep arriving. Because it is often impractical to know exact burst times, SJF is rarely used in real general-purpose systems in its pure form.
就最小化给这组进程的平均等待时间而言，SJF被证明是最优的。然而，它需要知道未来的爆发长度，通常使用指数平均进行估算。如果短进程不断到达，长进程可能会饥饿。由于通常难以获知确切的爆发时间，纯粹的SJF很少在实际的通用系统中使用。
7. Priority-Based Scheduling | 基于优先级的调度
Each process is assigned a priority, and the CPU is allocated to the process with the highest priority (smallest integer often denotes highest priority). Priorities can be internally defined (memory requirements, number of open files) or externally defined (user importance, process type). This scheme can be either preemptive or non-preemptive.
每个进程被分配一个优先级，CPU分配给具有最高优先级的进程（通常最小整数表示最高优先级）。优先级可以内部定义（内存需求、打开文件数）或外部定义（用户重要性、进程类型）。这种方案可以是抢占式的也可以是非抢占式的。
A major problem with priority scheduling is indefinite blocking, or starvation, where a low-priority process may never execute. Aging is a solution that gradually increases the priority of a waiting process over time, ensuring eventual execution. For example, in a system with priorities 0 (highest) to 127 (lowest), a process waiting for a minute might have its priority increased by 1 every 10 seconds.
优先级调度的一个主要问题是无限阻塞或饥饿，即低优先级的进程可能永远不会执行。老化是一种解决方案，它随时间逐渐增加等待进程的优先级，确保最终被执行。例如，在一个优先级为0（最高）到127（最低）的系统中，等待一分钟的进程可能每10秒将其优先级提高1。
8. Memory Management: Segmentation and Paging | 内存管理：分段与分页
Memory management aims to allocate main memory efficiently among competing processes. Two fundamental techniques are segmentation and paging. Segmentation divides a program’s address space into variable-sized logical segments, such as code, data, and stack. Each segment has a base and limit, and the MMU translates logical addresses by adding the segment base.
内存管理旨在在竞争进程中高效地分配主存。两个基本技术是分段和分页。分段将程序的地址空间划分为可变大小的逻辑段，如代码段、数据段和堆栈段。每个段有一个基址和界限，MMU通过加上段基址来转换逻辑地址。
Paging divides physical memory into fixed-sized blocks called frames and logical memory into blocks of the same size called pages. The page table maps each page number to a frame number. Paging eliminates external fragmentation but still suffers from internal fragmentation within each page. Most modern systems use a combination, such as paged segmentation, to leverage the benefits of both.
分页将物理内存划分为固定大小的块称为帧，将逻辑内存划分为相同大小的块称为页。页表将每个页码映射到帧号。分页消除了外部碎片，但每个页内仍存在内部碎片。大多数现代系统采用组合方式，如段页式，以利用两者的优点。
9. Virtual Memory and Page Replacement Algorithms | 虚拟内存与页面置换算法
Virtual memory enables a process to execute even if its entire address space is not in physical memory, using on-disk swap space. The OS manages a page table with present/absent bits; a page fault occurs when a needed page is not in memory, triggering a swap-in. When memory is full, the OS must choose a victim page to swap out.
虚拟内存使得即使进程的整个地址空间不在物理内存中，也能利用磁盘上的交换空间执行。操作系统管理带有存在/缺失位的页表；当所需页面不在内存中时发生缺页异常，触发换入。当内存已满时，操作系统必须选择一个牺牲页面换出。
Three classic page replacement algorithms are FIFO (First-In, First-Out), OPT (Optimal), and LRU (Least Recently Used). FIFO replaces the page that has been in memory longest; it is simple but suffers from Belady’s anomaly where more frames can lead to more page faults. LRU replaces the page that has not been used for the longest time, approaching optimal performance but is expensive to implement precisely without hardware support.
三种经典的页面置换算法是FIFO（先进先出）、OPT（最佳）和LRU（最近最少使用）。FIFO替换在内存中停留时间最长的页；它简单但存在Belady异常，即更多帧可能导致更多缺页。LRU替换最长时间未被使用的页，接近最佳性能，但在没有硬件支持的情况下精确实现的代价很高。
Edexcel candidates should be able to trace page references for a given frame count, calculate page fault rates, and compare algorithms. For example, with reference string 1,2,3,4,1,2,5,1,2,3,4,5 and 3 frames, FIFO gives 9 faults while LRU gives 10 faults, demonstrating that FIFO is not always worse but its vulnerability to Belady’s anomaly makes it less predictable.
Edexcel考生应能够对给定的帧数追踪页面引用、计算缺页率并比较算法。例如，对于引用串1,2,3,4,1,2,5,1,2,3,4,5和3个帧，FIFO产生9次缺页，而LRU产生10次缺页，这表明FIFO并不总是更差，但其易受Belady异常影响的弱点使其可预测性较差。
10. Practical Implementation Considerations in Programming | 编程中的实践考虑
When implementing scheduling simulations in a high-level language such as Python, understanding data structures is key. A ready queue for RR can be implemented using a circular linked list or a deque from the collections module. Priority scheduling requires a priority queue, often a heap structure supporting O(log n) insert and extract-min operations.
在用高级语言如Python实现调度模拟时，理解数据结构是关键。RR的就绪队列可以用循环链表实现，或者使用collections模块中的deque。优先级调度需要优先级队列，通常采用堆结构，支持O(log n)的插入和提取最小值操作。
Memory management simulations might involve representing physical memory as a fixed-size list and page tables as dictionaries. Page replacement algorithms can be coded by tracking access timestamps (for LRU) or positions in a queue (for FIFO). While coding, students should note that real OS kernels avoid using stack-based allocation or high-level abstractions due to performance constraints; instead, they use static arrays and pointer manipulation in C.
内存管理模拟可能涉及将物理内存表示为固定大小的列表，页表表示为字典。页面置换算法可以通过跟踪访问时间戳（LRU）或队列中的位置（FIFO）来编码。在编程时，学生应注意真实的操作系统内核由于性能限制，避免使用基于堆栈的分配或高级抽象；而是使用静态数组和C语言中的指针操作。
| Algorithm | Data Structure | Time Complexity per Operation |
|---|---|---|
| FCFS | Queue (FIFO) | O(1) |
| Round-Robin | Circular Queue / Deque | O(1) |
| SJF (non-preemptive) | Min-Heap | O(log n) per insert/extract |
| Priority (preemptive) | Heap + Arbiter | O(log n) |
11. Real-World Applications and Exam Tips | 实际应用与考试技巧
Real operating systems combine multiple scheduling classes. Linux uses a Completely Fair Scheduler (CFS) based on virtual runtime, while Windows employs a multilevel feedback queue with priority boosts for interactive processes. Memory management in Linux uses a buddy allocator for physical frames and a hierarchical page table structure to reduce overhead for sparse address spaces.
真实操作系统结合了多种调度类别。Linux使用基于虚拟运行时的完全公平调度器，而Windows采用多级反馈队列并对交互式进程进行优先级提升。Linux的内存管理使用伙伴分配器管理物理帧，并使用分层页表结构减少稀疏地址空间的开销。
For Edexcel exams, students should be able to calculate waiting times, turnaround times, and page fault rates from given process tables or reference strings. Draw Gantt charts clearly to illustrate scheduling sequences. Be ready to explain the convoy effect, starvation vs aging, and the conditions under which Belady’s anomaly occurs. Always state assumptions, such as whether context switch time is negligible, unless specified otherwise.
对于Edexcel考试，学生应能够根据给定的进程表或引用串计算等待时间、周转时间和缺页率。清晰地绘制甘特图以说明调度序列。准备好解释护航效应、饥饿与老化，以及Belady异常发生的条件。除非另有规定，应始终说明假设，如上下文切换时间是否可忽略。
12. Summary of Key Formulae and Terms | 关键公式和术语总结
Turnaround Time = Completion Time – Arrival Time
Waiting Time = Turnaround Time – Burst Time
Response Time = Time from submission to first CPU response
Throughput = Number of processes completed per unit time
CPU Utilization = (1 – fraction of idle time)
周转时间 = 完成时间 – 到达时间
等待时间 = 周转时间 – 爆发时间
响应时间 = 从提交到首次CPU响应的时间
吞吐量 = 单位时间内完成的进程数量
CPU利用率 = (1 – 空闲时间比例)
Effective Access Time (EAT) for virtual memory with paging = (1 – p) x memory access time + p x (page fault overhead + swap time), where p is the page fault rate. For a system with 100 ns memory access, 25 ms page fault service time, and p = 0.001, EAT ≈ 25,000 ns, showing how even a tiny fault rate drastically impacts performance.
带分页的虚拟内存的有效访问时间 = (1 – p) x 内存访问时间 + p x (缺页开销 + 交换时间)，其中p是缺页率。对于一个内存访问时间为100纳秒、缺页服务时间为25毫秒且p = 0.001的系统，EAT ≈ 25,000纳秒，表明即使微小的缺页率也会严重影响性能。
In the exam, you may be asked to compare algorithms using a given scenario; always refer back to these definitions and use a systematic approach to compute averages. Remember that the choice of algorithm depends on the system goals: interactive systems prioritize response time, batch systems prioritize throughput, and real-time systems require predictable deadlines.
在考试中，可能会要求你使用给定场景比较算法；始终回顾这些定义并使用系统的方法计算平均值。请记住，算法的选择取决于系统目标：交互系统优先考虑响应时间，批处理系统优先考虑吞吐量，而实时系统要求可预测的截止时间。
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课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply