ChoChoX/obsidian

Fork 0

Files

T

ChoChoX 3aac80fb26 vault backup: 2026-07-03 23:22:28

2026-07-03 23:22:28 +08:00

18 KiB

Raw Permalink Blame History

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

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

考点	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实现：

// 基本框架
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：

pthread_create()    // 创建线程
pthread_join()      // 等待线程结束
pthread_exit()      // 退出线程
pthread_detach()    // 分离线程

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

互斥锁（Mutex）：

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：

// 服务器
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）：

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：单指令多数据流

指针别名问题：

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. 银行家算法

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

步骤：

计算Need矩阵 = Max - Allocation
执行安全性检查算法
判断是否存在安全序列

四、2026年考试预测

必考题型（概率>90%）：

磁盘调度算法计算（SSTF/SCAN/C-SCAN）
虚拟内存页面置换（OPT/FIFO/LRU）
fork进程树分析
文件系统inode计算或Ext2结构分析

高概率题型（概率60-90%）：

CPU调度算法（HRRF或SJF）
I/O控制方式比较
段页式地址转换

可能题型（概率30-60%）：

银行家算法安全性检查
代码优化（别名问题、循环展开）
工作集模型与抖动分析
多线程同步（生产者消费者）

五、复习建议

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

18 KiB Raw Permalink Blame History Unescape Escape