跳转至

操作系统

核心概念

(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操作顺序错误会导致死锁。
  • 面试点:面试官常问“生产者消费者模型如何实现?”答案:用信号量或锁+条件变量。

死锁

四个必要条件

💡 定义(小白版):死锁 = 一组进程互相攥着对方需要的资源、谁都不肯放手,结果谁也别想往前走一步,程序永远卡住。上面四个条件是「四把锁一起扣上才死锁」:① 资源一次只能给一个人用(互斥)→ ② 别人不能硬抢(不可剥夺)→ ③ 每个人攥着已到手的、还等着别人手里的(保持并等待)→ ④ 你要的我拿着、我要的你拿着,绕成一圈(循环等待)。打破任意一条,死锁立刻解开。

  1. 互斥使用:资源只能被一个进程使用
  2. 不可剥夺:资源不能被抢占
  3. 保持并等待:已获得资源的进程仍需资源
  4. 循环等待:资源分配形成环形等待

死锁避免

银行家算法: - 安全状态检查:是否存在分配序列使所有进程都能完成 - 例子: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 先查页表做翻译。 - 为什么分页:① 进程之间各查各的页表,实现隔离;② 只需给用到的页准备真实房间,实现按需载入(缺页再搬);③ 固定大小,没有外部碎片。

  • 分页:将内存分成固定大小页
  • 页表:记录页号到物理页号的映射

缺页中断流程

  1. CPU访问页不在内存
  2. 触发缺页中断
  3. 缺页中断处理程序加载页
  4. 恢复进程

页面置换算法

  • 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 拒绝(非法指令异常)。

  • 内核态:执行内核代码,有最高权限
  • 用户态:执行用户代码,受限

系统调用流程

  1. 用户态调用陷入trap
  2. CPU切换到内核态
  3. 内核执行系统调用
  4. 返回用户态

易错点/面试点评

  • 易错:系统调用不是函数调用,是陷阱机制。
  • 面试点:问特权指令,答案:在用户态不能执行。

零拷贝

原理

  • 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"的进程):

  1. P0 的 Need=(1,1,2):需要 C=2 > Available 的 C=0 → 不满足
  2. P1 的 Need=(2,0,2):C=2 > 0 → 不满足
  3. P2 的 Need=(1,1,0):(1,1,0) ≤ (1,2,0) → 满足,先执行 P2;P2 释放后 Available = (1,2,0)+(3,0,2) = (4,2,2)
  4. 现在 P1 的 Need=(2,0,2) ≤ (4,2,2) → 满足,执行 P1;释放后 Available = (4,2,2)+(2,0,0) = (6,2,2)
  5. 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 解决的问题。

教程来源:Akun-python/autumn-recruitment。 MIT 许可证全文。