计算机操作系统

参考资料

• 《Operating System Concepts（第 10 版）》
• https://blog.csdn.net/Royalic/article/details/119999404

learning outcomes

• 谈谈操作系统的 整体结构 与 核心功能
• 进程、线程、调度 的完整生命周期及其关键数据结构（PCB、VMA、inode）
• 内存管理（分区、分页、伙伴系统、页面置换）与 文件系统（inode、日志、挂载） 的工作原理
• 中断、I/O 调度、设备驱动 的基本流程
• 设计 线程池 并正确使用同步原语保证线程安全
• 说说 死锁、饥饿、实时调度

看完下面的内容再回来尝试一下

操作系统概述

定义

操作系统（Operating System, OS） 是一种 系统软件，位于硬件与用户或应用程序之间
负责 控制、管理 计算机的软硬件资源，并为上层程序提供 统一、抽象且安全的接口

基本功能

• 进程/线程管理
  负责创建、调度、终止进程/线程，提供同步与通信机制

• 内存管理
  分配/回收内存、实现虚拟内存、页面置换

• 文件系统
  抽象存储设备为文件/目录，提供持久化存取

• 设备管理
  统一管理 I/O 设备，提供驱动程序、缓冲、调度

现代 OS 还会提供 网络栈、系统安全、资源隔离（容器/虚拟化） 等扩展功能

特征

“并发”不等同于“并行”。并发是 调度层面的交错，并行是 硬件层面的同时间执行
虚拟化和异步的前提是 并发：只有在并发环境下，才能把资源抽象为逻辑实体或采用非阻塞 I/O

时分复用：不同程序 分时使用 硬件资源，提高资源利用率
空分复用：将物理磁盘虚拟为逻辑磁盘，例如电脑的 C、D 盘等

按使用场景分类

系统结构

内核结构模型

Linux 采用 混合内核：核心功能在内核空间，驱动、文件系统等可编译为模块（loadable kernel modules, LKM）

用户态 vs. 内核态

系统调用 是用户态程序进入内核态的唯一受控入口，如 read()、write()、fork() 等。

进程 vs. 线程

进程管理

进程的概念与控制块 PCB

进程 是 资源分配和调度的基本单位，是 程序 在 运行时 的 动态实例

Process Control Block 是进程存在的唯一标识，记录进程的状态和运行的信息
典型的 PCB（结构体示例）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

typedef struct pcb {
    pid_t       pid;            // 进程标识符
    pid_t       ppid;           // 父进程标识符
    int         state;          // 进程状态（就绪、运行、阻塞、终止）
    struct context ctx;         // CPU 上下文（寄存器、PC、SP）
    void       *kstack;         // 内核栈基址
    void       *ustack;         // 用户栈基址
    struct mm_struct *mm;       // 地址空间描述（页表、段表）
    struct files_struct *files; // 打开的文件描述符表
    struct list_head children;  // 子进程链表
    struct list_head sibling;   // 同父进程的兄弟链表
    // … 其他资源（信号、计时器、调度信息） …
} pcb_t;

PCB 中记录的关键字段：

• PID：唯一标识
• 状态：TASK_RUNNING、TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE、TASK_STOPPED、TASK_ZOMBIE 等
• 上下文：保存寄存器、程序计数器、栈指针，以便 上下文切换 时恢复
• 地址空间：指向页表/段表结构
• 打开的文件：文件描述符表
• 调度信息：优先级、时间片、调度策略

进程状态模型（五状态 + 挂起）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

+-------------------+
|   创建 (new)      |
+--------+----------+
         |
         v
+--------+----------+          +-----------------+
|   就绪 (ready)    |<--------|   挂起 (suspend)|
+--------+----------+          +-----------------+
         |
+--------v----------+
|   运行 (running) |
+--------+----------+
         |
+--------v----------+
|   阻塞 (blocked) |
+--------+----------+
         |
+--------v----------+
|   终止 (exit)    |
+-------------------+

• 创建（new）：系统为进程分配 PCB，但尚未分配全部资源。
• 就绪（ready）：所有资源（内存、文件句柄）已就绪，等待 CPU。
• 运行（running）：获得 CPU，正在执行指令。
• 阻塞（blocked）：因等待 I/O、信号、同步对象等而主动放弃 CPU。
• 挂起（suspended）：进程已被换出至磁盘（Swap）或被管理员暂停。
• 终止（exit）：进程结束，资源回收，PCB 进入 僵尸（zombie） 状态直至父进程 wait()。

进程的创建、执行与终止

上下文切换（Context Switch）

