Operating System

操作系统（OS）是计算机系统中最核心的系统软件，它管理硬件资源并为上层应用提供统一的抽象接口。OS 的核心职责包括：进程与线程管理（CPU 时间的分配与调度）、内存管理（虚拟地址空间与物理内存的映射）、文件系统（数据的持久化存储与组织）、I/O 管理（设备驱动与缓冲策略）以及同步与安全（并发控制与权限隔离）。

理解操作系统是理解计算机体系结构、并行计算、分布式系统乃至深度学习训练框架（如 GPU 调度、显存管理）的基础。本笔记覆盖 OS 的核心知识点，适合课程复习与面试准备。

进程管理（Process Management）

进程 vs 线程

比较维度	进程（Process）	线程（Thread）
定义	资源分配的基本单位	CPU 调度的基本单位
地址空间	拥有独立的地址空间	共享所属进程的地址空间
资源开销	创建/销毁开销大	创建/销毁开销小
通信方式	需要 IPC 机制（管道、共享内存等）	可直接读写共享变量
切换开销	上下文切换开销大（需切换页表等）	上下文切换开销小
安全性	一个进程崩溃不影响其他进程	一个线程崩溃可能导致整个进程崩溃
并发性	多进程并发	多线程并发，同一进程内线程共享堆区

用户级线程 vs 内核级线程

用户级线程（User-Level Thread）：由用户空间的线程库管理，内核不感知。切换快但无法利用多核。
内核级线程（Kernel-Level Thread）：由内核管理和调度，可以利用多核并行，但切换开销较大。
映射模型：多对一（Many-to-One）、一对一（One-to-One）、多对多（Many-to-Many）。

进程状态转换

进程在其生命周期中会经历以下状态：

                    +---------+
                    |   New   |
                    +----+----+
                         | admitted
                         v
    +----------+    +---------+    +----------+
    | Waiting  |<---| Ready   |--->| Running  |
    |          |    |         |<---|          |
    +----+-----+    +---------+    +-----+----+
         |          scheduler      ^     |
         |          dispatch       |     |
         +----- I/O complete ------+     |
                                         | exit
                                         v
                                   +-----------+
                                   | Terminated|
                                   +-----------+

New → Ready：进程被创建，分配好资源后进入就绪队列
Ready → Running：调度器选中该进程，分配 CPU
Running → Waiting：进程发起 I/O 请求或等待事件
Running → Ready：时间片用完（被抢占）或更高优先级进程到达
Waiting → Ready：I/O 完成或等待的事件发生
Running → Terminated：进程执行完毕或被强制终止

进程控制块（PCB, Process Control Block）

PCB 是操作系统用来描述和管理进程的核心数据结构，每个进程都有唯一的 PCB。

字段	说明
PID（进程 ID）	进程的唯一标识符
进程状态	New / Ready / Running / Waiting / Terminated
程序计数器（PC）	下一条要执行的指令地址
CPU 寄存器	所有寄存器的当前值
CPU 调度信息	优先级、调度队列指针
内存管理信息	页表基址、段表、地址空间边界
I/O 状态信息	打开的文件列表、I/O 设备分配
记账信息	CPU 使用时间、时间限制等

上下文切换（Context Switch）

上下文切换是指 CPU 从一个进程切换到另一个进程时，保存当前进程的状态并恢复下一个进程的状态的过程。

切换步骤：

保存当前进程的 PCB（寄存器、PC、栈指针等）
更新当前进程的状态（Running → Ready / Waiting）
将当前进程的 PCB 放入相应队列
选择下一个要执行的进程（调度决策）
恢复新进程的 PCB
更新新进程的状态（Ready → Running）
跳转到新进程的 PC 继续执行

上下文切换的开销

上下文切换是纯粹的系统开销（overhead），在切换期间系统不做任何"有用"的工作。开销来源包括：

保存/恢复寄存器
刷新 TLB（页表缓存）
刷新 CPU Cache（缓存污染）
流水线排空

典型的上下文切换耗时在微秒级别（通常 1-10 us）。

进程间通信（IPC, Inter-Process Communication）

