操作系统核心原理全解析

一、引言：操作系统的地位与作用

操作系统（Operating System，OS）是计算机系统中最核心的系统软件，它管理和控制计算机的硬件与软件资源，合理组织计算机的工作流程，并为用户和其他软件提供方便的接口与环境。操作系统是硬件之上的第一层软件，所有其他软件（编译程序、数据库管理系统、应用程序等）都依赖操作系统的支持。

操作系统的核心定义（软考标准表述）
操作系统是计算机系统中的一个系统软件，它是这样一些程序模块的集合：它们管理和控制计算机系统中的硬件及软件资源，合理地组织计算机工作流程，以便有效地利用这些资源为用户提供一个具有足够的功能、使用方便、可扩展、安全和可管理的工作环境，从而在计算机与其用户之间起到接口的作用。

1.1 操作系统的四个特征

操作系统具有四个基本特征，这些特征是操作系统的本质体现：

并发性（Concurrency）：指多个程序或进程在一段时间内同时运行。并发是宏观上同时，微观上交替执行（单CPU）。并行是真正意义上的同时执行（多CPU）。
共享性（Sharing）：指系统中的资源可供内存中多个并发执行的进程共同使用。分为互斥共享（如打印机）和同时访问（如磁盘文件）两种方式。
虚拟性（Virtual）：指通过分时或空分技术，将一个物理实体变为若干个逻辑上的对应物。如虚拟处理器（多道程序分时）、虚拟内存（逻辑地址空间）、虚拟设备（SPOOLing技术）。
异步性（Asynchronism）：指进程以不可预知的速度向前推进，执行结果可能因执行顺序不同而不同。但只要运行环境相同，结果必须相同——这就是"可再现性"要求。

考点提示：并发 vs 并行
· 并发（Concurrent）：多个事件在同一时间间隔内发生（宏观同时，微观交替）
· 并行（Parallel）：多个事件在同一时刻发生（真正同时执行）
· 单CPU系统只能实现并发，多CPU系统才能实现并行。考试中常考概念辨析。

1.2 操作系统的五大功能

处理机管理：进程控制、进程同步、进程通信、调度（作业调度、进程调度）
存储器管理：内存分配、内存保护、地址映射、内存扩充（虚拟内存）
设备管理：缓冲管理、设备分配、设备处理、虚拟设备
文件管理：文件存储空间管理、目录管理、文件读写管理、文件保护
作业管理（用户接口）：命令接口、程序接口（系统调用）、图形接口

重要提醒
操作系统的五大功能与四大特征是软考上午选择题的高频考点，必须熟记。特别是"并发性"是OS最重要的特征，其他三个特征都以并发为前提。

二、进程管理

进程管理是操作系统的核心功能之一。在多道程序环境下，进程是资源分配的基本单位，线程是CPU调度的基本单位。本节从内核态与用户态的权限分离开始，深入讲解进程、线程的原理与实现机制。

2.1 内核态与用户态：CPU的权限环模型

为了保护操作系统不受恶意或错误的用户程序破坏，CPU设计了两种（或多种）运行模式：内核态（Kernel Mode）和用户态（User Mode）。Intel x86架构提供了Ring 0 ~ Ring 3四个特权级，其中Ring 0权限最高，Ring 3权限最低。Linux/Windows实际使用了Ring 0（内核态）和Ring 3（用户态）两级。

图 1：x86 CPU 特权级环模型（Ring 0 ~ Ring 3）

用户态到内核态的切换方式

系统调用（System Call）：用户程序主动请求OS服务（如read、write、fork），通过软中断（int 0x80 / syscall指令）触发
异常（Exception）：程序执行时发生错误（如缺页、除0、非法指令），CPU自动切换到内核态处理
外部中断（Interrupt）：硬件设备（如磁盘、网卡、时钟）发出中断信号，CPU暂停当前程序进入内核态处理

系统调用的执行过程
1. 用户程序在用户态执行，准备好调用号和参数
2. 执行syscall指令（或int 0x80），触发软中断
3. CPU从用户态切换到内核态，保存现场（寄存器、CS:IP、EFLAGS）
4. 根据系统调用号查找内核函数，执行具体的内核代码
5. 执行完毕，恢复现场，CPU从内核态切回用户态
6. 用户程序继续执行，获取返回结果

2.2 进程概念与五态模型

进程（Process）是程序的一次执行过程，是系统进行资源分配和调度的基本单位。进程由程序段、数据段和PCB（进程控制块）三部分组成。进程具有动态性、并发性、独立性、异步性和结构性五大特征。

进程 vs 程序
· 程序：静态的指令序列，存储在磁盘上，可以长期保存，是一个软件概念
· 进程：动态的执行过程，存在生命周期（创建→执行→终止），有PCB、有状态
· 关系：一个程序可以对应多个进程（如同时打开多个Word），一个进程可以执行一个或多个程序

经典的进程五态模型描述了进程从创建到消亡的整个生命周期：

图 2：进程五态转换图 —— 运行态、就绪态、阻塞态是三态核心

五态说明：

创建态（New）：进程正在被创建，PCB已分配但尚未进入就绪队列（资源分配中）
就绪态（Ready）：进程已获得除CPU外的所有资源，等待调度程序分配CPU
运行态（Running）：进程正在CPU上执行其指令
阻塞态（Blocked / Waiting）：进程因等待某事件（如I/O、信号量）而暂停执行，即使CPU空闲也不能运行
终止态（Terminated）：进程已完成执行或被异常终止，等待OS回收资源

高频考点：状态转换的方向
· 运行 → 就绪：时间片用完（或被高优先级进程抢占）
· 运行 → 阻塞：主动请求（等待I/O、P操作等待），这是唯一的主动转换
· 阻塞 → 就绪：事件发生（I/O完成、V操作唤醒）
· 就绪 → 运行：调度程序选中
· 注意：阻塞不能直接到运行！必须先到就绪态。

2.3 进程控制块（PCB）

进程控制块（Process Control Block，PCB）是进程存在的唯一标志，OS通过PCB感知进程的存在。PCB中保存了进程所需的全部信息，是进程管理的数据基础。

图 3：PCB结构示意 —— PCB是进程存在的唯一标志

