操作系统复习笔记

Chap 1 Introduction

• 什么是操作系统 (What is an operating system)

  • 自顶向下视角：扩展机器 (Extended machine) - 隐藏硬件杂乱的细节，为用户提供易用的虚拟机 (Virtual machine)
  • 自底向上视角：资源管理者 (Resource manager) - 在时间和空间上实现资源的复用 (Multiplexing)

• 操作系统历史 (History of operating systems)

  • 第一代 (1945-1955)：真空管与插接板 (Vacuum tubes, plug boards)，纯手工操作 (Handwork)
  • 第二代 (1955-1965)：晶体管 (Transistors) 与批处理系统 (Batch systems)
  • 第三代 (1965-1980)：集成电路 (ICs)，多道程序设计 (Multiprogramming)，分时系统 (Time-sharing system)
  • 第四代 (1980-至今)：个人计算机 (Personal computers)，网络操作系统与图形用户界面 (GUI)

• 计算机硬件复习 (Computer hardware review)

  • 处理器 (CPU) ：寄存器 (Registers，如程序计数器 PC、指令寄存器 IR、程序状态字 PSW)，流水线 (Pipeline)，超标量 (Superscalar) 与多核 (Multicore)
  • 存储器层次结构 (Memory hierarchy) ：寄存器 (Registers) $\rightarrow$ 缓存 (Cache) $\rightarrow$ 主存 (Main memory/RAM) $\rightarrow$ 磁盘 (Magnetic disk) $\rightarrow$ 磁带 (Magnetic tape)
  • 磁盘物理结构 ：柱面 (Cylinders)，磁道 (Tracks)，扇区 (Sectors)，盘片 (Platters)，磁头 (Heads)
  • 输入/输出设备 (I/O) ：包含控制器 (Controller) 与设备本身；交互方式包括轮询 (Polling)、中断驱动 (Interrupt-driven)、直接内存访问 (DMA)

• 操作系统动物园 (The operating system zoo)

  • 涵盖大型机 (Mainframe)、服务器 (Server)、多处理器 (Multiprocessor)、个人电脑 (PC)、嵌入式 (Embedded)、传感器节点 (Sensor node)、智能卡系统 (Smart card OS) 等
  • 实时操作系统 (Real-time OS) ：区分为强实时 (Hard real-time，绝对不能超时) 与弱实时

• 操作系统基本概念 (Operating system concepts)

  • 进程 (Processes) ：运行中的程序；构成进程树 (Process tree)；包含进程表 (Process table) 和标识符 (PID/UID/GID)；以及进程间通信 (IPC)
  • 地址空间 (Address Spaces) ：内存分配列表，涉及虚拟内存 (Virtual memory)
  • 文件系统 (Files) ：目录层次 (Directory hierarchy) 与根目录 (Root directory)，挂载 (Mount)，以及用于连接两个进程的管道 (Pipe)
  • 保护机制 (Protection) ：9位二进制保护码 (9-bit rwx protection code)
  • 命令解释器 (Shell) ：如 sh, bash 等，支持后台作业 (Background job, &) 和重定向 (Redirect, < 或 >)

• 系统调用 (System calls)

  • 概念：运行中的程序与操作系统之间的接口，调用时需要陷入内核 (Trap to the kernel)
  • 进程管理：fork, waitpid, execve, exit
  • 文件管理：open, close, read, write, lseek, stat
  • 目录与杂项：mkdir, rmdir, link, unlink, mount, chdir, chmod, kill 等

• 操作系统结构 (Operating system structure)

  • 单体系统/宏内核 (Monolithic System) ：”大杂烩” (The big mess)，包含主程序、服务过程和实用过程

  • 分层系统 (Layered System) ：将操作系统组织为进程层的层次结构

  • 微内核 (Microkernels / Client-server model) ：内核仅处理中断、调度等核心逻辑，客户端与服务器进程通过消息传递 (Sending messages) 获得服务

  • 虚拟机 (Virtual Machines) ：包含 Type 1 型与 Type 2 型虚拟机监控器 (Hypervisor)

重点与难点标注

• 核心必考点（基于例题） ：

  1. 平均内存访问时间计算（AMAT） ：考试极大概率出计算题。必须掌握逐级未命中的概率计算逻辑。

     • _公式应用_：$Time = 命中率_1 \times 时间_1 + (1-命中率_1) \times 命中率_2 \times 时间_2 + (1-命中率_1) \times (1-命中率_2) \times 时间_3$。（对应例题 Q15）

  2. 磁盘物理结构与访问时间 ：

     • 必须熟悉磁头 (Heads)、盘片 (Platters，1盘片=2磁头)、柱面 (Cylinders) 的容量计算。
     • 磁盘读写时间 = 寻道时间 (Seek time) + 旋转延迟 (Rotational latency) + 传输时间 (Transfer time)。（对应例题 Q11）

  3. 系统调用失败的边界条件 ：

     • fork() 失败：进程表（Process table）已满，或内存/交换空间耗尽。
     • exec() 失败：指定的文件名不存在，或该文件不是有效的可执行文件。
     • unlink() 失败：文件不存在，或调用进程没有权限。（对应例题 Q20）

  4. lseek 与 read 的组合操作 ：

     • 注意数组下标陷阱。lseek(fd, 3, SEEK_SET) 意味着将指针移动到文件的第 4 个字节（索引从 0 开始计，0, 1, 2, 3）。后续调用 read 读取 4 个字节时，将输出索引 3, 4, 5, 6 对应的字符。（对应例题 Q23，输出 1, 5, 9, 2）

• 易混淆的易错点 ：

  1. Trap 与 Interrupt 的混淆 ：Trap（陷阱）是由软件（用户程序）主动触发的指令，目的是为了从用户态切换到内核态（User mode $\rightarrow$ Kernel mode）来调用操作系统内核服务；而硬件中断（Interrupt）是异步的外部事件触发。 （对应例题 Q17）
  2. 时间单位换算失误 ：在存储金字塔和磁盘计算中，极容易在时间单位上丢分。牢记：1 ms（毫秒）= 1,000 µs（微秒）= 1,000,000 ns（纳秒）。（对应例题 Q15，最后需统一转换单位进行相加）
  3. 库函数名 vs 系统调用名 ：在 C 程序中，我们调用的是库函数（Library procedure，如 read），它会对程序员可见且非常重要。而在操作系统内核的底层，真正的系统调用是没有名字的，它仅通过寄存器或栈传入的一个“编号（Number）”来索引系统调用表（Table index）。（对应例题 Q26）

名词解释与核心公式

【名词解释】

• Operating System (OS) ：操作系统是运行在硬件基础之上的系统软件，它向应用程序提供一个清晰、美观的接口（Extended machine），同时负责公平、高效地管理计算机的所有硬件资源（Resource manager，涉及时间复用和空间复用）。

