操作系统

4 min中级2026/9/13

操作系统核心原理：进程管理、内存管理、文件系统、I/O系统、并发与同步。

学习目标

本文是「计算机基础」模块的第 15 篇，难度定位为进阶。重点内容：操作系统核心原理：进程管理、内存管理、文件系统、I/O系统、并发与同步。

主要章节：

1. 操作系统概述
1. 进程与线程
1. 进程调度
1. 同步与互斥
1. 内存管理
1. 文件系统
……共 8 个章节

1. 操作系统概述

1.1 操作系统的定义与角色

操作系统是硬件与应用之间的中间层，提供三个核心抽象：

抽象	对应硬件资源	接口
进程	CPU + 寄存器	fork/exec/wait
虚拟内存	物理内存 + 磁盘	mmap/brk/malloc
文件	磁盘/设备	open/read/write/close

操作系统在抽象层级中的位置 (参见 [概述](overview) 3.1节):

Layer 6: Application
         |  API
Layer 5: Language Runtime
         |  ABI / System Call
Layer 4: Operating System  <-- 本章节
         |  ISA / Driver Interface
Layer 3: Hardware

操作系统的双重角色:
  1. 面向上层: 提供简洁的抽象接口 (What)
  2. 面向下层: 管理复杂的硬件资源 (How)

1.2 内核架构

flowchart TD
    B0["User Space"]
    B1["Syscall Interface"]
    B0 --> B1
    B2["VFS | TCP/IP | Scheduler | ... | <-- 全部在内核态"]
    B1 --> B2
    B3["Hardware"]
    B2 --> B3
    B4["FS Server | Net Server | ... | <-- 用户态服务进程"]
    B3 --> B4
    B5["IPC Interface"]
    B4 --> B5
    B6["Schedule | VM | IPC | <-- 最小内核"]
    B5 --> B6
    B7["Hardware"]
    B6 --> B7

1.3 系统调用机制

flowchart TD
    C0_0["系统调用流程 (用户态 -> 内核态 -> 用户态):"]
    C0_1["User Space                          Kernel Space"]
    C0_2["系统调用开销:"]
    C0_3["x86-64 (syscall): ~200-1000 cycles"]
    C0_4["ARM (SVC):        ~100-500 cycles"]
    C0_5["主要开销: 上下文保存/恢复 + TLB冲刷 + 分支预测失效"]
    C1_0["Application"]
    C1_1["call"]
    C1_2["syscall"]
    C1_3["instruction"]
    C1_4["继续执行"]
    C2_0["1. 保存用户上下文"]
    C2_1[">"]
    C2_2["4. 恢复用户上下文"]
    C2_3["<"]
    C2_4["3. 切换回用户栈"]
    C3_0["2. 切换到内核栈"]
    C3_1["syscall"]
    C3_2["handler"]
    C3_3["(检查参数)"]
    C3_4["(执行操作)"]
    C3_5["返回结果"]
    C0_0 --> C0_1
    C0_1 --> C0_2
    C0_2 --> C0_3
    C0_3 --> C0_4
    C0_4 --> C0_5
    C1_0 --> C1_1
    C1_1 --> C1_2
    C1_2 --> C1_3
    C1_3 --> C1_4
    C2_0 --> C2_1
    C2_1 --> C2_2
    C2_2 --> C2_3
    C2_3 --> C2_4
    C3_0 --> C3_1
    C3_1 --> C3_2
    C3_2 --> C3_3
    C3_3 --> C3_4
    C3_4 --> C3_5
    C0_0 --> C1_0
    C1_0 --> C2_0
    C2_0 --> C3_0

跨模块引用：体系结构的特权级（Ring 0/3, EL0/EL1）是系统调用机制的基础。C语言的标准库(glibc)封装了系统调用接口。

2. 进程与线程

2.1 进程的状态机模型

进程是操作系统对运行程序的抽象，其生命周期可用状态机描述：