IPC 机制	说明	特点
管道（Pipe）	半双工，数据单向流动；分为匿名管道和命名管道（FIFO）	简单易用，但仅限于有亲缘关系的进程（匿名管道）
消息队列（Message Queue）	内核中维护的消息链表，进程可以发送/接收消息	支持消息优先级，不需要同步机制
共享内存（Shared Memory）	多个进程映射同一块物理内存到各自地址空间	速度最快，但需要配合同步机制（如信号量）
信号量（Semaphore）	一个计数器，用于控制多个进程对共享资源的访问	主要用于同步，而非数据传输
信号（Signal）	异步通知机制，如 `SIGKILL`、`SIGTERM`、`SIGINT`	开销小，但传递的信息量有限
套接字（Socket）	支持不同主机间的通信	功能最强大，可用于网络通信

CPU 调度（CPU Scheduling）

调度准则

准则	定义	优化方向
CPU 利用率（CPU Utilization）	CPU 处于忙碌状态的时间比例	最大化
吞吐量（Throughput）	单位时间内完成的进程数	最大化
周转时间（Turnaround Time）	从提交到完成的总时间：$$T_{turnaround} = T_{completion} - T_{arrival}$$	最小化
等待时间（Waiting Time）	在就绪队列中等待的总时间	最小化
响应时间（Response Time）	从提交请求到产生第一次响应的时间：$$T_{response} = T_{first\_run} - T_{arrival}$$	最小化

抢占式 vs 非抢占式

非抢占式（Non-preemptive）：进程一旦获得 CPU 就会一直运行到完成或主动让出（如 I/O）。
抢占式（Preemptive）：调度器可以在任意时刻中断当前进程，把 CPU 分配给其他进程。现代 OS 大多采用抢占式调度。

主要调度算法

算法	抢占式？	优点	缺点	适用场景
FCFS（先来先服务）	否	实现简单	护航效应（Convoy Effect），短进程等待长进程	批处理系统
SJF（短作业优先）	否	平均等待时间最优（非抢占情况下）	可能导致长作业饥饿；需要预知执行时间	已知运行时间的批处理
SRTF（最短剩余时间优先）	是	平均等待时间最优（抢占情况下）	同 SJF，饥饿问题更严重	同 SJF
Round Robin（时间片轮转）	是	公平，响应时间好	时间片过大退化为 FCFS；过小则上下文切换开销大	分时系统
Priority（优先级调度）	可选	灵活，支持区分任务重要性	低优先级进程饥饿（可用老化 Aging 解决）	通用系统
MLFQ（多级反馈队列）	是	兼顾交互式和批处理进程，自适应	实现复杂，参数调优困难	通用操作系统（Linux、Windows）

调度算法示例

FCFS 示例

进程到达顺序：P1(burst=24), P2(burst=3), P3(burst=3)，均在 t=0 到达。

甘特图：
| P1              | P2 | P3 |
0                24   27   30

平均等待时间 = (0 + 24 + 27) / 3 = 17

SJF 示例

进程到达顺序：P1(burst=6), P2(burst=8), P3(burst=7), P4(burst=3)，均在 t=0 到达。

甘特图：
| P4 | P1    | P3     | P2      |
0    3       9       16       24

平均等待时间 = (3 + 16 + 9 + 0) / 4 = 7

SRTF 示例

进程	到达时间	Burst
P1	0	8
P2	1	4
P3	2	2

甘特图：
| P1| P2| P3 | P2  | P1          |
0   1   2    4     6             14

P1 等待 = (0) + (6-1) = 5，P2 等待 = (1-1) + (4-2) = 2，P3 等待 = (2-2) = 0
平均等待时间 = (5 + 2 + 0) / 3 = 2.33

Round Robin 示例（时间片 q=4）

进程到达顺序：P1(burst=24), P2(burst=3), P3(burst=3)，均在 t=0 到达。

甘特图：
| P1  | P2 | P3 | P1  | P1  | P1  | P1  | P1  |
0     4    7   10    14    18    22    26    30

平均等待时间 = ((30-24) + 4 + 7) / 3 = 5.67

Round Robin 时间片的选择

时间片 $q$ 太大 → 退化为 FCFS
时间片 $q$ 太小 → 上下文切换开销增大
经验法则：$q$ 应使 80% 的 CPU burst 能在一个时间片内完成

Priority 调度示例

进程	Burst	优先级（数字小 = 高优先级）
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