• Multiprogramming ：多道程序设计。将内存划分为多个分区，同时存放多个作业，当一个作业等待 I/O 时，CPU 可以切换执行另一个作业，从而提高资源利用率。

• Trap instruction ：陷阱指令。一种特殊的机制，用于将 CPU 的执行模式从用户态（User mode）切换到内核态（Kernel mode），使得用户程序能够安全地调用操作系统内核中的特权函数（即系统调用）。

• System Call ：系统调用。运行中的程序与操作系统之间的标准接口，是操作系统向上层提供的底层服务函数（如创建进程、读写文件等）。

• Process ：进程。一个正在执行中的程序实例，是操作系统分配资源的基本单位，其状态信息存储在进程表（Process table / PCB）中。

• Pipe ：管道。一种用于连接两个进程的伪文件（Pseudofile），实现进程间通信（IPC），前一个进程的输出自动成为后一个进程的输入。

• Microkernel ：微内核。一种操作系统架构模型，将中断处理、进程调度、IPC等最核心的功能保留在内核态，而将文件服务、终端服务等移至用户态的“服务器进程”中，以此提高系统的可靠性和灵活性。

【核心公式】

• 磁盘总容量公式 (Disk Capacity) ：
  $Capacity = Cylinders \times Heads \times Sectors_per_track \times Bytes_per_sector$

  (注：总磁头数 Heads 等于 盘片数 Platters $\times 2$)

• 磁盘平均访问时间公式 (Average Disk Access Time) ：

  $T_{access} = T_{seek} \text{ (寻道时间)} + T_{rotational} \text{ (旋转延迟)} + T_{transfer} \text{ (传输时间)}$

  (注：传输时间 $T{transfer} = \text{要传输的数据量} / \text{传输速率}$)_

• 平均内存访问时间公式 (Average Memory Access Time, AMAT) ：

  $AMAT = H_{cache} \times T_{cache} + (1 - H_{cache}) \times H_{RAM} \times T_{RAM} + (1 - H_{cache}) \times (1 - H_{RAM}) \times T_{disk}$

  (注：计算时必须统一时间单位，例如全部转化为 ns)

你现在是一位拥有多年教学经验的专业讲师。请帮我总结以下ppt及例题内容，并为我制作一份期末复习提纲。
 例题及解析：
请严格按照以下结构输出：
核心逻辑框架：用一句话概括这部分内容的核心主旨。
知识点思维导图：使用层级列表（Markdown格式）梳理章节脉络（使用英文标注词汇，以应对全英文试题）：
重点与难点标注：标出考试必考的重点和容易混淆的易错点。
名词解释与核心公式：提取所有重要概念及专业术语的简明定义。

Chap 2 Processes and Threads

• 2.1 Processes (进程)

  • What is process: An abstraction of a running program (动态概念，执行中的程序).

  • Difference between process and program: Program is static (静态代码), Process is dynamic (包含代码、数据和PCB). Process is temporary; Program is permanent.

  • Process states and model:

    • Three basic states: Running (运行), Ready (就绪), Blocked (阻塞/等待).
    • State transitions (状态转换): 4种核心转换（如阻塞由于等待I/O，就绪由于调度器选择等）。

  • What information in a process:

    • PCB (Process Control Block): 核心数据结构，包含PID、CPU调度信息、内存管理、寄存器上下文等。

  • Process Context switch (上下文切换):

    • Includes User Context, Register Context, System Context. Overhead is high.
    • fork() 创建进程。fork(); fork(); 会让初始的1个进程变成4个进程。

• 2.2 Threads (线程)

  • What is thread? Why need threads?: Lightweight Process (LWP). 基本的CPU调度单位。原因：高响应性、资源共享、创建销毁开销小（Economy）、多核利用。

  • Difference between process and thread:

    • Process: 资源分配的基本单位 (Resource allocation unit).
    • Thread: CPU调度的基本单位 (Scheduler unit). 同一进程内的线程共享地址空间和全局变量。

  • Thread Implementations and their tradeoffs:

    • User-level threads (ULT): 用户级线程，内核无感知。切换极快，但一个线程阻塞导致整个进程阻塞。

    • Kernel-level threads (KLT): 内核级线程。支持多核并行，单个线程阻塞不影响其他，但切换开销大。

    • Hybrid: 混合模型 (如 Solaris)，将ULT多路复用到KLT上。

    • Pop-up threads: 弹出式线程，消息到达时动态创建。

• 2.3 Interprocess communication (IPC, 进程间通信)

  • Race condition (竞态条件): 多个进程并发访问共享数据，结果依赖于执行顺序。

  • Critical region and mutual exclusion (临界区与互斥): 满足4个条件（无两个进程同时进入、不假设CPU速度/数量、临界区外不阻塞他人、不无限期等待）。

  • Mutual exclusion using busy waiting (忙等待互斥):

    • Disabling Interrupts (关中断)
    • Lock Variables (锁变量)
    • Strict Alternation (严格轮换) - 若代码写死轮换，可能违背“临界区外不阻塞他人”原则（导致饥饿）。

  • Peterson’s Solution: 纯软件方案，结合 turn 和 interested 数组（仅限2个进程）。

  • TSL (Test-and-Set Lock): 硬件原子指令，支持多处理器。

  • Sleep and Wakeup: 解决忙等待带来的优先级翻转（Priority Inversion）问题。

    • 用户级线程（ULT）中，如果调度器采用优先级调度，优先级翻转依然可能发生（高优先级线程死循环等锁，低优先级线程无法运行释放锁）。

  • Semaphores (信号量): Integer counter + Queue。P(Dow申请资源n) ，V(Up) 释放资源。
    
    

  • Monitor (管程): 编程语言级别的同步机制，包含 Condition variables (wait/signal)。

  • Passing Message (消息传递): send() 和 receive() 原语。
    

  • Barrier (屏障): 阶段性同步。即使只有两个进程，使用Barrier进行阶段(phase)同步也是有意义的。
    

• 2.4 Classical IPC problems

  • Dining-Philosophers Problem (哲学家就餐问题): 重点在于避免死锁 (Circular Wait)。
  • Readers and Writers Problem (读者-写者问题): 读写互斥，读读共享。分为读者优先和写者优先。

• 2.5 Scheduling (调度)

  • What is scheduling / Scheduling objectives: 决定哪个进程获得CPU。目标包括公平、吞吐量、周转时间、响应时间等。

  • CPU Scheduling:

    • FCFS (First-Come First-Served): 先来先服务。易产生 Convoy effect (护航效应)。
    • SJF (Shortest Job First): 最短作业优先。平均等待时间 (AWT) 最优，但易导致长作业 Starvation (饥饿)。
    • Round-robin (RR): 时间片轮转。交互式系统最常用。例题 43 考点: 效率计算公式效率 $\text{Efficiency} = Q / (Q+S)$
    • Priority: 优先级调度。可静态可动态，可能导致饥饿。
    • Multi-Queue & Multi-level Feedback (MLFQ): 多级反馈队列。动态降低长时间占用CPU进程的优先级。例题 46 考点: CTSS系统时间片呈指数增长（1, 2, 4, 8, 15…）。
    • Guaranteed Scheduling / Lottery Scheduling / Fair Sharing: 保证调度 / 彩票调度（概率机制） / 公平共享调度。

  • Scheduling for real-time systems:

    • 可调度性校验公式 $\sum(C_i/P_i) \le 1$。

  • Scheduling for threads: User-level (内部调度) vs Kernel-level (系统调度)。