1. 保存当前进程上下文（寄存器、程序计数器、栈指针）到 PCB。
2. 切换页表（若进程地址空间不同）。
3. 调度器选择下一个就绪进程。
4. 恢复新进程上下文，返回到用户态或内核态继续执行。

开销：约 1–5 µs（取决于硬件、TLB 刷新、缓存失效）。
优化：使用 TLB 刷新延迟、CPU 亲和性（CPU affinity）等技术。

进程调度层次

进程同步

四大原则

这四条原则是 正确实现同步 的理论基石。若任意一条被破坏，都可能导致 死锁、饥饿或竞争错误。

常用原语

实现示例（POSIX）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

pthread_mutex_t mtx = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t  cv  = PTHREAD_COND_INITIALIZER;
int ready = 0;

void *producer(void *arg) {
    pthread_mutex_lock(&mtx);
    // 产生数据
    ready = 1;
    pthread_cond_signal(&cv);
    pthread_mutex_unlock(&mtx);
    return NULL;
}

void *consumer(void *arg) {
    pthread_mutex_lock(&mtx);
    while (!ready)               // 防止伪唤醒
        pthread_cond_wait(&cv, &mtx);
    // 消费数据
    ready = 0;
    pthread_mutex_unlock(&mtx);
    return NULL;
}

死锁（Deadlock）

• 死锁产生的前提（死锁的必要条件）

只要破坏其中任意一条，就能 预防 死锁。

死锁处理策略

• 银行家算法（Deadlock Avoidance）

  1. 系统状态：
     • Available: 各类资源当前可用数量
     • Max: 每个进程最大需求矩阵
     • Allocation: 已分配矩阵
     • Need = Max - Allocation
  2. 安全性检查：模拟分配后是否仍能满足所有进程的 Need。若能，则系统处于 安全状态，否则拒绝分配。
  3. 实现要点：
     • 只在 可抢占 环境下有效（如内存页可回收）
     • 需要 进程提前声明最大需求，不适用于动态需求变化的场景。

• 死锁检测（资源分配图）

  • 资源分配图（RAG）：节点分为 进程（圆）和 资源（方），边表示 请求 或 分配。
  • 等待图（Wait‑For Graph, WFG）：仅保留进程节点，若 Pi → Pj 表示 Pi 正在等待 Pj 持有的资源。环路即死锁。

• 恢复策略

  方法	说明
  终止进程	直接杀死一个或多个进程，释放资源（优先终止低优先级或占用资源最多的进程）
  资源抢占	强制回收进程持有的可抢占资源（需要进程能安全回滚）
  回滚	将进程回滚到安全检查点（事务式系统）

进程调度

计算机通过决策决定哪个进程获得 CPU 使用权

• 长程调度

  • 目标：控制系统负载、实现 多道程序（提高 CPU 利用率）。
  • 策略：
    • FCFS（先来先服务）：简单但可能导致 短作业延迟。
    • 多级队列：将作业按优先级、资源需求划分不同队列。
    • 作业控制块（JCB）：记录作业的状态、所需资源、优先级等。

• 短程调度（CPU 调度）

  进程主动放弃（非抢占），正常结束、调用 exit()、sleep()、wait()、I/O 阻塞 系统强制抢占，时间片耗尽、出现更高优先级进程、I/O 中断、系统调用 sched_yield()

调度机制与常见算法

调度评价指标

存储管理

内存的分配与回收

• 动态分区分配算法

  算法	原理	优点	缺点
  首次适应（First‑Fit）	从低地址向高地址扫描，找到第一个足够大的空闲块	实现简单，搜索时间短	易产生 外部碎片
  最佳适应（Best‑Fit）	在所有空闲块中挑选最小的满足需求的块	减少碎片	需要遍历全部空闲块，搜索时间长
  最差适应（Worst‑Fit）	选取最大的空闲块	产生的大块碎片易合并	仍会产生碎片，且浪费大块空间
  快速适应（Next‑Fit）	类似首次适应，但从上一次分配结束位置继续搜索	对循环负载有优势	与首次适应类似的碎片问题

• 内存回收的过程
  当回收区出现在空闲区的不同位置的时候，回收区和空闲区是直接合并，还是需要创建新的空闲节点？
  新的空闲区使用的地址是哪一个？

  • 立即合并（Immediate Coalescing）：释放块后立即检查前后相邻块是否空闲，若是则合并为更大的块。
  • 延迟合并（Deferred Coalescing）：将空闲块挂入空闲链表，等到 分配请求 或 内存回收周期 再统一合并。
  • 合并策略：
  • 地址顺序链表：空闲块按起始地址排序，便于检查相邻块。
  • 双向链表：便于向前/向后遍历合并。

  新空闲块的起始地址 为 被释放块的起始地址；若合并后形成更大的块，则该块的起始地址为最左侧块的地址。

