操作系统期末复习

🥇 第一部分：考前必背公式与计算套路

1. CPU 调度计算（画甘特图！）

• 完成时间 = 进程最后一次离开CPU的时刻。
• 周转时间 = 完成时间 - 到达时间。（进程在系统里一共待了多久）。
• 等待时间 = 周转时间 - 实际执行时间。（纯排队的时间，用减法算最不容易错！）。
• ⚠️ SJF/SRTF 避坑：时刻盯紧“当前时间点”，只能调度已经到达的进程；抢占式要注意随时对比剩余时间。

2. 页面置换与缺页率计算

• 缺页次数 = 只要内存里没有，去外存拿了，就算一次（包括初始刚装入时的前几次，必定缺页！）。
• 置换次数 = 缺页次数 - 分配给进程的物理块数。
• LRU（最近最久未使用）：往前看历史。⚠️ 命中时，一定要在草稿纸上标记它变成了“最新被访问”，重置寿命！
• Belady 异常：只有 FIFO（先进先出） 会出现分配的物理块增加、缺页率反而升高的奇葩现象。

3. 分页地址转换（十六进制转物理地址）

• 三步刀法：
  1. 看页大小，确定偏移量位数（如1KB = $2^{10}$，偏移量10位）。
  2. 把十六进制逻辑地址转成二进制，一刀切开，右边10位是偏移，左边是逻辑页号。
  3. 查页表把逻辑页号替换为物理块号，和刚才的偏移量重新拼接，最后转回十六进制。

4. 磁盘调度计算

• 访盘时间 = 寻道时间 + 旋转延迟 + 传输时间。（磁盘调度算法只能优化寻道时间）。
• SCAN（电梯算法）：必须走到磁盘最尽头（如199）才能掉头！
• C-SCAN（循环扫描）：走到尽头后，直接飞跃回起点（0），飞跃途中的请求不服务！

5. 混合索引（Inode）最大文件大小计算

• 步骤：先算出一个盘块能装几个指针 N = 盘块大小 / 指针大小。
• 公式：最大文件大小 = (直接索引项数 + N + N² + N³) × 盘块大小。

6. FAT表大小计算（硬核推演）

• 盘块数 = 硬盘大小 / 盘块大小。（如500MB / 1KB = 500K 个盘块）。
• 项数 = 盘块数。（500K项）。
• 每项位数 = 满足 $2^n \ge$ 盘块数 的最小 $n$。（$2^{19} = 524288 > 500K$，至少19位）。
• 字节对齐：19位不好存，向上对齐到4的倍数即20位（2.5字节）。
• FAT表总大小 = 项数 × 每项字节数。（500K × 2.5B = 1250KB）。

---

🥈 第二部分：大题伪代码神级模板（PV操作）

遇到写PV操作伪代码，死守以下三条铁律：

1. 第一步写信号量定义和初值！不写扣一半分！（empty=N, full=0, mutex=1等，并加注释）。
2. 死锁防雷：如果有两个P操作连在一起，必须先 P(同步/资源)，再 P(互斥锁)！ 写反必死锁，直接零分！V操作顺序随意。
3. 第一类读者-写者问题（读者优先）口诀：
   • 第一个来的读者负责加写锁：if(readcount == 1) P(w);
   • 最后一个走的读者负责解写锁：if(readcount == 0) V(w);

⚠️ P/V 原语底层逻辑填空（必考抠字眼）：

• P 操作：信号量 减1。当其值 < 0 时，进程阻塞。
• V 操作：信号量 加1。当其值 <= 0 时，唤醒阻塞队列中的进程（千万别漏了等于号！）。

---

🥉 第三部分：核心概念速览（选择/判断/填空）

1. 进程与线程的灵魂辨析

• 进程：资源分配的独立单位，拥有独立的地址空间。
• 线程：CPU调度的基本单位，只拥有极少的私有资源（TCB、PC程序计数器、寄存器、栈Stack），与其他线程共享代码段、数据段、打开的文件。
• 线程切换：同进程内线程切换极快（不切内存）；不同进程的线程切换和普通进程切换一样慢。

2. 状态转换（只能这么转，其他全错！）