重点与难点标注

必考重点 1：CPU利用率与并行时间计算（结合例题 7、8）

• 难点解析 ：当多个进程并发执行时，它们会交替使用CPU和I/O。我们需要使用概率论的思想。若一个进程的I/O等待概率为 $p$，则 $n$ 个进程同时等待I/O的概率为 $p^n$。此时CPU闲置。

• 实战运用（例题8） ：多道程序度 $n=6$，I/O等待率 $p=40% = 0.4$。

  CPU Utilization = $1 - p^n$ $= 1 - 0.4^6 \approx 1 - 0.004096 = 99.59%$。

• 实战运用（例题7） ：串行执行时间 = $20 + 20 = 40$ 分钟。并行执行时，I/O $p=50%$，$n=2$。并行时的 CPU 效率 $= 1 - 0.5^2 = 75%$。两个任务共需要 $40$ 分钟的绝对CPU时间，故实际流逝的物理时间 = $40 / 0.75 = 53.33$ 分钟。

必考重点 2：各类调度算法的周转时间计算（结合例题 45）

• 易错点 ：画甘特图（Gantt Chart）时，务必看清题目是否“抢占（Preemptive）”，是否考虑“上下文切换开销（Overhead）”。

• 周转时间 (Turnaround Time) = 完成时间 - 到达时间。

• 实战对比 ：对于运行时间(10, 6, 2, 4, 8)的5个任务：

  • SJF (最短作业优先) ：按 (2, 4, 6, 8, 10) 顺序执行。完成时间分别为 2, 6, 12, 20, 30。平均周转时间 = $(2+6+12+20+30)/5 = 14$ 分钟。（永远是最小的！）

  • FCFS (先来先服务) ：按 (10, 6, 2, 4, 8) 顺序执行。平均 = $19.2$ 分钟。

  • Priority (优先级) ：按优先级高低执行，得出平均 = $18.8$ 分钟。

必考重点 3：实时系统的可调度性分析

• 判断标准 ：如果所有周期性任务的CPU占用率总和 $\le 1$（即 $100%$），则系统是可调度的 (Schedulable)。

• 实战运用 ：两个语音任务，每 $6$ms 运行 $1$ms $\rightarrow 2 \times (1/6) = 33.33%$。视频任务 $25$帧/秒（即周期 $P = 1000/25 = 40$ms），每帧消耗 $C=20$ms $\rightarrow 20/40 = 50%$。总利用率 $= 33.33% + 50% = 83.33% \le 100%$。结论：系统可调度！

☠️ 高频易混淆点：Peterson算法 vs Strict Alternation（结合例题 30）

• 易错辨析 ：严格轮换（Strict Alternation，while(turn != 0) 这种纯靠一个变量交替的代码）违背了互斥四大条件中的“临界区外不阻塞他人”。如果进程0执行完把 turn 改为1，但进程1此时并不想进入临界区，进程0想再次进入时会被永远卡死。Peterson算法通过增加 interested 数组完美解决了这个问题，考试时极大概率要求分析残缺代码会违背哪条原则。

名词解释与核心公式

【重要概念 / 名词解释】

1. Process Control Block (PCB / 进程控制块): The data structure used by the operating system to store all the information about a process (e.g., PID, state, registers, memory pointers). 它是系统感知进程存在的唯一标志。

2. Context Switch (上下文切换): The process of saving the state of the currently running process and loading the state of the next process to run. Pure overhead (纯消耗，不作有用功).

3. Race Condition (竞态条件): A situation where multiple processes read and write shared data concurrently, and the final result depends on the exact execution order.

4. Priority Inversion (优先级翻转): A scenario where a high-priority process is blocked waiting for a lock held by a low-priority process, while medium-priority processes continue to execute, effectively delaying the high-priority process indefinitely. (使用Sleep and Wakeup或优先级继承协议解决).

5. Convoy Effect (护航效应): In FCFS scheduling, short I/O-bound processes gather behind a long CPU-bound process, resulting in low device utilization and poor response times.

【核心计算公式】

1. CPU Utilization (CPU利用率概率公式) ：

   $$CPU_Utilization = 1 - p^n$$

   (其中 $p$ 为单一进程等待 I/O 的时间比例/概率，$n$ 为内存中的多道程序数量即 Degree of multiprogramming)

2. Real-Time Schedulability (实时可调度条件) ：

   $$\sum_{i=1}^{m} \frac{C_i}{P_i} \le 1$$

   (其中 $C_i$ 为任务 $i$ 需要的CPU计算时间 Burst time，$P_i$ 为任务 $i$ 的发生周期 Period)

3. Turnaround Time (周转时间) ：

   $$T_{turnaround} = T_{completion} - T_{arrival}$$

   (完成时刻减去到达时刻。Average Turnaround Time 则是所有进程此指标的平均值)

4. Round-Robin CPU Efficiency (轮转调度效率 - 例题 43) ：

   $$Efficiency = \frac{\text{Useful Time}}{\text{Useful Time} + \text{Switch Overhead}}$$

   (若时间片 $Q$ 极长 $Q>T$，则效率为 $\frac{T}{T+S}$；若 $S < Q < T$，则发生时间片耗尽切换，效率为 $\frac{Q}{Q+S}$)

Chapter 6 Deadlock

• Resource

  • Preemptable resources (可抢占资源)：如内存 。

  • Nonpreemptable resources (不可抢占资源)：如CD刻录机 。

  • Resource utilization sequence (资源使用顺序)：Request (请求), Use (使用), Release (释放) 。

• Introduction to deadlocks (死锁简介)

  • 一组进程中的每个进程都在等待仅由该组中另一个进程才能引发的事件 。

  • Four Conditions for Deadlock (死锁的四个必要条件) ：

    1. Mutual exclusion (互斥条件) 。
    2. Hold and wait (持有并等待条件) 。
    3. No preemption (不可抢占条件) 。
    4. Circular wait (循环等待条件) 。

  • Deadlock Modeling (死锁建模)：Resource-Allocation Graph (资源分配图，使用有向图表示) 。
    

• The ostrich algorithm (鸵鸟算法)

  • Ignore the problem：假设死锁极少发生，由于预防成本高昂，UNIX和Windows等系统通常采用此策略 。

  • 当系统表填满导致鸵鸟算法面临崩溃时，系统管理员可以通过预留部分专属资源（Reserved resources）来运行Shell和关键程序，从而手动杀死死锁进程以恢复系统。