甘特图：
| P2| P5    | P1          | P3 | P4|
0   1       6            16   18  19

平均等待时间 = (6 + 0 + 16 + 18 + 1) / 5 = 8.2

MLFQ（多级反馈队列）

MLFQ 的核心规则：

如果 Priority(A) > Priority(B)，运行 A
如果 Priority(A) = Priority(B)，按 RR 运行
新进程进入最高优先级队列
如果进程用完了当前层的时间配额，降到下一层队列
经过一段时间 $S$（boost interval），将所有进程提升到最高优先级队列（防止饥饿）

Queue 0 (最高优先级, q=8ms):   | P_new | ...
Queue 1 (中优先级, q=16ms):    | P_cpu_bound | ...
Queue 2 (最低优先级, FCFS):    | P_long_running | ...

同步与互斥（Synchronization）

临界区问题（Critical Section Problem）

临界区：进程中访问共享资源的代码段。同一时刻只允许一个进程进入临界区。

解决临界区问题需要满足三个条件：

互斥（Mutual Exclusion）：同一时刻最多一个进程在临界区内
前进（Progress）：如果没有进程在临界区内，那么想进入临界区的进程不应被无限推迟
有限等待（Bounded Waiting）：一个进程从请求进入临界区到被允许进入，其等待次数有上限

Peterson's Solution

Peterson 算法是一个经典的两进程互斥的软件解决方案。

// 进程 i 的代码
int flag[2];  // flag[i] = true 表示进程 i 想进入临界区
int turn;     // 表示轮到谁进入临界区

// 进程 i 进入临界区
flag[i] = true;
turn = j;  // 礼让对方
while (flag[j] && turn == j)
    ;  // 忙等待（busy waiting）

// --- 临界区 ---

flag[i] = false;  // 退出临界区

Peterson's Solution 的局限性

Peterson 算法在现代多核处理器上不保证正确性，因为 CPU 和编译器可能对指令进行重排序（reordering）。实际应用中需要使用内存屏障（Memory Barrier）或硬件原子指令。

互斥锁（Mutex）与信号量（Semaphore）

互斥锁（Mutex Lock）：

acquire(lock);   // 如果锁被占用则阻塞
// --- 临界区 ---
release(lock);   // 释放锁

信号量（Semaphore）：一个整数变量，通过 wait()（P 操作）和 signal()（V 操作）两个原子操作访问。

wait(S) {       // P 操作
    while (S <= 0)
        ;       // 忙等待（或阻塞）
    S--;
}

signal(S) {     // V 操作
    S++;
}

类型	说明
二值信号量（Binary Semaphore）	值为 0 或 1，功能等同于互斥锁
计数信号量（Counting Semaphore）	值可以为任意非负整数，用于控制对有限资源的并发访问

经典同步问题

生产者-消费者问题（Producer-Consumer Problem）

又称有界缓冲区问题（Bounded Buffer Problem）。

semaphore mutex = 1;    // 互斥访问缓冲区
semaphore empty = N;    // 空槽位数量
semaphore full  = 0;    // 已占槽位数量

// 生产者
void producer() {
    while (true) {
        item = produce_item();
        wait(empty);        // 等待空位
        wait(mutex);        // 进入临界区
        insert(item);
        signal(mutex);      // 离开临界区
        signal(full);       // 通知消费者
    }
}

// 消费者
void consumer() {
    while (true) {
        wait(full);         // 等待数据
        wait(mutex);        // 进入临界区
        item = remove();
        signal(mutex);      // 离开临界区
        signal(empty);      // 通知生产者
        consume(item);
    }
}

注意 wait 的顺序

wait(empty) 和 wait(mutex) 的顺序不能颠倒，否则可能导致死锁：生产者持有 mutex 但缓冲区满而等待 empty，消费者等待 mutex 无法消费。

读者-写者问题（Readers-Writers Problem）

多个读者可以同时读
写者必须独占访问

semaphore rw_mutex = 1;   // 读写互斥
semaphore mutex = 1;      // 保护 read_count
int read_count = 0;

// 写者
void writer() {
    wait(rw_mutex);
    // --- 写操作 ---
    signal(rw_mutex);
}