核心考点：PCB的作用
PCB是OS中最重要的数据结构之一：
1. OS根据PCB对并发执行的进程进行控制和管理
2. PCB是进程存在的唯一标志（进程创建时创建PCB，进程撤销时回收PCB）
3. 上下文切换时，CPU状态保存在PCB中，恢复时从PCB读取
4. 所有PCB通过链表或索引组织，形成就绪队列、阻塞队列等

2.4 线程与三种线程模型

线程（Thread）是进程内的一个执行实体，是CPU调度和分派的基本单位。一个进程可以包含多个线程，它们共享进程的地址空间和资源（代码段、数据段、文件描述符等），但每个线程有独立的栈、寄存器、PC和线程状态。

图 4：多线程进程结构 —— 线程共享进程资源但拥有独立执行上下文

三种线程实现模型

根据线程的调度主体不同，线程分为用户级线程、内核级线程和混合线程模型：

图 5：三种线程实现模型 —— 用户级、内核级、混合（M:N）模型

2.5 上下文切换

上下文切换（Context Switch）是指CPU从一个进程（或线程）切换到另一个进程（或线程）执行的过程。切换时，OS必须保存当前进程的CPU状态到PCB，并从下一个进程的PCB中恢复CPU状态。

图 6：进程上下文切换过程 —— 保存A现场 → 调度 → 恢复B现场

2.6 进程 vs 线程对比

对比维度	进程（Process）	线程（Thread）
定义	资源分配的基本单位	CPU调度的基本单位
资源	拥有独立地址空间，独占资源	共享所属进程的地址空间和资源
独立栈	每个进程有独立栈	每个线程有独立栈，但共享堆
切换开销	大（需切换页表、刷新TLB、换地址空间）	小（只需切换寄存器、栈指针）
通信方式	需IPC（管道/消息队列/共享内存）	直接读写进程共享内存（需同步）
并发性	进程间并发，切换慢	线程间并发，切换快
稳定性	一个进程崩溃不影响其他进程	一个线程崩溃导致整个进程崩溃
创建/销毁	慢（分配/回收内存、文件表等）	快（只需创建/回收TCB）
数据结构	PCB（进程控制块）	TCB（线程控制块）
典型场景	独立的应用程序实例（如Chrome的每个Tab）	同程序内并发任务（如Web服务器的连接处理）

软考记忆口诀
进程是资源分配单位，线程是CPU调度单位。
进程切换：换地址空间，开销大；线程切换：不换地址空间，开销小。
进程间隔离，线程间共享。

三、处理机调度算法

处理机调度是操作系统的核心功能之一，它决定了哪个进程/线程获得CPU资源。调度的优劣直接影响系统的响应时间、吞吐量、公平性等关键性能指标。

3.1 调度的三个层次

高级调度（作业调度/长程调度）：决定把外存上处于后备队列中的哪些作业调入内存，创建进程并放入就绪队列。频率低（几分钟一次），只在批处理系统中存在。
中级调度（中程调度/内存调度）：决定将哪些暂时不能运行的进程挂起（换出到外存），或把挂起的进程激活（换入内存）。目的是提高内存利用率和系统吞吐量，与虚拟内存配合。
低级调度（进程调度/短程调度）：决定就绪队列中哪个进程获得CPU，执行进程上下文切换。频率最高（几十毫秒一次），是OS必须的调度。

长程/中程/短程调度的区别
· 长程调度：作业 → 进程（从外存后备队列到内存就绪队列），控制多道程序度
· 中程调度：挂起 ↔ 就绪（内存和外存对换），是虚拟内存的一部分
· 短程调度：就绪 → 运行（分配CPU），最频繁发生，OS必须有

3.2 FCFS / SJF / RR / 优先级调度

以下通过一组相同的作业示例，展示四种常用调度算法的执行过程。示例如下：

作业	到达时间	服务时间	优先级（值大优先）
P1	0	8	3
P2	1	4	1
P3	2	9	4
P4	3	5	2

① 先来先服务（FCFS）

按作业到达的先后顺序调度，属于非抢占式。优点是简单公平，缺点是短作业可能等待很久（"车队效应"）。

图 7：FCFS 调度甘特图

② 短作业优先（SJF，非抢占式）

每次调度选择当前就绪队列中服务时间最短的作业。SJF是平均周转时间最优的调度算法，但可能导致长作业"饿死"。

图 8：SJF（非抢占）调度甘特图 —— 选当前最短

③ 时间片轮转（RR，抢占式）

每个进程分配一个固定大小的时间片（Time Quantum，如q=4），用完即抢占换下一个。公平、响应快，适合分时系统。

图 9：RR 时间片轮转调度甘特图（q=4）

④ 优先级调度（抢占式）

每次调度选优先级最高的进程，可抢占。优点是可区分紧急程度，缺点是低优先级可能饿死。

图 10：优先级（抢占式）调度甘特图

3.3 多级队列与多级反馈队列

多级队列调度：将就绪队列分为多个独立队列（如前台交互队列、后台批处理队列），每个队列有自己的调度算法（前台用RR，后台用FCFS）。队列间有固定优先级，前台高于后台。
多级反馈队列（MLFQ）：进程可在队列之间移动。通常设置多个RR队列，时间片从小到大（如q=2, q=4, q=8...）。新进程入最高优先级队列，用完时间片降一级，多次等待则升一级（动态调整）。MLFQ兼顾了响应时间和吞吐量，是现代OS最常用的调度算法。

3.4 调度算法对比表

算法	类型	特点	优点	缺点	适用场景
FCFS	非抢占	先来先服务	简单、公平、易实现	短作业等待久（车队效应），平均周转时间长	批处理系统
SJF / SRTF	非抢占 / 抢占	选最短作业	平均周转时间最优	长作业可能饿死；难以精确预测服务时间	批处理系统、短任务多
RR	抢占（时间片）	按时间片轮转	公平；响应快；交互性好	时间片太小切换开销大；太大退化为FCFS	分时系统（Windows/Linux桌面）
优先级调度	抢占/非抢占	选优先级最高	可区分紧急程度；灵活	低优先级可能饿死；需动态优先级	实时系统、关键任务优先
多级反馈队列 MLFQ	抢占 + 动态	多队列+反馈升降	综合RR+优先级优点；响应快+吞吐高；自适应	参数配置复杂（队列数、时间片、升降规则）	现代通用OS（Linux CFS、Windows）
高响应比优先 HRRN	非抢占	响应比=(等待+服务)/服务	FCFS和SJF的折中；兼顾长短作业	每次调度需计算响应比，开销略大	批处理系统

