# 操作系统期末知识点总结与考点分析

## 一、历年试卷考点频率统计

| 考点 | 20-21A | 21-22A | 2023A | 2025A | 频率 |
|------|--------|--------|-------|-------|------|
| 磁盘调度算法 | ✓ | ✓ | ✓ | ✓ | ★★★★★ |
| 虚拟内存页面置换 | ✓ | ✓ | ✓ | ✓ | ★★★★★ |
| 进程控制(fork) | ✓ | ✓ | ✓ | ✓ | ★★★★★ |
| CPU调度算法 | ✓ | - | ✓ | ✓ | ★★★★ |
| 文件系统(Ext2/inode) | - | ✓ | ✓ | ✓ | ★★★★ |
| I/O控制方式 | ✓ | - | - | ✓ | ★★★ |
| 段页式地址转换 | ✓ | ✓ | - | - | ★★★ |
| 银行家算法 | ✓ | - | - | - | ★★ |
| 工作集模型 | ✓ | ✓ | ✓ | - | ★★★ |
| 代码优化 | - | ✓ | ✓ | - | ★★ |
| 系统运行机制 | - | - | ✓ | - | ★★ |
| 多级反馈队列 | - | - | ✓ | - | ★★ |

---

## 二、各章核心知识点总结

### 第1章：操作系统概述

**考点：OS基本概念、发展历史、结构**

- **四大特征**：并发、共享、虚拟、异步
- **OS结构类型**：
  - 单体结构（Linux）：所有服务在内核态运行，性能好但耦合度高
  - 分层结构：按层次组织，便于调试但层间通信开销大
  - 微内核结构：内核只保留最基本功能，其余在用户态运行，可靠性高但性能差
  - 虚拟机结构：在硬件上运行多个OS实例

---

### 第2章：系统运行机制

**考点：中断、MMU、CPU双模式、系统调用**

- **中断机制**：
  - 硬中断：外部设备产生，异步
  - 软中断（异常）：CPU内部产生，同步（除零错误、缺页异常、系统调用）
  - **时钟中断**：OS获得CPU控制权的关键机制

- **MMU地址转换**：
  - 逻辑地址 → 物理地址的硬件支持
  - U/S位：用户态/内核态标识，实现内存保护

- **CPU双模式**：
  - 用户态（目态）→ 内核态（管态）：通过中断/异常/系统调用
  - 内核态 → 用户态：通过PSW（程序状态字）切换

- **系统调用流程**：
  ```
  用户程序 → 系统调用号放入EAX → int $0x80 → 内核态
  → 查系统调用表 → 执行服务程序 → 返回用户态
  ```

---

### 第3章：Linux基础

**考点：目录结构、文件权限、/proc文件系统**

- **目录结构**：/bin, /etc, /home, /proc, /dev, /tmp
- **文件权限**：chmod 数字法（r=4, w=2, x=1）
- **/proc文件系统**：虚拟文件系统，提供进程和内核信息

---

### 第4章：C语言开发基础

**考点：编译流程、ELF内存布局、调试**

- **编译流程**：预处理 → 编译 → 汇编 → 链接
- **ELF内存布局**（从低到高）：
  ```
  .text（代码段）
  .rodata（只读数据）
  .data（已初始化全局变量）
  .bss（未初始化全局变量，不占磁盘空间）
  heap（堆，向上增长 ↗）
  ↓
  stack（栈，向下增长 ↘）
  ```
- **关键区别**：.bss不占磁盘空间但占内存空间（运行时分配）

---

### 第5-6章：文件I/O

**考点：UNIX IO、文件描述符共享、mmap、重定向**

- **UNIX IO函数**：open/read/write/close/lseek
- **文件描述符表共享**：
  ```
  进程fd表 → 文件表（引用计数） → v-node表（共享）
  fork后父子进程共享文件表，引用计数+1
  ```
