操作系统（OS）

当前尚未收到个人 OS 原始记录，因此本页均为补充框架。后续新增个人记录时，使用蓝色块原样追加。

一、操作系统概述

操作系统是计算机硬件与用户之间的接口，也是计算机资源的管理者。主要管理处理机、存储器、文件和 I/O 设备，并向用户和应用程序提供接口。

操作系统的基本特征：并发、共享、虚拟和异步。其中并发和共享是最基本的特征。

二、进程与线程

进程是程序的一次执行过程，是资源分配和独立运行的基本单位。线程是处理机调度的基本单位，同一进程的线程共享进程地址空间和大部分资源。

进程常见状态：运行、就绪、阻塞；引入挂起后还可分为活动/静止就绪和活动/静止阻塞。

1
2
3
4

就绪 --被调度--> 运行
运行 --时间片到--> 就绪
运行 --等待事件--> 阻塞
阻塞 --事件完成--> 就绪

阻塞进程不能直接变为运行态，必须先进入就绪态；就绪态表示只缺少 CPU，阻塞态表示正在等待某个事件或资源。

进程通信

三、处理机调度

常用指标：CPU 利用率、吞吐量、周转时间、带权周转时间、等待时间和响应时间。

1
2
3

周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 ÷ 实际运行时间
等待时间 = 周转时间 - 实际运行时间 - I/O 时间

四、同步与互斥

临界资源一次只允许一个进程使用；访问临界资源的代码段称为临界区。同步解决进程间执行次序问题，互斥解决临界资源竞争问题。

进入区应遵循：空闲让进、忙则等待、有限等待、让权等待。

信号量

1
2

P(S): S = S - 1；若 S < 0，则当前进程阻塞
V(S): S = S + 1；若 S <= 0，则唤醒一个等待进程

P、V 操作必须是原子操作。用于互斥的信号量通常初始化为 1；用于表示资源数量时，初值通常为资源数；用于同步时，初值取决于前驱事件是否已经发生。

经典问题

• 生产者—消费者：既有同步关系，也有缓冲区互斥访问。
• 读者—写者：允许多个读者同时读，但写者需独占。
• 哲学家进餐：重点考查死锁避免与资源分配顺序。

五、死锁

死锁产生的四个必要条件：互斥、不可剥夺、请求并保持、循环等待。只要破坏其中任意一个，死锁就不能产生。

不安全状态不等于已经死锁，但可能进入死锁；安全状态一定不存在死锁。银行家算法判断的是系统是否存在安全序列。

六、内存管理

逻辑地址由程序使用，物理地址对应主存单元。地址重定位可在装入时一次完成，也可在运行时动态完成。

连续分配

• 首次适应：从低地址开始寻找第一个足够大的空闲分区。
• 最佳适应：选择能够满足要求的最小空闲分区，容易留下小碎片。
• 最坏适应：选择最大的空闲分区。
• 邻近适应：从上次查找结束处继续查找。

分页与分段

地址转换

若页大小为 2^k 字节，则逻辑地址低 k 位为页内偏移，其余高位为页号。页表将页号映射为物理页框号。

七、虚拟内存

虚拟内存基于局部性原理，只把当前需要的部分页面调入主存。请求分页系统需要页表机制、缺页中断机构和地址变换机构。

缺页异常属于内中断/异常，发生在指令执行期间；处理完成后通常重新执行引发缺页的指令。只有 FIFO 等部分算法可能出现 Belady 异常，LRU 和 OPT 不会。

八、文件管理

文件的逻辑结构面向用户，常见为无结构文件和有结构文件；物理结构描述文件在外存上的组织方式。

目录用于实现文件名到文件控制块或索引节点的映射。文件打开后，系统通常维护系统级和进程级打开文件表。

九、I/O 管理与磁盘调度

I/O 软件通常采用分层结构，包括用户层软件、设备独立性软件、设备驱动程序和中断处理程序。设备控制器位于设备与 CPU/主存之间。

磁盘调度主要优化寻道时间；旋转延迟还与扇区位置、请求顺序和磁盘控制器有关。

十、系统调用、内核与中断

补充内容：本节及后续内容补齐操作系统统考中的概念、算法和计算题考点。