// 读者
void reader() {
    wait(mutex);
    read_count++;
    if (read_count == 1)
        wait(rw_mutex);   // 第一个读者锁定写者
    signal(mutex);

    // --- 读操作 ---

    wait(mutex);
    read_count--;
    if (read_count == 0)
        signal(rw_mutex); // 最后一个读者释放写者
    signal(mutex);
}

读者-写者问题的变体

第一类（读者优先）：上述方案，可能导致写者饥饿。
第二类（写者优先）：有写者等待时，新读者不能进入。
实际系统中常使用 读写锁（Read-Write Lock, rwlock） 来解决。

哲学家就餐问题（Dining Philosophers Problem）

5 个哲学家围坐圆桌，每两个人之间有一根筷子。哲学家交替进行思考和进餐，进餐需要同时拿起左右两根筷子。

朴素解法（可能死锁）：

semaphore chopstick[5] = {1, 1, 1, 1, 1};

void philosopher(int i) {
    while (true) {
        think();
        wait(chopstick[i]);         // 拿左筷子
        wait(chopstick[(i+1)%5]);   // 拿右筷子
        eat();
        signal(chopstick[(i+1)%5]);
        signal(chopstick[i]);
    }
}

避免死锁的策略：

最多允许 4 个哲学家同时拿筷子
奇数编号先拿左、偶数编号先拿右（破坏循环等待）
使用 trylock，拿不到就放下已有的（破坏持有并等待）

死锁（Deadlock）

死锁的四个必要条件

同时满足以下四个条件才会产生死锁：

互斥（Mutual Exclusion）：资源不能同时被多个进程共享
持有并等待（Hold and Wait）：进程持有至少一个资源，同时等待获取其他资源
非抢占（No Preemption）：资源不能被强制剥夺，只能由持有者主动释放
循环等待（Circular Wait）：存在一组进程 $\{P_0, P_1, \dots, P_n\}$，其中 $P_i$ 等待 $P_{(i+1) \mod (n+1)}$ 持有的资源

死锁的处理策略

策略	方法	说明
预防（Prevention）	破坏四个必要条件之一	如：要求进程一次申请所有资源（破坏持有并等待）；对资源编号，按序申请（破坏循环等待）
避免（Avoidance）	动态检查资源分配是否安全	银行家算法；要求事先知道资源最大需求量
检测（Detection）	允许死锁发生，定期检测	资源分配图（Resource Allocation Graph）；等待图（Wait-for Graph）
恢复（Recovery）	检测到死锁后采取措施	终止进程（逐个或全部）；资源抢占（回滚进程状态）

实际系统的做法

大多数操作系统（如 Linux、Windows）采用鸵鸟策略：忽略死锁问题，将其交给应用程序开发者处理。因为死锁预防/避免的开销可能大于偶发死锁带来的损失。

银行家算法（Banker's Algorithm）

银行家算法用于死锁避免，核心思想是：在分配资源前，检查分配后系统是否仍处于安全状态（Safe State）。

数据结构（$n$ 个进程，$m$ 种资源）：

$Available[m]$：每种资源当前可用数量
$Max[n][m]$：每个进程对每种资源的最大需求
$Allocation[n][m]$：每个进程当前已分配的资源
$Need[n][m]$：每个进程还需要的资源，$Need[i][j] = Max[i][j] - Allocation[i][j]$

安全性检查算法：

令 $Work = Available$，$Finish[i] = false$（$\forall i$）
找到一个进程 $P_i$，使得 $Finish[i] = false$ 且 $Need[i] \leq Work$
如果找到，令 $Work = Work + Allocation[i]$，$Finish[i] = true$，回到第 2 步
如果所有进程的 $Finish[i] = true$，则系统处于安全状态

安全状态 vs 不安全状态

安全状态：存在一个安全序列（Safe Sequence），使得所有进程都能顺利完成。安全状态一定不会死锁。
不安全状态：不存在安全序列。不安全状态不一定死锁，但有死锁的风险。

内存管理（Memory Management）

连续分配 vs 非连续分配

分配方式	说明	优点	缺点
连续分配	每个进程占用一段连续的内存空间	实现简单，访问效率高	外部碎片（External Fragmentation）
非连续分配	进程可以分散在内存中的不同位置	减少碎片问题	需要额外的地址映射机制

连续分配策略：