flowchart TD
    B0["fork/exec / v / scheduler / Ready | > | Running"]
    B1["^ / preempt/ / yield"]
    B0 --> B1
    B2["Blocked | <--IO/wait"]
    B1 --> B2
    B3["IO完成/wakeup / v"]
    B2 --> B3
    B4["Terminated"]
    B3 --> B4

2.2 进程控制块 (PCB)

进程控制块 (task_struct in Linux) 关键字段:

struct task_struct {
    pid_t               pid;          // 进程ID
    volatile long        state;        // 进程状态
    int                  prio;         // 优先级
    struct mm_struct    *mm;           // 内存管理信息
    struct files_struct *files;        // 打开文件表
    struct signal_struct*signal;       // 信号处理
    struct thread_info   thread_info;  // 底层线程信息
    struct sched_entity  se;           // 调度实体
    struct list_head     tasks;        // 进程链表
    void                *stack;        // 内核栈
    // ... 数百个字段
};

2.3 进程创建: fork()

flowchart TD
    B0["pid = 100 | pid = 101 / ppid = 1 | ppid = 100"]
    B1["fork() / 分配PCB / 复制页表(COW) / 复制fd表 / 设置ppid / 加入调度队列 / return 101 (child_pid) | return 0"]
    B0 --> B1

fork伪代码：

pid_t fork(void) {
    struct task_struct *child = alloc_task_struct();
    copy_process(current, child);       // 复制PCB
    dup_mm(child, current->mm);         // 复制页表(COW)
    dup_fd(child, current->files);      // 复制文件描述符表
    wake_up_process(child);             // 加入调度队列
    if (current == child) return 0;     // 子进程返回0
    else return child->pid;             // 父进程返回子PID
}

2.4 线程模型

flowchart TD
    B0["Process"]
    B1["Thread | Thread | Thread / 栈 | 栈 | 栈"]
    B0 --> B1
    B2["共享: 代码段 | 数据段 | 堆 | fd表"]
    B1 --> B2

跨模块引用：Java的Thread类在Linux上使用1:1模型(pthread)。C++的std::thread同样映射到OS线程。Go的goroutine使用M:N模型。

3. 进程调度

3.1 调度算法

调度算法对比:

1. FCFS (先来先服务):
   队列: P1(24) -> P2(3) -> P3(3)
   等待时间: P1=0, P2=24, P3=27
   平均等待: (0+24+27)/3 = 17
   缺点: 护航效应 (短作业等长作业)

2. SJF (最短作业优先):
   队列: P2(3) -> P3(3) -> P1(24)
   等待时间: P2=0, P3=3, P1=6
   平均等待: (0+3+6)/3 = 3
   缺点: 长作业饥饿，需预知执行时间

3. RR (时间片轮转):
   时间片 q=4
   P1(24): run 4 -> run 4 -> run 4 -> ... -> run 4
   P2(3):  run 3 -> done
   P3(3):  run 3 -> done
   优点: 公平，响应快
   缺点: 时间片大小影响性能

4. 优先级调度:
   每个进程有优先级，高优先级先执行
   可配合: 老化(aging)防止饥饿

3.2 Linux CFS调度器

CFS (Completely Fair Scheduler) 核心思想:

  目标: 公平分配CPU时间给所有可运行进程

  虚拟运行时间 (vruntime):
    vruntime += 实际运行时间 * (NICE_0_LOAD / 进程权重)

    权重越高(优先级越高) -> vruntime增长越慢
    -> 被调度的机会越多

  红黑树:
    所有可运行进程按vruntime排序
    左下角 = vruntime最小 = 下一个被调度

  调度决策:
    1. 选择红黑树最左节点
    2. 运行直到vruntime不再是最小
    3. 重新插入红黑树

  时间片计算:
    time_slice = (调度周期 * 进程权重) / 总权重

CFS伪代码：

def cfs_schedule(rq):
    leftmost = rq.rbtree.leftmost()
    next_task = leftmost.task
    current_task = rq.current

    if current_task.state == RUNNING:
        update_vruntime(current_task)
        rbtree_insert(rq.rbtree, current_task)

    rq.current = next_task
    rbtree_remove(rq.rbtree, next_task)
    context_switch(current_task, next_task)