虚拟内存与分页

虚拟内存概念

• 虚拟地址空间：每个进程拥有独立的 32/64 位线性地址空间。
• 页面（Page）：固定大小的块（常见 4 KB、2 MB、1 GB 大页），是虚拟内存管理的基本单元。
• 页表（Page Table）：记录 虚拟页号 ↔ 物理帧号 的映射关系。
• TLB（Translation Lookaside Buffer）：CPU 中的高速缓存，用于存放最近使用的页表项，降低地址转换延迟。

页面置换算法

交换（Swapping）与页面置换的关系

• Swap 区：磁盘上专门用于保存被换出的页面或整个进程的 交换空间。
• 页面置换：当物理内存不足时，页面 被写入 Swap；当页面再次被访问时，触发 缺页异常，内核将其调回内存（可能再置换其他页面）。

Linux 中的 Swap 采用 页面级 交换（默认 4 KB），并通过 swapiness 参数控制换出倾向。

伙伴系统（Buddy System）

• 原理：将空闲内存块划分为 2 的幂次大小的 伙伴（如 2 KB、4 KB、8 KB…），当分配请求到来时，找最小的足够块；若块太大则 拆分 成两个相同大小的伙伴；释放时若其伙伴也是空闲，则 合并 成更大的块。
• 优点：快速分配/合并，碎片率低，适合 页框分配（Linux 物理页帧）和 内核对象（Slab）管理。
• 缺点：只能分配 2 的幂次大小，导致 内部碎片。

Linux 的存储管理

常用命令：free -h、cat /proc/meminfo、vmstat、top、htop、cat /proc/[pid]/smaps。

Buddy 内存管理算法：解决内存外碎片的问题

Swap 空间是 Linux 系统的交换空间
是磁盘的一个分区，在初始化系统时配置的
当内存满时，系统会将一些内存交换至 Swap 空间

文件管理

文件的抽象层次

1. 用户视图：文件名、路径、权限、属性（size、mtime、atime）。
2. VFS（Virtual File System）层：统一的文件系统抽象（struct file, struct inode），实现跨文件系统的统一接口。
3. 具体文件系统实现：如 ext4、xfs、btrfs、vfat、ntfs，负责磁盘块的布局、目录结构、日志（journal）等。

关键概念

常见文件系统对比

文件操作系统调用（POSIX）

文件描述符表：每个进程维护一个 打开文件表（指向全局 系统文件表），实现 共享打开文件（如 fork 后子进程共享同一 fd）。

设备管理与 I/O

设备分类

设备驱动模型（Linux）

1. 字符设备驱动：实现 file_operations（open, read, write, ioctl, poll）。
2. 块设备驱动：实现 block_device_operations（submit_bio, getgeo），配合 I/O 调度器。
3. 网络设备驱动：实现 net_device_ops（ndo_start_xmit, ndo_open, ndo_stop）。

驱动注册后会在 /dev 生成对应的 设备文件，用户通过系统调用访问。

中断处理（Interrupt Handling）

• 为什么需要中断？

  • 异步事件：外设（键盘、网卡）在任意时刻需要 CPU 关注。
  • 提高 CPU 利用率：CPU 不必轮询 I/O，能够在 I/O 完成时立即响应。
  • 实现实时响应：对高优先级硬件事件（如时钟）进行及时处理。

• 中断的分类

  类型	示例	触发方式
  内部中断（Exception / Fault）	除零、页面错误、非法指令	CPU 在执行指令时检测
  外部硬件中断	键盘、网卡、定时器	设备向 IRQ 线发送信号
  软件中断（System Call）	int 0x80、syscall	程序显式触发，进入内核态
  可屏蔽中断（Maskable）	大多数外设中断	可被 cli/sti 或 CPU 中断屏蔽位屏蔽
  不可屏蔽中断（NMI）	硬件错误、看门狗	不能被屏蔽，最高优先级

• 中断处理流程（以 Linux 为例）

  1. 中断请求（IRQ）：外设向中断控制器（APIC / PIC）发送信号。
  2. CPU 响应：CPU 通过 中断向量（Interrupt Vector Table）定位对应的 中断服务例程（ISR）。
  3. 保存上下文：CPU 自动压栈保存 寄存器、EFLAGS、CS/EIP（或 RIP）等。
  4. 进入中断处理程序：
     • Top‑half（硬件中断上下文）完成快速处理（如读取状态寄存器、确认中断、唤醒等待队列）。
     • Bottom‑half（软中断、tasklet、工作队列）在稍后以 进程上下文 完成耗时操作（如磁盘 I/O、网络协议栈处理）。
  5. 恢复上下文：执行 IRET（x86）或 eret（ARM），恢复原先进程的寄存器并返回。

  中断屏蔽：在 ISR 中常使用 local_irq_save/restore 防止同一中断嵌套。
  中断共享：同一 IRQ 线可挂载多个设备，驱动在 ISR 中通过 设备链表 判断是哪一个设备触发。