- **mmap内存映射**：将文件映射到进程地址空间，实现高效I/O
- **dup2重定向**：实现I/O重定向的标准方法
- **stdio vs UNIX IO缓冲**：
  - stdio有用户缓冲区（全缓冲/行缓冲/无缓冲）
  - UNIX IO无用户缓冲区

---

### 第7章：磁盘空间管理 ★★★★★必考

**考点：分配方式、Ext2文件系统、inode混合索引**

- **三种分配方式**：
  - 连续分配：支持顺序/随机访问，有外部碎片
  - 链接分配：无外部碎片，只支持顺序访问，FAT是改进
  - 索引分配：支持直接/间接访问，inode是典型实现

- **FAT文件系统**：FAT12/16/32，链接分配的改进版本

- **NTFS**：基于MFT（主文件表），B+树结构

- **Ext2文件系统**（重点）：
  ```
  超级块 → 块组描述符 → 块位图 → inode位图 → inode表 → 数据块
  ```
  - **inode结构**：15个地址项
    - 0-11：直接索引（12个块）
    - 12：一次间接索引（256个块，假设块大小1KB，指针4字节）
    - 13：二次间接索引（256×256个块）
    - 14：三次间接索引（256³个块）
  - **最大文件计算**：
    ```
    块大小=1KB，指针=4B，则每块256个指针
    直接：12块
    一次间接：256块
    二次间接：256×256=65536块
    三次间接：256³=16777216块
    总计：12+256+65536+16777216 ≈ 16GB+
    ```

- **HDFS**：分布式文件系统，NameNode+DataNode架构

- **空闲空间管理**：位图法、成组链接法

- **RAID**：
  - RAID0：条带化，无冗余
  - RAID1：镜像，100%冗余
  - RAID3：位交叉+专用校验盘
  - RAID5：块交叉+分布式校验

---

### 第8章：进程控制 ★★★★★必考

**考点：fork/exec/wait/exit、僵尸进程、shell实现**

- **fork()**：
  - 调用一次，返回两次（父进程返回子进程PID，子进程返回0）
  - **COW（写时复制）**：父子进程共享物理页，写时才复制
  - fork后文件描述符共享（引用计数+1）

- **exec系列函数**：替换进程映像，不创建新进程

- **wait/waitpid**：
  - 阻塞等待子进程状态变化
  - 回收子进程资源，防止僵尸进程

- **exit/_exit**：
  - exit：执行清理（刷新缓冲区、调用atexit处理函数）
  - _exit：直接退出，不执行清理

- **僵尸进程**：
  - 子进程exit但父进程未wait
  - 解决方法：父进程调用wait/waitpid，或SIGCHLD信号处理

- **shell实现**：
  ```c
  // 基本框架
  while (1) {
      读取命令行
      解析命令
      if (内置命令) 直接执行
      else {
          pid = fork()
          if (pid == 0) execvp(...)  // 子进程执行
          else wait(NULL)            // 父进程等待
      }
  }
  ```

- **守护进程（daemon）创建5步**：
  1. fork()创建子进程，父进程exit
  2. setsid()创建新会话
  3. fork()再次fork，父进程exit（防止重新获得控制终端）
  4. chdir("/")改变工作目录
  5. umask(0)重设文件权限掩码

---

### 第9章：多线程 ★★★★

**考点：pthread API、竞态条件、互斥锁、信号量、生产者消费者**

- **pthread API**：
  ```c
  pthread_create()    // 创建线程
  pthread_join()      // 等待线程结束
  pthread_exit()      // 退出线程
  pthread_detach()    // 分离线程
  ```

- **竞态条件（Race Condition）**：
  - 多线程并发访问共享数据，结果取决于执行顺序
  - 解决：互斥锁、信号量

- **互斥锁（Mutex）**：
  ```c
  pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
  pthread_mutex_lock(&mutex);    // 加锁
  // 临界区
  pthread_mutex_unlock(&mutex);  // 解锁
  ```

- **信号量（Semaphore）**：
  - P操作（wait）：S--，若S<0则阻塞
  - V操作（signal）：S++，若有等待者则唤醒
  - **实现同步和互斥**