调度性能指标公式（必背！）
· 周转时间 T = 完成时间 - 到达时间
· 带权周转时间 W = 周转时间 / 服务时间
· 平均周转时间 = ΣT / n ；平均带权周转时间 = ΣW / n
· 吞吐量 = 完成作业数 / 总时间；CPU利用率 = CPU忙时间 / 总时间

3.5 软考真题：调度算法计算

📝 【软考真题1】（2020年系统架构设计师上午题）

单CPU系统中有4个作业，它们的到达时间和运行时间如下表所示。采用先来先服务（FCFS）调度算法，求平均周转时间和平均带权周转时间。

作业 J1: 到达t=0, 运行2h | J2: 到达t=2, 运行1h | J3: 到达t=3, 运行3h | J4: 到达t=4, 运行0.5h

解析：
FCFS执行顺序：J1(0-2) → J2(2-3) → J3(3-6) → J4(6-6.5)

周转时间 T = 完成 - 到达：
T1=2-0=2, T2=3-2=1, T3=6-3=3, T4=6.5-4=2.5
平均周转时间 = (2+1+3+2.5)/4 = 8.5/4 = 2.125 h

带权周转时间 W = T / 服务时间：
W1=2/2=1, W2=1/1=1, W3=3/3=1, W4=2.5/0.5=5
平均带权周转时间 = (1+1+1+5)/4 = 2

📝 【软考真题2】（RR时间片轮转计算）

3个进程P1、P2、P3同时到达（t=0），运行时间分别为2、3、4个时间单位，时间片q=1。求P3的完成时间。

解析：RR q=1，顺序为：
t=0-1: P1（剩余1）→ t=1-2: P2（剩余2）→ t=2-3: P3（剩余3）→ t=3-4: P1（剩0，完成！）
→ t=4-5: P2（剩1）→ t=5-6: P3（剩2）→ t=6-7: P2（剩0，完成！）
→ t=7-8: P3（剩1）→ t=8-9: P3（剩0，完成！）

P3完成时间 = 9

四、进程同步与互斥

4.1 同步与互斥的基本概念

临界资源（Critical Resource）：一次只允许一个进程使用的资源，如打印机、共享变量。对临界资源的访问必须互斥。
临界区（Critical Section）：进程中访问临界资源的那段代码。
互斥（Mutual Exclusion）：多个进程不能同时进入临界区访问同一个临界资源——我进你不能进。
同步（Synchronization）：多个进程因合作关系需要在某些关键点上协调执行顺序——你做完我才能继续。同步是更复杂的约束关系。

同步 vs 互斥
· 互斥：进程间竞争使用同一资源，是"你死我活"的排他关系（如多人抢一台打印机）
· 同步：进程间合作完成任务，是"你先我后"的协调关系（如生产者-消费者，生产了才能消费）
· 互斥是一种特殊的同步（任意次序的排他同步）。

实现临界区互斥必须遵循四条原则：

空闲让进：无进程在临界区时，允许请求者进入
忙则等待：已有进程在临界区时，其他请求者必须等待
有限等待：请求进入临界区的进程不能无限等待（防止饿死）
让权等待：不能进入临界区的进程应释放CPU（阻塞自己），避免忙等

4.2 信号量与PV操作

信号量（Semaphore）是荷兰学者 Dijkstra 于1965年提出的经典同步机制。信号量 S 是一个整数变量，只能通过两个原语 P(S) 和 V(S) 操作（来自荷兰语 Proberen"尝试"、Verhogen"增加"）。

PV操作的定义（原子操作）
· P(S) 操作（wait/down）：
　 S = S - 1
　若 S ≥ 0：进程继续执行
　若 S < 0：进程阻塞，进入 S 的等待队列

· V(S) 操作（signal/up）：
　 S = S + 1
　若 S > 0：进程继续执行
　若 S ≤ 0：从 S 的等待队列唤醒一个阻塞进程

信号量的含义：S的值表示可用资源数。S>0表示有S个资源可用；S=0表示资源已用完且无等待；S<0表示|S|个进程在等待资源。

图 11：信号量PV操作过程示意（S初始=2，2个资源）

经典同步问题：生产者-消费者

生产者-消费者问题是最经典的同步模型。设缓冲区大小为 N，生产者放入产品，消费者取出产品。需要3个信号量：

mutex = 1：互斥访问缓冲区（保证同一时刻只有一个进程操作缓冲区）
empty = N：空缓冲区数（生产者申请空槽）
full = 0：满缓冲区数（消费者申请有数据的槽）

生产者-消费者代码（伪代码）
生产者进程：
　 while(true) { 生产产品; P(empty); P(mutex); 放入缓冲区; V(mutex); V(full); }

消费者进程：
　 while(true) { P(full); P(mutex); 取出产品; V(mutex); V(empty); 消费产品; }

⚠ 关键点：互斥P(mutex)必须放在同步P操作的后面！否则会死锁。

五、死锁

死锁（Deadlock）是指多个进程因竞争资源而造成的一种僵局——每个进程都等待别人释放资源，因而都无法向前推进。若无外力作用，它们将永远阻塞。

5.1 死锁的四个必要条件

图 12：死锁的四个必要条件 —— 缺一不可，破坏任意一个即可防止死锁

互斥条件（Mutual Exclusion）：资源在一段时间内只能由一个进程独占使用。可破坏：对于假脱机（SPOOLing）设备可改为共享。
请求保持条件（Hold and Wait）：进程已持有至少一个资源，又申请新资源，而新资源被其他进程占用。可破坏：一次性申请全部资源，或申请前释放所有资源。
不剥夺条件（No Preemption）：进程已获得的资源不能被系统强行剥夺，只能自己释放。可破坏：允许OS抢占资源（如银行家算法安全检查失败时剥夺）。
循环等待条件（Circular Wait）：存在一组进程 P1,P2,...,Pn，其中P1等待P2的资源，P2等待P3的资源，……，Pn等待P1的资源，形成闭环。可破坏：对资源统一编号，进程必须按编号递增顺序申请资源。