• Deadlock detection and recovery (死锁检测与恢复)

  • Detection (检测)：

    • One resource of each type (每类单一资源)：Directed graph cycle detection (有向图环检测算法) 。
    • Multiple resources of each type (每类多个资源)：Vector/Matrix comparison algorithm (向量/矩阵比较算法) 。

  • Recovery (恢复)：

    • Recovery through preemption (通过抢占恢复) 。
    • Recovery through rollback (通过回滚恢复) 。
    • Recovery through killing processes (通过杀死进程恢复) 。

• Deadlock avoidance (死锁避免)

  • Safe and Unsafe States (安全与不安全状态) 。

  • Banker’s Algorithm (银行家算法) 。

    • _例题25考法_：在有 $m$ 个资源类和 $n$ 个进程的系统中，银行家算法检查一次状态安全性的操作步数正比于 $m n^2$（即 $a=1, b=2$）。

• Deadlock prevention (死锁预防)

  • Attacking Mutual Exclusion (破坏互斥)：Spooling (假脱机技术) 。

  • Attacking Hold and Wait (破坏持有并等待)：Request all resources initially (初始一次性请求所有资源) 。

  • Attacking No Preemption (破坏不可抢占)：Take resources away (强行剥夺资源) 。

  • Attacking Circular Wait (破坏循环等待)：Order resources numerically (资源按序编号) 。

    • _例题27考法_：通过限制进程“在任何时刻只能拥有一个资源”来消除循环等待是不可接受的。例如将大文件从磁带复制到打印机，由于内存不足，必须循环执行请求和释放，这会导致无法保证文件在连续的纸张上打印。

• Other issues (其他问题)

  • Two-Phase Locking (两阶段锁) 。

  • Communication Deadlocks (通信死锁)：由消息丢失引起，通过 Timeout (超时重传) 解决 。

    • 路由器A向B发送窗口大小为0的阻塞消息，随后发送恢复传输的消息丢失，导致双方永远等待。这是一种典型的 Communication Deadlock，可通过超时重传机制解决。

    • 分布式系统中使用信箱（Mailbox），如果A发给B并等待回复，B发给C并等待回复，C发给A并等待回复，此时信箱为空，所有通信死锁的条件均已满足，会发生死锁。

  • Livelock (活锁) 与 Starvation (饥饿) 。

重点与难点标注

• 重点 (Must-Know) ：

  • Banker’s Algorithm (银行家算法) 的计算与推演 ：务必熟练掌握通过 Allocation (已分配)、Max (最大需求)、Need (还需) 和 Available (可用) 矩阵来寻找 Safe Sequence (安全序列) 的过程。考试极大概率会给出一个矩阵表，问当前状态是否安全，或某进程请求 $X$ 资源后是否安全 。

  • 四大必要条件及对应的 Prevention (预防) 策略 ：这是极高频的简答题考点 。

• 易错/混淆点 (Common Pitfalls) ：

  • Deadlock Avoidance (避免) vs. Deadlock Prevention (预防) ：

    • Avoidance 是动态的，系统在分配资源前（如使用银行家算法）计算是否会进入不安全状态 。
    • Prevention 是静态的，通过在系统设计时直接破坏死锁的四个必要条件之一来达成 。

  • Unsafe State (不安全状态) $\neq$ Deadlock (死锁) ：安全状态保证没有死锁，但不安全状态只是代表“有可能”发生死锁（There is a possibility of deadlock），并不意味着当前已经死锁 。

  • Deadlock (死锁) vs. Livelock (活锁) ：死锁的进程是处于 Blocked (阻塞) 状态，无法消耗CPU；活锁的进程（如使用轮询 Polling/Busy waiting）状态不断改变但没有实质进展，会持续消耗CPU 。

名词解释与核心公式

名词解释 (Glossary)：

• Safe State (安全状态): 系统中存在一种按照某种顺序为每个进程分配资源的方式，使得所有进程都能获得最大需求并顺利执行完毕 。

• Safe Sequence (安全序列): 在安全状态下，能够让所有进程依次顺利获取资源并终止的进程执行顺序 。

• Spooling (假脱机): 将独占设备（如打印机）改为共享设备的技术，由守护进程统一管理资源，从而破坏死锁的互斥条件 。

• Starvation (饥饿): 进程并未死锁也未阻塞，但由于资源分配算法（如最短任务优先）的不公，导致该进程被无限期推迟执行 。

核心公式 (Core Formulas - 银行家算法相关)：

• 资源守恒约束 (Resource Constraint): $\sum_{i=1}^{n}C_{ij} + A_{j} = E_{j}$ (其中 $C$ 是当前分配矩阵，$A$ 是可用资源向量，$E$ 是系统中存在的资源总向量) 。

• 需求计算 (Need Calculation): $Need_{ij} = Max_{ij} - Allocation_{ij}$ (某个进程对某类资源的剩余需求量 = 声明的最大需求量 - 已经分配给它的量) 。

• 算法复杂度 (Algorithm Complexity): $O(m n^2)$

  (其中 $m$ 是资源种类的数量，$n$ 是进程的数量。在极限情况下，寻找安全序列的最坏步数)。

*Chapter 3 Memory Management

• No Memory Abstraction

  • 核心特征:

    • 程序直接访问物理内存 (Direct access to physical memory)。
    • 同一时间只能运行一个程序 (难以实现多道程序设计)。

  • 早期多道程序解决方案 (以 IBM 360 为例):

    • 保护机制 (Protection): 使用 4-bit 的保护键 (Protection keys) 存放在 CPU 寄存器和程序状态字 (PSW) 中，访问时比对。
    • 重定位问题 (Relocation problem): 程序加载到不同物理地址时，内部的绝对地址跳转会导致崩溃。

• A Memory Abstraction: Address Space

  • 地址空间概念 (Address Space): 为每个进程提供一套独立、连续的逻辑地址集合，解决保护与重定位问题。

  • 基址与界限寄存器 (Base and Limit Registers):

    • Base Register: 存储进程在物理内存中的起始地址，每次内存访问都会自动加上该值 (动态重定位)。
    • Limit Register: 存储进程的长度，每次访问前进行越界检查 (提供保护)。

  • 交换技术 (Swapping):

    • 将整个进程在内存与磁盘之间换入换出，以支持总内存需求超过物理内存的情况。
    • 外部碎片与内存紧缩 (External Fragmentation & Compaction): 交换会产生内存空洞，需通过紧缩技术(极其耗时)合并空闲区。

  • 内存分配管理 (Memory Allocation):

    • 位图 (Bitmaps): 用 1 bit 表示一个分配单元（0代表空闲，1代表已分配）。单元越小位图越大，查找连续零串的速度慢。
    • 链表 (Linked Lists): 维护已分配区和空闲区(Hole)的链表，可按地址或大小排序。
    • 放置策略 (Placement Strategies):
      • First Fit: 遍历链表，找到第一个足够大的空闲区。速度快。
      • Next Fit: 类似于 First Fit，但每次从上次查找结束的位置继续寻找。性能略差于首次适配。
      • Best Fit: 遍历整个链表，找到满足要求且最小的空闲区。缺点是会产生极小且无法利用的碎片 。
      • Worst Fit: 分配最大的空闲区，以保留较大的剩余空间。缺点是破坏了支持大程序的连续大空闲区 。
      • Quick Fit: 为常被请求的几种特定大小维护单独的链表。分配极快，但合并相邻空闲区代价高 。