- **生产者消费者模型**：
  ```
  信号量：
  mutex = 1    // 互斥访问缓冲区
  empty = N    // 空闲缓冲区数量
  full = 0     // 满缓冲区数量

  生产者：                  消费者：
  P(empty)                  P(full)
  P(mutex)                  P(mutex)
  放入产品                  取出产品
  V(mutex)                  V(mutex)
  V(full)                   V(empty)
  ```

- **并行计算**：
  - 加速比 S = T_serial / T_parallel
  - 效率 E = S / P（P为处理器数量）
  - Amdahl定律：S = 1 / ((1-f) + f/P)

---

### 第10章：进程间通信IPC

**考点：管道、消息队列、共享内存、信号**

- **管道**：
  - 匿名管道：只能用于父子进程，单向通信
  - 命名管道FIFO：可用于无亲缘关系进程

- **消息队列**：内核中的链表，按消息类型读取

- **共享内存**：最快的IPC方式，需要同步机制保护

- **信号**：异步通知机制，SIGINT/SIGTERM/SIGCHLD等

---

### 第11章：网络编程

**考点：Socket API、TCP客户端服务器模型**

- **Socket API**：
  ```c
  // 服务器
  socket() → bind() → listen() → accept() → read/write → close()
  // 客户端
  socket() → connect() → read/write → close()
  ```

- **字节序转换**：htonl/htons/ntohl/ntohs

---

### 第12章：并发服务器

**考点：多进程/多线程模型、I/O多路复用、线程池**

- **多进程模型**：fork per request，简单但开销大
- **多线程模型**：pthread_create per request，开销较小
- **I/O多路复用（select）**：
  ```c
  fd_set read_set;
  FD_ZERO(&read_set);
  FD_SET(fd, &read_set);
  select(maxfd+1, &read_set, NULL, NULL, NULL);
  ```
- **线程池**：预先创建线程，减少创建/销毁开销

---

### 第13章：CPU调度 ★★★★

**考点：调度算法计算、优先级反转、CFS**

- **三级调度**：高级调度（作业调度）、中级调度（内存调度）、低级调度（进程调度）

- **调度算法**：
  - **FCFS**（先来先服务）：简单，对长作业有利
  - **SJF/SRTF**（最短作业优先/最短剩余时间优先）：平均等待时间最短，但可能饥饿
  - **HRRF**（最高响应比优先）：响应比 = 1 + 等待时间/运行时间
  - **RR**（时间片轮转）：时间片太大退化为FCFS，太小上下文切换开销大
  - **MFQ**（多级反馈队列）：综合了多种算法优点
  - **优先级调度**：可能导致低优先级饥饿

- **优先级反转**：高优先级进程等待低优先级进程持有的资源
  - 解决方案：优先级继承协议

- **EDF**（最早截止时间优先）：实时调度
- **LLF**（最低松弛度优先）：松弛度 = 截止时间 - 剩余执行时间

- **CFS**（完全公平调度）：Linux默认
  - vruntime（虚拟运行时间）
  - 红黑树组织运行队列

- **调度公式**：
  ```
  周转时间 = 完成时间 - 到达时间
  带权周转时间 = 周转时间 / 运行时间
  平均周转时间 = Σ周转时间 / n
  ```

---

### 第14章：死锁 ★★★

**考点：必要条件、资源分配图、银行家算法**

- **四个必要条件**：
  1. 互斥条件
  2. 请求和保持条件
  3. 不可抢占条件
  4. 循环等待条件

- **资源分配图**：检测死锁的图形化方法

- **银行家算法**：
  ```
  Available: 系统可用资源向量
  Max: 进程最大需求矩阵
  Allocation: 已分配矩阵
  Need = Max - Allocation: 还需要矩阵

  安全性检查：
  1. Work = Available, Finish = false
  2. 找一个 Need ≤ Work 且 Finish=false 的进程
  3. Work += Allocation, Finish = true
  4. 重复直到所有 Finish=true（安全）或找不到（不安全）
  ```