• 就绪 ➡️ 运行：被调度程序选中。
• 运行 ➡️ 就绪：时间片用完 / 被抢占。
• 运行 ➡️ 阻塞：进程主动请求I/O。
• 阻塞 ➡️ 就绪：I/O完成。
• 绝对不可能：阻塞 ➡️ 运行（必须去排队）；就绪 ➡️ 阻塞（没上CPU不能自己阻塞）。
• 挂起（Suspend）：中级调度（内存调度）干的事，为了腾内存，把进程踢到外存。

3. 死锁（Deadlock）

• 死锁四大必要条件：互斥、请求和保持、不剥夺、循环等待。
• 不安全状态 ≠ 死锁：死锁 ⊂ 不安全状态。不安全只是可能死锁。
• 资源分配图：无环必定无死锁；有环+单实例必定死锁；有环+多实例未必死锁。

4. 内存管理（碎片与重定位）

• 内碎片：固定分区、分页。（口诀：页有内）。
• 外碎片：动态分区、分段。（口诀：段有外）。
• 动态重定位：在执行过程中将逻辑地址转换物理地址（需要硬件重定位寄存器）。静态重定位是在装入过程中转换。
• 快表（TLB）：放在Cache里，加速页表查找。多级页表是为了节省页表连续内存，反而会降低查询速度。
• 抖动（Thrashing）：分配的物理块太少，频繁缺页。用工作集（Working Set）解决。

5. 文件与I/O系统

• 所有 I/O 指令统统是特权指令。
• DMA 的中断：传输大块数据，全程只有两次中断（开始前和结束后），数据传输不经过CPU。
• 文件目录改进：把FCB一分为二（文件名 + Inode编号）。目录只存这两个，极大增加一个盘块能装的条目，大幅减少查找时启动磁盘的次数。
• open() 系统调用：只是把 FCB/Inode 读入内存的打开文件表，绝对不会把文件内容读入内存！

---

🚫 第四部分：黄金避坑指南（看到这些字眼立刻拉响警报）

1. “向下管理硬件” ➡️ ❌ 错！OS向下管理所有软硬件资源（包括文件、进程等）。
2. “系统调用是在用户态执行的” ➡️ ❌ 错！用户态发起，内核态执行。
3. “微内核提高了系统效率/速度” ➡️ ❌ 错！微内核提高了安全性和可扩展性，但通信开销极大，导致速度变慢。
4. “用户进程可以从PCB中读取信息” ➡️ ❌ 错！PCB存放在内核态（系统区），用户进程毫无权限读取。
5. “同步是间接制约，互斥是直接制约” ➡️ ❌ 错！说反了！互斥是间接（无意识抢东西），同步是直接（有意识协作）。
6. “无名管道任意进程都能用” ➡️ ❌ 错！无名管道在内存中，只能用于父子/兄弟等有亲缘关系的进程。

---

💡 Linux 专场速记词典：

• 0号进程：INIT_TASK。
• 僵死态：TASK_ZOMBIE (4) —— 进程已死，但PCB还在等父进程收尸。
• 调度策略：普通进程 SCHED_OTHER；实时进程 SCHED_FIFO 或 SCHED_RR。
• Linux内存分配：Buddy（伙伴算法）治外碎片，Slab分配器治内碎片。
• 页面交换守护进程：kswapd()。

---

计算题

🧮 第一战区：内存与虚拟存储（最硬核，4种题型）

题型 1：逻辑地址转物理地址（十六进制切拼法）

• 题源：《复习题》综合题第3题（逻辑空间32页，每页1K，主存16K，求 0A5C 的物理地址）。
• 计算套路（三步定乾坤）：
  1. 算位宽：看页面大小定“页内偏移位”（1K = $2^{10}$，偏移占10位）。
  2. 转二进制切开：把 16 进制转成二进制，从右往左数 10 位切一刀。左边是页号，右边是偏移。
  3. 查表拼接：根据左边的页号查出物理块号，转成二进制，拼在刚才的 10 位偏移量前面。再每 4 位一划，转回 16 进制。

题型 2：页表规模评估计算

• 题源：《复习题》综合题第2题（逻辑空间32页，每页2K，物理空间1M，求页表项数和位数）。
• 计算套路：
  1. 页表项数 = 逻辑空间的总页数（题目直接给了32页，就是32项）。
  2. 物理块数 = 物理空间 / 页面大小（1M / 2K = 500K 个块）。
  3. 页表项位数 = 物理块数转成二进制需要的位数。$500K \approx 2^{19}$，所以至少需要 19位。