用户接口包括命令接口和程序接口，程序通过系统调用请求内核服务。库函数不一定触发系统调用；系统调用通常通过陷入指令主动进入内核态。

中断/异常使 CPU 从用户态转入内核态。外中断来自 CPU 外部，如时钟和 I/O；异常来自正在执行的指令，如缺页、越权、除零、系统调用。访管/陷入是有意产生的异常。处理中断时，硬件至少保存断点与必要状态，完整现场通常由硬件和软件共同保存。

操作系统结构包括分层、模块化、宏内核、微内核和外核。宏内核把主要服务放在内核态，调用高效但内核庞大；微内核只保留基本机制，其他服务在用户态，通过消息传递协作，可靠性和可扩展性较好但通信开销可能更大。

十一、进程控制与线程实现

11.1 PCB 与进程控制

PCB 是进程存在的唯一标志，保存 PID、状态、程序计数器、寄存器、调度和资源信息。进程创建通常包括分配标识与 PCB、分配资源、初始化上下文并进入就绪队列；终止时回收资源并撤销 PCB。

阻塞是进程自身因等待事件而主动发生，唤醒通常由其他进程或中断处理完成；调度和切换由内核控制。进程切换需保存/恢复上下文并切换地址空间，开销通常大于同进程线程切换。

11.2 线程与多线程模型

• 用户级线程：内核不知道线程存在，切换无需内核，但一个线程阻塞系统调用可能使整个进程阻塞，通常难以利用多核并行。
• 内核级线程：由内核调度，可并行，一个线程阻塞不必阻塞同进程其他线程，但切换开销较大。
• 组合方式：多对一、一对一、多对多。

线程共享代码段、数据段、打开文件等进程资源，但各自有线程 ID、程序计数器、寄存器和栈。

11.3 进程通信深化

共享存储速度快但必须用同步机制协调。消息传递分直接和间接（邮箱），也可分阻塞/非阻塞发送接收。管道是固定大小内核缓冲区，普通管道通常半双工且面向字节流；读空管道、写满管道时进程可能阻塞。管道与共享文件不是同一概念。

十二、调度算法计算

12.1 调度层次

• 高级调度（作业调度）：从外存后备队列选择作业进入内存。
• 中级调度：在内外存间挂起/激活进程，提高内存利用率。
• 低级调度（进程调度）：从就绪队列选择进程占用 CPU，频率最高。

不能进行调度/切换的典型时机包括处理中断的关键阶段、持有内核自旋锁等不可抢占临界区；具体以系统和题设为准。发生调度的时机包括进程终止、阻塞、时间片用完或更高优先级进程到达。

12.2 指标与算法细节

1
2
3
4

周转时间 = 完成时刻 - 到达时刻
带权周转时间 = 周转时间 / 服务时间
响应时间 = 首次获得 CPU 时刻 - 到达时刻
等待时间 = 在就绪队列等待的时间总和

SJF 在所有作业同时到达且服务时间已知时可使平均等待时间最小，但可能饥饿；HRRN 的响应比：

1

响应比 = (等待时间 + 服务时间) / 服务时间

等待越久优先级越高，可兼顾长短作业。优先级调度中，“数值越大优先级越高”或相反必须看题设；动态优先级和老化可缓解饥饿。

时间片过大趋近 FCFS，过小则切换开销增大。多级反馈队列通常新进程进入最高优先级队列，各队列时间片逐级增大；用完整时间片仍未完成则降级，高优先级队列可抢占低级进程。

十三、同步互斥经典模型

13.1 软件与硬件方法

单标志法会违背空闲让进；双标志先检查法可能同时进入；双标志后检查法可能都无法进入；Peterson 算法用意愿数组和谦让变量解决两个进程互斥，满足空闲让进、忙则等待和有限等待，但忙等。

硬件方法包括中断屏蔽、TestAndSet、Swap/Exchange、CompareAndSwap。屏蔽中断只适合内核短临界区且对多处理器不足；原子指令可构造自旋锁，等待时不让权，适合等待极短或多核场景。

13.2 信号量题统一方法

先识别：互斥资源、资源数量、前驱关系。互斥信号量初值 1；资源信号量初值为资源数；同步信号量初值通常 0。P 操作申请资源，V 操作释放资源或通知事件。