3.3 上下文切换

flowchart TD
    B0["用户态上下文 | 用户态上下文 / 寄存器 | 寄存器 / 栈指针 | 栈指针 / PC | PC"]
    B1["^ / 1. 保存A的上下文到A的内核栈 / 2. 切换内核栈(A -> B) / 3. 从B的内核栈恢复B的上下文"]
    B0 --> B1

4. 同步与互斥

4.1 临界区问题

临界区问题的三个条件:

1. 互斥 (Mutual Exclusion):  同一时刻只有一个进程进入临界区
2. 前进 (Progress):          临界区空闲时，等待进程应能进入
3. 有限等待 (Bounded Wait):  进程等待进入临界区的时间有限

Peterson算法 (两进程互斥的软件方案):

  // 进程 Pi (i=0, j=1-i)
  flag[i] = true;
  turn = j;
  while (flag[j] && turn == j) { /* wait */ }
  // --- 临界区 ---
  flag[i] = false;
  // --- 剩余区 ---

4.2 硬件同步原语

Test-And-Set (TAS):

  boolean TestAndSet(boolean *target) {
    boolean rv = *target;
    *target = true;
    return rv;
  }

  // 使用TAS实现互斥锁
  while (TestAndSet(&lock)) { /* spin */ }
  // --- 临界区 ---
  lock = false;

Compare-And-Swap (CAS):

  boolean CAS(int *addr, int expected, int new_val) {
    if (*addr == expected) {
      *addr = new_val;
      return true;
    }
    return false;
  }

  // 使用CAS实现无锁计数器
  do {
    old = counter;
    new = old + 1;
  } while (!CAS(&counter, old, new));

4.3 信号量

信号量定义 (Dijkstra, 1965):

  semaphore S = integer value;

  P(S) / wait(S) / down(S):     // Proberen (尝试)
    while (S <= 0) { block(); }
    S--;

  V(S) / signal(S) / up(S):     // Verhogen (增加)
    S++;
    wakeup_one_waiter();

信号量的两种用途:
  1. 互斥: 初值 = 1 (二元信号量 = 互斥锁)
  2. 同步: 初值 = 0 (事件通知)

生产者-消费者问题:

  semaphore mutex = 1;    // 互斥访问缓冲区
  semaphore empty = N;    // 空槽位数
  semaphore full  = 0;    // 已占槽位数

  Producer:                      Consumer:
    produce(item);                 P(full);
    P(empty);                      P(mutex);
    P(mutex);                      item = remove();
    insert(item);                  V(mutex);
    V(mutex);                      V(empty);
    V(full);                       consume(item);

4.4 经典同步问题

读者-写者问题：

读者优先:

  semaphore rw_mutex = 1;   // 读写互斥
  semaphore mutex = 1;      // 保护read_count
  int read_count = 0;

  Reader:                        Writer:
    P(mutex);                      P(rw_mutex);
    read_count++;                  // 写操作
    if (read_count == 1)           V(rw_mutex);
      P(rw_mutex);
    V(mutex);
    // 读操作
    P(mutex);
    read_count--;
    if (read_count == 0)
      V(rw_mutex);
    V(mutex);

问题: 写者可能饥饿
解决: 写者优先变体 (增加写者等待计数)

哲学家就餐问题：

5个哲学家，5根筷子，左右各一根

死锁方案 (每人先拿左筷子):
  Philosopher i:
    P(chopstick[i]);         // 拿左筷子
    P(chopstick[(i+1)%5]);   // 拿右筷子
    eat();
    V(chopstick[i]);
    V(chopstick[(i+1)%5]);

防死锁方案:
  1. 最多4人同时拿筷子
  2. 奇数先拿左、偶数先拿右 (破坏循环等待)
  3. 仅当两根筷子都可用时才拿 (AND信号量)

4.5 死锁

死锁四个必要条件:

1. 互斥: 资源不能共享
2. 占有并等待: 持有资源同时等待其他资源
3. 不可抢占: 已获得的资源不能被强制剥夺
4. 循环等待: 存在进程的循环等待链

破坏条件 -> 预防:
  破坏2: 一次性申请所有资源
  破坏3: 允许抢占
  破坏4: 资源有序分配

死锁检测 (资源分配图):

  进程 P1 --请求--> 资源 R1 <--占有-- 进程 P2
  进程 P2 --请求--> 资源 R2 <--占有-- 进程 P1

  图中存在环 -> 死锁

银行家算法 (避免死锁):

  Available[1..m]:  每类资源可用数
  Max[1..n][1..m]:  每个进程最大需求
  Allocation[1..n][1..m]: 每个进程已分配
  Need[i][j] = Max[i][j] - Allocation[i][j]

  安全性检查:
    1. 找到 Need[i] <= Work 的进程
    2. 假设它完成，释放资源: Work += Allocation[i]
    3. 重复直到所有进程完成(安全) 或无法继续(不安全)

跨模块引用：Java的synchronized和ReentrantLock是信号量/互斥锁的语言级封装。C++的std::mutex和std::condition_variable对应OS的互斥锁和条件变量。设计模式中的Singleton模式需要考虑多线程同步。

5. 内存管理

5.1 内存管理演进

内存管理方案演进:

1. 单一连续分配: 一次只运行一个程序
2. 固定分区:      内存划分为固定大小分区
3. 动态分区:      按需分配，产生外部碎片
4. 分页:          固定大小页帧，消除外部碎片
5. 分段:          按逻辑单位划分，消除内部碎片
6. 段页式:        结合分段和分页的优点
7. 虚拟内存:      按需调页，突破物理内存限制

5.2 分页机制

分页地址翻译 (参见 [体系结构](architecture) 4.5节):

  虚拟地址 = [页号 VPN | 偏移 Offset]
  物理地址 = [帧号 PPN | 偏移 Offset]

  页表项 (PTE):
  |--- Frame Number ---| V | R | W | X | D | A |
                        |   |   |   |   |   |
                        |   |   |   |   |   +-- Accessed
                        |   |   |   |   +------ Dirty
                        |   |   |   +---------- Execute
                        |   |   +-------------- Write
                        |   +------------------ Read
                        +---------------------- Valid

页大小选择:
  小页(4KB):  内部碎片少，页表大
  大页(2MB):  页表小，TLB覆盖更多内存
  巨页(1GB):  数据库/虚拟化场景

5.3 页面置换算法

flowchart TD
    B0["1 | 0 | 1 | 0 | 1 | 引用位"]
    B1["时钟指针"]
    B0 --> B1

Clock算法伪代码：

def clock_replace(frames, clock_hand):
    while True:
        frame = frames[clock_hand]
        if frame.reference_bit == 0:
            victim = clock_hand
            clock_hand = (clock_hand + 1) % len(frames)
            return victim
        else:
            frame.reference_bit = 0
            clock_hand = (clock_hand + 1) % len(frames)

5.4 虚拟内存与按需调页

按需调页流程:

  1. 进程访问虚拟地址
  2. MMU查找页表
  3. PTE Valid = 0 -> Page Fault
  4. 陷入内核态
  5. 检查地址合法性 (是否在进程地址空间内)
  6. 若合法:
     a. 选择一个空闲帧 (或置换一个已占帧)
     b. 从磁盘读取页面到该帧
     c. 更新页表 (PTE Valid = 1, Frame Number)
     d. 刷新TLB
     e. 重新执行触发缺页的指令
  7. 若非法:
     发送SIGSEGV (段错误)

写时复制 (COW):
  fork()后父子共享页面(标记只读)
  任一方写入 -> Page Fault
  内核检测到COW标志 -> 复制该页
  修改页表为可写
  重新执行写入指令

5.5 进程地址空间布局