• Virtual Memory

  • 分页机制 (Paging):

    • 虚拟地址 (Virtual Address): 拆分为 虚拟页号 (Virtual Page Number) + 页内偏移量 (Offset)。

    • 页与页框: 逻辑上等长的块叫**页面 (Pages)，物理内存中对应的块叫页框 (Page Frames)**。

    • MMU (内存管理单元): 硬件，负责将虚拟地址映射为物理地址 。

  • 页表结构 (Page Table):

    • 页表项 (PTE - Page Table Entry) 关键位:

      • 存在/缺席位 (Present/absent bit): $1$ 表示该页已在物理内存中，$0$ 表示引发缺页中断 (Page Fault) 。

      • 保护位 (Protection bit): 控制读/写/执行权限 (Read/Write/Execute) 。

      • 修改位/脏位 (Modified/Dirty bit): 页面被写入时置为1，决定淘汰时是否需要写回磁盘 。

      • 访问位 (Referenced bit): 页面被读取或写入时置为1，供页面置换算法参考 。

  • 加速映射：TLB (快表/转换检测缓冲区):

    • 集成在 MMU 内部的高速缓存，存储少数最频繁访问的 PTE。

    • 命中与未命中: TLB 命中则直接物理寻址；未命中则查常规页表并更新 TLB；若页表中也不在，则触发缺页中断。

  • 应对大地址空间:

    • 多级页表 (Multilevel Page Tables): 避免将整个大页表保存在内存中。地址结构变为 [ PT1 (顶级页表) | PT2 (二级页表) | Offset ]。

    • 倒排页表 (Inverted Page Tables): 物理内存中的每个页框只对应一个页表项，极大节省空间 。需要通过散列函数 Hash(Vpage, pid) 来加速查找 。

• 页面置换算法 (Page Replacement Algorithms)

  • 最优算法 (Optimal): 淘汰未来最远才会使用的页面。理论最优，无法实现，仅作性能对比基准 。

  • 最近未使用 (NRU - Not Recently Used):

    • 基于定时清零的 R 位和 M 位 。
    • 分为4个优先级 (Class 0: R=0,M=0; Class 1: R=0,M=1 等)，从最低非空类中随机淘汰 。

  • 先进先出 (FIFO - First-In First-Out):

    • 维护页面加载时间的链表，淘汰最老的页 。
    • 致命弱点: 可能会引发 **Belady 异常 (Belady’s Anomaly)**——分配的物理页框越多，缺页率反而越高 。

  • 第二次机会算法 (Second-Chance):

    • 改进的 FIFO。检查最老页面的 R 位：若 R=0，直接淘汰；若 R=1，将其 R 位清零并移至链表尾部（给予第二次机会） 。

  • 时钟算法 (Clock):

    • Second-Chance 的环形链表实现，只需移动指针，避免了移动链表元素的开销 。

  • 最近最少使用 (LRU - Least Recently Used):

    • 淘汰最长时间未被访问的页面 。
    • 硬件实现代价高: 需要 64位指令计数器 或 $N \times N$ 的硬件矩阵 。

  • 软件模拟 LRU:

    • 最不经常使用 (NFU - Not Frequently Used): 每次时钟滴答将 R 位累加到软件计数器，淘汰计数值最小的页 。缺点：从不遗忘历史。
    • 老化算法 (Aging): 重点考点！ 每次滴答先将计数器右移一位，然后将当前 R 位加到最高位 (最左侧) 。近期访问权重极高 。

  • 工作集算法 (Working Set):

    • 利用空间局部性，维护进程过去 $k$ 次内存访问中实际使用的页面集合 。
    • 淘汰规则：当 R=0 且 (当前虚拟时间 - 页面上次访问时间) > 阈值 $\tau$ 时，将其淘汰 。

  • 工作集时钟算法 (WSClock):

    • 结合 Clock 的环形结构与 Working Set 的时间戳规则，是工业界公认高效的算法 。

• 设计与实现问题 (Design & Implementation Issues)

  • 分配策略 (Allocation Policies):

    • 局部 (Local): 仅在触发缺页的进程自己的页面中选择淘汰对象（分配给进程的页框数固定） 。

    • 全局 (Global): 在整个内存所有进程的页面中选择淘汰（页框数动态调整，通常效果更好） 。

  • 系统抖动与负载控制 (Thrashing & Load Control):

    • 当多个进程的工作集总和 > 物理内存时，系统陷入无休止的缺页中断（抖动）。

    • 解决: 挂起（换出到磁盘）部分进程，降低多道程序度 。

  • 页面大小的设计权衡 (Page Size):

    • 页面小：内部碎片少，但页表极大 。

    • 最优页面大小公式：$p = \sqrt{2se}$ （其中 $s$ 是进程平均大小，$e$ 是页表项字节数） 。

  • 指令与数据空间分离 (Separate I & D spaces): 将程序指令与数据映射到独立地址空间，扩展寻址能力 。

  • 共享页面 (Shared Pages): 多个进程的页表指向同一个物理页框，常用于共享只读代码段 (Code Sharing) 。

  • 缺页中断处理流程 (Page Fault Handling): 硬件陷入内核 $\rightarrow$ 保存寄存器 $\rightarrow$ OS查找所需虚拟页 $\rightarrow$ 选定页框 (必要时写回脏页) $\rightarrow$ 调度磁盘读入 $\rightarrow$ 更新页表 $\rightarrow$ 恢复指令执行 。

• 分段机制 (Segmentation)

  • 设计初衷: 内存应按逻辑单元（如主程序、子例程、符号表、栈）划分，每个单元称为一个段 (Segment) 。每个段独立从0开始寻址，长度可变。

  • 逻辑地址: 格式为 <段号 (Segment-number), 段内偏移 (Offset)> 。

  • 段表 (Segment Table):

    • 每个段表项包含该段的 基址 (Base) 和 界限/长度 (Limit) 。

  • 分页 vs. 分段 (Paging vs. Segmentation):

    • 分页: 提供一个巨大的、线性的一维地址空间；目的是为了扩大内存；对程序员透明 (硬件自动处理) 。

    • 分段: 提供多个独立的线性地址空间 (多维)；目的是方便程序和数据的模块化、共享与保护；对程序员可见 。

  • 段页式混合 (Segmentation with Paging):

    • 以 MULTICS 系统为例。

    • 地址翻译过程: 逻辑地址拆分为 [段号 | 段内页号 | 页内偏移] 。

    • 通过段号查段表 $\rightarrow$ 找到该段对应的专属页表基址 $\rightarrow$ 通过页号查页表 $\rightarrow$ 找到物理页框号 $\rightarrow$ 拼接偏移量得到最终物理地址 。