生产者—消费者（容量 n）：

1
2
3
4

semaphore mutex = 1, empty = n, full = 0

producer: P(empty) -> P(mutex) -> 放入 -> V(mutex) -> V(full)
consumer: P(full)  -> P(mutex) -> 取出 -> V(mutex) -> V(empty)

资源信号量必须先 P，再 P 互斥量，否则可能拿着互斥锁等待资源造成死锁。

读者优先模型用 readcount 和互斥量保护计数，第一个读者锁住写者、最后一个读者释放；可能导致写者饥饿。增加排队信号量可实现读写公平。哲学家问题可通过最多允许四人同时拿筷子、一次原子获取两根筷子或规定奇偶拿取顺序避免死锁。

管程把共享数据及其操作封装，并保证同一时刻只有一个进程在管程内活跃；条件变量的 wait/signal 用于等待条件，不是资源计数信号量。

十四、死锁算法

14.1 资源分配图

进程到资源的请求边表示等待，资源实例到进程的分配边表示已占用。每类资源只有一个实例时，资源分配图存在环是死锁的充分必要条件；有多个实例时，存在环只是可能死锁。

14.2 银行家算法

1
2
3
4
5

Need = Max - Allocation
Work = Available
寻找尚未完成且 Need_i <= Work 的进程 i
Work = Work + Allocation_i，标记 i 完成
重复，若全部可完成则存在安全序列

处理新请求 Request_i 时，先验证 Request_i≤Need_i、Request_i≤Available，再试分配并做安全性检查；若不安全则回滚。安全序列是当前资源状态下的一种完成顺序，不等同于实际 CPU 调度顺序。

14.3 检测与解除

死锁检测与安全性算法形式相似，但检测使用当前请求矩阵。可完全满足的进程视为最终能结束并释放资源；无法消去的进程即死锁相关进程。解除可撤销进程、剥夺资源或回退，需考虑代价和饥饿。

十五、连续内存管理

固定分区会产生内部碎片；动态分区主要产生外部碎片。动态分区分配算法：

• 首次适应：按地址递增，低地址易出现碎片，但综合性能好。
• 邻近适应：从上次位置循环查找，可能使高地址也产生小碎片。
• 最佳适应：按容量递增，容易留下很多难利用的小碎片。
• 最坏适应：优先切割最大分区，可能迅速失去大分区。

回收相邻空闲区时需要合并。紧凑可把分散空闲空间合成大区，但需要动态重定位且移动开销大。

覆盖由程序员安排同一内存区域装入互斥使用的程序段，不要求把进程调出；交换由操作系统在内存与外存对换区之间移动整个进程或其主要部分。

十六、分页、分段与段页式

16.1 基本分页地址转换

页大小 L，逻辑地址 A：

1
2
3

页号 P = floor(A/L)
页内偏移 W = A mod L
物理地址 = 页框号 × L + W

若逻辑地址以 (页号, 偏移) 给出，先检查页号是否越界和页表项有效，再检查偏移是否小于页大小。页表基址寄存器保存页表起始地址，页表长度寄存器用于越界检查。

无 TLB 时，一次数据访问通常先访问页表再访问目标单元，共两次主存；有 TLB 时需按命中率计算平均时间。若 Cache 也参与，应明确 TLB 查找是否与 Cache 并行、页表是否经过 Cache，严格按题设列路径。

16.2 多级页表与反置页表

单级页表可能连续占用大量内存。多级页表把页表本身分页，只把需要的下级页表调入内存，但一次 TLB 未命中的地址转换需要多次访存。顶级页表一般常驻。

反置页表按物理页框建立表项，空间与物理内存大小相关，但按虚页查找较慢，常配合散列。

16.3 分段与段页式

分段地址为 (段号, 段内偏移)。段表项含段基址、段长和权限；先用段长检查越界，再由 基址+偏移 得物理地址。段可独立共享和保护。

段页式先按逻辑模块分段，再把每段分页。逻辑地址含段号、段内页号和页内偏移；无 TLB 时通常依次访问段表、页表和数据。它兼具分段的逻辑性与分页的离散分配，但管理和转换更复杂。

十七、请求分页与页面置换

17.1 缺页与有效访问时间