- **死锁处理**：
  - 预防：破坏四个必要条件之一
  - 避免：银行家算法
  - 检测：资源分配图
  - 恢夺：终止进程或资源抢占

---

### 第15章：内存管理 ★★★★

**考点：地址转换、页表、TLB、多级页表、段页式**

- **逻辑地址 vs 物理地址**

- **分页管理**：
  - 虚拟页号(VPN) + 页内偏移(VPO)
  - 物理帧号(PPN) + 帧内偏移(PPO)
  - 页表项：有效位、脏位、引用位、R/W位、U/S位

- **缺页处理**：
  ```
  访问页表 → 有效位=0 → 缺页异常
  → 选择牺牲页（若修改过则写回磁盘）
  → 从磁盘调入新页
  → 更新页表 → 重新执行指令
  ```

- **TLB（快表）**：
  ```
  有效访问时间 EAT = λ + t + (1-a)·t
  λ: TLB访问时间
  t: 内存访问时间
  a: TLB命中率
  ```

- **多级页表**：减少页表占用的连续内存
  - 二级页表：VPN分为两部分，第一级索引页目录，第二级索引页表

- **倒排页表**：按物理帧组织，减少内存占用但查找慢

- **段页式**：三维地址（段号 + 页号 + 页内偏移）

---

### 第16章：虚拟内存 ★★★★★必考

**考点：页面置换算法、工作集、抖动**

- **请求调页**：访问时才调入页面

- **局部性原理**：
  - 时间局部性：最近访问的数据可能再次访问
  - 空间局部性：相邻地址可能被访问

- **页面置换算法**（重点中的重点）：
  - **OPT**（最优算法）：替换将来最长时间不使用的页面，理论最优但不可实现
  - **FIFO**（先进先出）：可能产生**Belady异常**（增加页框数反而增加缺页次数）
  - **LRU**（最近最久未使用）：替换最长时间未使用的页面，无Belady异常
  - **Clock算法**：LRU的近似，检查引用位
  - **LFU**（最不经常使用）：替换访问次数最少的页面

- **抖动（Thrashing）**：
  - 分配的页框数太少，频繁缺页
  - 工作集 > 分配的页框数

- **工作集模型**：
  ```
  工作集 W(t, Δ) = 在时刻t前Δ时间窗口内访问的页面集合
  Δ: 工作集窗口大小
  ```
  - 若 W(t,Δ) > 分配页框数 → 抖动

- **内存分配策略**：
  - 固定分配 vs 可变分配
  - 全局置换 vs 局部置换

---

### 第17章：I/O系统 ★★★

**考点：I/O控制方式、缓冲、磁盘调度**

- **四种I/O控制方式**：
  1. **程序直接控制**：CPU忙等，效率最低
  2. **中断驱动**：CPU不必忙等，但每次传输一个字
  3. **DMA**：直接内存访问，以块为单位传输
  4. **通道**：独立的I/O处理器，执行通道程序

- **I/O软件层次**：
  ```
  用户层I/O软件
  ↓
  设备独立性软件
  ↓
  设备驱动程序
  ↓
  中断处理程序
  ↓
  硬件
  ```

- **缓冲**：
  - 单缓冲、双缓冲、循环缓冲、缓冲池
  - **SPOOLing**：假脱机技术，将独占设备改为共享设备

- **磁盘调度算法**（必考）：
  - **FCFS**：简单但移动距离长
  - **SSTF**（最短寻道时间优先）：可能饥饿
  - **SCAN**（电梯算法）：双向扫描到边界
  - **C-SCAN**：单向扫描，返回时快速移动
  - **LOOK/C-LOOK**：改进版，不到达边界

- **磁盘访问时间**：
  ```
  访问时间 = 寻道时间 + 旋转延迟 + 传输时间
  ```

---

### 第18章：代码优化