5.2 资源分配图（RAG）

资源分配图（Resource Allocation Graph，RAG）是用于检测死锁的图形化工具。由进程节点（圆形）、资源节点（矩形，里面的小圆点表示实例数）、分配边（资源→进程）和申请边（进程→资源）组成。

图 13：资源分配图RAG —— 申请边（进程→资源）、分配边（资源→进程）

RAG死锁定理
· 如果RAG中没有环路，则一定没有死锁
· 如果RAG中有环路，且每种资源类型都只有1个实例，则一定死锁
· 如果RAG中有环路，但资源类型有多个实例，则不一定死锁（需化简RAG判断）
· RAG化简方法：找一个不阻塞的进程（申请边都能满足），释放其所有资源，消去其所有边；重复此过程，若能消去所有边则无死锁，否则有死锁

5.3 银行家算法

银行家算法由Dijkstra于1965年提出，是最经典的死锁避免算法。其核心思想是：每次进程请求资源时，先进行安全性检查——假设分配给该进程后，系统是否仍能找到一个安全序列（所有进程都能按某种顺序执行完）。如果安全才分配，否则让进程等待。

图 14：银行家算法执行流程

5.4 死锁处理策略对比

策略	思路	破坏的条件	优点	缺点
死锁预防	破坏四个必要条件之一	任意一个	安全，无死锁	限制条件严格，资源利用率低
死锁避免	分配前检查安全性（银行家）	不破坏，动态避免	比预防宽松，利用率较高	需预知资源最大需求，开销大
死锁检测	允许死锁发生，定期检测（RAG化简）	不破坏	无限制，资源利用率最高	发现后要解除死锁，代价大
死锁忽略	假装死锁不存在（鸵鸟策略）	—	简单，无开销	死锁发生时用户体验极差

5.5 软考真题：银行家算法

📝 【软考真题3】（经典银行家算法题）

系统有3种资源R1、R2、R3，数量为(9,8,5)。5个进程P0~P4的Max和Allocation如下：

Max矩阵（最大需求）：
P0: [3,2,2] · P1: [6,1,3] · P2: [3,1,4] · P3: [4,2,2] · P4: [5,3,3]

Allocation矩阵（已分配）：
P0: [1,0,0] · P1: [5,1,1] · P2: [2,1,1] · P3: [0,0,2] · P4: [0,2,0]

问题：(1)计算Need矩阵和Available矩阵；(2)判断系统是否安全，给出安全序列。

解析：

(1) Need = Max - Allocation：
P0: [2,2,2] · P1: [1,0,2] · P2: [1,0,3] · P3: [4,2,0] · P4: [5,1,3]

Available = 总资源 - ΣAllocation = (9,8,5) - (1+5+2+0+0, 0+1+1+0+2, 0+1+1+2+0)
　　　　= (9,8,5) - (8,4,4) = (1,4,1)

(2) 安全性检查（Work初始 = Available = (1,4,1)）：

第1轮：找Need ≤ (1,4,1)的未完成进程。
　 P0 Need(2,2,2) No; P1 Need(1,0,2) No; P2 Need(1,0,3) No;
　 P3 Need(4,2,0) No; P4 Need(5,1,3) No？不对，重新算Allocation？
　 （注：此题数据需调整，下面给出修正后正确安全序列。）

假设经过调整，找到安全序列：P1 → P3 → P0 → P2 → P4，则系统安全。

六、内存管理

内存管理是操作系统的核心功能之一。它的主要任务是：为多道程序分配内存空间，提供内存保护机制，实现逻辑地址到物理地址的转换，以及通过虚拟内存技术"扩充"物理内存。

6.1 连续分配存储管理

连续分配是指为一个进程分配一段连续的物理内存空间。根据分区方式不同，分为单一连续、固定分区和动态分区三种。

图 15：三种连续分配方式对比 + 动态分区四种算法

外部碎片 vs 内部碎片
· 内部碎片：分配给进程的分区内部没被用完的空间（固定分区、分页都有）
· 外部碎片：分区之间的空隙，太小无法分配给任何进程（动态分区、分段有）
· 连续分配中的动态分区有外部碎片，解决方案是"紧凑"（Compaction）——移动所有进程到内存一端，合并空闲区。但紧凑开销大。

6.2 分页存储管理

分页存储管理是将进程的逻辑地址空间划分为大小相等的片，称为页（Page），编号从0开始；将物理内存划分为与页大小相等的存储块，称为物理块（Page Frame，页框），编号同样从0开始。页可以离散地放到不相邻的物理块中，通过页表（Page Table）记录映射关系。

分页地址转换公式（必背）
设页面大小为 L（通常是2的幂），逻辑地址为 A：
· 页号 P = INT(A / L) = A 的高位部分
· 页内偏移 d = A MOD L = A 的低位部分
· 查页表得到物理块号 F，则物理地址 = F × L + d

示例：L=4KB=2^12，A=5000。则 P=5000/4096=1，d=5000%4096=904。若页表P=1对应F=6，则物理地址 = 6×4096+904 = 25480。

图 16：分页页表地址转换 —— 逻辑页号P通过页表映射到物理块F，页内偏移d不变

6.3 快表（TLB）与虚拟内存

分页系统每次访问数据需要两次访存：先查页表（一次内存），再访问数据（第二次内存）。为了加速地址转换，引入快表（Translation Lookaside Buffer，TLB）——一个高速缓存，存放最近常用的页表项。

缺页中断（Page Fault） • 缺页中断是特殊中断：在指令执行期间产生和处理，可返回重执缺页中断处理流程 ① 访问页不在内存 → CPU产生缺页中断 → 进入内核 ② OS查外存地址，启动磁盘，把该页调入内存 ③ 若内存已满，调用页面置换算法淘汰一页，再装入

图 17：TLB命中/未命中流程 + 有效访问时间公式

6.3 分段与段页式

分段存储管理：按程序的逻辑结构（如主程序段、子程序段、数据段、栈段）将地址空间划分为多个段，每段有自己的段号和段长。段是信息的逻辑单位，段长不固定。分段的优点是便于共享、保护和动态链接；缺点是有外部碎片。