• 重点:

  • 地址转换与EAT计算 (Address Translation & EAT Calculation): 这是必考计算题。你需要熟练掌握TLB命中、TLB未命中但页表命中、以及缺页中断三种情况下的有效访问时间（EAT）。如例题16所示，计算公式需考虑各情况的概率分支。

  • 内存分配策略模拟 (Memory Placement Strategies): 如例题4所示，掌握 First Fit (从头找第一个满足的)、Best Fit (找刚好满足或略大的最小空闲块)、Worst Fit (找最大的空闲块)、Next Fit (从上次分配位置继续找) 的执行过程。注意：Best Fit 容易产生微小碎片，Worst Fit 容易破坏大空闲区 。

  • 多级页表位长划分 (Multilevel Page Table Bit Allocation): 如例题17所示。首先必须根据页大小计算 Offset 位数（例如 16 KB = 14 bits），然后用虚拟地址总长度减去 Offset，剩余部分再根据每个页表所需的大小（Bytes/Entry size）划分给各级页表 。

  • 页面置换算法全家桶 (Page Replacement Simulations): 必考模拟大题。极大概率要求你在给定的表格中计算 LRU、FIFO、NRU 和 Second Chance 的淘汰对象。需严格记录各个算法的判断指标（LRU看最后访问时间，FIFO看加载时间，NRU看(R,M)级数，Second Chance结合加载时间和R位）。

• 难点与易混淆点 (Difficult & Confusing Points):

  • 老化算法的移位规则 (Aging Algorithm Shift Rules): 非常容易算错！在每个时钟滴答，计数器必须先右移一位，然后再将当前的 R 位加到最左侧（最高位） 。如例题30 即考察此动态演变过程，切记移位顺序。

  • 空间局部性与缺页率 (Spatial Locality & Page Faults): 难点应用题（如例题38）。C/C++语言采用行主序（Row-major order）在内存中线性存储数组。若代码按列遍历（Fragment A），会破坏空间局部性，导致极其频繁的缺页中断；按行遍历（Fragment B）则能大幅减少缺页错误。

  • 工作集时钟算法 (WSClock Algorithm): 难点。需分清当指针扫到 R=0 的页面时，比较的是“当前时间与最后一次访问时间的差值（Age）”是否大于阈值 $\tau$。如例题32，若Age为991，当 $\tau=400$ 时由于超出容忍阈值被淘汰；但若 $\tau=1000$，说明它刚刚险过，仍留在工作集中 。

  • Belady异常 (Belady’s Anomaly): 容易混淆适用对象。必须记住，只有 FIFO 这类没考虑访问局部性的算法才会出现“分配的页框越多、缺页率反而越高”的异常现象 。LRU 等基于栈的算法绝不会发生此异常 。

  • 分页 vs. 分段 (Paging vs. Segmentation): 概念极易混淆。分页对程序员是透明的，主要目标是扩大线性的（1维）可用物理内存 ；而分段对程序员可见，主要目标是将程序划分为逻辑意义上的多个独立模块（多维空间），以方便代码共享和权限保护 。

名词解释与核心公式

核心名词解释:

• Address Space (地址空间): 一个进程可以用来寻址内存的虚拟地址集合。它为每个进程提供了独立的逻辑内存视图，以此解决了多道程序下的内存保护与重定位问题 。

• Virtual Memory (虚拟内存): 一种将用户逻辑内存与物理内存分离的机制。它允许程序总体的地址空间远远大于实际物理内存，系统仅将当前正在被引用（或即将在局部性中被引用）的页面加载到内存中 。

• TLB (Translation Look-aside Buffer / 快表): 位于 MMU (内存管理单元) 中的硬件级高速缓存，专门用于存放最常用的页表项，通过并行查找极大地加速了虚拟地址到物理地址的转换 。

• Page Fault (缺页中断): 当程序试图访问一个有效但目前不在物理内存页框中的虚拟页面时，硬件陷入（Trap）操作系统并触发异常，从而执行从磁盘调页的处理流程 。

• Thrashing (系统抖动/颠簸): 当内存中运行的进程过多（或工作集过大）时，导致系统将绝大部分时间浪费在页面的频繁换入换出上，而不是去执行实际的CPU指令 。

• Working Set (工作集): 一个进程在最近 $k$ 次内存引用中正在积极使用的页面集合集合 。

核心公式:

• Effective Access Time (有效地址转换时间):

• $$EAT = P_{TLB} \times T_{TLB} + P_{PT} \times T_{PT} + P_{Fault} \times T_{Fault}$$

  (注：$P$ 代表发生的概率/命中率，$T$ 代表对应的耗时周期/纳秒。)

• Page Table Overhead Optimization (页表开销最优化页面大小):

  $$p = \sqrt{2se}$$

  (注：$p$ 为最优页面大小，$s$ 为平均进程的总大小，$e$ 为每个页表项的大小。其目的是平衡内部碎片开销与页表占用空间开销 。)

• Offset Bits Calculation (页内偏移位数计算):

  $$Offset\ Bits = \log_2(\text{Page Size})$$

  (注：例如页面大小为 4 KB ($2^{12}$ Bytes)，则 Offset 为 12 bits。这是做多级页表设计题的基础。)

• Chapter 4 File Systems

  • Files (文件)

    • Naming (命名): 文件名与扩展名 (Extension) 。

    • Structure (结构): 字节序列 (Byte sequence)、记录序列 (Record sequence)、树 (Tree) 。

    • Types (类型): 普通文件 (Regular files)、目录 (Directories)、字符特殊文件 (Character special files)、块特殊文件 (Block special files) 。

    • Access (访问): 顺序访问 (Sequential access)、随机访问 (Random access) 。

    • Attributes (属性): 包括元数据 (Metadata) 比如权限、创建者、时间戳等 。

  • Directories (目录)

    • 结构演进: 单级目录 (Single-level)、双级目录 (Two-level)、层次化目录 (Hierarchical) 。
      

    • Path Names (路径名): 绝对路径 (Absolute path name)、相对路径 (Relative path name) 以及当前工作目录 (Working directory) 。

  • File System Implementation (文件系统实现)

    • Layout (布局): MBR、分区表 (Partition table)、引导块 (Boot block)、超级块 (Super block)、I节点区 (I-nodes) 。

    • 

    • Implementing Files (文件实现技术):

      • 连续分配 (Contiguous Allocation): 性能极佳但有外部碎片 。

      • 链表分配 (Linked List Allocation): 无碎片但随机访问慢 。
        

      • 结合FAT的链表分配 (Linked List using FAT): 将指针抽出放入内存以加速访问 。
        

      • 索引分配 (Indexed Allocation / i-Node): 仅在文件打开时加载至内存，有效支持直接访问且节省空间 。
        

    • Implementing Directory (目录实现): 目录项直接含属性 (Windows) 或 目录项仅指向I节点 (UNIX) 。
      

    • Shared Files (共享文件):

      • 硬链接 (Hard Link): 多个目录指向同一I节点，有引用计数 。
      • 软链接 (Symbolic Link): 保存原文件路径的快捷方式 。

    • Disk Space Management (磁盘空间管理):

      • Block size (块大小权衡): 大块空间利用率低，小块性能差 。

      • Free Blocks (空闲块追踪): 空闲块链表 (Linked list) vs 位图 (Bit-map) 。

    • Reliability (可靠性) : 备份策略 (物理/逻辑) 与 一致性检查 (fsck 检查块与目录引用计数) 。

    • Journaling FS (日志文件系统): 崩溃恢复前先记日志 。

    • Virtual File System (VFS): 上层应用抽象与底层物理实现的接口界限 。

  • Example File Systems (典型系统示例)

    • MS-DOS: 经典的8+3命名与FAT表限制 。

    • Windows 98: 兼容长文件名 (Long file names) 。

    • UNIX V7: i-node 结构及寻址机制 。