flowchart TD
    B0["Kernel Space | (所有进程共享) / Stack (向下增长) / v"]
    B1["Memory Mapping Region | mmap区域 (共享库等)"]
    B0 --> B1
    B2["^ / Heap (向上增长)"]
    B1 --> B2
    B3["BSS (未初始化全局变量)"]
    B2 --> B3
    B4["Data (已初始化全局变量)"]
    B3 --> B4
    B5["Text (代码段)"]
    B4 --> B5

跨模块引用：体系结构的TLB和页表是虚拟内存的硬件基础。C语言的malloc/free操作堆区，栈区由编译器自动管理。编译原理的代码生成决定了Text/Data/BSS段的布局。

6. 文件系统

6.1 文件系统层次

flowchart TD
    B0["Application"]
    B1["VFS (Virtual File System) | <-- 统一接口层"]
    B0 --> B1
    B2["Ext4 | XFS | Btrfs | FAT32 | ... | <-- 具体文件系统"]
    B1 --> B2
    B3["Block Device Layer | <-- 块设备抽象"]
    B2 --> B3
    B4["Device Driver | <-- 硬件驱动"]
    B3 --> B4
    B5["HDD / SSD"]
    B4 --> B5

6.2 Ext4文件系统

flowchart TD
    B0["Boot | Block | Block | Block | ... | Block / Block | Group0 | Group1 | Group2 | GroupN"]
    B1["Superblock (备份) / Group Descriptor Table / Block Bitmap / Inode Bitmap / Inode Table / Data Blocks"]
    B0 --> B1
    B2["Mode | UID | Size | Timestamps | Blocks | Links / Direct Blocks [0-11] | 直接指针 / Indirect Block | 一级间接 / Double Indirect Block | 二级间接 / Triple Indirect Block | 三级间接"]
    B1 --> B2

6.3 文件操作流程

读取文件的完整路径:

  open("/home/user/file.txt", O_RDONLY)

  1. VFS解析路径:
     root dentry -> "home" -> dentry -> "user" -> dentry -> "file.txt" -> inode
     每级需要读取目录项 (可能触发磁盘IO)

  2. 创建file对象:
     file->inode = 目标inode
     file->pos = 0
     file->mode = O_RDONLY

  3. 分配文件描述符:
     fd = 3 (0=stdin, 1=stdout, 2=stderr)

  read(fd, buf, count)

  1. 通过fd找到file对象
  2. 检查权限 (file->mode允许读?)
  3. 计算逻辑块号: block = file->pos / block_size
  4. 通过inode的块映射找到物理块号
  5. 若页缓存命中 -> 直接返回
  6. 若未命中 -> 提交块IO请求
  7. 更新file->pos

6.4 页缓存

页缓存 (Page Cache):

  原理: 利用内存缓存磁盘数据，利用时间局部性

  读流程:
    read() -> 检查页缓存 -> 命中 -> 返回
                            未命中 -> 磁盘IO -> 加入缓存 -> 返回

  写流程:
    write() -> 写入页缓存 -> 标记为脏页 -> 返回
    脏页回写:
      - 定期 (kupdate内核线程, 30s)
      - 内存压力时 (pdflush)
      - sync/fsync强制回写

  页缓存查找:
    address_space -> radix_tree/xarray -> 按页索引查找

7. I/O系统

7.1 I/O层次

flowchart TD
    B0["User Application"]
    B1["System Call Interface | read/write/ioctl"]
    B0 --> B1
    B2["VFS / Block Layer | 通用块层"]
    B1 --> B2
    B3["I/O Scheduler | 请求合并与排序"]
    B2 --> B3
    B4["Device Driver | 硬件操作"]
    B3 --> B4
    B5["Device Controller | 寄存器/DMA"]
    B4 --> B5
    B6["Physical Device"]
    B5 --> B6

7.2 I/O调度算法

I/O调度算法:

1. NOOP (No Operation):
   简单FIFO队列，仅合并相邻请求
   适用: SSD (随机访问延迟均匀)

2. Deadline:
   每个请求有截止时间
   维护: 排序队列(按扇区) + FIFO队列(按时间)
   读请求优先(500ms超时)，写请求次之(5s超时)