**考点：CPE、代码移动、消除别名、循环展开**

- **CPE**（每元素周期数）：衡量循环性能

- **优化技术**：
  1. **代码移动**：将循环不变量移到循环外
  2. **消除过程调用**：用内联代码替代函数调用
  3. **减少内存引用**：使用局部变量累积，最后写回
  4. **消除指针别名**：使用restrict关键字或引入局部变量
  5. **循环展开**：减少循环控制开销
  6. **SIMD**：单指令多数据流

- **指针别名问题**：
  ```c
  void twiddle1(int *xp, int *yp) {
      *xp += *yp;
      *xp += *yp;
  }
  // 若xp==yp，结果是4倍；否则是2倍
  // 引入局部变量可消除别名影响
  ```

---

## 三、高频计算题型总结

### 1. 磁盘调度计算（每年必考）

**题型**：给定磁道请求序列和磁头初始位置，计算各算法的磁头移动总道数

**解题模板**：
```
请求序列：98,183,37,122,14,124,65,67
初始位置：53

FCFS: 53→98→183→37→122→14→124→65→67
SSTF: 53→65→67→37→14→98→122→124→183
SCAN: 53→37→14→0→65→67→98→122→124→183
C-SCAN: 53→65→67→98→122→124→183→0→14→37
```

---

### 2. 虚拟内存页面置换（每年必考）

**题型**：给定页面访问序列和页框数，计算各算法的缺页次数

**解题模板**：
```
访问序列：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
页框数：3

OPT: 替换将来最长时间不用的
FIFO: 替换最早进入的
LRU: 替换最长时间未使用的
```

---

### 3. fork进程树分析（每年必考）

**题型**：分析fork()调用序列，画出进程树

**关键规则**：
- fork()创建子进程，子进程从fork处继续执行
- 进程总数 = 2^n（n为fork调用次数，假设无嵌套）
- 嵌套fork需仔细跟踪每个进程的执行路径

---

### 4. CPU调度计算

**题型**：给定进程到达时间和运行时间，计算各算法的周转时间

**公式**：
```
周转时间 = 完成时间 - 到达时间
带权周转时间 = 周转时间 / 运行时间
```

---

### 5. Ext2 inode最大文件计算

**题型**：给定块大小和指针大小，计算单个inode支持的最大文件

**公式**：
```
每块指针数 = 块大小 / 指针大小
直接索引：12块
一次间接：块指针数
二次间接：块指针数²
三次间接：块指针数³
```

---

### 6. TLB有效访问时间计算

**题型**：给定TLB访问时间、内存访问时间、TLB命中率，计算EAT

**公式**：
```
EAT = λ + t + (1-a)·t
```

---

### 7. 银行家算法

**题型**：给定资源分配状态，判断是否安全

**步骤**：
1. 计算Need矩阵 = Max - Allocation
2. 执行安全性检查算法
3. 判断是否存在安全序列

---

## 四、2026年考试预测

### 必考题型（概率>90%）：
1. 磁盘调度算法计算（SSTF/SCAN/C-SCAN）
2. 虚拟内存页面置换（OPT/FIFO/LRU）
3. fork进程树分析
4. 文件系统inode计算或Ext2结构分析

### 高概率题型（概率60-90%）：
5. CPU调度算法（HRRF或SJF）
6. I/O控制方式比较
7. 段页式地址转换

### 可能题型（概率30-60%）：
8. 银行家算法安全性检查
9. 代码优化（别名问题、循环展开）
10. 工作集模型与抖动分析
11. 多线程同步（生产者消费者）

---

## 五、复习建议

1. **重点掌握计算题**：磁盘调度、页面置换、CPU调度、inode计算必考
2. **理解fork机制**：画进程树是每年必考题型
3. **掌握基本概念**：I/O控制方式、死锁条件、虚拟内存原理
4. **练习画图**：进程树、资源分配图、地址转换过程
5. **熟悉公式**：EAT、CPI、周转时间、响应比等