627 lines
18 KiB
Markdown
627 lines
18 KiB
Markdown
# 操作系统期末知识点总结与考点分析
|
||
|
||
## 一、历年试卷考点频率统计
|
||
|
||
| 考点 | 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、周转时间、响应比等
|