3. CFQ (Completely Fair Queue):
   每个进程一个队列，轮转服务
   分配时间片给每个队列
   适合桌面系统

4. BFQ (Budget Fair Queue):
   CFQ的改进版，基于预算
   更好的吞吐量和延迟平衡

7.3 DMA与零拷贝

传统数据传输 (4次拷贝):

  磁盘 -> 内核缓冲区 -> 用户缓冲区 -> Socket缓冲区 -> 网卡
  [DMA拷贝]  [CPU拷贝]    [CPU拷贝]     [DMA拷贝]

零拷贝技术:

1. sendfile():
   磁盘 -> 内核缓冲区 -> Socket缓冲区 -> 网卡
   [DMA拷贝]             [CPU拷贝]      [DMA拷贝]
   省去: 内核->用户的一次CPU拷贝

2. sendfile() + DMA Scatter-Gather:
   磁盘 -> 内核缓冲区 -> 网卡
   [DMA拷贝]             [DMA拷贝]
   省去: 所有CPU拷贝

3. mmap():
   文件映射到进程地址空间
   直接操作内核缓冲区，无需read/write
   注意: 信号处理、页面错误等复杂情况

跨模块引用：计算机网络的高性能网络框架(Netty/DPDK)大量使用零拷贝技术。Java的NIO使用DirectByteBuffer减少拷贝。C语言的mmap系统调用直接映射文件到内存。

8. 速查表

8.1 进程状态速查

状态	含义	转移条件
Created	刚创建	fork()
Ready	可运行	被调度器选中 -> Running
Running	正在执行	时间片完 -> Ready; IO -> Blocked
Blocked	等待事件	事件完成 -> Ready
Terminated	已终止	exit()

8.2 同步原语速查

原语	作用	开销
自旋锁	忙等待互斥	低(无上下文切换)
互斥锁	睡眠等待互斥	中(上下文切换)
信号量	计数同步	中
条件变量	等待条件	中
读写锁	读共享写互斥	中
RCU	读无锁写延迟	低(读)高(写)

8.3 页面置换速查

算法	策略	优缺点
OPT	置换最远将来使用	理论最优，不可实现
FIFO	置换最早进入	简单，有Belady异常
LRU	置换最久未用	近似最优，实现代价高
Clock	LRU近似	实用，性能接近LRU
LFU	置换最少使用	适合热点数据，需老化

8.4 系统调用速查

类别	系统调用	功能
进程	fork/exec/wait/exit	创建/替换/等待/退出
文件	open/read/write/close/mmap	文件操作
目录	mkdir/rmdir/chdir/getcwd	目录操作
内存	brk/mmap/munmap/mprotect	内存管理
信号	kill/signal/sigaction	信号处理
网络	socket/bind/listen/accept/connect	网络通信
管道	pipe/dup2	进程间通信

操作系统

学习目标#

1. 操作系统概述#

1.1 操作系统的定义与角色#

1.2 内核架构#

1.3 系统调用机制#

2. 进程与线程#

2.1 进程的状态机模型#

2.2 进程控制块 (PCB)#

2.3 进程创建: fork()#

2.4 线程模型#

3. 进程调度#

3.1 调度算法#

3.2 Linux CFS调度器#

3.3 上下文切换#

4. 同步与互斥#

4.1 临界区问题#

4.2 硬件同步原语#

4.3 信号量#

4.4 经典同步问题#

4.5 死锁#

5. 内存管理#

5.1 内存管理演进#

5.2 分页机制#

5.3 页面置换算法#

5.4 虚拟内存与按需调页#

5.5 进程地址空间布局#

6. 文件系统#

6.1 文件系统层次#

6.2 Ext4文件系统#

6.3 文件操作流程#

6.4 页缓存#

7. I/O系统#

7.1 I/O层次#

7.2 I/O调度算法#

7.3 DMA与零拷贝#

8. 速查表#

8.1 进程状态速查#

8.2 同步原语速查#

8.3 页面置换速查#

8.4 系统调用速查#