重点与难点标注

• 🔥 【必考重点】

  1. 文件实现方式的优缺点对比 ：必须熟练区分连续分配（适合唯读光盘、易有碎片）、链表分配、FAT表和I节点分配的各自应用场景和优劣 。

  2. I节点 (i-Node) 最大文件大小计算（必考大题，结合例题16和38） ：考察对直接地址块 (Direct blocks) 与 各级间接地址块 (Indirect blocks) 嵌套能力的计算。

  3. 空闲空间管理策略抉择（结合例题24） ：能够推导并计算出什么空间占用比例下使用 Free list 比 Bitmap 更节省空间。

  4. 路径解析的磁盘操作次数评估（结合例题41） ：考察对UNIX目录树查找过程的熟练度（目录块读入 -> I节点读入的交替过程）。

• ⚠️ 【易混淆与易错点】

  1. 硬链接 (Hard Link) 与 软链接 (Symbolic Link) ：硬链接靠递增和递减引用计数(Reference count)存活，本质上是相同的底层文件；而软链接新建了一个独立文件，且有额外的路径解析开销 。

  2. fsck 灾难恢复逻辑（结合例题26） ：如果丢失空闲块信息，UNIX 可以通过扫描已使用的 I-node 取反来恢复；但 FAT 系统天然没有独立的空闲链表（其空闲状态直接标记在 FAT 中特殊的位上），机制完全不同。

  3. Bitmap 空间计算单位转换 ：在计算 Bitmap 需要多少空间时，很容易把 bit (位) 和 Byte (字节)、Block (块) 搞混，计算时务必统一度量衡 。

名词解释与核心公式

核心名词解释

• i-Node (索引节点) ：为每个文件分配的数据结构，集中存储了文件的属性以及指向文件各个数据块的磁盘地址。只有当文件被打开时，它才会被载入内存，大大节省了内存空间 。

• FAT (File Allocation Table, 文件分配表) ：将所有数据块的链表指针抽出，集中在一张表格中并放在内存里。解决了普通链表分配无法高效随机访问的缺陷 。

• VFS (Virtual File System, 虚拟文件系统) ：操作系统向上提供统一的 POSIX 接口，向下整合多种异构底层物理文件系统（如 ext3, FAT）的中间抽象层 。

• Bitmap (位图) ：使用一串二进制序列记录磁盘分配状态，1表示空闲，0表示已用（或相反）。通常在磁盘接近满载时，比空闲链表占用更少空间 。

• Journaling File System (日志文件系统) ：在实际修改文件系统元数据之前，先将意图写入日志文件。如果在执行期间系统崩溃，重启后可读取日志完成断点恢复 。

核心公式与例题解析

1. I节点最大文件大小计算公式

• 公式 ：$Max Size = (\text{直接块数} + \text{一级间接块包含的指针数} + \text{二级间接块包含的指针数}^2 + …) \times \text{磁盘块大小}$

• 例题38（常见考法） ：块大小 = 4 KB，地址指针 = 4 Bytes。包含10个直接指针和1个一级间接指针。

  • 间接块可存放指针数：$4 KB / 4 B = 1024$ 个。

  • 总寻址块数：$10 + 1024 = 1034$ 块。

  • 最大文件大小：$1034 \times 4096 \text{ Bytes} = 4,235,264 \text{ Bytes}$。

• 例题16 ：块大小 = 1 KB (1024 B)，地址指针 = 8 Bytes，10个直接指针和1个间接块。

  • 间接块可存指针数：$1024 B / 8 B = 128$ 个。

  • 最大块数：$10 + 128 = 138$ 块。即 $138 \text{ KB}$。

2. 空闲链表 vs. 位图的空间阈值公式

• 公式 ：设磁盘总块数为 $B$，其中空闲块数为 $F$，每个块指针需要占用 $D$ bits。

  • Bitmap需要：$B$ bits。

  • Free List需要：$F \times D$ bits。

• 例题24（最优策略条件） ：当且仅当 $F \times D < B$ 时，使用 Free List 更节省空间。变换公式为空闲率：$F / B < 1 / D$。若 $D=16$ 位，则当磁盘空闲空间少于 $1/16$ (即 $6.25%$) 时，空闲链表比位图更优。

3. 目录树路径查找的磁盘I/O次数（例题41）

• 计算规则 ：按层级依次读取 目标目录的数据块 -> 子目录的I-Node -> 子目录的数据块 -> ... -> 最终文件的I-Node。

• 例题41应用 ：寻找 /usr/ast/courses/os/handout.t。已知根目录 ( / ) 的 I-node 已经在内存中。

  1. 读 / 目录数据块

  2. 读 usr 对应的 I-node

  3. 读 usr 目录数据块

  4. 读 ast 对应的 I-node

  5. 读 ast 目录数据块

  6. 读 courses 对应的 I-node

  7. 读 courses 目录数据块

  8. 读 os 对应的 I-node

  9. 读 os 目录数据块

  10. 读最终文件 handout.t 对应的 I-node

      _总计_：$10$ 次磁盘读取操作。

