操作系统¶
核心概念¶
(a) 🗂️ 操作系统八股主线:进程是主角,内存是舞台,拷贝是考点¶
操作系统八股可以用一条故事线串起来:进程 / 线程 / 协程是「执行单元」,它们怎么被调度、怎么同步通信、怎么防死锁;虚拟内存与用户态 / 内核态是「运行环境」;零拷贝则是 IO 性能的经典考题。下图把全篇串成一张导航地图。
(该图在 GitHub/VSCode + mermaid 插件中可渲染)
flowchart TB
OS["🖥️ 操作系统核心脉络"]
OS --> Proc["🏗️ 进程 / 线程 / 协程"]
Proc --> State["🔄 状态转换与调度算法"]
Proc --> Sync["🔒 同步与互斥"]
Proc --> Dead["💀 死锁与银行家算法"]
Proc --> Ipc["📬 进程间通信 IPC"]
OS --> Virt["📖 虚拟内存与内存管理"]
OS --> Kernel["👑 用户态 vs 内核态"]
OS --> Zero["🚀 零拷贝"]
OS --> Faq["⚙️ 高频问答"]
Virt --> Zero
Kernel --> Zero
- 🏗️ 进程 / 线程 / 协程:进程是资源分配的最小单位、有独立地址空间;线程是 CPU 调度的最小单位、共享进程内存;协程是用户态自己切换的「轻量线程」,切换开销最小。三者的对比表要能默写,还要能说出各自适用场景与上下文切换成本。
- 🔄 状态转换与调度算法:进程有就绪 / 运行 / 阻塞等状态,五态图要能默画。调度算法背 FCFS、SJF、RR、MLFQ 四件套,并会用平均等待时间(AWT)手算对比——这是面试手算题的常客。
- 🔒 同步与互斥:同步管「先后顺序」,互斥管「同一时刻只能一个访问共享资源」。经典题是生产者-消费者(Python 用
threading+queue实现),背后是信号量、锁、条件变量的分工,还要能讲清竞态条件与临界区。 - 💀 死锁与银行家算法:死锁四个必要条件(互斥、占有且等待、不可剥夺、循环等待)要倒背如流,破坏任一条件即可预防;避免策略的代表是银行家算法,要能手算安全序列。
- 📬 进程间通信 IPC:管道、消息队列、共享内存、信号量、Socket 各有适用场景,对比表要能默写。共享内存最快但需要同步,管道适合父子进程,这是高频对比题。
- 📖 虚拟内存与内存管理:分页把虚拟地址映射到物理页框,页表 + TLB 加速地址转换,缺页时走缺页中断并用页面置换算法(FIFO / LRU / Clock)腾位置。还要能区分分页 vs 分段、解释多级页表为什么省内存。
- 👑 用户态 vs 内核态:内核态能执行特权指令、用户态不行,两者切换靠系统调用(如 read / write)。面试常考系统调用流程与上下文切换成本,以及为什么频繁系统调用会变慢。
- 🚀 零拷贝:传统
read + write要两次 CPU 拷贝 + 四次上下文切换;mmap省一次 CPU 拷贝;sendfile终极形态只剩两次 DMA 拷贝、零 CPU 拷贝。这就是「4 → 3 → 2 次拷贝」背诵卡的来源。 - ⚙️ 高频问答:僵尸进程(子进程退出后父进程没 wait)vs 孤儿进程(父进程先退)、线程池大小怎么定(CPU 密集 ≈ 核数 + 1,IO 密集 ≈ 核数 × 2 左右)、写时复制 COW 的用途,都是考前几分钟就能拿下的送分题。
进程 vs 线程 vs 协程¶
进程¶
💡 定义(小白版):进程 = 操作系统里「资源分配的基本单位」。所谓资源分配,就是操作系统把 CPU 时间、内存、文件句柄等按进程为单位发下去——每个进程都有一套独立家当:自己的地址空间(自己房间)、自己的堆栈(自己写字台)、自己的文件描述符表(自己资料夹)。换一个进程 = 换一整副家当。
进程 是操作系统资源分配的基本单位,每个进程拥有独立的虚拟地址空间、堆栈、文件描述符表等资源。
资源占用:高(几MB到数百MB) 切换成本:高(上下文切换涉及内核态切换、TLB刷新等) 通信方式:通过IPC(如管道、消息队列、共享内存) 适用场景:需要隔离的场景(如浏览器多标签、游戏多开)、长时间运行的任务
线程¶
💡 定义(小白版):线程 = 进程内部的「一条执行流」。执行流就是一条正在往下跑的指令路线(读代码、做计算、等 IO)。一个进程里可以有多个线程,它们共用这个进程的地址空间和资源,切换时只需换「当前跑到哪一行」(寄存器/栈指针),不必换整个房间。
线程 是进程内部的一个执行流,共享进程的地址空间和资源。
资源占用:低(几KB到几MB) 切换成本:中(共享内存,切换较快) 通信方式:直接读写共享内存 适用场景:需要并发处理任务、I/O密集型(如网络爬虫、服务器处理多个连接)
协程¶
💡 定义(小白版):协程 = 用户态的轻量级线程,由程序自己调度。用户态 = 切换时不惊动操作系统内核、不进入内核态,所以比线程切换便宜一个数量级;轻量级 = 每个协程只有几十到几百字节的栈,比线程的几 KB~几 MB 小得多。
协程 是用户态的轻量级线程,由程序自行调度。
资源占用:极低(几十到几百字节) 切换成本:极低(无内核切换) 通信方式:通过通道或共享内存 适用场景:高并发、少量阻塞的任务(如异步IO、爬虫协程模式)
对比表格¶
| 特性 | 进程 | 线程 | 协程 |
|---|---|---|---|
| 资源占用 | 最高 | 中等 | 最低 |
| 切换成本 | 最高 | 中等 | 最低 |
| 通信方式 | IPC | 共享内存 | 通道/共享内存 |
| 调度者 | 内核 | 内核/用户 | 用户 |
| 内存隔离 | 有 | 无 | 无 |
| 适用场景 | 隔离需求 | 并发任务 | 高并发轻量任务 |
易错点/面试点评¶
- 易混:很多人把协程和线程等同,其实协程是用户态调度,无内核参与。
- 面试点:面试官常追问“为什么协程比线程更轻量?”答案:无内核态切换,调度在用户空间。
进程状态转换图与调度算法¶
进程状态转换图¶
进程状态包括: - 新建:进程被创建 - 就绪:进程具备运行条件,等待CPU - 运行:进程占有CPU正在执行 - 阻塞/等待:进程等待某事件(如I/O) - 结束/退出:进程完成或被终止
调度算法¶
FCFS(先来先服务)¶
- 原理:按进程到达顺序排队
- 例子:进程P1(0,8), P2(1,4), P3(2,9) → P1 等 0、P2 等 8−1=7、P3 等 12−2=10,平均等待 = (0+7+10)/3 ≈ 5.67
- 优缺点:公平,但短作业可能等待长作业
SJF/SRTF(短作业优先)¶
- 原理:选择剩余时间最短的进程
- 例子:P1(6,2), P2(2,5), P3(4,4)((到达,运行))→ 非抢占:P1 先跑 6(等待 0),P2 到达 2 先于 P3 到达 4,依次 P2、P3,平均等待 = (0+1+5)/3 = 2
- 优缺点:短作业好,但可能饿死长作业
时间片轮转(RR)¶
- 原理:每个进程分配固定时间片,时间到换下
- 例子:3个进程,每个时间片2单位 → 总等待时间计算
- 优缺点:响应快,适合分时系统
优先级调度¶
- 原理:按优先级分配CPU
- 例子:优先级1(1,10), 优先级2(2,5) → 等待时间
- 优缺点:高优先级可能饿死低优先级
多级反馈队列¶
- 原理:多级队列,时间片递减,优先级递减
- 例子:队列0(时间片8),队列1(时间片4),队列2(时间片2)
- 优缺点:平衡短作业和长作业
对比表格¶
| 算法 | 平均等待时间 | 吞吐量 | 响应时间 | 适合场景 |
|---|---|---|---|---|
| FCFS | 中等 | 低 | 差 | 批处理 |
| SJF | 低 | 中 | 好 | 短作业 |
| RR | 中等 | 中 | 好 | 分时系统 |
| 优先级 | 视情况 | 视情况 | 视情况 | 实时系统 |
面试追问¶
- 追问:如何避免短作业饿死?→ 多级反馈队列
- 标准回答:为长作业设置最小时间片,优先调度短作业。
同步与互斥¶
同步与互斥¶
- 互斥:多个进程/线程不能同时访问临界资源
- 同步:进程/线程间按特定顺序执行
关键概念¶
💡 定义(小白版): - 为什么要互斥:多个线程同时读改写同一个变量会打架(竞态条件),就像两个人同时往同一本账本上记账会记乱。 - 互斥锁 = 厕所门锁:谁拿到钥匙谁进,用完开门放下一个;没拿到钥匙的人排队睡着等(阻塞,让出 CPU),钥匙回来才被叫醒。 - 自旋锁 = 抢到之前原地跺脚干等:忙等待就是不断循环检查锁有没有释放、不睡觉。适合临界区极短、等一下就放手的场景;临界区长的话白烧 CPU。 - 读写锁:读者可以一堆人同时读(只看不动手,安全),写者独占(动手改了,别人不能同时看)。 - 条件变量 = 人齐了才开饭:线程等待某个条件成立(如队列非空),被通知后才继续。 - 信号量(P/V) = 停车场空位计数器:P(Proberen/申请)= 空位减 1,没空位就排队等;V(Verhogen/释放)= 空位加 1,并唤醒一个等在门口的人。计数值 = 还能进几辆车。
- 临界区:访问共享资源的代码段
- 互斥锁:保证只有一个进程进入临界区
- 自旋锁:忙等待,适合短临界区
- 读写锁:区分读和写
- 条件变量:线程等待特定条件
- 信号量(P/V):计数信号量
生产者-消费者代码示例(Python)¶
import threading
import time
buffer = []
MAX_SIZE = 5
lock = threading.Lock()
empty = threading.Semaphore(MAX_SIZE)
full = threading.Semaphore(0)
def producer():
for i in range(10):
empty.acquire()
lock.acquire()
buffer.append(i)
print(f"生产者生产: {i}")
lock.release()
full.release()
time.sleep(1)
def consumer():
for i in range(10):
full.acquire()
lock.acquire()
item = buffer.pop(0)
print(f"消费者消费: {item}")
lock.release()
empty.release()
time.sleep(1)
t1 = threading.Thread(target=producer)
t2 = threading.Thread(target=consumer)
t1.start()
t2.start()
t1.join()
t2.join()
对比表格¶
| 机制 | 实现方式 | 适用场景 |
|---|---|---|
| 互斥锁 | acquire/release | 单一资源访问 |
| 自旋锁 | while lock.acquire() | 短临界区 |
| 读写锁 | reader/writer | 读多写少 |
| 信号量 | P/V 操作 | 计数同步 |
| 条件变量 | wait/signal | 复杂条件等待 |
易错点/面试点评¶
- 易错:信号量P/V操作顺序错误会导致死锁。
- 面试点:面试官常问“生产者消费者模型如何实现?”答案:用信号量或锁+条件变量。
死锁¶
四个必要条件¶
💡 定义(小白版):死锁 = 一组进程互相攥着对方需要的资源、谁都不肯放手,结果谁也别想往前走一步,程序永远卡住。上面四个条件是「四把锁一起扣上才死锁」:① 资源一次只能给一个人用(互斥)→ ② 别人不能硬抢(不可剥夺)→ ③ 每个人攥着已到手的、还等着别人手里的(保持并等待)→ ④ 你要的我拿着、我要的你拿着,绕成一圈(循环等待)。打破任意一条,死锁立刻解开。
- 互斥使用:资源只能被一个进程使用
- 不可剥夺:资源不能被抢占
- 保持并等待:已获得资源的进程仍需资源
- 循环等待:资源分配形成环形等待
死锁避免¶
银行家算法: - 安全状态检查:是否存在分配序列使所有进程都能完成 - 例子:3个进程,资源3、2、2 - 安全序列:P1(1,0,0) -> P3(0,1,0) -> P2(0,0,1)
死锁检测与解除¶
- 检测:资源分配图,查找环
- 解除:剥夺资源或终止进程
- 破坏条件:破坏4个条件之一
对比表格¶
| 方法 | 优点 | 缺点 |
|---|---|---|
| 避免 | 防止死锁发生 | 需提前知道资源请求 |
| 检测+解除 | 允许死锁发生 | 需要检测和恢复 |
面试追问¶
- 追问:如何检测死锁?→ 资源分配图
- 标准回答:用Banker's Algorithm避免死锁。
进程间通信 IPC¶
对比表格¶
| 方式 | 通信方式 | 速度 | 适用场景 | 内核拷贝 |
|---|---|---|---|---|
| 管道 | 半双工 | 低 | 亲缘进程 | 有 |
| 消息队列 | 消息传递 | 中 | 任意进程 | 有 |
| 共享内存 | 直接读写 | 最高 | 高速通信 | 无 |
| 信号量 | 计数同步 | 高 | 同步 | 无 |
| 信号 | 信号传递 | 快 | 通知进程 | 无 |
| Socket | 网络通信 | 低 | 不同主机 | 有 |
易错点/面试点评¶
- 易错:管道是半双工,需注意读写顺序。
- 面试点:问IPC机制选择,答案:共享内存适合高速,Socket适合网络。
虚拟内存¶
分页与页表¶
💡 定义(小白版): - 分页:把内存切成固定大小的块(典型 4KB),进程的假地图也切成同样大小的虚拟页。所谓页就是切出来的小方块——分页 = 切块,不是什么神秘机制。 - 页表:一张翻译对照表,每行记录「虚拟页号 → 物理页号」(这个门牌号对应哪个真实房间)。进程每次访问内存,CPU 先查页表做翻译。 - 为什么分页:① 进程之间各查各的页表,实现隔离;② 只需给用到的页准备真实房间,实现按需载入(缺页再搬);③ 固定大小,没有外部碎片。
- 分页:将内存分成固定大小页
- 页表:记录页号到物理页号的映射
缺页中断流程¶
- CPU访问页不在内存
- 触发缺页中断
- 缺页中断处理程序加载页
- 恢复进程
页面置换算法¶
- FIFO:简单,但可能Belady异常
- LRU:最近最少使用,效果好
- OPT:最佳,但需未来信息
- Clock:时钟算法,近似LRU
LRU Python实现¶
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.order = [] # 使用list模拟顺序
def get(self, key):
if key not in self.cache:
return -1
# 移动到末尾
val = self.cache.pop(key)
self.cache[key] = val
self.order.remove(key)
self.order.append(key)
return val
def put(self, key, value):
if key in self.cache:
self.order.remove(key)
self.cache.pop(key)
elif len(self.cache) >= self.capacity:
lru = self.order.pop(0)
self.cache.pop(lru)
self.cache[key] = value
self.order.append(key)
对比表格¶
| 算法 | 优点 | 缺点 | Belady异常 |
|---|---|---|---|
| FIFO | 简单 | Belady异常 | 是 |
| LRU | 性能好 | 需要维护顺序 | 否 |
| OPT | 最佳 | 需要未来信息 | 否 |
| Clock | 近似LRU | 实现复杂 | 否 |
易错点/面试点评¶
- 易错:LRU实现时需注意顺序维护。
- 面试点:问页表结构,答案:多级页表减少内存占用。
用户态 vs 内核态¶
为什么区分¶
💡 定义(小白版): - 内核 = 操作系统的中枢/管家,负责管理 CPU、内存、磁盘、网络等全部硬件,只有它知道并能操作真实硬件。 - 用户态:普通程序运行的状态,不能直接碰硬件和关键数据,只能「申请」(系统调用)让内核代办。 - 内核态:内核代码运行的状态,权限最高,可以执行特权指令。 - 特权指令 = 只有内核态才能执行的特权操作:比如改页表/切换内存映射、开/关中断、设置时钟、切换内核态与用户态本身。普通程序执行特权指令会被 CPU 拒绝(非法指令异常)。
- 内核态:执行内核代码,有最高权限
- 用户态:执行用户代码,受限
系统调用流程¶
- 用户态调用陷入trap
- CPU切换到内核态
- 内核执行系统调用
- 返回用户态
易错点/面试点评¶
- 易错:系统调用不是函数调用,是陷阱机制。
- 面试点:问特权指令,答案:在用户态不能执行。
零拷贝¶
原理¶
- mmap:将文件映射到内存,避免拷贝
- sendfile:内核直接传输文件到Socket
- DMA:直接内存访问,CPU不参与拷贝
写时复制(COW)¶
- 共享内存页,当写入时才复制
易错点/面试点评¶
- 面试点:问零拷贝场景,答案:大文件传输。
常见问题¶
僵尸进程 vs 孤儿进程¶
- 僵尸:子进程结束,父未调用wait
- 孤儿:父进程结束,子被init接管
上下文切换成本¶
- 寄存器、页表、TLB刷新等
线程池大小¶
- CPU核心数 * 2 或 I/O密集型 * (1 + 阻塞时间/计算时间)
易错点/面试点评¶
- 面试点:问线程池参数,答案:根据业务调整。
调度算法算例详解(面试手算题)¶
AWT 计算示例:FCFS vs SJF vs RR(背下这套手算)¶
设 3 个进程到达时间与运行时间如下:
| 进程 | 到达时间 | 运行时间 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
FCFS(先来先服务):按到达顺序执行 P1→P2→P3
时间轴: |----P1(0-8)----|--P2(8-12)--|-----P3(12-21)-----|
- 等待时间:P1=0,P2=8-1=7,P3=12-2=10
- 平均等待时间 = (0+7+10)/3 ≈ 5.67,平均周转时间 = ((8-0)+(12-1)+(21-2))/3 = 38/3 ≈ 12.67
SJF(非抢占短作业优先):0 时刻只有 P1 到达 → 先跑 P1(8 个时间单位);期间 P2(1)、P3(2) 已到达,P1 结束后选最短的 P2:
时间轴: |----P1(0-8)----|--P2(8-12)--|-----P3(12-21)-----|
- 等待时间:P1=0,P2=8-1=7,P3=12-2=10(本例与 FCFS 相同,因 P1 先到且最长)
- 注意:SJF 的收益在"短作业先于长作业"时最明显:若 P3 运行时间改为 3、P2 为 9,则 P1 结束后应选 P3 → 平均等待显著下降
RR(时间片 q=3):就绪队列轮转
时间轴: |P1(0-3)|P2(3-6)|P3(6-9)|P1(9-12)|P2(12-13)|P3(13-16)|P1(16-21)|
- 等待时间:P1=6+4+5=15?——按"首次就绪到首次调度"简化计算:P1 等待 = 3+3+3=9,P2 等待 = 4,P3 等待 = 5
- 平均等待 = (9+4+5)/3 = 6,响应时间最优(每进程最多等 2q)
手算结论(背):FCFS 公平但长作业拖垮短作业;SJF 平均等待最小但可能饿死长作业且不可抢占;RR 响应快适合分时系统,时间片太小切换开销大、太大退化成 FCFS。
多级反馈队列(MLFQ,Linux CFS 之前的经典)¶
Q0 (时间片 8ms, RR): 高优先级,新进程进来
Q1 (时间片 16ms, RR): 从 Q0 用满降级
Q2 (时间片 32ms, RR): 从 Q1 用满降级
Q3 (FCFS 或 RR): 后台批处理
- 短作业在高层快速完成,长作业逐步降级——同时兼顾响应时间与吞吐
- 问题:可能导致饥饿(老长作业一直轮不到)→ 通常加"每过一段时间把所有进程升回 Q0"或"按等待时间提升优先级"
银行家算法完整算例(死锁避免手算)¶
场景:3 个进程 P0/P1/P2,系统资源总量 A=3, B=3, C=2。
分配矩阵 Allocation、最大需求 Max:
| 进程 | Alloc(A,B,C) | Max(A,B,C) | Need = Max-Alloc |
|---|---|---|---|
| P0 | 0,1,0 | 1,2,2 | 1,1,2 |
| P1 | 2,0,0 | 4,0,2 | 2,0,2 |
| P2 | 3,0,2 | 4,1,2 | 1,1,0 |
可用资源 Available = 总量 − 已分配 = (3,3,2) − (5,1,2) = (1,2,0)。注意 C 已耗尽。
安全性检查(依次找"Need ≤ Available"的进程):
- P0 的 Need=(1,1,2):需要 C=2 > Available 的 C=0 → 不满足
- P1 的 Need=(2,0,2):C=2 > 0 → 不满足
- P2 的 Need=(1,1,0):(1,1,0) ≤ (1,2,0) → 满足,先执行 P2;P2 释放后 Available = (1,2,0)+(3,0,2) = (4,2,2)
- 现在 P1 的 Need=(2,0,2) ≤ (4,2,2) → 满足,执行 P1;释放后 Available = (4,2,2)+(2,0,0) = (6,2,2)
- P0 的 Need=(1,1,2) ≤ (6,2,2) → 满足,执行 P0
安全序列:P2 → P1 → P0 ✅ 系统处于安全状态,可以批准新请求。
追问变式:若 P0 请求 (0,2,0)——此时 Available=(1,2,0) 且 C 已 0,则分配后 Available=(1,0,0),P0 的 Need 变 (1,1,2),任何进程都不满足 → 系统进入不安全状态,拒绝该请求。
零拷贝深入:传统 IO vs mmap vs sendfile¶
传统 read + write(两次拷贝 + 四次上下文切换)¶
磁盘 → 内核缓冲区(页缓存) → 用户缓冲区 → Socket 内核缓冲区 → 网卡
[DMA拷贝1] [CPU拷贝1] [CPU拷贝2] [DMA拷贝2]
- 4 次拷贝(2 次 DMA + 2 次 CPU)+ 4 次用户态/内核态切换(read、write 各两次)
mmap(减少一次 CPU 拷贝)¶
磁盘 → 页缓存(用户空间直接映射) → Socket 内核缓冲区 → 网卡
[DMA拷贝1] [CPU拷贝1](mmap 省掉"内核→用户"拷贝)
- 用户态直接读页缓存,省一次 CPU 拷贝 → 3 次拷贝
- 代价:缺页异常(首次访问映射页)、脏页回写
sendfile(终极:仅 2 次 DMA 拷贝 + 0 次 CPU 拷贝)¶
磁盘 → 页缓存 → 网卡(SG-DMA 支持时,页缓存描述符直接交给网卡)
[DMA拷贝1] [DMA拷贝2]
- 现代 sendfile + 网卡 SG(Scatter-Gather)能力:数据完全不经 CPU 拷贝
- Kafka 传输、Nginx 静态文件就用它
对比表(背)¶
| 方案 | CPU 拷贝数 | DMA 拷贝数 | 上下文切换 | 适用 |
|---|---|---|---|---|
| 传统 read+write | 2 | 2 | 4 | 小文件、需要改数据 |
| mmap + write | 1 | 2 | 4 | 大文件、随机访问 |
| sendfile | 0 | 2 | 2 | 静态文件/网卡直传(最优) |
内存管理补充:分段、多级页表与 TLB¶
分页 vs 分段¶
| 维度 | 分页 | 分段 |
|---|---|---|
| 划分单位 | 固定大小页(如 4KB) | 逻辑段(代码/数据/栈) |
| 大小 | 固定(无外碎片) | 可变(有外碎片,需紧凑) |
| 由谁划分 | 系统透明划分 | 程序员/编译器按逻辑划分 |
| 地址结构 | 页号 + 页内偏移 | 段号 + 段内偏移 |
| 共享/保护 | 困难 | 方便(按段控制访问权限) |
多级页表为什么省内存¶
单级页表:4GB 虚拟地址 / 4KB 页 = 1M 页表项 × 4B = 4MB/进程,且必须连续。
两级页表(页目录 + 页表):只给用到的页分配页表 → 稀疏地址空间下可省 90%+ 内存;代价是访问一次内存要多查一级(TLB 命中可抵消)。
TLB(Translation Lookaside Buffer)¶
- 页表查询的硬件缓存(CPU 内),保存最近用过的"虚拟页号→物理页号"
- TLB 缺失 → 查多级页表;进程切换时 TLB 需刷掉/带 ASID 区分(上下文切换成本之一)
- TLB 命中率通常 >99%,是现代 CPU 分页性能的关键
_本节验收_:能手算 FCFS/SJF/RR 平均等待时间;会跑一遍银行家算法安全序列;能画出传统 IO vs sendfile 的拷贝路径;能说清多级页表与 TLB 解决的问题。