缺页处理需查找空闲页框或选择淘汰页；脏页先写回；从外存读入所需页；修改页表/TLB；重新执行被中断指令。缺页率虽小，磁盘访问代价巨大。

1

EAT = (1-p)×正常访问时间 + p×缺页处理平均时间

是否把一次失败访存、重启访存、写回时间计入，按题目给定流程展开，不能机械套式。

17.2 置换算法细节

• OPT：淘汰未来最晚使用页，是理论最优，用于评价。
• FIFO：淘汰驻留最久页，可能出现 Belady 异常。
• LRU：淘汰过去最长时间未访问页，栈算法，不出现 Belady 异常。
• CLOCK：访问位为 1 时清零并跳过，找到 0 淘汰。
• 改进 CLOCK：结合访问位和修改位，优先淘汰未访问且未修改页。

分配策略分固定/可变分配，置换范围分局部/全局。固定分配常配局部置换；可变分配可配局部或全局置换。

17.3 抖动与工作集

进程页框过少会频繁缺页，CPU 利用率下降，系统又可能误以为进程不足而调入更多进程，形成抖动。工作集是某时间窗口内访问页面集合的近似，驻留集应覆盖工作集。页故障频率策略根据缺页率动态增减页框。

十八、文件系统深化

18.1 文件属性与操作

文件控制块 FCB 保存文件名、类型、权限、大小、位置和时间等元数据。目录项可直接存 FCB，也可存文件名与索引结点号；UNIX inode 保存除文件名外的主要元数据。打开文件后，系统把相关信息放入系统级和进程级打开文件表，返回文件描述符，减少重复目录检索。

基本操作包括创建、删除、打开、关闭、读、写、定位和截断。open 不等于把整个文件读入内存。

18.2 目录结构与共享保护

目录结构包括单级、两级、树形和无环图。绝对路径从根开始，相对路径从当前目录开始。硬链接指向同一 inode，不能跨文件系统且通常不允许普通用户链接目录；符号链接是保存路径名的特殊文件，可跨文件系统，但目标删除后会悬空。

保护方式包括访问控制矩阵、访问控制表和口令等。权限检查主体、客体及操作类型必须区分。共享文件还需考虑并发访问和锁。

18.3 文件分配

• 连续分配：顺序和随机访问快，外部碎片、扩展困难。
• 链接分配：无外部碎片、便于增长，但随机访问差；FAT 把指针集中在内存表中改善访问。
• 索引分配：索引块保存数据块号，支持随机访问；大文件可用多级索引或混合索引。

若索引块大小为 B、块号占 b 字节，一个索引块可存 B/b 个地址。混合索引最大文件长度等于直接块容量与各级间接块容量之和，注意数据块与索引块都占磁盘块，但最大文件“数据长度”通常只算数据块。

18.4 空闲空间管理

位示图用一位表示一个磁盘块，易于找到连续空闲块；空闲表适合连续空闲区；空闲链表简单但找连续空间慢；成组链接法把空闲块号分组，适合大型文件系统。位号到盘块号的换算要确认行列下标是否从 0 开始。

十九、磁盘与 I/O 管理深化

19.1 I/O 软件层次

典型层次从上到下：用户层 I/O 软件、设备独立性软件、设备驱动程序、中断处理程序、硬件。设备独立性软件提供统一接口、逻辑设备名映射、缓冲和分配；驱动程序与具体控制器密切相关。

设备可按信息交换单位分块设备和字符设备，也可按共享属性分独占、共享和虚拟设备。SPOOLing 利用磁盘模拟脱机输入输出，把独占设备改造成逻辑共享设备；输入井和输出井在磁盘上，输入/输出缓冲区在内存中。

19.2 缓冲

缓冲用于缓和 CPU 与设备速度差、减少中断、提高并行性。单缓冲、双缓冲计算应画出“设备输入—CPU 处理—传送”的流水关系；双缓冲允许设备和 CPU 更充分重叠。循环缓冲适合速度波动，缓冲池可被多个进程共享。

19.3 磁盘调度

计算磁头移动量时要区分是否必须到磁盘端点、初始移动方向、回程是否计入。磁盘访问时间还包括旋转延迟和传输时间，调度算法主要优化寻道时间。

19.4 RAID 与固态存储