• 常见中断相关系统调用 / 接口

  接口	说明
  request_irq()	注册 ISR（Linux）
  free_irq()	释放 IRQ
  enable_irq()/disable_irq()	局部屏蔽/解除屏蔽
  irq_set_affinity()	绑定中断到特定 CPU（NUMA）
  ioctl()	通过系统调用向驱动发送控制命令（如 FIONREAD）

I/O 调度（Disk Scheduling）

线程与线程池

线程概念

• 线程（Thread） 是 进程内部的执行流，共享进程的 地址空间、文件描述符、信号处理 等资源。
• 轻量级进程（LWP）：在某些系统（如 Solaris）中，线程被实现为 LWP，内核直接调度。
• 用户态线程（如 Green Threads）在用户空间调度，不需要内核介入，适用于 I/O 密集型协程框架。

线程的创建与管理（POSIX 示例）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <pthread.h>
#include <stdio.h>

void *worker(void *arg) {
    int id = *(int *)arg;
    printf("Thread %d started\n", id);
    // ... 执行任务 ...
    return NULL;
}

int main(void) {
    const int N = 4;
    pthread_t th[N];
    int ids[N];
    for (int i = 0; i < N; ++i) {
        ids[i] = i;
        pthread_create(&th[i], NULL, worker, &ids[i]);
    }
    for (int i = 0; i < N; ++i)
        pthread_join(th[i], NULL);
    return 0;
}

• pthread_create → 内核 clone() 系统调用（创建新线程）。
• pthread_join → 等待线程结束并回收资源。

线程池设计模式

为什么使用线程池？

• 降低创建/销毁开销：线程的栈、调度信息、内核对象的分配成本较高。
• 控制并发度：通过固定线程数限制系统资源占用，防止 线程风暴。
• 任务调度解耦：生产者只负责提交任务，消费者（工作线程）负责执行。

典型结构（伪代码）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

+-------------------+        +-------------------+
|   任务生产者      |  --->  |   任务队列 (FIFO) |
+-------------------+        +-------------------+
                                   |
                                   v
+-------------------+        +-------------------+
|   工作线程 1      |  <---  |   线程池管理器    |
+-------------------+        +-------------------+
|   工作线程 2      |
+-------------------+
|   …               |
+-------------------+

关键组件

线程安全实现（POSIX 示例）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

typedef struct {
    pthread_mutex_t mtx;
    pthread_cond_t  not_empty;
    pthread_cond_t  not_full;
    Task **queue;
    int head, tail, size, capacity;
    int stop;               // 线程池关闭标志
} TaskQueue;

/* 入队 */
void enqueue(TaskQueue *q, Task *t) {
    pthread_mutex_lock(&q->mtx);
    while (q->size == q->capacity && !q->stop)
        pthread_cond_wait(&q->not_full, &q->mtx);
    if (q->stop) { pthread_mutex_unlock(&q->mtx); return; }
    q->queue[q->tail] = t;
    q->tail = (q->tail + 1) % q->capacity;
    ++q->size;
    pthread_cond_signal(&q->not_empty);
    pthread_mutex_unlock(&q->mtx);
}

/* 出队 */
Task *dequeue(TaskQueue *q) {
    pthread_mutex_lock(&q->mtx);
    while (q->size == 0 && !q->stop)
        pthread_cond_wait(&q->not_empty, &q->mtx);
    if (q->stop) { pthread_mutex_unlock(&q->mtx); return NULL; }
    Task *t = q->queue[q->head];
    q->head = (q->head + 1) % q->capacity;
    --q->size;
    pthread_cond_signal(&q->not_full);
    pthread_mutex_unlock(&q->mtx);
    return t;
}

• 生产者 调用 enqueue()，消费者（工作线程）循环调用 dequeue()。
• 当 stop 为真时，所有线程安全退出，防止 死锁。

常见实现（语言/库）

问题自测

• 进程状态转换图、四大同步原则、死锁必要条件？
• 银行家算法 检查安全状态？
• 解释 TLB Miss、Cache Miss、Page Fault 的区别与处理流程。
• 比较 FCFS、SJF、RR、MLFQ 的优缺点并给出适用场景。