首次适应（First Fit）：从头开始找到第一个足够大的空闲区域
最佳适应（Best Fit）：找到最小的足够大的空闲区域（产生最小剩余碎片）
最差适应（Worst Fit）：找到最大的空闲区域

碎片类型

外部碎片（External Fragmentation）：空闲内存总量足够，但不连续，无法分配给进程。可通过紧凑（Compaction）解决。
内部碎片（Internal Fragmentation）：分配给进程的内存大于实际需要，多余部分浪费。分页中常见。

分页（Paging）

分页是一种非连续内存分配方案：

将物理内存划分为固定大小的块，称为帧（Frame）
将逻辑地址空间划分为同样大小的块，称为页（Page）
通过页表（Page Table）将逻辑页号映射到物理帧号

地址翻译：

逻辑地址由两部分组成：页号（Page Number, p） 和 页内偏移（Page Offset, d）。

\[\text{逻辑地址} = (p, d) \xrightarrow{\text{页表}} (f, d) = \text{物理地址}\]

其中 $f = PageTable[p]$ 是对应的物理帧号。

若页面大小为 $2^n$ 字节，逻辑地址空间为 $2^m$ 字节，则：

页内偏移 = 低 $n$ 位
页号 = 高 $(m - n)$ 位
页表项数 = $2^{m-n}$

TLB（Translation Lookaside Buffer）

TLB 是页表的高速缓存（通常在 CPU 内部的 MMU 中），用于加速地址翻译。

\[\text{有效访问时间（EAT）} = \alpha \times (t_{TLB} + t_{mem}) + (1 - \alpha) \times (t_{TLB} + 2 \times t_{mem})\]

其中 $\alpha$ 为 TLB 命中率，$t_{TLB}$ 为 TLB 查找时间，$t_{mem}$ 为一次内存访问时间。

TLB 典型参数

TLB 条目数：64 ~ 1024
命中率：通常 > 99%
上下文切换时需要刷新 TLB（或使用 ASID 标识进程）

多级页表（Multi-Level Page Table）

当逻辑地址空间很大时，单级页表会占用大量内存。多级页表将页表分层，只为实际使用的地址空间分配页表内存。

以二级页表为例：

逻辑地址：| 一级页号 p1 | 二级页号 p2 | 页内偏移 d |
           ↓
      一级页表[p1] → 二级页表基址
                        ↓
                   二级页表[p2] → 物理帧号 f
                                    ↓
                              物理地址 = (f, d)

优点：节省内存（不需要的页表项不分配）
缺点：增加一次内存访问（每级页表需要访问一次内存）

分段（Segmentation）

分段将逻辑地址空间按程序的逻辑结构划分为若干段（Segment），如代码段、数据段、栈段等。

逻辑地址：(段号 s, 段内偏移 d)

段表项：(段基址 base, 段长度 limit)
地址翻译：若 $d < limit$，物理地址 = $base + d$；否则产生段错误

对比	分页	分段
划分依据	物理划分，固定大小	逻辑划分，可变大小
碎片类型	内部碎片	外部碎片
用户可见？	对用户透明	用户可感知（按逻辑模块划分）
共享与保护	以页为单位，粒度较粗	以段为单位，便于共享和保护

虚拟内存（Virtual Memory）

虚拟内存允许进程使用比物理内存更大的地址空间。核心思想：只将当前需要的页面加载到物理内存中，其余保留在磁盘上。

按需分页（Demand Paging）

只有当访问某一页时，才将其从磁盘调入内存。

缺页中断（Page Fault）：访问的页不在内存中，触发中断
处理流程：陷入内核 → 查找磁盘位置 → 读入空闲帧 → 更新页表 → 重新执行指令

缺页率与有效访问时间：

\[EAT = (1 - p) \times t_{mem} + p \times t_{page\_fault}\]

其中 $p$ 为缺页率，$t_{page\_fault}$ 通常在毫秒级（包括磁盘 I/O），远大于 $t_{mem}$（纳秒级）。

缺页的代价

一次缺页中断的处理时间约为 10ms（磁盘访问），而一次内存访问约为 100ns。因此缺页中断比正常内存访问慢约 $10^5$ 倍。即使 0.1% 的缺页率也会导致显著的性能下降。

页面置换算法

