操作系统¶
面试定位:进程/线程/协程、调度、同步互斥、死锁、虚拟内存、零拷贝 是后端岗必考。 标记:🔴 必背 / 🟡 掌握 / 🟢 了解。本 notebook 配套
02-操作系统.md速查文档,全部代码可运行。
核心概念¶
(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,Average Waiting Time)手算对比——这是面试手算题的常客。
- 🔒 同步与互斥:同步管「先后顺序」,互斥管「同一时刻只能一个访问共享资源」。经典题是生产者-消费者(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 协程¶
配图来源:手绘 SVG(images/os_process_states.svg)
进程¶
进程 是操作系统资源分配的基本单位,每个进程拥有独立的虚拟地址空间、堆栈、文件描述符表等资源。
资源占用:高(几MB到数百MB) 切换成本:高(上下文切换涉及内核态切换、TLB刷新等) 通信方式:通过IPC(如管道、消息队列、共享内存) 适用场景:需要隔离的场景(如浏览器多标签、游戏多开)、长时间运行的任务
💡 定义(小白版):进程 = 操作系统里「资源分配的基本单位」。所谓资源分配,就是操作系统把 CPU 时间、内存、文件句柄等按进程为单位发下去——每个进程都有一套独立家当:自己的地址空间(自己房间)、自己的堆栈(自己写字台)、自己的文件描述符表(自己资料夹)。换一个进程 = 换一整副家当。
🏢 类比:进程 = 一家公司。每家公司有独立办公室(独立地址空间)、独立账本(文件描述符表)、独立员工名册;公司之间不串门,要合作只能走公共渠道(IPC)。
线程¶
线程 是进程内部的一个执行流,共享进程的地址空间和资源。
资源占用:低(几KB到几MB) 切换成本:中(共享内存,切换较快) 通信方式:直接读写共享内存 适用场景:需要并发处理任务、I/O密集型(如网络爬虫、服务器处理多个连接)
💡 定义(小白版):线程 = 进程内部的「一条执行流」。执行流就是一条正在往下跑的指令路线(读代码、做计算、等 IO)。一个进程里可以有多个线程,它们共用这个进程的地址空间和资源,切换时只需换「当前跑到哪一行」(寄存器/栈指针),不必换整个房间。
🏢 类比:线程 = 公司里的员工。同一家公司的员工坐在同一间办公室(共享地址空间)、共用文件柜(共享资源),互相借东西很快(共享内存通信);但员工多了要协调,别抢同一支笔(要加锁)。
协程¶
协程 是用户态的轻量级线程,由程序自行调度。
资源占用:极低(几十到几百字节) 切换成本:极低(无内核切换) 通信方式:通过通道或共享内存 适用场景:高并发、少量阻塞的任务(如异步IO、爬虫协程模式)
💡 定义(小白版):协程 = 用户态的轻量级线程,由程序自己调度。用户态 = 切换时不惊动操作系统内核、不进入内核态,所以比线程切换便宜一个数量级;轻量级 = 每个协程只有几十到几百字节的栈,比线程的几 KB~几 MB 小得多。
🏢 类比:协程 = 员工在自己工位上轮班:员工 A 做一半发现要等订单回包,自己把工位让给员工 B(await 主动挂起),不需要惊动保安或经理(内核)来安排。所以协程切换 = 员工内部换班,最快。
对比表格¶
| 特性 | 进程 | 线程 | 协程 |
|---|---|---|---|
| 资源占用 | 最高 | 中等 | 最低 |
| 切换成本 | 最高 | 中等 | 最低 |
| 通信方式 | IPC | 共享内存 | 通道/共享内存 |
| 调度者 | 内核 | 内核/用户 | 用户 |
| 内存隔离 | 有 | 无 | 无 |
| 适用场景 | 隔离需求 | 并发任务 | 高并发轻量任务 |
进程状态转换图与调度算法¶
调度算法¶
FCFS(先来先服务)¶
- 原理:按进程到达顺序排队
- 例子:进程P1(0,8), P2(1,4), P3(2,9),括号含义为(到达时间, 运行时间)→ 按到达顺序执行 P1→P2→P3:P1 等待 0,P2 等待 8−1=7,P3 等待 12−2=10 → 平均等待时间 = (0+7+10)/3 ≈ 5.67(完整手算见下文 cell 53)
- 优缺点:公平,但短作业可能等待长作业
SJF/SRTF(短作业优先)¶
- 原理:选择剩余时间最短的进程
- 例子:P1(6,2), P2(2,5), P3(4,4),括号含义为(到达时间, 运行时间):t=2 只有 P2 到达 → 先跑 P2(2→7);t=7 时 P1(运行 2)、P3(运行 4)都在等 → 选最短的 P1(7→9);最后 P3(9→13)。等待时间 P1=7−6=1、P2=0、P3=9−4=5 → 平均等待时间 = (1+0+5)/3 = 2
- 优缺点:短作业好,但可能饿死长作业
时间片轮转(RR)¶
- 原理:每个进程分配固定时间片,时间到换下
- 例子:沿用 FCFS 的进程 P1(0,8), P2(1,4), P3(2,9),时间片 q=3 时平均等待 ≈ 6(简化口径,完整推导见下文 cell 53)
- 优缺点:响应快,适合分时系统
优先级调度¶
- 原理:按优先级分配CPU
- 例子:P1(0,10,高优先级)、P2(2,5,低优先级),括号含义为(到达时间, 运行时间, 优先级):P1 先到且优先级高 → 先跑 P1(0→10);P2 第 2 时刻到达、等到第 10 时刻才运行 → P2 等待时间 = 10−2 = 8
- 优缺点:高优先级可能饿死低优先级
多级反馈队列¶
- 原理:多级队列,时间片递减,优先级递减
- 例子:队列0(时间片8),队列1(时间片4),队列2(时间片2)
- 优缺点:平衡短作业和长作业
对比表格¶
| 算法 | 平均等待时间 | 吞吐量 | 响应时间 | 适合场景 |
|---|---|---|---|---|
| FCFS | 中等 | 低 | 差 | 批处理 |
| SJF | 低 | 中 | 好 | 短作业 |
| RR | 中等 | 中 | 好 | 分时系统 |
| 优先级 | 视情况 | 视情况 | 视情况 | 实时系统 |
同步与互斥¶
同步与互斥¶
- 互斥:多个进程/线程不能同时访问临界资源
- 同步:进程/线程间按特定顺序执行
关键概念¶
- 临界区:访问共享资源的代码段
- 互斥锁:保证只有一个进程进入临界区
- 自旋锁:忙等待,适合短临界区
- 读写锁:区分读和写
- 条件变量:线程等待特定条件
- 信号量(P/V):一个计数器——P 申请(减 1)、V 释放(加 1),控制同时访问资源的上限(如停车场空位)
💡 定义(小白版):
- 为什么要互斥:多个线程同时读改写同一个变量会打架(竞态条件),就像两个人同时往同一本账本上记账会记乱。
- 互斥锁 = 厕所门锁:谁拿到钥匙谁进,用完开门放下一个;没拿到钥匙的人排队睡着等(阻塞,让出 CPU),钥匙回来才被叫醒。
- 自旋锁 = 抢到之前原地跺脚干等:忙等待就是不断循环检查锁有没有释放、不睡觉。适合临界区极短、等一下就放手的场景;临界区长的话白烧 CPU。
- 读写锁:读者可以一堆人同时读(只看不动手,安全),写者独占(动手改了,别人不能同时看)。
- 条件变量 = 人齐了才开饭:线程等待某个条件成立(如队列非空),被通知后才继续。
- 信号量(P/V) = 停车场空位计数器:P(Proberen/申请)= 空位减 1,没空位就排队等;V(Verhogen/释放)= 空位加 1,并唤醒一个等在门口的人。计数值 = 还能进几辆车。
生产者-消费者代码示例(Python)¶
🧩 这段代码怎么配合的(信号量实战,先看解释再跑代码):
empty = Semaphore(5):记录缓冲区还剩几个空位(初始 5 个,即最多放 5 件货);full = Semaphore(0):记录缓冲区已装几件货(初始 0 件)。- 生产者:先
empty.acquire()—— 申请一个空位(P 操作,空位减 1,满了就阻塞等待);放货成功后full.release()—— 货物加 1(V 操作),唤醒等在取货的消费者。- 消费者:先
full.acquire()—— 申请一件货(P 操作,没货就阻塞等待);取走货后empty.release()—— 空位加 1(V 操作),唤醒等在放货的生产者。- 两个信号量一唱一和:保证缓冲区不满才能放、不空才能取;中间的
lock(互斥锁)只负责「同一时刻只有一个线程在修改 buffer 列表本身」,防止两个人同时往列表里写。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
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(0.05)
def consumer():
for i in range(10):
full.acquire()
lock.acquire()
item = buffer.pop(0)
print(f"消费者消费: {item}")
lock.release()
empty.release()
time.sleep(0.05)
t1 = threading.Thread(target=producer)
t2 = threading.Thread(target=consumer)
t1.start()
t2.start()
t1.join()
t2.join()
生产者生产: 0 消费者消费: 0 生产者生产: 1 消费者消费: 1 生产者生产: 2 消费者消费: 2 生产者生产: 3 消费者消费: 3 生产者生产: 4 消费者消费: 4
生产者生产: 5 消费者消费: 5 生产者生产: 6 消费者消费: 6 生产者生产: 7 消费者消费: 7 生产者生产: 8 消费者消费: 8 生产者生产: 9 消费者消费: 9
对比表格¶
| 机制 | 实现方式 | 适用场景 |
|---|---|---|
| 互斥锁 | acquire/release | 单一资源访问 |
| 自旋锁 | while lock.acquire() | 短临界区 |
| 读写锁 | reader/writer | 读多写少 |
| 信号量 | P/V 操作 | 计数同步 |
| 条件变量 | wait/signal | 复杂条件等待 |
死锁¶
四个必要条件¶
- 互斥使用:资源只能被一个进程使用
- 不可剥夺:资源不能被抢占
- 保持并等待:已获得资源的进程仍需资源
- 循环等待:资源分配形成环形等待
💡 定义(小白版):死锁 = 一组进程互相攥着对方需要的资源、谁都不肯放手,结果谁也别想往前走一步,程序永远卡住。上面四个条件是「四把锁一起扣上才死锁」:① 资源一次只能给一个人用(互斥)→ ② 别人不能硬抢(不可剥夺)→ ③ 每个人攥着已到手的、还等着别人手里的(保持并等待)→ ④ 你要的我拿着、我要的你拿着,绕成一圈(循环等待)。打破任意一条,死锁立刻解开。
🚦 类比:十字路口四辆车互相堵死:每辆车都占着一个方向(互斥),谁都不肯倒车(不可剥夺),都想等别人先让(保持并等待),结果 A 等 B、B 等 C、C 等 D、D 等 A 绕成环(循环等待)。只要有一个人倒车让路,死锁就解开了。
死锁避免¶
银行家算法:
- 安全状态检查:是否存在分配序列使所有进程都能完成
- 术语:Need(还差多少) = Max(最大需求) − Allocation(已分到)
- 完整可手算的算例见下文 cell 55:3 个进程 P0/P1/P2,资源总量 (A,B,C)=(3,3,2),安全序列 P2 → P1 → P0;元组 (a,b,c) 依次是 A、B、C 三种资源的数量
死锁检测与解除¶
- 检测:资源分配图,查找环
- 解除:剥夺资源或终止进程
- 破坏条件:破坏4个条件之一
🔍 资源分配图逐步做法(面试手画):
- 画两类节点:圆圈 = 进程(P1、P2…),方块 = 资源(R1、R2…)。
- 画「资源 → 进程」的边:该资源已分配给这个进程(表示「我持有你」)。
- 画「进程 → 资源」的边:该进程正在等待这个资源(表示「我想要你」)。
- 沿箭头找环:从某节点出发能走回自己 = 有环。每类资源只有一份时,有环 = 死锁;多份资源时还要再核对每个进程持有/等待的具体数量。
- 解除三招:剥夺资源(从 P1 手里抢过来给 P2)、终止进程(回滚重来)、破坏循环等待(资源按编号从小到大申请)。
- 代码验证:下文 cell 70
deadlock_detect.py用 DFS 三色标记找环,能直接跑。
对比表格¶
| 方法 | 优点 | 缺点 |
|---|---|---|
| 避免 | 防止死锁发生 | 需提前知道资源请求 |
| 检测+解除 | 允许死锁发生 | 需要检测和恢复 |
进程间通信 IPC¶
💡 IPC 六机制定义(小白版):
- 管道:两个进程之间的水管,A 的输出接进 B 的输入,水只能单向流(半双工)。适合父子等亲缘进程,简单但慢。
- 消息队列:进程把消息投进内核里的邮筒(队列),别的进程随时来取,不必双方同时在线;适合任意进程,按消息为单位传递。
- 共享内存:内核划一块公共白板,多个进程直接在上面写写画画——最快(无内核拷贝),但要自己协调别同时改同一块区域(得配信号量/锁),否则数据乱。
- 信号量:严格说是同步机制而非通信机制——它不搬数据,只当空位计数器(P 减 V 加),保证多个进程配合的节奏。
- 信号:内核给进程发对讲机广播(如 Ctrl+C 发 SIGINT),异步通知「有事件要处理」,不传数据只传事件。
- Socket:跨主机通信的邮局系统(信封 + 地址 + 邮递员),进程把数据装进信封寄出去走网络;本机两个进程也能用(Unix Domain Socket)。
⚠️ 易混点:表格把信号量列为通信方式之一,但它本质是同步手段(管秩序不管数据)。面试主动点破这个边界是加分项。
对比表格¶
| 方式 | 通信方式 | 速度 | 适用场景 | 内核拷贝 |
|---|---|---|---|---|
| 管道 | 半双工 | 低 | 亲缘进程 | 有 |
| 消息队列 | 消息传递 | 中 | 任意进程 | 有 |
| 共享内存 | 直接读写 | 最高 | 高速通信 | 无 |
| 信号量 | 计数同步 | 高 | 同步 | 无 |
| 信号 | 异步通知(事件) | 快 | 通知进程(如 Ctrl+C 发 SIGINT) | 无 |
| Socket | 网络通信 | 低 | 不同主机 | 有 |
虚拟内存¶
什么是虚拟内存、为什么需要它¶
💡 定义(小白版):虚拟内存 = 给每个进程发一张假地图(虚拟地址空间,32 位下 4GB)。进程以为自己独占整块内存、随便用;真正的物理内存是真实房间,由操作系统悄悄完成「地图上的门牌号 → 真实房间号」的翻译。
为什么要这么绕?三个原因:
- 隔离:每个进程各拿各的地图,谁也不会踩进别人的房间(进程 A 的地址 0x100 和进程 B 的地址 0x100 是两个不同的真实房间)。
- 装下比物理内存大的程序:地图可以比真实房间多得多,用到哪间才临时搬进来(按需载入),用不到的先放在磁盘上。
- 方便共享:想让两个进程共享一段数据,只需让两张地图的某两个门牌指向同一个真实房间。
🏨 类比:虚拟内存 = 酒店的楼层分布图。每个客人(进程)手里都有一张整栋楼的平面图,想去哪层都画在上面;但酒店只有有限的真实房间(物理内存),前台(操作系统)按平面图上的门牌号把客人临时安排进真实房间。客人们互不知道对方住哪间,秩序由前台统一管理。
配图来源:手绘 SVG(images/os_paging.svg)
分页与页表¶
- 分页:将内存分成固定大小页
- 页表:记录页号到物理页号的映射
💡 定义(小白版):
- 分页:把内存切成固定大小的块(典型 4KB),进程的假地图也切成同样大小的虚拟页。所谓页就是切出来的小方块——分页 = 切块,不是什么神秘机制。
- 页表:一张翻译对照表,每行记录「虚拟页号 → 物理页号」(这个门牌号对应哪个真实房间)。进程每次访问内存,CPU 先查页表做翻译。
- 为什么分页:① 进程之间各查各的页表,实现隔离;② 只需给用到的页准备真实房间,实现按需载入(缺页再搬);③ 固定大小,没有外部碎片。
📖 类比:分页 = 把一本大书拆成固定页数的册子(如 1000 页的书拆成 250 本 4 页小册子)。每本册子在书架的哪一格(物理内存),记在索引目录(页表)里。要找第 328 页 → 查目录:第 82 册在第 15 格 → 直接去 15 格取。
缺页中断流程¶
- CPU 访问虚拟页号 P:先查 TLB/页表
- 发现页表项有效位 = 0(该页不在物理内存)→ CPU 暂停当前指令,触发缺页中断(page fault),陷入内核态
- 内核的缺页处理程序检查这次访问是否合法:越界/越权 → 报段错误并终止进程;合法 → 继续
- 找一个空闲页框;没有空闲就按页面置换算法(FIFO/LRU/Clock)踢出一页(若该页被写过、脏位=1,先写回磁盘)
- 从磁盘读入目标页到页框(这期间进程阻塞等待磁盘 IO)
- 更新页表项:填上物理页号、把有效位置 1
- 重新执行刚才那条被中断的指令(这次能正常访问了)
页面置换算法¶
- FIFO:简单,但可能Belady异常
- LRU:最近最少使用,效果好
- OPT:最佳,但需未来信息
- Clock:时钟算法,近似LRU
🔄 页面置换逐步过程(以容量 3、访问序列 1 2 3 4 1 2 5 …为例):
- FIFO(先来先淘汰):内存队列 [1,2,3] → 访问 4 时队头 1 被淘汰,变 [2,3,4] → 访问 1 时队头 2 被淘汰…规则 = 最早进来的最先走。缺点:可能把常用页踢掉,且会发生 Belady 异常(容量 3→4 缺页数反而变多,见 cell 68 代码)。
- LRU(最近最少使用):谁最久没被碰谁先走。访问 4 时 [1,2,3] 里 1 最久没用 → 淘汰 1;访问 1 时最久没用的是 2 → 淘汰 2。效果接近最优,但要维护访问顺序(有额外代价)。
- OPT(最佳):谁未来最晚才被用到谁先走——需要预知未来,现实中做不到,只当理论下界参考。
- Clock(时钟/二次机会):LRU 的低成本近似:页框排成环,每页带一个访问位(0/1);指针转圈,遇到访问位=0 就淘汰,遇到 1 就把位清零(给第二次机会)再转。效果接近 LRU,但每个页只需一个位。
验证代码:下文 cell 68
page_repl.py直接跑缺页数对比,容量 3→4 时 FIFO 缺页 9→10,正好演示 Belady 异常。
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 | 实现复杂 | 否 |
用户态 vs 内核态¶
为什么区分¶
- 内核态:执行内核代码,有最高权限
- 用户态:执行用户代码,受限
💡 定义(小白版):
- 内核 = 操作系统的中枢/管家,负责管理 CPU、内存、磁盘、网络等全部硬件,只有它知道并能操作真实硬件。
- 用户态:普通程序运行的状态,不能直接碰硬件和关键数据,只能「申请」(系统调用)让内核代办。
- 内核态:内核代码运行的状态,权限最高,可以执行特权指令。
- 特权指令 = 只有内核态才能执行的特权操作:比如改页表/切换内存映射、开/关中断、设置时钟、切换内核态与用户态本身。普通程序执行特权指令会被 CPU 拒绝(非法指令异常)。
🛡️ 类比:普通用户程序 = 普通员工(能用自己的工位和文件);内核 = 保安队长(能开特权门:机房、配电房、总闸)。员工不能自己开总闸(特权指令),只能按流程申请(系统调用)让保安队长代办。
系统调用流程(以 read 为例,逐步)¶
- 应用程序(用户态)调用
read(fd, buf, n)—— 这是 libc 库函数(C 标准库的封装) - libc 把系统调用号放进寄存器,执行一条 trap(陷入)指令:这条指令会触发 CPU 从用户态切换到内核态
- CPU 通过中断向量表跳到内核的系统调用入口,先保存用户态现场(寄存器等)
- 内核按系统调用号查表,执行真正的
read实现:从磁盘/网卡等设备取数据 - 内核把结果放回寄存器,执行返回指令,恢复用户态现场
- 回到用户态,
read()正常返回给应用程序
一句话串讲:应用 → libc 封装 → trap 陷入内核 → 内核查表执行 → 返回用户态。整个过程要经历两次用户态/内核态切换,所以频繁系统调用会变慢。
零拷贝¶
原理¶
- mmap:将文件映射到内存(用户空间直接读页缓存),省一次「内核→用户」的 CPU 拷贝——注意不是「完全避免拷贝」,拷贝次数从 4 次降到 3 次,详见下文 cell 58
- sendfile:内核直接传输文件到Socket
- DMA:直接内存访问,CPU不参与拷贝
写时复制(COW)¶
- 共享内存页,当写入时才复制
常见问题¶
僵尸进程 vs 孤儿进程¶
- 僵尸:子进程结束,父未调用wait
- 孤儿:父进程结束,子被init接管
上下文切换成本¶
- 寄存器、页表、TLB刷新等
线程池大小¶
- CPU 密集型 ≈ 核数 + 1(如 8 核 ≈ 9 个线程/进程,留出系统余量,避免线程互相抢 CPU 反而变慢)
- I/O 密集型 ≈ 核数 × 2 左右(8 核 ≈ 16 个线程);更精确的写法是 核数 /(1 − 阻塞占比),阻塞占比 50% 时恰好等于 2×核数,两式同源
- 代码验证:下文 cell 73
pool_size.py按「核数 /(1 − 阻塞占比)」和「核数 × 1.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 解决的问题。
🔴 必背总结卡(进程/线程/协程 + 进程五态)¶
一句话版¶
- 进程:资源分配基本单位,独立地址空间,通信靠 IPC,切换成本最高
- 线程:CPU 调度基本单位,共享进程地址空间,靠锁/条件变量同步
- 协程:用户态轻量调度,无内核参与,切换成本最低,适合 IO 密集
进程五态(背)¶
新建 → 就绪 ⇄ 运行 → 阻塞 → 就绪 → 终止
↑_______________|
- 就绪→运行:调度器分配 CPU;运行→就绪:时间片用完被抢占
- 运行→阻塞:等待 IO/锁/事件;阻塞→就绪:等待的事件完成
- 面试追问:为什么线程切换比进程切换快?→ 同进程线程共享地址空间,只需换寄存器/栈/PC,无需换页表刷 TLB
# schedule_sim.py —— FCFS / SJF(非抢占) / RR 平均等待时间数值验证(对应手算题 P1(0,8) P2(1,4) P3(2,9))
from collections import deque
def fcfs(jobs):
jobs = sorted(jobs)
t, waits = 0, []
for a, r in jobs:
if t < a:
t = a
waits.append(t - a)
t += r
return sum(waits) / len(waits)
def sjf_nonpreemptive(jobs):
jobs = sorted(jobs)
n = len(jobs)
t = jobs[0][0]
rest = [r for _, r in jobs]
done = [False] * n
waits = [0.0] * n
for _ in range(n):
cand = [i for i in range(n) if jobs[i][0] <= t and not done[i]]
if not cand:
t = min(jobs[i][0] for i in range(n) if not done[i])
cand = [i for i in range(n) if jobs[i][0] <= t and not done[i]]
i = min(cand, key=lambda k: rest[k])
done[i] = True
waits[i] = t - jobs[i][0]
t += rest[i]
return sum(waits) / n
def rr(jobs, q):
jobs = sorted(jobs)
n = len(jobs)
rest = [r for _, r in jobs]
comp = [0.0] * n
done = [False] * n
t = jobs[0][0]
order = deque()
finish = 0
def enqueue_new(cur):
for i in range(n):
if not done[i] and jobs[i][0] <= cur and i not in order:
order.append(i)
enqueue_new(t)
while finish < n:
if not order:
t = min(jobs[i][0] for i in range(n) if not done[i])
enqueue_new(t)
continue
i = order.popleft()
run = min(q, rest[i])
rest[i] -= run
t += run
enqueue_new(t)
if rest[i] > 0:
order.append(i)
else:
done[i] = True
comp[i] = t
finish += 1
# 严格口径: 等待 = 完成时间 - 到达时间 - 运行时间
return sum(comp[i] - jobs[i][0] - jobs[i][1] for i in range(n)) / n
jobs = [(0, 8), (1, 4), (2, 9)]
print(f'FCFS 平均等待: {fcfs(jobs):.2f} 手算 ≈5.67 ✓')
print(f'SJF(非抢占) 平均等待: {sjf_nonpreemptive(jobs):.2f}')
print(f'RR(q=3) 严格口径平均等待: {rr(jobs, 3):.2f} 手算简化口径 ≈6,差异来自口径定义(面试讲相对大小即可)')
FCFS 平均等待: 5.67 手算 ≈5.67 ✓ SJF(非抢占) 平均等待: 5.67 RR(q=3) 严格口径平均等待: 1.67 手算简化口径 ≈6,差异来自口径定义(面试讲相对大小即可)
🟡 上下文切换成本详解(面试必答)¶
切换时到底保存什么¶
- 进程切换:寄存器(通用寄存器/PC/SP)+ 页表基址(换 CR3)+ TLB 刷掉(或用 ASID 区分)+ 内核栈/用户栈
- 线程切换(同进程):只需换寄存器 + 栈指针 + PC,页表不换、TLB 不刷 → 明显更便宜
- 协程切换:纯用户态,只保存协程的局部变量/栈帧 + 指令地址,几十纳秒级
成本对比表(背)¶
| 切换类型 | 是否进内核 | 是否换页表/TLB | 相对开销 |
|---|---|---|---|
| 协程切换 | 否 | 否 | 1x |
| 同进程线程切换 | 是 | 否 | ~10x |
| 不同进程切换 | 是 | 是 | ~100x |
面试加分句:高并发 IO 场景用协程(asyncio),躲开 GIL 等待且切换成本压到最低。
# page_repl.py —— 页面置换算法缺页数对比(FIFO / LRU / OPT)
def fifo(pages, cap):
mem, faults = [], 0
for p in pages:
if p not in mem:
faults += 1
if len(mem) == cap:
mem.pop(0)
mem.append(p)
return faults
def lru(pages, cap):
mem, faults = [], 0
for p in pages:
if p in mem:
mem.remove(p)
mem.append(p) # 最近使用移到末尾
else:
faults += 1
if len(mem) == cap:
mem.pop(0) # 淘汰最久未用
mem.append(p)
return faults
def opt(pages, cap):
mem, faults = [], 0
for i, p in enumerate(pages):
if p not in mem:
faults += 1
if len(mem) == cap:
def future(x):
return pages[i + 1:].index(x) if x in pages[i + 1:] else 10 ** 9
far = max(mem, key=future) # 未来最远才用到的淘汰
mem.remove(far)
mem.append(p)
return faults
seq = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] # 教材经典序列
for cap in (3, 4):
print(f'容量 {cap}: FIFO 缺页 {fifo(seq, cap)}, LRU {lru(seq, cap)}, OPT {opt(seq, cap)}')
print('→ 本序列 FIFO 出现 Belady 异常:容量 3→4 缺页反而变多(9→10),说明 FIFO 缺"栈"特性')
print(' 面试点: LRU/OPT 无 Belady 异常; FIFO 有')
容量 3: FIFO 缺页 9, LRU 10, OPT 7 容量 4: FIFO 缺页 10, LRU 8, OPT 6 → 本序列 FIFO 出现 Belady 异常:容量 3→4 缺页反而变多(9→10),说明 FIFO 缺"栈"特性 面试点: LRU/OPT 无 Belady 异常; FIFO 有
🟡 Python 并发选型(GIL 场景落地,后端高频)¶
GIL 是什么¶
- GIL(全局解释器锁):同一时刻只有一个线程执行 Python 字节码
- 只影响 CPU 密集型:多线程无法并行,反而有锁竞争开销
- IO 密集型不受影响:线程在等待 IO 时释放 GIL,其他线程可运行
选型表(背)¶
| 场景 | 推荐 | 原因 |
|---|---|---|
| CPU 密集(计算) | 多进程 | 每个进程独立 GIL,真并行 |
| IO 密集(网络/文件/DB) | 多线程 / 协程 | IO 等待释放 GIL,线程切换便宜 |
| 高并发连接数 > 1 万 | 协程 asyncio | 线程有 8MB 栈上限,协程几十字节 |
| 混合场景 | 进程池 + 线程池 | 计算进进程池,IO 进线程池 |
易错点:不是"多线程没用",而是"多线程对 CPU 密集没用"。面试这样开头即可满分。
# deadlock_detect.py —— 资源分配图成环检测(DFS 三色标记)
def detect_cycle(edges):
"""edges: [(holder, requester)],holder 持有资源,requester 在等待"""
g = {}
for a, b in edges:
g.setdefault(a, []).append(b)
color = {} # 0=未访问 1=在栈上 2=已完成
def dfs(u):
color[u] = 1
for v in g.get(u, []):
if color.get(v) == 1:
return True # 回到栈上节点 → 有环
if color.get(v) is None and dfs(v):
return True
color[u] = 2
return False
return any(dfs(u) for u in list(g))
# P1 持 R1 等 R2;P2 持 R2 等 R1 → 循环等待 → 死锁
print('P1↔P2 互相等待(死锁):', detect_cycle([('P1', 'P2'), ('P2', 'P1')]))
print('链式等待无环:', detect_cycle([('P1', 'P2'), ('P2', 'P3')]))
print('自环(进程等自己持有的资源):', detect_cycle([('P1', 'P1')]))
print('→ 检测到环后, 解除死锁 = 打破必要条件之一: 剥夺资源/进程回滚/破坏循环等待(资源按编号序申请)')
P1↔P2 互相等待(死锁): True 链式等待无环: False 自环(进程等自己持有的资源): True → 检测到环后, 解除死锁 = 打破必要条件之一: 剥夺资源/进程回滚/破坏循环等待(资源按编号序申请)
🟢 补充概念:僵尸/孤儿/守护进程/写时复制¶
僵尸 vs 孤儿(必背)¶
- 僵尸进程:子进程已退出,但父进程没调用
wait()回收 → 进程表残留 PCB(占 PID,几乎不占资源)- 危害:PID 耗尽;解法:父进程
wait()/处理SIGCHLD,或让 init 收养
- 危害:PID 耗尽;解法:父进程
- 孤儿进程:父进程先退出,子进程被 init (PID=1) 收养,最终正常回收(无害)
写时复制 COW(fork 优化)¶
- fork 时子进程共享父进程物理页(只读映射),不复制
- 任一方首次写入该页时触发缺页异常,才复制私有副本 → 省内存、加速 fork
- 面试点:为什么 fork 快?→ COW 让 fork 基本是 O(1) 元信息复制
可重入 vs 线程安全¶
- 可重入:可被中断后再次安全调用(不依赖全局/静态状态);线程安全:多线程并发调用安全
- 不等价:线程安全不一定可重入(如用信号量保护,可能被中断后死锁)
🟡 页表项内容与 TLB 细节(虚拟内存背诵卡)¶
一个页表项包含什么¶
| 页框号(物理页号) | 有效位 | 脏位 | 访问位 | 权限位R/W | 用户/内核位 |
- 有效位:页是否在物理内存(不在 → 缺页中断)
- 脏位:页被写过,换出时要写回磁盘
- 访问位:供 Clock/二次机会算法选择淘汰
TLB 命中/缺失¶
- TLB 是页表查询的硬件缓存,命中率通常 >99%,命中不访问内存
- 缺失惩罚:完整走两级/三级页表(多 2~4 次内存访问),软件填充 TLB
- 进程切换时 TLB 失效 → 上下文切换成本的一大来源(ASID 可避免全刷)
面试追问:为什么用多级页表¶
- 单级页表:4GB/4KB = 1M 项 × 4B = 4MB/进程 且须连续(稀疏地址空间浪费)
- 多级(页目录+页表):只为用到的页建立页表 → 稀疏场景省 90%+ 内存
- 代价:一次访问多查 1~2 级,但 TLB 命中覆盖绝大多数访问
# pool_size.py —— 线程/进程池大小经验公式计算器(背公式 + 自己会算)
import os
def io_threads(cores, block_ratio=0.9):
"""I/O 密集: N = 核心数 / (1 - 阻塞占比)"""
return int(cores / (1 - block_ratio))
def cpu_processes(cores, overhead=1.1):
"""CPU 密集: N ≈ 核心数 * 1.1(留一点系统余量)"""
return int(cores * overhead)
cores = os.cpu_count() or 4
print(f'本机 CPU 核心数: {cores}')
print(f'I/O 密集型线程池建议: {io_threads(cores)} 个线程(阻塞占比 0.9 时)')
print(f'CPU 密集型进程池建议: {cpu_processes(cores)} 个进程')
print('补充: 线程数不是越多越好——上下文切换会吃掉收益, 超线程 2x 后收益递减')
本机 CPU 核心数: 20 I/O 密集型线程池建议: 200 个线程(阻塞占比 0.9 时) CPU 密集型进程池建议: 22 个进程 补充: 线程数不是越多越好——上下文切换会吃掉收益, 超线程 2x 后收益递减
🔴 零拷贝背诵卡(4 → 3 → 2 次拷贝推导)¶
传统 read + write¶
磁盘 → 页缓存 → 用户缓冲区 → Socket 内核缓冲 → 网卡
[DMA] [CPU] [CPU] [DMA] = 2 CPU + 2 DMA, 4 次上下文切换
mmap + write¶
磁盘 → 页缓存(用户空间直接映射读) → Socket 内核缓冲 → 网卡 = 1 CPU + 2 DMA
- 节省"内核→用户"那次 CPU 拷贝;代价:缺页异常、脏页回写
sendfile(SG-DMA)¶
磁盘 → 页缓存 → 网卡 = 0 CPU + 2 DMA, 2 次上下文切换 ← 最优
- 网卡支持 SG(Scatter-Gather)时,页缓存描述符直接交给网卡搬运
- 应用:Kafka 发消息、Nginx 静态文件、文件下载服务
面试串讲:"大文件传输用 sendfile 零拷贝,Kafka 快的原因之一就是它"。
🟡 内存管理补充背诵(分段/多级页表/TLB 三连问)¶
分页 vs 分段(表格背)¶
| 维度 | 分页 | 分段 |
|---|---|---|
| 划分 | 固定 4KB 页 | 逻辑段(代码/数据/栈) |
| 碎片 | 页内碎片(小) | 外碎片(大,需紧凑) |
| 可见性 | 系统透明 | 程序员/编译器可见 |
| 共享/保护 | 难 | 按段控制,容易 |
| 地址结构 | 页号+偏移 | 段号+偏移 |
面试追问速答¶
- Q:为什么 32 位机器进程虚拟地址空间是 4GB?→ 2^32 = 4G 个字节
- Q:如何用虚拟内存装下比物理内存大的程序?→ 按需调页 + 页面置换,程序只需局部性
- Q:TLB 和 CPU 缓存区别?→ TLB 缓存"虚拟→物理"映射;Cache 缓存数据;缺 TLB 多访内存,缺 Cache 访磁盘
- Q:大页(HugePage)有什么用?→ 减少页表项/TLB 缺失,适合数据库缓冲池等大内存应用