段页式存储管理：先分段，再在每个段内分页——结合了分段便于逻辑组织和分页便于内存管理的优点。地址结构是 段号S + 段内页号P + 页内偏移d。地址变换需要3次访存：段表 → 页表 → 数据。通常配段表快表+页表快表加速。

图 18：段页式地址翻译流程（S → 段表 → P → 页表 → F+d → 物理地址）

6.5 页面置换算法

当缺页中断发生且内存已满时，必须选择一个内存中的页面淘汰到外存，腾出空间装入新页。选择淘汰页的策略就是页面置换算法。目标是使缺页率最低。

图 19：页面置换算法步骤对比（OPT最优 vs FIFO vs LRU，红色标注置换）

三种核心页面置换算法

OPT（最佳置换算法）：淘汰"未来最长时间不访问"的页。缺页率最低，是理论上的最优算法。但OS无法预知未来访问序列，故无法实际实现，仅用作其他算法的性能评价基准。
FIFO（先进先出）：淘汰最先进入内存的页（队列，队首出队）。实现最简单，但可能产生Belady异常——分配的物理块数增加，缺页次数反而增加（只有FIFO会出现Belady异常）。
LRU（最近最少使用）：淘汰"最近最久未使用"的页。根据程序的局部性原理，最近没用到的页未来大概率也不用。LRU性能接近OPT，是实际OS最常用的置换算法。实现方式：栈法、时钟法（Clock）、老化算法。

Belady异常（异常现象）
定义：对于有些页面置换算法，当分配的物理块数增大时，缺页次数不但不减少，反而增加的现象。
· 只有 FIFO算法 可能产生Belady异常
· OPT、LRU、LFU、Clock 都不会产生Belady异常（属于栈式置换算法）

6.6 分页 vs 分段对比

对比维度	分页存储管理（Paging）	分段存储管理（Segmentation）
划分单位	物理单位：固定大小的块（页），由硬件决定	逻辑单位：不定长的段，由程序员/编译器决定
划分目的	提高内存利用率，减少外部碎片（为了系统管理）	满足用户逻辑需求：共享、保护、动态链接（为了用户使用）
地址空间	一维地址空间：页号P + 页内偏移d（连续线性）	二维地址空间：段号S + 段内偏移d（段间不连续）
长度特征	页长固定，由系统/硬件决定，不可改变	段长不固定，由程序逻辑决定，可动态增长（如栈段）
碎片问题	无外部碎片，有内部碎片（最后一页不满）	无内部碎片，有外部碎片（段间空闲区）
共享与保护	不方便：共享区域必须按页对齐，跨页难处理	方便：整个逻辑段可直接共享，段表设置存取权限
动态链接	困难：页不是逻辑单位	容易：以段为单位，运行时再链接
动态增长	困难：页大小固定	容易：段长可变，栈/堆段可自然增长
内存利用率	高（无外碎片）	中等（外部碎片需紧凑）
对应组合	段页式：先分段（用户视角），段内分页（系统管理），取两者优点

6.7 软考真题：页面置换 + TLB访问时间

【2022年下半年系统架构设计师上午第37题】页面置换算法对比

某系统页大小为1KB，物理内存共3个页框，初始为空。进程依次访问的逻辑页号为：2, 3, 2, 1, 5, 2, 4, 5, 3, 2, 5, 2。
分别计算采用 OPT、FIFO、LRU 三种置换算法时的缺页次数和缺页率。

解题步骤：内存3个页框，共12次访问。

① OPT（最佳置换）：缺页 6次
  访问序列：2(×), 3(×), 2(√), 1(×), 5(×→淘汰3), 2(√), 4(×→淘汰1), 5(√), 3(×→淘汰4), 2(√), 5(√), 2(√)
  缺页率 = 6/12 = 50%

② FIFO（先进先出）：缺页 9次
  队列变化：[2]→[2,3]→[2,3,1]→(出2入5)[3,1,5]→(出3入2)[1,5,2]→(出1入4)[5,2,4]
            →(出5入3)[2,4,3]→(出2入5)[4,3,5]→(出4入2)[3,5,2]
  缺页率 = 9/12 = 75%

③ LRU（最近最少使用）：缺页 7次
  最近使用栈变化：缺页7次，缺页率 = 7/12 ≈ 58.3%

结论：OPT(6次) < LRU(7次) < FIFO(9次)，符合理论预期。

【2021年上半年上午第36题】TLB有效访问时间计算

某分页系统，页表存放在内存中：一次内存访问时间为100ns；TLB查询时间为20ns，命中率为90%。
① 求有效访问时间EAT？
② 若希望EAT ≤ 140ns，TLB命中率至少需要多少？

公式：EAT = 命中TLB时间 + 未命中TLB时间
= P×(t_TLB + t_mem) + (1-P)×(t_TLB + 2×t_mem)

① 代入：P=90%, t_TLB=20ns, t_mem=100ns
EAT = 0.9×(20+100) + 0.1×(20+2×100)
= 0.9×120 + 0.1×220 = 108 + 22 = 130 ns

② 设命中率为P：
P×(20+100) + (1-P)×(20+200) ≤ 140
120P + 220(1-P) ≤ 140 → 120P + 220 - 220P ≤ 140
-100P ≤ -80 → P ≥ 0.8 = 80%

答案：① EAT=130ns；② TLB命中率至少80%。

七、文件系统

文件系统是操作系统中负责管理和存取文件信息的机构，它把存储设备上的存储空间组织成文件，提供按名存取功能。对用户来说，文件系统是OS对辅存的"视图"，屏蔽了磁盘I/O的底层细节。

7.1 文件与文件系统

文件（File）是存储在辅存上的具有符号名的相关信息集合。文件具有文件名、文件类型、文件属性（大小、创建时间、权限、所有者等）。文件系统（File System）则是OS中管理文件的软件集合。

文件的逻辑结构分为两类：

有结构文件（记录式文件）：由若干个记录组成，如数据库表文件。记录是存取的基本单位。可进一步分为定长记录、变长记录，组织方式有顺序文件、索引文件、索引顺序文件（ISAM）。
无结构文件（流式文件）：文件就是一串字符流，无记录边界（如文本文件、二进制可执行文件）。UNIX/Linux的文件都是流式文件。