• Chapter 5 Input/Output

  • Principles of I/O Hardware (I/O硬件原理)

    • I/O Devices (I/O设备分类):

      • Block Devices (块设备): 可寻址、以固定大小（如512B）读写（e.g. Disks磁盘）。

      • Character Devices (字符设备): 不可寻址、字符流收发（e.g. Keyboard, Network interfaces）。

    • Device Controllers (设备控制器):

      • 充当CPU与机械/电子设备之间的接口，利用 Registers (寄存器) 和 Data buffers (数据缓冲区) 通信。

    • CPU与控制器通信方式:

      • Separate I/O and memory space (独立I/O与内存空间): 需专属指令(IN/OUT)，独立地址空间。

      • Memory-mapped I/O (内存映射I/O): 控制寄存器映射入常规内存空间，无需特殊指令，但存在 Caching (缓存) 挑战。

      • Hybrid (混合模式): 数据缓冲区映射到内存，控制寄存器使用独立端口（如Pentium架构）。

  • Principles of I/O Software (I/O软件原理)

    • Goals of I/O software (I/O软件目标):

      • Device independence (设备独立性)

      • Uniform naming (统一命名)

      • Error handling (错误处理)

      • Buffering (缓冲技术)

    • 三种数据传输方式演进:

      • Programmed I/O (程序控制I/O): CPU全程参与 Polling (轮询等待)，无并发，浪费CPU资源。

      • Interrupt driven I/O (中断驱动I/O): CPU启动传输后阻塞，硬件就绪发中断；但若以字符为单位，中断过于频繁。

      • I/O using DMA (基于DMA的I/O): Direct Memory Access控制器接管数据传输，直接在内存与外设间搬运，仅在开始和结束时打断CPU（效率最高）。

  • I/O Software Layers (I/O软件层次结构) (由下至上)

    • Interrupt handlers (中断处理程序): 隐藏中断底层细节，唤醒被阻塞的驱动程序。
    • Device drivers (设备驱动程序): 封装底层硬件操作，将抽象请求转换为具体的硬件指令集（不同设备驱动不同）。
    • Device-independent OS software (设备无关/独立OS软件): 核心功能层，提供统一接口、Buffering (缓冲)、Error reporting (错误报告)、Uniform naming (统一命名，管理主次设备号 Major/Minor number)。
    • User-level I/O software (用户层软件): 发起系统调用，包含I/O库（如C标准库）和 Spooling (假脱机系统)。
      
      

  • Disks (磁盘)

    • Physical Geometry (物理结构): Cylinder (柱面), Track (磁道), Sector (扇区)。

    • Disk formatting (磁盘格式化):

      • Sector format: Preamble (前导码) - Data - ECC (纠错码)。

      • Cylinder skew (柱面斜进): 错开相邻柱面的起始扇区，弥补磁头切换柱面的延迟。

      • Interleaving (扇区交叉): 逻辑相邻扇区物理不相邻，弥补控制器将数据拷贝到内存的时间。

    • Disk arm scheduling algorithm (磁盘臂调度算法):

      • FCFS (First Come First Served / 先来先服务): 按请求顺序服务，寻道代价极大。

      • SSF (Shortest Seek First / 最短寻道优先): 优先服务距离当前磁头最近的请求，可能导致远端请求饥饿 (Starvation)。

      • Elevator Algorithm / SCAN (电梯算法): 磁头单向移动，到底后反转，兼顾公平与效率。

  • Virtualization & I/O (基于例题扩展的虚拟化I/O挑战)

    • Privilege Rings (特权环机制): Ring 0 (Hypervisor/Kernel), Ring 1 (Guest OS), Ring 3 (User mode)。

    • Instruction Interception (指令拦截): Binary translation (二进制翻译) vs. Hardware traps (硬件陷入机制)。

    • Live Migration Challenges (热迁移挑战): 物理I/O设备内部 Registers (寄存器) 含有关键状态，无法随虚拟机移动；网络I/O迁移易导致丢包 (Packet loss) 或网络无响应。

重点与难点标注

• 必考重点 (Must-Test Points):

  1. 三种I/O传输方式的对比: 一定要搞清CPU在 Programmed I/O、Interrupt-driven、DMA 中的参与度。考点：DMA只在整个Block传输开始和结束时才打乱CPU，而中断驱动是每个字符都会引发中断。

  2. I/O软件层次与职责划分: 考试极爱出选择/填空题让你判断某项功能属于哪一层。切记：Spooling 属于用户层；缓冲(Buffering)和主次设备号解析属于设备独立软件层；硬件寄存器的设置属于设备驱动层。

  3. 磁盘调度算法计算题: 给出一个磁道请求序列及当前磁头位置，要求计算总寻道跨度（总柱面数）。务必熟练推演 FCFS、SSF 和 Elevator 算法的移动轨迹。

  4. 虚拟化Privilege Rings分布（例题重点）: 知道谁运行在Ring 0 (Hypervisor/VMM)，谁运行在Ring 1或3。Guest OS执行特权指令时，通过Trap(陷入)交由Hypervisor处理。

• 易错混淆点 (Easily Confused Points):

  1. Cylinder Skew (柱面斜进) vs. Interleaving (扇区交叉): 这俩非常容易混。区别：Cylinder Skew是解决跨_不同柱面(磁道)_移动磁头的延迟；Interleaving是解决在_同一磁道_内连续读多个扇区时，因控制器内部缓冲区往内存复制数据耗时导致错过下一个扇区的问题。

  2. Major / Minor Device Number (主/次设备号): 主设备号找的是哪一类驱动程序（如某品牌磁盘驱动），次设备号找的是哪个具体的硬件物理单元（如连接在驱动上的第2个磁盘）。

  3. VM Live Migration的痛点（例题难点）: 网络数据包丢失和设备内部状态寄存器无法直接打包迁移是物理I/O在虚拟化中最大的障碍。

名词解释与核心公式

• Memory-mapped I/O (内存映射I/O): 将外设的控制寄存器地址映射到普通内存的地址空间中，CPU可以直接用普通的内存读写指令（如MOV）去操作外设，无需特殊的I/O指令。

• DMA (Direct Memory Access / 直接内存访问): 一种允许外设绕过CPU直接与系统主存进行数据交换的硬件机制，可极大减轻CPU的I/O传输负担。

• Device Independence (设备独立性): 应用程序可以无需知道特定硬件细节而统一使用各种I/O设备（如统一使用open, read, write处理U盘和硬盘）。

• Double Buffering (双缓冲): 操作系统在内核空间开辟两个缓冲区交替使用，当进程从缓冲A读取数据时，网卡/外设可以将新数据写入缓冲B，避免数据溢出或CPU空等。

• Hypervisor / VMM (虚拟机监视器 - 见例题): 运行在最高特权级（通常为Ring 0）的系统软件，用于管理、隔离并向Guest OS提供虚拟硬件平台，它会接管Guest OS的特权指令陷入（Traps）。

• Binary Translation (二进制翻译 - 见例题): 在早期缺乏硬件虚拟化支持时，Hypervisor通过动态重写Guest OS内核代码，将其中的敏感指令替换为安全的调用，防止其在用户态执行失败。

• 核心计算公式 (Disk Access Time):
  $$磁盘存取时间 = Seek Time (寻道时间) + Rotational Latency (旋转延迟) + Transfer Time (数据传输时间)$$

  (注：寻道时间通常占据绝大部分比例，因此磁盘调度的核心任务是优化寻道路径。)