RAID 0 条带化无冗余；RAID 1 镜像；RAID 5 分布式奇偶校验，可容忍一个磁盘故障。不同 RAID 的可用容量、读写性能和容错能力按磁盘数和级别计算。

SSD 以页读写、以块擦除，原地覆盖前通常需擦除；闪存转换层完成逻辑到物理地址映射，垃圾回收和磨损均衡会影响写放大与性能。SSD 无机械寻道和旋转延迟，但仍有控制器、通道和擦写开销。

十九-A、补充专题：引导、虚拟化、内存与设备管理

19-A.1 系统引导

典型启动链路为：固件上电自检并初始化硬件 → 选择启动设备 → 加载引导程序 → 引导程序把操作系统内核装入内存 → 内核初始化内存管理、中断、设备驱动和文件系统 → 创建首批用户态进程。

BIOS/UEFI、MBR/GPT 的具体组合因平台而异。408 题目更重视“固件—引导程序—内核”的职责边界：固件不等于操作系统，启动程序也不是常驻的完整内核。

19-A.2 虚拟机

虚拟机监控器（VMM/Hypervisor）为多个客户操作系统提供相互隔离的虚拟硬件环境。

• Ⅰ型直接运行在硬件上；
• Ⅱ型运行在宿主操作系统之上；
• 陷入—模拟：客户机执行敏感操作时陷入 VMM，由 VMM 检查并模拟；
• 硬件辅助虚拟化可降低特权指令和地址转换开销。

虚拟机虚拟化整套硬件并可运行不同内核；容器通常共享宿主机内核，隔离粒度和开销不同，不能视为完全相同的概念。

19-A.3 页框分配与回收

页框分配可采用平均分配、按进程大小比例分配或按优先级分配。置换范围分为：

• 局部置换：只能从本进程已有页框中换出页面，进程间影响较小；
• 全局置换：可从系统可用页框甚至其他进程处获得页框，吞吐量可能更高，但进程间相互影响更明显。

系统可维护空闲页框链表。回收页框时，干净页可直接复用；脏页必须先写回外存。工作集或缺页率方法可动态调节驻留集，缓解抖动。

19-A.4 内存映射文件

内存映射把文件的一部分映射到进程虚拟地址空间。访问映射区像普通内存访问一样，首次访问可能触发缺页，再由内核把对应文件块调入页框。共享映射的修改可对其他映射同一文件区域的进程可见，并最终回写文件；私有映射通常采用写时复制。

内存映射减少了显式 read/write 调用和用户缓冲区复制，但不意味着文件一次性全部进入内存，也不能消除缺页和磁盘 I/O。

19-A.5 VFS

虚拟文件系统（VFS）在系统调用和具体文件系统之间提供统一抽象，使应用可用一致接口访问不同类型的本地或网络文件系统。常见抽象对象包括超级块、索引结点、目录项和打开文件对象；具体名称依操作系统实现而异。

一次路径访问通常经历：解析目录项 → 检查权限 → 定位文件元数据 → 通过页缓存/缓冲区访问数据 → 必要时调用具体文件系统和设备驱动。

19-A.6 设备分配与 SPOOLing

设备可分为独占设备、共享设备和虚拟设备。设备分配时通常依次确定设备、控制器和通道，并维护设备控制表、控制器控制表、通道控制表等数据结构；具体表名以教材为准。为避免死锁，可采用安全分配、统一申请或规定申请顺序。

SPOOLing 利用磁盘上的输入井、输出井以及输入/输出进程，把独占设备改造成逻辑上可被多个进程共享的虚拟设备。打印任务先写入输出井并排队，由后台进程依次送往打印机。它以空间换时间并提高设备利用率，但物理设备在某一时刻仍通常只执行一个任务。

二十、应试导航与题型库

20.1 调度题模板

1. 列出到达时间、服务时间和优先级。
2. 明确抢占/非抢占、时间片长度以及优先数大小含义。
3. 按事件点画甘特图：到达、完成、时间片用尽、被抢占。
4. 周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间。
5. 等待时间的口径依题设；存在 I/O 时不要机械套用“周转减服务”。

20.2 PV 题型库与统一建模

题型：生产者—消费者、读者—写者、哲学家进餐、吸烟者、前驱关系、单行桥、有限缓冲区。