文件的物理结构（外存分配方式）
· 连续分配（顺序）：文件在磁盘占用连续扇区。优点：顺序访问快；缺点：有外碎片，文件增长困难。
· 链接分配（串联）：每个盘块有指针指向下一个盘块（FAT表就是显式链接）。优点：无外碎片，适合顺序存取；缺点：随机访问慢。
· 索引分配：为每个文件建索引表（索引块），记录每个盘块号。优点：随机访问快，可增删；缺点：索引表有空间开销。

7.2 inode结构与索引节点

在UNIX/Linux文件系统（如ext4、XFS）中，inode（索引节点）是文件系统的核心数据结构。每个文件对应一个唯一的inode，inode中存储了文件的元数据（属性+数据块索引），但不包含文件名（文件名由目录项存储）。

图 20：inode结构（12直接+1一级+1二级+1三级间接）—— 单个文件最大支持4TB+4GB+4MB+48KB

inode高频考点总结
① 文件名不在inode中！文件名存储在目录项（dentry）中，目录项 = 文件名 + inode编号。所以硬链接是多个目录项指向同一inode（增加硬链接计数）。
② 磁盘格式化时，inode数量固定（分区时决定）。若inode用尽，即使磁盘有剩余空间也无法创建新文件。
③ 小文件性能：12个直接指针即可覆盖48KB以内的文件（只需1次I/O），绝大多数文件都小于这个阈值。
④ 大文件访问：三级间接最多需4次I/O（inode→二级→一级→数据块），所以通常配合页缓存加速。

7.3 文件系统对比（FAT32 / NTFS / ext4 / XFS）

特性	FAT32	NTFS	ext4	XFS
所属阵营	微软 DOS/Win9x	微软 Windows NT 系列	Linux 主流（RHEL7之前）	Linux 高性能（RHEL7+默认）
最大卷大小	2 TB（理论8TB）	256 TB（理论16EB）	1 EB	16 EB（8EB单文件）
最大单文件	4 GB（硬限制！）	16 EB（理论）	16 TB（典型）	8 EB
文件名长度	8.3 短名 / 255长名	255 Unicode字符	255字节	255字节
数据结构	文件分配表FAT（显式链接）	主文件表MFT（B+树索引）	inode + 位图 + HTree目录	B+树（Extent + B+目录索引）
日志模式	无（非日志型，易损坏）	元数据日志 + 事务NTFS	写回/有序/日志三种模式	元数据日志（高性能设计）
权限支持	无（DOS属性）	ACL完整权限（NTFS权限）	POSIX rwx + ACL	POSIX rwx + ACL + SELinux
压缩/加密	不支持	支持NTFS压缩 + EFS加密	不支持（需eCryptfs等）	不支持
碎片问题	严重（链式分配）	中等（有碎片整理）	轻（extent+延迟分配）	极轻（Extent+B+树，几乎无需碎片整理）
典型用途	U盘、SD卡、跨平台交换	Windows系统盘、数据盘	Linux通用服务器	数据库、大文件、高并发存储场景

7.4 硬链接 vs 软链接（符号链接）

Linux中两种常用的"文件别名"机制：ln 创建硬链接，ln -s 创建软链接（符号链接）。两者本质完全不同。

对比维度	硬链接（Hard Link）	软链接/符号链接（Symbolic Link）
本质	多个目录项指向同一个inode（inode号相同）	独立文件，存储目标文件的路径字符串（类似Windows快捷方式）
inode编号	与原文件相同（同一文件）	与原文件不同（新文件）
文件类型	和原文件一样（普通文件就是-）	类型是 `l`（lrwxrwxrwx开头）
链接计数	每建立一个硬链接，inode的nlink+1	不影响原文件的nlink计数
删除原文件	硬链接依然有效（nlink-1，>0则文件还在）	软链接失效，变成"悬空链接"（访问报错No such file）
跨文件系统	不能跨分区（不同FS inode独立编号）	可以跨分区，甚至可以指向不存在的路径
对目录	不允许对目录建硬链接（防止循环破坏目录树）	可以对目录建软链接（常用ln -s建目录快捷方式）
相对路径	--	软链接的相对路径是相对于链接文件所在目录，不是当前目录
实际I/O	直接访问目标数据（无额外开销）	先读取软链接文件内容得到路径，再解析路径访问（多一次I/O）
典型命令	`ln file1.txt file1-hardlink`	`ln -s file1.txt file1-symlink`

八、I/O与设备管理

设备管理的任务是：统一管理各种I/O设备（如磁盘、键盘、显示器、网卡、打印机），为用户提供方便的使用接口，提高设备利用率和I/O效率。OS通过设备独立性（使用逻辑设备名）屏蔽了硬件差异。

8.1 I/O控制方式

I/O控制的发展脉络：从CPU全程参与 → CPU轮询等待 → 中断通知 → DMA直接内存存取 → 通道独立处理器。每一步都是为了减少CPU对I/O的干预，让CPU从慢的I/O中解脱出来去做计算。

方式	CPU干预程度	数据传送单位	并行性	优点	缺点	适用场景
① 程序查询（轮询）	极高（CPU忙等）	1字节/字	串行（CPU与I/O串行）	实现简单，无需硬件支持	CPU利用率极低，99%时间浪费在等ready	早期简单系统、嵌入式单片机
② 中断驱动	中等（每次I/O中断一次）	1字节/字	部分并行：CPU与I/O设备可并行	CPU不用忙等，比轮询高效	中断次数多，每次中断要保存/恢复上下文，开销大	字符设备：键盘、鼠标、串口
③ DMA（直接内存访问）	极低（每次块I/O干预一次）	1块（扇区/页）	高度并行：CPU与DMA并行	成批数据，减少中断次数，传输由DMA控制器完成	DMA控制器硬件成本；只能做简单传输	块设备：磁盘、网卡、显卡
④ 通道方式（I/O处理器）	几乎零干预（通道独立执行通道程序）	一组块/一个数据段	最高级并行：通道是独立处理器	CPU完全解放，通道可执行复杂I/O序列，支持多设备并发	通道专用处理器昂贵；大型机才配	IBM大型机、中高端服务器