题型 3：动态分区分配推演图

• 题源：《复习题》综合题第1题（内存640K，OS占40K。按序列申请/释放，用首次适应和最佳适应画图）。
• 计算套路：
  • 首次适应（First Fit）：只看地址！只要从头数第一个能塞进去的洞，直接塞！
  • 最佳适应（Best Fit）：找大小最贴合的洞！每次分配前，把所有的洞按大小排个序，挑那个“大于等于申请量且最小的洞”。
  • ⚠️ 避坑：释放内存时，一定要看它上下有没有相邻的空洞，有的话必须合并成一个大洞！

题型 4：页面置换与缺页率计算

• 题源：PPT第10章与《复习题》综合题第3下半部分（FIFO、OPT、LRU）。
• 计算套路：
  • 画格子推演！命中时，LRU一定要在草稿上更新它的寿命。
  • 公式：缺页率 = 缺页次数 / 总访问次数。

---

💽 第二战区：文件与磁盘系统（最巧妙，3种题型）

题型 5：混合索引最大文件大小计算

• 题源：《复习题》简答题第2题（10个直接，1个一次间接，1个二次间接。物理块4KB，指针4B）。
• 计算套路：
  1. 算出一个盘块能装几个指针：N = 4KB / 4B = 1024 个。
  2. 直接索引：10 × 4KB = 40KB。
  3. 一次间接：N × 4KB = 1024 × 4KB = 4MB。
  4. 二次间接：N × N × 4KB = 1024 × 1024 × 4KB = 4GB。
  5. 累加：4GB + 4MB + 40KB。

题型 6：目录改进（FCB瘦身）检索次数计算

• 题源：《复习题》简答题第3题（FCB 64B，瘦身后文件名+Inode为 10B，256个目录项）。
• 计算套路：
  1. 算老方法占几个盘块：$256 \div (512/64) = 32$ 块。平均找一半：$(1+32)/2 = 16.5$ 次。
  2. 算新方法占几个盘块：$256 \div \lfloor 512/10 \rfloor = 256 \div 51 = 6$ 块。平均找一半：$(1+6)/2 = 3.5$ 次。
  3. 绝命陷阱：新方法找到后只是拿到了Inode编号，还要再去磁盘读一次真实的Inode内容！ 所以最后总次数是 3.5 + 1 = 4.5 次。（漏加这个 1 直接全错）。

题型 7：FAT表存储空间计算

• 题源：《复习题》综合题第1题（1KB盘块，500MB硬盘，求FAT表大小）。
• 计算套路（三步走）：
  1. 盘块总数 = 500MB / 1KB = 500K 个。
  2. 求位数：$2^{18} < 500K < 2^{19}$，至少需要 19 位。字节对齐向上取整到 20 位（2.5 Byte）。
  3. 总大小 = 500K × 2.5 Byte = 1250 KB。

题型 8：磁盘寻道调度计算

• 题源：PPT 第13章。
• 计算套路：
  • SCAN（电梯）：当前位置走到尽头最大值（如199）或最小值（0），再折返。
  • C-SCAN（循环扫描）：走到尽头后，直接用减法飞回另一个尽头起点，再继续。
  • 把每一步的差值取绝对值相加即可。

---

⏱️ 第三战区：CPU与进程（最容易看错，2种题型）

题型 9：CPU调度甘特图与时间计算

• 题源：PPT第6章（FCFS、SJF、RR）。
• 计算套路：
  • 一定要标明时间轴！
  • 如果是 抢占式SJF (SRTF)，每当有新进程到达，都必须暂停当前进程，重新比对剩余时间！
  • 等待时间 = 周转时间 - 执行时间（用减法算，千万别去图上一块块数排队时间，极易漏数）。

题型 10：资源分配图化简（死锁检测）

• （严格来说这是逻辑推演题，但具有计算属性）
• 计算套路：
  • 找“不被阻塞”的进程（它申请的资源，方框里还有剩下的黑点）。
  • 把它的线全部擦掉，把黑点释放回方框。
  • 继续找下一个不被阻塞的进程。全擦完 = 安全；擦不完 = 死锁。