当物理内存已满，需要调入新页面时，必须选择一个页面换出（置换）。

算法	策略	优点	缺点
OPT（最优）	置换未来最长时间不会被访问的页面	缺页率最低（理论最优）	无法实现（需预知未来访问序列）
FIFO（先进先出）	置换最早进入内存的页面	实现简单	性能较差；存在 Belady 异常
LRU（最近最少使用）	置换最近最长时间未被访问的页面	性能接近 OPT	实现开销大（需记录访问时间或维护栈）
Clock（时钟算法）	基于使用位（reference bit）的近似 LRU	实现简单，性能较好	只是 LRU 的近似

FIFO 示例

页面引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1（3 个帧）

引用: 7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1
帧1:  7  7  7  2  2  2  2  4  4  4  0  0  0  0  0  0  0
帧2:     0  0  0  0  3  3  3  2  2  2  2  2  1  1  1  1
帧3:        1  1  1  1  0  0  0  3  3  3  3  3  2  2  2  (修正)
缺页: *  *  *  *     *  *  *  *  *  *        *  *     *

缺页次数：15

Belady 异常

FIFO 算法可能出现分配更多帧反而缺页率更高的现象，称为 Belady 异常（Belady's Anomaly）。LRU 和 OPT 不存在此问题（它们属于栈算法，Stack Algorithm）。

LRU 示例

页面引用串：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1（3 个帧）

引用: 7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1
帧:  {7}{7,0}{7,0,1}{2,0,1}{2,0,1}{2,0,3}{2,0,3}→置换最久未用
     → 最终缺页次数：12

LRU 的缺页次数（12）少于 FIFO（15）。

Clock 算法

Clock 算法使用一个环形链表和一个指针（clock hand）：

每个帧有一个 reference bit（引用位），页面被访问时置 1
需要置换时，指针扫描：
- 若引用位 = 1，将其置 0（给第二次机会），指针前移
- 若引用位 = 0，选择该页面进行置换

抖动（Thrashing）

当系统中进程数量过多，每个进程分配的帧数不足时，会频繁发生缺页中断，进程大部分时间都在进行页面置换（I/O），CPU 利用率反而下降。这种现象称为抖动（Thrashing）。

原因： 进程的工作集（Working Set）大于分配的物理帧数。

解决方案：

工作集模型（Working Set Model）：跟踪每个进程在时间窗口 $\Delta$ 内访问的页面集合（工作集），确保为每个进程分配足够的帧来容纳其工作集
缺页频率策略（Page Fault Frequency, PFF）：监控每个进程的缺页率。缺页率过高则分配更多帧；缺页率过低则回收部分帧
降低多道程序度（减少并发进程数）

文件系统（File System）

文件系统层次结构

从上到下的层次：

┌─────────────────────────────────┐
│       应用程序（Application）     │
├─────────────────────────────────┤
│      逻辑文件系统（Logical FS）    │  ← 管理元数据、目录结构
├─────────────────────────────────┤
│   文件组织模块（File Organization）│  ← 逻辑块号 → 物理块号
├─────────────────────────────────┤
│     基本文件系统（Basic FS）       │  ← 向设备驱动发出 I/O 请求
├─────────────────────────────────┤
│      I/O 控制（I/O Control）      │  ← 设备驱动程序、中断处理
├─────────────────────────────────┤
│         设备（Devices）           │  ← 物理硬盘/SSD
└─────────────────────────────────┘

目录结构

结构	说明	特点
单级目录	所有文件在同一目录下	简单但文件名不能重复
二级目录	每个用户一个目录	解决命名冲突，但不灵活
树形目录	层次化目录结构	最常用，支持路径名（绝对/相对）
无环图目录（DAG）	允许共享文件/子目录（硬链接、符号链接）	支持文件共享，需处理悬空引用

文件分配方式

分配方式	说明	优点	缺点
连续分配	文件占用磁盘上连续的块	顺序/随机访问都快	外部碎片；文件大小难以动态增长
链接分配	每个块包含指向下一个块的指针	无外部碎片；文件大小可动态增长	只能顺序访问；指针占用空间
索引分配	专门一个索引块存储所有数据块的指针	支持直接访问；无外部碎片	索引块本身占用空间

FAT 与 inode