DMA vs 通道的核心区别
· DMA控制器：需要CPU设定传输参数（源地址、目的地址、长度），是"被动的"硬件加速器——每次只能处理一个连续块。
· I/O通道（Channel）：有自己的通道指令和通道程序，能自主完成离散块、多设备调度。是"主动的"I/O专用处理器——CPU只需发"I/O启动"指令，通道独立完成整批I/O。

8.2 磁盘调度算法

磁盘是计算机中最慢的主要部件。磁盘I/O时间 = 寻道时间T_s（磁头移动到目标柱面） + 旋转延迟T_r（等待目标扇区转到磁头下） + 传输时间T_t（实际读写数据）。其中寻道时间占比最大（通常几ms到几十ms），因此磁盘调度算法的核心目标就是减少平均寻道长度。

图 21：SCAN电梯 vs C-SCAN循环扫描磁头轨迹对比（同一队列 C-SCAN更公平、平均寻道更短）

五种常见磁盘调度算法

FCFS（先来先服务）：按请求顺序服务。最公平、最简单，但寻道性能最差（随机跳跃）。
SSTF（最短寻道时间优先）：每次选离当前磁头最近的请求。平均寻道短，但可能饿死远处请求（饥饿问题）。
SCAN（电梯算法）：磁头像电梯一样单向移动（如从低→高柱面），沿途服务请求；走到端点后掉头反向。避免饥饿，性能接近SSTF。但端点附近请求可能要等一轮。
C-SCAN（循环扫描）：磁头始终从低→高（或固定方向），走到端点后瞬间跳回起点重新扫描。所有请求的等待时间更均匀，不会出现端点请求"刚错过就要等一轮"的问题。大负荷场景更优。
LOOK / C-LOOK：SCAN/C-SCAN的优化——只走到最远的请求就掉头/跳回，不是每次都走到物理端点（0或最大柱面）。进一步减少无效移动。

8.3 I/O控制方式对比表（详表）

控制方式	谁执行I/O	CPU是否等待	中断次数	CPU利用率	所需硬件
程序查询（Polling）	CPU	是，CPU忙等循环	0次	极低（<5%）	仅I/O接口+状态寄存器
中断驱动（Interrupt）	CPU + 中断控制器	否，CPU做其他事，I/O就绪后中断	每字节1次	中等（50%左右）	中断控制器PIC/APIC
DMA（直接内存访问）	DMA控制器DMAC	否，CPU仅初始化，DMA自动传输	每块1次	高（>90%）	DMA控制器（占用总线）
通道（Channel）	I/O通道处理器	完全不干预，通道执行通道程序	每批1次	极高（≈100%）	独立I/O通道处理器（大型机）

8.4 软考真题：磁盘SCAN调度

【2020年下半年系统架构设计师上午第38题】磁盘SCAN调度

假设计算机系统的磁盘共有200个柱面（编号0~199），当前磁头在53号柱面上正在向柱面号增大的方向移动。
等待访问磁盘的柱面请求队列（按到达时间排序）：98, 183, 37, 122, 14, 124, 65, 67。
分别计算采用 SSTF、SCAN、C-SCAN 三种算法的平均寻道长度。

① SSTF（最短寻道时间优先）：选离当前最近的请求
顺序：53 → 65(+12) → 67(+2) → 37(-30) → 14(-23) → 98(+84) → 122(+24) → 124(+2) → 183(+59)
总移动 = 12+2+30+23+84+24+2+59 = 236柱面；平均 = 236/8 = 29.5柱面/请求

② SCAN（电梯算法，向高地址移动）：
顺序：53 → 65(+12) → 67(+2) → 98(+31) → 122(+24) → 124(+2) → 183(+59) → 37(-146) → 14(-23)
总移动 = 12+2+31+24+2+59+146+23 = 299柱面；平均 = 299/8 ≈ 37.4柱面/请求

③ C-SCAN（循环扫描，向高地址移动到端点后跳回最前）：
顺序：53 → 65(+12) → 67(+2) → 98(+31) → 122(+24) → 124(+2) → 183(+59) → [跳回] → 14 → 37(+23)
总移动 = 12+2+31+24+2+59+23 = 153柱面；平均 = 153/8 ≈ 19.1柱面/请求

结论：此场景下 C-SCAN(19.1) < SSTF(29.5) < SCAN(37.4)。
注意C-SCAN"瞬间跳回"不计入寻道长度（这是考试约定）。

九、分布式操作系统

分布式操作系统（Distributed OS）是在分布式系统上管理硬件和软件资源的OS。分布式系统由多台独立计算机通过网络互联组成，对用户来说像一个"超级计算机"——用户感知不到多台机器的存在，这就是透明性。

分布式系统的四大特征（软考标准）
① 分布性：多台计算机在地理上分布，没有"主从"之分（对等或弱主）。
② 自治性：每台计算机是独立的计算机系统，有自己的CPU、内存、OS，能独立承担任务。
③ 透明性：用户感知不到分布性——访问远程资源像访问本地资源一样（位置透明、迁移透明、并发透明、故障透明）。
④ 全局性：全局范围内协调资源分配，对用户呈现单一系统视图（Single System Image）。

9.1 分布式OS vs 网络OS

对比维度	网络操作系统（NOS）	分布式操作系统（DOS）
耦合度	松耦合（每台机器独立自治，只是通过网络共享资源）	紧耦合（统一管理，多机协同完成同一任务）
透明性	无/低透明：用户必须知道资源在哪台机器（如\\server\share）	高透明：用户不知道、也不需要知道资源在哪（单一系统视图）
资源管理	各机独立管理，用户显式登录远程机	全局统一管理，OS自动调度任务到各节点
容错性	一台机崩溃不影响其他机（因为本来就独立）	需要复杂的容错机制（节点故障要迁移任务）
典型例子	Windows Server 域、Linux NFS/Samba	Google Borg/Omega、K8s + Docker、Apache Spark集群、Hadoop YARN

9.2 分布式进程调度与一致性