每题强制回答：

1. 并发进程有哪些；共享数据和临界资源是什么；
2. 哪些是互斥约束，哪些是同步先后约束；
3. 每个信号量的语义与初值；
4. P、V 分别放在哪里；
5. 是否可能形成循环等待；是否产生饥饿；
6. 是否错误地在持有互斥锁时执行可能阻塞的同步 P 操作。

20.3 银行家与页面置换模板

• 银行家：计算 Need=Max-Allocation；令 Work=Available；反复寻找 Need≤Work 的进程，完成后令 Work+=Allocation。能遍历全部进程才存在安全序列。
• 页面置换：先写引用串和帧数；逐次记录帧内容、命中/缺页及被换出页。FIFO 看进入先后，LRU 看最近使用，OPT 看未来最晚使用。
• Belady异常：FIFO 可能出现，栈算法 OPT 和 LRU 不出现。
• 有效访问时间：必须读题判断页表、TLB、Cache访问能否并行，以及缺页处理时间是否含内存访问。

20.4 文件与磁盘计算模板

• 索引分配：先求每个索引块可容纳的地址项数，再分别计算直接、一级、二级和三级间接可覆盖的数据块。
• 位示图：明确字长、字号和位号从 0 还是 1 开始，以题设为准。
• 磁盘调度：写明初始磁头位置、初始方向、是否必须到端点、回程是否计入。
• 磁盘访问：访问时间=寻道时间+旋转延迟+传输时间，调度算法主要优化寻道部分。

20.5 错题登记字段

编号｜模型假设｜进程/资源｜时间线或状态表｜错误原因｜修正步骤｜复习日期

二十一、2009—2025 真题融合复习地图

本节按真题常见模型把知识点串联起来。频率标签用于安排复习，不等同于未经逐题核验的精确统计。

21.1 进程、线程与调度

高频 状态转换、进程控制、线程模型、调度算法、周转时间和响应时间。

时间线法：列出到达、运行、阻塞、唤醒、抢占和完成时刻，再计算周转时间、带权周转时间与响应时间。抢占式与非抢占式必须分开。

21.2 同步互斥与死锁

高频 信号量、管程、经典同步问题、死锁条件、银行家算法。

1
2
3

先写语义：mutex=互斥；empty=空位数；full=产品数
再写约束：谁等待谁、谁唤醒谁
最后检查：是否持有 mutex 后执行可能阻塞的 P 操作

21.3 内存与虚拟内存

高频 分页地址转换、多级页表、TLB、缺页处理、页面置换、工作集与抖动。

• 页内偏移位数由页大小决定；多级页表每级索引位数由页表项大小和页表页大小共同决定。
• TLB 未命中不等于缺页；缺页需要操作系统调页，并可能触发页面置换和脏页写回。
• FIFO 可能出现 Belady 异常；LRU 与 OPT 属于栈算法，不出现该异常。

21.4 文件系统与 I/O

高频 文件分配、目录、索引结点、空闲空间管理、磁盘调度、设备控制与 DMA。

索引文件题先求“一个索引块可存多少块号”，再分别计算直接、一级、二级和三级间接的覆盖范围；注意文件大小与磁盘占用空间不是同一概念。

21.5 OS 综合题统一时间线

1
2
3

用户程序 → 系统调用/异常/中断 → 内核态
→ 进程状态变化与调度 → 地址转换/缺页
→ 文件系统与设备驱动 → DMA传送 → 中断完成 → 返回用户态

21.6 经核验真题登记表

历年真题跳转

操作系统在统考卷中通常对应 第 23—32、45—46 题。以下链接可直接进入各年试卷的本科目区域：

• 2009 年操作系统真题

• 2010 年操作系统真题

• 2011 年操作系统真题

• 2012 年操作系统真题

• 2013 年操作系统真题

• 2014 年操作系统真题

• 2015 年操作系统真题

• 2016 年操作系统真题

• 2017 年操作系统真题

• 2018 年操作系统真题

• 2019 年操作系统真题

• 2020 年操作系统真题

• 2021 年操作系统真题

• 2022 年操作系统真题

• 2023 年操作系统真题

• 2024 年操作系统真题

• 2025 年操作系统真题

• 查看 408 历年真题总索引