FAT（File Allocation Table）：链接分配的变体。将所有块的指针集中存储在一张表中（FAT 表），支持随机访问。
inode（Unix/Linux）：索引分配的扩展。inode 包含直接指针（12个）、一级间接指针、二级间接指针、三级间接指针，可以支持非常大的文件。

空闲空间管理

方法	说明
位图（Bit Map / Bit Vector）	每个块用 1 bit 表示（0=空闲，1=已分配）。查找连续空闲块方便
链表（Free List）	将所有空闲块链接成链表。分配第一个空闲块很快，但查找连续空间慢
分组（Grouping）	将空闲块分组，第一个空闲块存储若干其他空闲块的地址
计数（Counting）	记录连续空闲块的首地址和数量

磁盘调度算法

磁盘调度的目标：最小化磁头移动的总距离（寻道时间）。

假设磁头当前位于磁道 53，请求队列：98, 183, 37, 122, 14, 124, 65, 67，磁道范围 0-199。

算法	策略	特点
FCFS	按请求到达顺序服务	公平，但磁头移动距离大
SSTF（最短寻道时间优先）	选择离当前磁头最近的请求	总移动距离小，但可能饥饿
SCAN（电梯算法）	磁头单方向移动到尽头，然后反向	较均匀的等待时间
C-SCAN（循环扫描）	单方向移动到尽头，然后直接跳回起始端	更均匀的等待时间

SCAN 示例

磁头从 53 向 0 方向移动：

磁头路径: 53 → 37 → 14 → 0 → 65 → 67 → 98 → 122 → 124 → 183
总移动距离: 53 + 183 = 236 磁道

C-SCAN 示例

磁头从 53 向 199 方向移动：

磁头路径: 53 → 65 → 67 → 98 → 122 → 124 → 183 → 199 → 0 → 14 → 37
总移动距离: (199 - 53) + (199 - 0) + 37 = 382 磁道

现代磁盘调度

现代操作系统通常使用更复杂的调度器（如 Linux 的 CFQ、Deadline、BFQ 调度器），综合考虑公平性、延迟、吞吐量等因素。SSD 由于没有机械寻道，磁盘调度的意义大大降低。

I/O 管理（I/O Management）

I/O 方式

I/O 方式	机制	优点	缺点
轮询（Polling / Busy Waiting）	CPU 不断检查 I/O 设备状态寄存器	实现简单	浪费 CPU 时间，效率低
中断（Interrupt-driven I/O）	I/O 完成后设备向 CPU 发送中断信号	CPU 可以在等待时执行其他任务	每个字节/字都需要中断，频繁中断开销大
DMA（Direct Memory Access）	DMA 控制器直接在设备与内存间传输数据，完成后中断 CPU	CPU 负担最小，适合大批量数据传输	需要 DMA 硬件，与 CPU 竞争总线

轮询:   CPU ──循环检查──> 设备状态
中断:   CPU ──执行其他──> 设备完成 ──中断──> CPU 处理
DMA:    CPU ──启动DMA──> DMA控制器搬运数据 ──完成中断──> CPU

中断处理流程

设备完成 I/O，通过中断控制器向 CPU 发送中断请求
CPU 完成当前指令后响应中断
保存当前进程上下文（PC、寄存器等）
根据中断向量表跳转到对应的中断处理程序（ISR）
执行中断处理（如将数据从设备缓冲区拷贝到内核缓冲区）
恢复上下文，返回被中断的程序继续执行

缓冲策略（Buffering）

缓冲用于协调 CPU 与 I/O 设备之间的速度差异。

策略	说明
无缓冲	数据直接在用户空间与设备间传输。效率最低
单缓冲（Single Buffer）	内核空间设置一个缓冲区。设备写入缓冲区时 CPU 可处理上一批数据
双缓冲（Double Buffer）	两个缓冲区交替使用。设备向一个写入时，CPU 从另一个读取
循环缓冲（Circular Buffer）	多个缓冲区组成环形队列。适用于生产者-消费者模型

Spooling（假脱机技术）

Spooling（Simultaneous Peripheral Operations On-Line）将独占设备（如打印机）虚拟化为共享设备。多个进程的输出先写入磁盘的 Spool 区域，然后由 Spooling 系统按序送往设备。最常见的例子：打印队列。