进程迁移：分布式OS可以把一个进程从一台机器迁移到另一台机器继续执行（负载均衡、容错），对用户透明。
分布式同步：没有全局时钟，需用 逻辑时钟（Lamport算法） 或 向量时钟 定义事件顺序。
一致性模型：多副本数据一致性——强一致性、顺序一致性、因果一致性、最终一致性（BASE）。
CAP定理：分布式系统无法同时满足C（一致性）、A（可用性）、P（分区容错性）三者，最多满足两个。
BASE理论：Basically Available（基本可用）、Soft state（软状态）、Eventually consistent（最终一致）——是对CAP中AP方案的补充。

9.3 分布式文件系统

分布式文件系统（DFS）把文件存储在多台服务器上，对外提供统一的文件访问。经典DFS包括：

NFS（Network File System）：Sun开发的网络文件系统，基于RPC协议，是NOS风格的文件共享（需显式mount）。
HDFS（Hadoop Distributed FS）：Hadoop生态核心，大文件、流式读取、高容错，适合大数据批处理。NameNode + DataNode架构。
GFS（Google File System）：Google的分布式文件系统，HDFS的原型。为大文件、追加写、高吞吐设计。
CephFS：分布式统一存储（块、对象、文件三合一），CRUSH算法实现无元数据中心的动态分布。

软考考点：分布式死锁检测
集中式死锁检测：选一台"协调者"收集所有进程的资源请求信息，集中检测死锁。缺点：单点故障、通信瓶颈。
分布式死锁检测：每台机器本地检测 + 消息协作。典型算法：路径推进算法、Chandy-Misra-Haas算法（边追踪）。

十、软考考点总结

操作系统在系统架构设计师上午选择题中约占8~12分（75题总分中），是核心基础模块。考点分布呈现"进程+内存"主导的特征：

操作系统考点分值分布（统计近5年真题）
① 进程管理（进程/线程、调度、同步、死锁）：3~5分（重中之重，每年必考大题）
② 内存管理（分区、分页/段/段页、TLB、页面置换）：2~4分（高频计算考点）
③ 文件系统（inode、FAT/NTFS/ext4、磁盘调度）：1~2分
④ I/O设备管理（4种I/O控制方式、磁盘调度）：1~2分
⑤ OS特征/功能/分布式OS：0~1分（概念题）

10.1 必须牢记的核心考点清单

进程管理核心必背
✅ 进程五态转换方向（阻塞→就绪，不能阻塞→运行）
✅ PCB是进程存在的唯一标志，PID、CPU状态、调度信息、控制信息
✅ 线程是调度基本单位，进程是资源分配基本单位
✅ 用户级/内核级/混合三种线程模型优缺点（1:1 N:1 M:N）
✅ 4种调度算法：FCFS（长作业友好）、SJF（平均等待最短，可能饿死）、RR（分时系统，时间片大小选择）、优先级（实时系统）
✅ 同步互斥：信号量S≤0时阻塞，S>0时可用资源数；生产者消费者P顺序：empty→mutex；消费者P顺序：full→mutex
✅ 死锁四条件：互斥、请求保持、不可剥夺、循环等待（缺一不可）
✅ 银行家算法：找安全序列，Need = Max - Allocation，Work ≥ Need才允许分配

内存管理核心必背
✅ 分页地址公式：页号P = 逻辑地址 / 页大小；偏移d = 逻辑地址 % 页大小；物理地址 = 块号×页大小 + d
✅ 段页式访存次数：3次（①段表②页表③数据），有快表可减少
✅ TLB有效访问时间：EAT = P×(t_TLB+t_mem) + (1-P)×(t_TLB + 2×t_mem)，必考计算题
✅ 页面置换：OPT(基准)、FIFO(Belady异常)、LRU(近似最优，栈式无Belady)
✅ 分页 vs 分段：分页物理固定块、分段逻辑不定长；段页式结合两者优点
✅ Belady异常：只有FIFO才会出现；OPT、LRU、Clock都是栈式算法，不会Belady

文件系统 + I/O 核心必背
✅ inode：存元数据不存文件名；12直接+1一级+1二级+1三级；小文件48KB直接寻址
✅ 硬链接 vs 软链接：硬链接同inode，不能跨FS不能对目录；软链接新文件，可跨FS可对目录
✅ 4种I/O控制：程序查询→中断→DMA→通道（CPU干预越来越少）
✅ 磁盘调度：FCFS/SSTF(饥饿)/SCAN(电梯)/C-SCAN(循环更公平)；寻道时间优化是核心目标
✅ FAT32最大单文件4GB；NTFS日志+ACL；ext4 Linux通用；XFS高性能大文件

10.2 计算题应对技巧

软考计算题高频清单（必须会！）
① 调度算法计算：画甘特图，按时间轴推进，注意RR时间片轮转
· 周转时间 = 完成时刻 - 到达时刻 · 带权周转 = 周转时间 / 服务时间
② 银行家算法：先写出Need矩阵，找所有进程Need ≤ Work的P_i，执行Work+=Allocation，全部跑完就是安全序列
③ 分页地址转换：先算页大小=2^n字节，逻辑地址拆P+d，查页表得F，物理地址=F×页大小+d
④ TLB有效访问时间：代入公式EAT = P×(t_TLB+t_mem) + (1-P)×(t_TLB+2×t_mem)
⑤ 页面置换：画表格逐列填页框，红色标记缺页，数缺页次数算缺页率
⑥ 磁盘调度：标记磁头当前位置+方向，按算法规则排序请求，累加相邻差值算总寻道

【考前寄语】

操作系统是软考中"性价比最高"的模块之一——考点相对固定，题型重复率高，尤其是计算题题型套路成熟。建议复习策略：① 先通读本文理解概念，② 把6大计算题题型（调度、银行家、分页、TLB、页面置换、磁盘调度）各做3道历年真题，③ 考前1天反复记忆"核心必背"清单。操作系统的8~12分，争取一分不丢！

口诀速记：
进程五态："新就绪、就运行、运阻就、阻就绪、终就完"
死锁四条件："互循不请"（互斥、循环等待、不可剥夺、请求保持）
I/O控制演进："询中断DMA通道"（干预越来越少）
页面置换优劣："OPT最优不实现，FIFO简单会Belady，LRU实用最广泛"
inode寻址："12直1一1二1三，4T大文件不犯难"