知识库
先学知识点，再做题检验。当前：操作系统
01. 计算机系统知识 (13个)
02. 程序语言基础 (3个)
03. 操作系统 (8个)
04. 软件工程 (8个)
05. 数据结构与算法 (23个)
06. 数据库系统 (11个)
07. 计算机网络 (12个)
08. 面向对象技术 (10个)
09. 信息安全 (4个)
10. 知识产权与标准化 (4个)
11. 多媒体基础 (2个)
12. 项目管理 (4个)
进程PV与死锁
PV操作
重点 难度 2/3
通俗理解
PV操作是操作系统的"红绿灯"——控制多个进程对共享资源的访问，避免"抢车位"导致混乱。
想象一个公共厕所只有3个坑位（信号量=3）：
• P操作（荷兰语Proberen=尝试/减量）：你进去前先拿一把钥匙→坑位数-1。如果没钥匙了（信号量≤0），就在门口排队等。
• V操作（荷兰语Verhogen=增加/增量）：你出来把钥匙放回去→坑位数+1。如果有人在排队，叫下一个人进来。
核心概念：
• 临界资源：一次只能被一个进程使用的资源（如打印机、共享变量）
• 临界区（Critical Section）：访问临界资源的代码段
• 信号量（Semaphore）：一个整型变量，P/V操作对其做原子加减
• 互斥信号量：初值=1，用于实现互斥访问（P→临界区→V）
• 同步信号量：初值=0或N，用于实现先后顺序（前V后P）
核心公式/考点
信号量S的取值意义：
• S>0：还有S个可用资源
• S=0：无可用资源，无等待进程
| • S<0：有 | S | 个进程在等待该资源 |
经典同步问题：
1.生产者-消费者问题（有界缓冲区）
2.读者-写者问题
3.哲学家进餐问题
4.吸烟者问题
表格对比：三大经典PV问题
| 问题 | 核心冲突 | 信号量设计 | 关键点 |
| 生产者-消费者 | 缓冲区满/空 | mutex=1, empty=N, full=0 | 两个同步信号量控制缓冲区状态 |
|---|---|---|---|
| 读者-写者 | 读写互斥/读读可共享 | mutex=1, rcount=0 | 第一个读者上锁，最后一个读者解锁 |
| 哲学家进餐 | 死锁风险 | 筷子信号量[5] | 加限制（最多4人同时拿筷/同时拿两根） |
真题演练
例题：（经典题）系统中有3个并发进程，都需要同类资源5个，不会发生死锁的最少资源数是？
解：
1.每个进程最多需要5个资源
2.死锁最坏情况：每个进程都占4个（已满足临界条件），都在等第5个
3.3×4=12个资源被占用，只要再给1个，某个进程就能完成并释放
4.最少资源数 = n×(max-1)+1 = 3×4+1 = 13
答案：13个资源。
例题：（软考真题）PV操作中，信号量S的初值为3，当前值为-2，表示有几个等待进程？
| 解：S为负时， | S | =等待进程数。S=-2→有2个进程在等待。已分配资源数=初值-当前值=3-(-2)=5。 |
注意事项
⚠️ 易错点1：P操作是"申请资源"，S减1；V操作是"释放资源"，S加1。不要搞反。
| ⚠️ 易错点2：S<0时不表示资源数为负，而表示有 | S | 个进程在等待。 |
⚠️ 易错点3：互斥信号量初值=1，同步信号量初值=0（表示事件未发生）或N（表示缓冲区容量）。
⚠️ 易错点4：P/V操作必须是原子操作（不可中断），否则会出现竞态条件。
⚠️ 易错点5：PV操作要成对出现——互斥PV在同一进程内，同步PV在不同进程间配对。
⚠️ 易错点6：死锁的判断：资源分配图中有环不一定死锁（如果有多种资源，一个环内可能还有剩余资源）。有环+每个资源只分配一个实例→一定死锁。
死锁与银行家算法
重点 难度 2/3
通俗理解
死锁就像四个人打麻将，每人等一个人出牌，但每个人都在等别人先出——四个人都僵住了，没人能继续。
死锁产生的四大必要条件（缺一不可）：
1.🌟 互斥：资源一次只能给一个进程用
2.🌟 请求与保持：进程拿着资源不放，还继续要别的
3.🌟 不可剥夺：不能强行把进程的资源抢走
4.🌟 循环等待：多个进程形成等待环路——A等B，B等C，C等A
银行家算法——避免死锁的"放贷策略"：
想象你是银行家，有10万元可供贷款：
• 进程A说：我最多需要7万，目前已有3万
• 进程B说：我最多需要5万，目前已有2万
• 进程C说：我最多需要3万，目前已有2万
• 银行剩余：10-3-2-2=3万
判断是否能安全放贷：算一下有没有"安全序列"——按某种顺序运行，所有进程都能得到所需资源并完成释放。
核心公式/考点
死锁处理四大策略：
| 策略 | 做法 | 优点 | 缺点 |
| 预防 | 破坏四大条件之一 | 简单 | 资源利用率低 |
|---|---|---|---|
| 避免 | 银行家算法（动态判断） | 较高效 | 需提前知道最大需求 |
| 检测 | 资源分配图定期检测 | 不限制进程 | 发现死锁后要处理 |
| 恢复 | 撤销进程/剥夺资源 | 最终能解决 | 开销大 |
银行家算法核心数据结构：
• Available[m]：每种资源可用数量
• Max[n][m]：每个进程最大需求
• Allocation[n][m]：每个进程已分配
• Need[n][m] = Max - Allocation（还需要多少）
安全性检查算法：
1.初始化Work=Available, Finish=false
2.找满足 Finish[i]=false 且 Need[i]≤Work 的进程i
3.若找到：Work=Work+Allocation[i], Finish[i]=true, 重复步骤2
4.若找不到：检查所有Finish→全true则安全，否则不安全
表格对比：死锁四大处理策略
| 策略 | 破坏条件 | 具体方法 | 典型算法 |
| 预防-互斥 | 破坏互斥 | 使用SPOOLing技术 | 打印机共享 |
|---|---|---|---|
| 预防-请求保持 | 破坏请求保持 | 一次性申请所有资源 | 资源静态分配 |
| 预防-不可剥夺 | 破坏不可剥夺 | 进程资源可被抢占 | 优先级调度 |
| 预防-循环等待 | 破坏循环等待 | 资源按序号申请 | 资源有序分配 |
| 避免 | 动态判断 | 每步检查安全性 | 银行家算法 |
真题演练
例题1：（软考真题）进程P1、P2、P3分别有资源需求(3,2,1)、(6,3,3)、(4,3,2)，当前已分配(1,1,0)、(3,1,1)、(2,1,1)，系统剩余(2,2,0)。当前系统是否安全？
解：
1.Need = (2,1,1)、(3,2,2)、(2,2,1)
2.找Need≤Available(2,2,0)的进程：
P1(2,1,1)的R3=1 > 可用R3=0 → 不行
P2(3,2,2)太大 → 不行
P3(2,2,1)的R3=1 > 可用R3=0 → 不行
3.没有一个进程能满足→不安全！系统可能发生死锁。
例题2：（经典题）有m个同类资源，n个并发进程，每个进程最多需要x个资源。不发生死锁的条件是？
解：最坏情况是每个进程都已获得x-1个资源，此时m ≥ n(x-1)+1 才能保证不死锁。
所以：m ≥ n(x-1)+1 → x ≤ (m-1)/n + 1
注意事项
⚠️ 易错点1：死锁四大条件缺一不可——破坏任意一个就能预防死锁！
⚠️ 易错点2：银行家算法需要进程预先声明最大需求——这是它的主要局限。
⚠️ 易错点3：安全状态→一定不死锁；不安全状态→不一定死锁（可能通过合理调度不死锁）。
⚠️ 易错点4：有环不一定死锁（资源分配图中，如果一种资源有多个实例，有环也可能不锁死）。
⚠️ 易错点5：死锁检测的典型频率：定期检测（如每5分钟）或CPU空闲率低于阈值时检测。
⚠️ 易错点6：资源有序分配法（给每种资源编号，进程必须按编号递增申请）破坏的是循环等待条件。
分页分段虚拟内存
分页存储管理
重点 难度 2/3
通俗理解
分页存储管理 = 把内存切成"豆腐块"，程序也切成同样大小的"豆腐块"——随便塞到空闲块中，用页表记录每一块放哪儿了。
想象你搬家（程序装入内存）：
• 房子有100个房间（物理内存），每个房间大小相同（页框/物理块）
• 你家有50箱东西（程序），每箱也切成同样大小的一箱（页/逻辑页面）
• 1号箱放到27号房、2号箱放到5号房...页表就是一张"箱号→房间号"的对照表
• 搬家不需要把所有箱子放连续的房间——哪间空着放哪间（消除外部碎片）
为什么需要分页？
• 解决外部碎片问题（之前固定分区、可变分区都有碎片问题）
• 逻辑地址连续但物理地址可以不连续
• 为虚拟内存打下基础（程序不需要全部装入就能运行）
核心公式/考点
逻辑地址结构：
| 页号(P) | 页内偏移(W) |
页号位数→最大页数，页内偏移位数→页面大小
页面大小=2^(页内偏移位数)
逻辑地址空间=页数×页面大小=2^(页号位数+页内偏移位数)
地址转换（逻辑→物理）：
1.从逻辑地址分离页号P和页内偏移W
2.查页表：P对应的物理块号B
3.物理地址 = B × 页面大小 + W
TLB（快表）加速：
• TLB是高速缓存，存最近用过的页表项
• TLB命中→一次访存；TLB不命中→两次访存（查页表+取数据）
• TLB命中率直接影响有效访存时间
两级页表（解决页表过大问题）：
| 逻辑地址： | 外层页号 | 内层页号 | 页内偏移 |
先查外层页表找到内层页表，再查内层页表找到物理块号。
表格对比：分页 vs 分段
| 维度 | 分页（Paging） | 分段（Segmentation） |
| 划分方式 | 系统自动划分（固定大小） | 用户/编译器划分（逻辑单位） |
|---|---|---|
| 大小 | 固定（如4KB） | 可变（如代码段、数据段） |
| 地址空间 | 一维线性 | 二维（段号+段内偏移） |
| 可见性 | 对程序员透明 | 程序员可见 |
| 碎片 | 内部碎片（页内未用完） | 外部碎片（段间空隙） |
| 共享保护 | 不方便 | 容易（按段保护） |
| 典型系统 | Linux/Windows | Intel x86分段机制 |
真题演练
例题1：（经典题）某系统页面大小4KB，逻辑地址65540，页表如下{0→5, 1→10, 2→3, 3→7}，求物理地址。
解：
1.页面大小=4KB=4096B，页内偏移位数=12
2.页号=65540÷4096=16（商），页内偏移=65540 mod 4096=4（余数）
3.等等，65540÷4096=16.001...实际是：65540=16×4096+4，页号=16
4.页表最多到3（只有4项），页号16超出了页表范围→缺页中断！
修正：若逻辑地址为6555：
1.6555÷4096=1，页号=1，偏移=6555-4096=2459
2.页表[1]=10→物理块号10
3.物理地址=10×4096+2459=40960+2459=43419
例题2：（软考真题）若页表项大小4B，页面大小4KB，单级页表占多少空间？
解：逻辑地址空间为32位，页面大小4KB=2^12→页内偏移12位→页号20位
页表项数=2^20=1,048,576项
页表大小=1,048,576×4B=4MB
每个进程都有自己的页表→4MB×N个进程，内存开销大→需要多级页表。
注意事项
⚠️ 易错点1：分页的地址是一维的（页号+偏移只是逻辑划分），分段是二维的（程序员显式指定段号）。
⚠️ 易错点2：页面大小选值权衡——太小→页表过大；太大→内部碎片增多。
⚠️ 易错点3：TLB（快表）是硬件实现（MMU内部），不是软件结构。
⚠️ 易错点4：缺页中断是一种特殊的中断——发生在指令执行期间（而非指令执行完），且可能多次触发。
⚠️ 易错点5：逻辑地址=虚拟地址，物理地址=真实内存地址，两者通过页表转换。
⚠️ 易错点6：多级页表节省内存的原理——外层页表中空页号对应的内层页表不需要实际分配。
虚拟内存
重点 难度 2/3
通俗理解
虚拟内存 = 给程序"画大饼"——告诉程序你有128TB的内存空间，但实际上只有8GB物理内存。用到了才把数据从磁盘搬到内存，没用到就搁磁盘上。
就像住酒店（程序运行）：
• 酒店有100间房（物理内存），但你有VIP会员卡号称能入住1万间（虚拟地址空间）
• 实际你只带了5箱行李（当前需要访问的页面），放进了5间房
• 想用第6箱（访问未在内存的页面）→前台叫服务员从仓库搬上来（缺页中断→磁盘I/O）
• 如果酒店满了（内存满了），要把一个客人的行李先存到仓库（页面置换）
局部性原理（虚拟内存的根基）：
• 时间局部性：刚执行的代码/访问的数据很可能马上再用→循环
• 空间局部性：刚访问地址附近的也可能马上要用→数组遍历
核心公式/考点
缺页中断处理流程（重点）：
1.CPU访问某页→MMU查页表→页表项有效位=0（不在内存）
2.触发缺页中断→CPU切换到内核态
3.检查地址合法性→非法→段错误/终止进程
4.合法→找空闲页框→有→直接调入；无→执行页面置换
5.磁盘读取页面到内存页框→更新页表→重新执行指令
页面置换算法对照表：
| 算法 | 策略 | 优点 | 缺点 | 是否Belady异常 |
| OPT（最佳） | 替换未来最久不会用的 | 理论最优 | 无法实现（需预知未来） | ❌ |
|---|---|---|---|---|
| LRU（最近最久未用） | 替换最久没被访问的 | 性能接近OPT | 硬件支持复杂 | ❌ |
| FIFO（先进先出） | 替换最早进来的 | 实现简单 | 性能较差 | ⚠️ 会！ |
| Clock（NRU） | 近似LRU，扫描使用位 | 折中方案 | 性能不如LRU | ❌ |
有效访问时间（EAT）：
EAT = (1-p)×内存访问时间 + p×缺页中断处理时间
其中p是缺页率。
工作集模型：
• 工作集=进程在某段时间内频繁访问的页面集合
• 工作集大小=当前需要的页框数
• 工作集策略：确保进程可用页框数≥工作集大小→否则频繁缺页（抖动/Thrashing）
表格对比：常见虚拟内存管理方式
| 方式 | 基本单位 | 地址结构 | 碎片 | 实现复杂度 |
| 纯分页 | 页 | 页号+偏移 | 内部碎片 | 中等 |
|---|---|---|---|---|
| 纯分段 | 段 | 段号+偏移 | 外部碎片 | 较低 |
| 段页式 | 段+页 | 段号+页号+偏移 | 综合 | 最高 |
真题演练
例题1：（经典题）系统页面大小1KB，访问序列7,0,1,2,0,3,0,4,2,3,0,3,2,1,0,1，分配给进程3个页框，求LRU和FIFO的缺页次数。
解（简化解法——只给思路，真题需完整列置换表）：
LRU缺页次数：通过模拟页面访问序列，每次替换最久未使用的页面。
FIFO缺页次数：通过模拟，每次替换最早进入的页面。
结果通常：LRU缺页数≈12次左右，FIFO≈13次左右，LRU略优于FIFO。
例题2：（概念题）以下哪种情况会导致系统抖动（Thrashing）？A.页面置换算法太慢 B.分配给进程的页框数少于工作集 C.CPU利用率太高 D.内存容量不足
解：抖动=进程频繁缺页，导致大量时间花在磁盘I/O上而不是真正执行。根本原因是分配给进程的物理块（页框）太少，小于其工作集大小。选B。
注意事项
⚠️ 易错点1：缺页中断是"指令执行过程中"触发的中断（而非指令结束后），需要重新执行当前指令！
⚠️ 易错点2：OPT无法实现，只做理论比较用。LRU是最接近OPT的实用算法。
⚠️ 易错点3：Belady异常只发生在FIFO算法——增加页框数缺页率反而上升！
⚠️ 易错点4：LRU的硬件实现方案：计数器法（每页配计数器）或矩阵法（n×n矩阵）。
⚠️ 易错点5：抖动（Thrashing）≠死锁——抖动是频繁缺页导致几乎不执行，OS通过工作集模型或缺页频度控制来缓解。
⚠️ 易错点6：虚拟内存的最大大小不是物理内存大小，而是地址总线位数决定的寻址空间（如32位=4GB），但受限于物理内存+交换区。
⚠️ 易错点7：请求分页（Demand Paging）是"用到了才调入"，预调页是"提前调入可能用到的"，后者利用了空间局部性。
文件与磁盘调度
文件系统
重点 难度 2/3
通俗理解
文件系统 = 操作系统的"图书馆管理系统"——负责书（文件）放在哪、怎么找、怎么分类、怎么借还（读写）。
想象一个图书馆（文件系统）：
• 书（文件）→有名字、有内容、有作者（属性）
• 书架位置（目录/文件夹）→分类存放不同类别的书
• 借书登记表（FCB/文件控制块）→记录每本书的编号、位置、借阅状态
• 索书号（文件名/路径）→你要找书的唯一标识
• 目录卡片（目录文件）→按字母/分类排列，方便找书
核心公式/考点
文件控制块（FCB）包含：
• 文件名、文件类型、物理位置（磁盘块号列表）
• 大小、创建/修改时间、访问权限
• 文件所有者、链接计数
目录结构发展：
| 类型 | 特点 | 优点 | 缺点 |
| 单级目录 | 一个目录放所有文件 | 最简单 | 文件名不能重名 |
|---|---|---|---|
| 二级目录 | 每个用户一个目录 | 用户间隔离 | 组内文件管理不便 |
| 树形目录 | 目录嵌套（Linux/Windows） | 灵活、层次分明 | 路径较长 |
文件物理结构（磁盘块分配方式）：
| 分配方式 | 实现 | 优点 | 缺点 |
| 连续分配 | 文件占用连续磁盘块 | 顺序访问快 | 产生外部碎片，扩展困难 |
|---|---|---|---|
| 链接分配 | 每块存指向下一块的指针 | 无外部碎片，易扩展 | 随机访问慢，指针占空间 |
| 索引分配 | 用索引块存所有数据块指针 | 随机访问快 | 小文件浪费（1个索引块） |
| FAT表 | 文件分配表（链式+表） | 随机访问快，易于管理 | FAT表需占内存 |
| Unix混合索引 | 直接+间接索引块 | 小文件高效，大文件能管理 | 实现复杂 |
Unix混合索引（重点）：
• 12个直接块指针（小文件直接访问）
• 1个一级间接块（指向存有数据块指针的块）
• 1个二级间接块（指向存有一级间接块指针的块）
• 1个三级间接块（指向存有二级间接块指针的块）
真题演练
例题1：（软考真题）Unix文件系统使用混合索引，一个块大小4KB，地址指针4B，最大文件大小？
解：
1.一个块可存指针数=4KB/4B=1024个
2.直接块：12个块=12×4KB=48KB
3.一级间接：1024个块=1024×4KB=4MB
4.二级间接：1024×1024个块=4GB
5.三级间接：1024×1024×1024个块=4TB
6.最大文件≈48KB+4MB+4GB+4TB≈4TB+（实际还要考虑大文件）
例题2：（经典题）FAT（文件分配表）中，第i个表项存的是第i块下一块的块号。FAT表项大小32位，磁盘分区大小2TB，问FAT表多大？
解：
1.每个簇（基本分配单位）最小=磁盘大小/最大表项数
2.32位→最多2^32个表项
3.每个簇大小=2TB/2^32=512B
4.FAT表大小=2^32×4B=16GB（太大了！所以大磁盘用FAT32不合适）
注意事项
⚠️ 易错点1：文件目录本身也是文件——存的是FCB列表。
⚠️ 易错点2：树形目录中绝对路径从根"/"开始，相对路径从当前目录开始。
⚠️ 易错点3：连续分配的文件扩展需要移动大量数据——所以不适合动态增长的文件。
⚠️ 易错点4：索引分配中，文件大小受索引块数量限制——大文件需要多级索引。
⚠️ 易错点5：Unix混合索引对小文件（≤48KB）只用直接块，效率很高；大文件才用到间接块。
⚠️ 易错点6：FAT表既是链式分配（通过表项链），又支持随机访问（查表直接定位），是两种方式的结合。
磁盘调度
重点 难度 2/3
通俗理解
磁盘调度 = 电梯如何最高效地接送乘客——磁头就是电梯，请求就是按了楼层按钮的人，目标是总移动距离最小。
磁盘的结构：
• 盘片（Platter）：多个圆形盘片叠放
• 磁道（Track）：盘片上的同心圆
• 扇区（Sector）：磁道上的弧段，每个扇区512B或4KB
• 柱面（Cylinder）：所有盘片上同一磁道的集合
• 磁头（Head）：读写数据的装置，每个盘面一个磁头
磁盘访问时间 = 寻道时间 + 旋转延迟 + 传输时间
• 寻道时间（最耗时！占了60%~80%）：磁头移动到目标磁道
• 旋转延迟：盘片转到目标扇区
• 传输时间：实际读写数据
核心公式/考点
旋转延迟平均 = 转一圈时间的一半
转速7200RPM→每转时间=60/7200=8.33ms→平均旋转延迟=4.17ms
表格对比：五大磁盘调度算法
| 算法 | 策略 | 优点 | 缺点 |
| FCFS（先来先服务） | 按请求顺序处理 | 公平简单 | 平均寻道长，效率低 |
|---|---|---|---|
| SSTF（最短寻道优先） | 每次选最近的 | 平均寻道短 | 饥饿（边缘磁道请求） |
| SCAN（电梯算法） | 从内到外再到内（来回扫描） | 平均寻道好，无饥饿 | 中间磁道最公平 |
| C-SCAN（循环扫描） | 从外到内扫描，再到最外重新开始 | 各磁道等待时间均匀 | 额外空跑一次 |
| N-step SCAN | 分批次处理（N个请求一批） | 避免磁臂粘着 | 实现复杂 |
真题演练
例题1：（经典题）磁道请求序列：98,183,37,122,14,124,65,67。当前磁头在53，向0方向移动。求FCFS、SSTF、SCAN的总移动距离。
解：
FCFS顺序到：98→183→37→122→14→124→65→67
| 寻道距离： | 98-53 | + | 183-98 | + | 37-183 | + | 122-37 | + | 14-122 | + | 124-14 | + | 65-124 | + | 67-65 |
=45+85+146+85+108+110+59+2=640
SSTF：从53开始，最近的是65→67→37→14→98→122→124→183
距离：12+2+30+23+84+24+2+59=236（比FCFS好很多）
SCAN（往0方向）：
53→37→14→0（折返）→65→67→98→122→124→183
距离：16+23+14+65+2+31+24+2+59=236
注意：SCAN到达0后折返是公式化做法，实际不一定到0边界。
例题2：（概念题）以下哪种算法不会发生"饥饿"现象？A.SSTF B.FCFS C.SCAN D.以上都是
解：FCFS按请求顺序处理，绝对公平→不会饥饿。SSTF优先服务最近的，边缘磁道可能被忽略→会饥饿！SCAN（电梯算法）来回扫描，所有磁道都能被服务到→不会饥饿。选FCFS和SCAN。
注意事项
⚠️ 易错点1：磁盘访问时间中，寻道时间占比最大——所以调度算法主要优化寻道距离。
⚠️ 易错点2：SSTF是"局部最优"不是"全局最优"——贪心策略不能保证总的平均时间最小。
⚠️ 易错点3：SCAN算法的方向很重要——"往大方向扫描"和"往小方向扫描"结果不同。
⚠️ 易错点4：C-SCAN（循环扫描）对比SCAN：一个方向到头→直接跳到最另一端重新开始，服务更均匀。
⚠️ 易错点5：提高磁盘性能的方法：磁盘调度（算法层面）、磁盘缓存（内存层面提前缓存）、RAID（硬件层面并行）。
⚠️ 易错点6：固态硬盘（SSD）没有寻道时间和旋转延迟，所以磁盘调度算法对SSD意义不大。
进程PV与死锁
进程调度算法
重点 难度 2/3
通俗理解
进程调度算法=CPU决定"下一个谁用"的排队策略。就像银行柜台处理顾客的方式各有不同。
想象去银行办事：
• 🥇 FCFS（先来先服务）：谁先到谁先办——公平但后面排队的人等死
• 🥇 SJF（短作业优先）：取个号最快的业务先办——吞吐量大但长业务可能一直轮不到（饥饿）
• 🥇 时间片轮转RR：每人办5分钟，到时间换下一个人——大家轮流，没人等太久
• 🥇 优先级调度：VIP客户先办（优先级高的先执行）
• 🥇 多级反馈队列：新人先到快速窗口试试（时间片短），超时没办完就转到普通窗口（时间片长）
核心公式/考点
常用调度指标：
• 周转时间 = 完成时间 - 到达时间（从进来到离开的总时间）
• 平均周转时间 = Σ周转时间 / 进程数
• 带权周转时间 = 周转时间 / 实际运行时间（越接近1越好）
• 响应时间 = 第一次获得CPU时间 - 到达时间（用户感知的等待）
• 等待时间 = 周转时间 - 执行时间（排队等CPU的总时间）
表格对比：六大调度算法
| 算法 | 特点 | 优点 | 缺点 | 适用场景 |
| FCFS | 非抢占 | 简单公平 | 短作业等待长 | 批处理系统 |
|---|---|---|---|---|
| SJF | 可抢占/非抢占 | 平均等待时间最小 | 长作业饥饿 | 批处理（预估时间已知） |
| SRTF（最短剩余时间） | SJF的抢占版 | 响应更快 | 上下文切换多 | 交互式系统 |
| 时间片RR | 轮流 | 响应快，公平 | 时间片选值敏感 | 分时系统 |
| 优先级 | 分抢占/非抢占 | 紧急任务优先 | 低优先级饥饿 | 实时系统 |
| 多级反馈队列 | 多队列+动态调整 | 兼顾各类进程 | 实现复杂 | 通用OS（如Unix） |
真题演练
例题1：（经典题）三个进程A(到达0,执行8)、B(到达1,执行4)、C(到达2,执行9)，用FCFS、SJF（非抢占）、RR(q=3)求平均周转时间。
解：
FCFS顺序=A→B→C（按到达时间）
A: 0+8=8, B: 8+4=12, C: 12+9=21
平均周转=(8+12+21)/3=13.67
SJF（非抢占）：
0时刻只有A→A先执行（到8时刻）
8时刻：B(已到7,需4)和C(已到6,需9)→B短先执行
B: 8+4=12, C: 12+9=21
平均周转=(8+12+21)/3=13.67（这次SJF和FCFS一样，因为A太长了）
RR(q=3)：
0: A执行3→剩余5
3: B执行3→剩余1
6: C执行3→剩余6
9: A执行3→剩余2
12: B执行1→完成 (周转=12-1=11)
13: C执行3→剩余3
16: A执行2→完成 (周转=16-0=16)
18: C执行3→剩余0→完成(周转=18-2=16)
平均周转=(16+11+16)/3=14.33
例题2：（概念题）哪种调度算法可能导致饥饿？A.FCFS B.RR C.优先级调度 D.多级反馈队列
解：SJF（长作业饥饿）、优先级调度（低优先级饥饿）都可能导致饥饿。选C。
注意事项
⚠️ 易错点1：FCFS是非抢占的，但很多调度算法可以是抢占或非抢占版本（如SJF有抢占版SRTF）。
⚠️ 易错点2：时间片太小→上下文切换开销太大；时间片太大→退化为FCFS，响应变慢。
⚠️ 易错点3：SJF需要知道或预估进程执行时间——实际系统中难以准确预估。
⚠️ 易错点4：多级反馈队列的典型规则：时间片用完降级、新进程进入最高优先级队列、优先级高的队列先执行。
⚠️ 易错点5：周转时间vs响应时间——周转是"从生到死"，响应是"从生到第一次被服务"。
⚠️ 易错点6：抢占式调度可能在时间片用完或更高优先级进程到达时发生。
文件与磁盘调度
Spooling系统
重点 难度 2/3
通俗理解
Spooling（SPOOL=Simultaneous Peripheral Operations On-Line）系统 = 用磁盘做"缓冲池"，让慢速的独占设备（如打印机）看起来像可以共享的高速设备。
想象办公室只有一台打印机的场景：
• 没有Spooling：所有人排队打印——张三打印时打印机被独占，李四王五都得等
• 有Spooling：你把文件传给"打印服务器"（Spooling系统）→系统说"好的，排队中"，你马上可以回去工作→打印任务在后台排队处理
• 相当于有了一个"打印秘书"统一管理打印请求
Spooling系统的三大组件：
1.输入井/输出井：磁盘上的一块区域，用于暂存I/O数据
2.输入进程/输出进程：负责实际与设备打交道的守护进程
3.井管理程序：协调输入井和输出井的使用
核心公式/考点
Spooling技术的特点：
• 将独占设备改造成共享设备（逻辑上共享）
• 实现了虚拟设备功能（一台物理设备对应多个虚拟设备）
• 提高了I/O速度和设备利用率
• 典型的假脱机系统
Spooling系统的典型工作流程（以打印机为例）：
1.用户进程提交打印请求→系统在输出井中创建打印文件
2.打印守护进程从输出井中取出文件→发送给物理打印机
3.用户可以立即返回→无需等待打印完成
4.多个用户同时打印→输出井中按FIFO或其他算法排队
表格对比：Spooling vs 缓冲 vs Cache
| 维度 | Spooling系统 | 普通缓冲区 | Cache缓存 |
| 存储介质 | 磁盘（辅存） | 内存 | 高速内存/SRAM |
|---|---|---|---|
| 主要用途 | 解耦慢速独占设备 | 临时存储I/O数据 | CPU与主存速度匹配 |
| 典型应用 | 打印机共享 | 键盘输入缓冲 | CPU Cache |
| 数据流向 | 进程→磁盘→设备 | 进程↔内存↔设备 | CPU↔Cache↔主存 |
| 实现方式 | 软件（守护进程+磁盘） | 软件（内存分配） | 硬件（MMU+TBL） |
| 是否虚拟化 | ✅ 虚拟设备 | ❌ | ❌ |
真题演练
例题1：（软考真题）以下关于Spooling系统的描述，错误的是？A.实现了虚拟设备功能 B.把独占设备改造成共享设备 C.提高了CPU利用率 D.需要硬件DMA支持
解：
A✅ Spooling技术正是通过磁盘井+守护进程模拟出多个"虚拟打印机/终端"
B✅ 一台物理打印机，多个进程可以同时"打印"（逻辑上共享）
C✅ 进程不需要等待慢速I/O设备，可以继续执行CPU任务→CPU利用率提升
D❌ Spooling主要是软件技术（守护进程+磁盘空间），不需要特殊的DMA硬件支持
选D。
例题2：（经典题）Spooling系统中，负责将输出井中的数据实际发送给打印机的是？A.用户进程 B.打印守护进程 C.井管理程序 D.中断处理程序
解：
A❌ 用户进程只负责提交打印请求
B✅ 打印守护进程（也叫输出进程）负责从输出井取数据→送打印机
C❌ 井管理程序管理井空间分配
D❌ 中断处理程序处理打印机中断信号
选B。
注意事项
⚠️ 易错点1：Spooling的"虚拟化"是指一台物理设备对应多个逻辑设备，不是把一台设备变成另一台。
⚠️ 易错点2：Spooling系统使用磁盘空间作为缓冲，不是用内存——因为磁盘容量大，适合长期排队。
⚠️ 易错点3：Spooling并不是所有独占设备都能改造——如磁带机这种需要顺序访问的设备不适合Spooling。
⚠️ 易错点4：Spooling中的"输入井"预处理输入数据，"输出井"暂存输出数据，各司其职。
⚠️ 易错点5：Spooling系统的存在显著提高了多道程序系统的效率——I/O操作从同步变为异步。
⚠️ 易错点6：Spooling和缓冲区的区别：缓冲区（Buffer）是内存中的临时存储；Spooling用磁盘，容量更大，可以长期保存。