磁盘组织与空闲空间管理

概念

磁盘（disk）是唯一能同时满足"大容量 + 可随机访问 + 断电不丢"三个条件的存储设备——内存快但小又易失，磁带大但只能顺序访问，只有磁盘三者兼备。

一句话说清本章管什么：上一章说"文件要用哪些盘块"，本章说"磁盘长什么样"和"哪些块还空着"。

问题	属于谁
文件的第 100 个逻辑块对应哪个物理块？	`os/30-filesystem.md`（文件系统）
这块磁盘一共有多少块？一块多大？	本章（磁盘组织）
哪些块是空闲的？怎么找到它们？	本章（空闲空间管理）
磁头先去哪个磁道？	`os/33-disksched.md`（磁盘调度）

⚠️ 本章的两个核心词："组织"（磁盘物理结构 + 地址 + 容量）与 "管理"（空闲块怎么记账）。考试里的计算题全落在这两处。

原理

一、磁盘的物理结构：从盘片到柱面

text

   ① 盘片(platter)        一张双面涂磁的圆盘 -> 上下两面各是一个"盘面"
        └─ ② 盘面(surface)  8 张盘片 = 16 个盘面, 每面一个读写磁头
             └─ ③ 磁道(track)  盘面上同心圆的圆环
                  └─ ④ 扇区(sector)  磁道等分出来的弧段, 是最小读写单位(通常 512 B)

   ⑤ 柱面(cylinder) = 各盘面上"半径相同"的那一圈磁道的集合

为什么"柱面"这个概念重要：磁头在所有盘面上是"联动"的——同一个柱面号上的所有磁道，磁头不动就能依次读到。**所以磁盘地址的递增顺序是

text

   扇区号 → 盘面号 → 柱面号

先在同一磁道里转、再换盘面（不用寻道）、最后才移臂换柱面。

磁盘地址（8 位盘面、4096 磁道、1024 扇区/道）：

字段	位数	范围	算式
柱面号	12 位	0 ~ 4095	$\log_{2} 4096$
盘面号（磁头号）	3 位	0 ~ 7	$\log_{2} 8$
扇区号	10 位	0 ~ 1023	$\log_{2} 1024$
合计	25 位	—	$12 + 3 + 10$

容量公式（必背）：

容量 = 盘面数 \times 每面磁道数 \times 每道扇区数 \times 扇区大小

⚠️ 只数"盘片"会错：1 张盘片有 2 个盘面。题目若说"4 张盘片"，盘面数是 8——这是本章最便宜的一道送分/送命题。另外：磁盘容量按 10 进制还是 2 进制标称是个历史坑（厂商标 1 GB = $10^{9}$ B，操作系统按 $2^{30}$ 算），答题按题目给的换算走，别自作主张。

二、磁盘访问时间：三部分

读一个盘块要花三段时间，这三段是哪一章都爱考：

text

   ① 寻道时间 Ts    移动磁臂把磁头挪到目标柱面   ← 最贵, 通常占 60%~80%
   ② 旋转延迟 Tr    等目标扇区转到磁头下         ← 平均 = 转半圈 = (60/RPM)/2
   ③ 传输时间 Tt    把数据从盘面读进内存         ← = 数据量 / 传输率

传输率的算法有两种等价写法：

传输率 = \frac{每道字节数}{转一圈的时间} = 每道字节数 \times \frac{R P M}{60}

锚点（本章定死，后续篇沿用）：8 盘面 × 4096 磁道 × 1024 扇区 × 512 B = 16 GB；每道 512 KB；7200 rpm → 转一圈 8.3333 ms、平均旋转延迟 4.1667 ms；传输率 = 62.91 MB/s；寻道时间取 8.0 ms。

读的块大小	寻道	旋转	传输	总计
512 B	8.0	4.1667	0.0081	12.1748 ms
4096 B	8.0	4.1667	0.0651	12.2318 ms
65536 B	8.0	4.1667	1.0417	13.2083 ms

⚠️ 这张表要读出三个结论：
读 512 B 和读 4 KB 的总时间几乎一样（12.1748 vs 12.2318 ms，只差 0.47%）——因为传输时间可以忽略，开销全在"寻道 + 旋转"上。
这就是"盘块要大"的理由：把块从 512 B 提到 4 KB，单块时间只涨 0.47%，但一次读进来的数据多了 8 倍。
只有块大到 64 KB（一整道）时，传输时间才涨到 1.04 ms——所以"顺序读大文件"比"随机读小块"快几十倍，靠的不是传输率，而是把"寻道 + 旋转"摊薄了。

三、磁盘管理：格式化三级 + 引导块

一块裸盘要经过三步才能用：

text

   ① 低级格式化(物理格式化)
        划出磁道、把磁道切成扇区、每扇区写"头(标识符 + CRC 校验码)"和数据区
        ★ 出厂时做, 用户一般做不了(会破坏全盘数据)

   ② 分区
        把磁盘切成若干独立区域, 每个分区可以装不同的文件系统

   ③ 高级格式化(逻辑格式化)
        在分区里建立文件系统: 引导块 / 超级块 / 空闲空间管理结构 / 根目录 / inode 表

引导块（MBR，主引导记录）——一个必考的小结构：

偏移	长度	内容
0	446 B	引导代码（第一阶段引导程序）
446	64 B	分区表：4 个分区项 × 16 B
510	2 B	结束标志 `0x55 0xAA`
—	512 B	合计（正好一个扇区）

⚠️ 三个数字连起来记：446 + 64 + 2 = 512。"MBR 只认 4 个主分区"这个历史限制就来自"分区表只有 64 B、每项 16 B"——要知道为什么，就得会算这个加法。

"引导块在磁盘上的位置"还有一层考点：整个磁盘的第一个扇区（0 号扇区）是 MBR，它不属于任何分区。这就是"磁盘"与"分区"的分界：MBR 在分区之外。

四、空闲空间管理：四种记账法

文件系统要随时回答"哪些盘块还空着"。四法各有取舍：

text

   ① 空闲表法      一张表: (起始块号, 空闲块数) ...
        ┌────────┬────────┐
        │ 首块号 │ 块数   │
        ├────────┼────────┤
        │   12   │   5    │  表示 12~16 空
        ├────────┼────────┤
        │   40   │   3    │  表示 40~42 空
        └────────┴────────┘
        ★ 天生适合"连续分配", 分配时找"够大的第一个/最小的空闲区"

   ② 空闲链表法
        空闲盘块链: 每个空闲块里存"下一个空闲块号"
        空闲盘区链: 每个空闲盘区存"下一个盘区号 + 本盘区块数"

   ③ 位示图法      1 位表示 1 个盘块, 0 = 空闲, 1 = 已占
        ┌───────────────────────┐
        │ 0 0 0 1 1 0 0 0 ...   │  1 位 / 块
        └───────────────────────┘
        ★ 最省空间: 1 GB / 1 KB 的盘只需要 128 KB 位示图

   ④ 成组链接法    空闲表 + 空闲链的结合
        超级块(内存)里放"栈顶组"的块号, 每组占一块, 存"下一组的块号"
        ★ UNIX 采用, 兼顾"检索快"与"超级块不至于太大"

四种方法的对比（必背表）：

方法	空间开销	检索空闲块	分配/回收	能否快速找"连续若干块"	典型场景
空闲表法	与"空闲区个数"成正比	顺序扫表	要合并/分裂表项	能（本来就是连续区）	连续分配的文件系统
空闲链表法	0（借用空闲块本身）	慢（要沿链走）	简单	难	无额外空间可用时
位示图法	固定（1 位/块）	快（位运算/扫描字）	简单（置 0/1）	能（扫连续 0）	通用，主流
成组链接法	每 100 个块多占约 1 个块	快（栈顶在内存）	稍复杂（涉及下钻/上溢）	难	UNIX 类系统

⚠️ "位示图"与"成组链接"的定位不同：
位示图把"是否空闲"摊平成一个比特——优点是简单、快、能按位运算找连续块；缺点是"位示图本身也要占盘"。
成组链接把"空闲块本身"当成链表节点——优点是额外开销极小（每 100 块才多用一块）；缺点是实现复杂。两者的共同目标都是"既省空间又快检索"，但走的路线相反。

五、位示图的字号位号换算（必考计算）

设字号从 0 开始、位号从 0 开始、块号从 1 开始（考试默认）：

字号 = ⌊ \frac{块号 - 1}{字长} ⌋, 位号 = (块号 - 1) mod 字长

反算：

块号 = 字号 \times 字长 + 位号 + 1

⚠️ 三处"从 0 还是从 1"必须按题目原文执行：
块号：教材惯例是从 1 开始（对应 0 号块留给引导块）。
字号：通常从 0 开始，但有的题从 1 开始。
位号：通常从 0 开始（低位在前）。
如果题目说"块号从 0 开始 / 字号从 1 开始"，公式里的 -1 就要挪位置。先看清三句话再代公式，这是位示图题唯一的坑。

六、提高磁盘 I/O 速度的几条路

手段	做法	效果
磁盘缓存	把刚读过的盘块留在内存	命中就不用再访问磁盘（与 `arch/12-cache.md` 同构）
提前读（read-ahead）	读第 i 块时顺手把第 i+1 块也读进来	顺序访问时几乎消灭旋转延迟
延迟写（delayed write）	要写的块先在内存里攒着，攒够一起写	把多次随机写合并成一次
优化物理块分布	交替编号 / 错位命名	让"读完一块、处理完再来"时扇区刚好又转回来

"交替编号"为什么要跳号（可算的一道题）：每道 1024 扇区、转一圈 8.3333 ms，则

读一个扇区 = \frac{8333.3 μ s}{1024} = 8.1380 μ s

相邻两个扇区之间只隔 8.1380 μs。如果 CPU/内存处理完一块需要 15 μs，那读完第 i 块后再想读物理相邻的第 i+1 块时，它早就转过去了，必须再等将近一整圈。

解法 = 交替编号：逻辑上相邻的两块，物理上隔开 ⌈15 / 8.1380⌉ = 2 个扇区，等处理完刚好转回来。

处理时间	需要跳过的扇区数	交替编号间隔
5.000 μs	0	1（不用跳）
15.000 μs	1	2
20.000 μs	2	3

⚠️ "错位命名"是另一回事：把不同盘面上的扇区编号错开，这样换盘面读下一块时不必等旋转。"交替编号治同面、错位命名治换面"——两句别混。

示例

例 1：C 实现——容量、访问时间与位示图换算

参数：8 盘面、每面 4096 磁道、每道 1024 扇区、扇区 512 B、7200 rpm、寻道 8.0 ms。 位示图参数：磁盘 1 GB、盘块 1 KB、字长 32 位、块号从 1 开始、字号/位号从 0 开始。

#include <stdio.h>

#define SECTOR   512        /* 扇区大小(字节) */
#define SPT      1024       /* 每道扇区数 */
#define TRACKS   4096       /* 每面磁道数 */
#define SURFACES 8          /* 盘面数(= 盘片数 x 2) */
#define RPM      7200
#define SEEK_MS  8.0

#define DISK_GB  1          /* 位示图这题用的磁盘容量 */
#define BLKSZ    1024       /* 盘块大小 */
#define WORD     32         /* 字长 */

int main(void) {
    long   cap  = (long)SECTOR * SPT * TRACKS * SURFACES;
    long   pertrack = (long)SPT * SECTOR;
    double rev  = 60000.0 / RPM;                    /* 转一圈的毫秒数 */
    double rate = pertrack * (RPM / 60.0);          /* 传输率 B/s */
    long   sizes[3] = {512, 4096, 65536};
    long   nblk, blks[5] = {1, 32, 33, 100, 1000};
    long   ws[3] = {0, 3, 31}, zs[3] = {0, 3, 7};
    int    i;

    printf("盘面 %d, 每面磁道 %d, 每道扇区 %d, 扇区 %d B\n",
           SURFACES, TRACKS, SPT, SECTOR);
    printf("容量 = %d x %d x %d x %d = %ld B = %ld GB\n",
           SURFACES, TRACKS, SPT, SECTOR, cap, cap / 1024 / 1024 / 1024);
    printf("每道字节 = %d x %d = %ld B = %ld KB\n",
           SPT, SECTOR, pertrack, pertrack / 1024);
    printf("转速 %d rpm -> 一圈 %.4f ms, 平均旋转延迟 %.4f ms\n",
           RPM, rev, rev / 2);
    printf("传输率 = %ld x %.0f = %.0f B/s = %.2f MiB/s = %.2f MB/s\n",
           pertrack, RPM / 60.0, rate, rate / 1024 / 1024, rate / 1000000);
    printf("\n");

    for (i = 0; i < 3; i++) {
        double tt = sizes[i] / rate * 1000.0;       /* 毫秒 */
        printf("读 %6ld B: 寻道 %.1f + 旋转 %.4f + 传输 %.4f = %.4f ms\n",
               sizes[i], SEEK_MS, rev / 2, tt, SEEK_MS + rev / 2 + tt);
    }

    nblk = (long)DISK_GB * 1024 * 1024 * 1024 / BLKSZ;
    printf("\n磁盘 %d GB, 盘块 %d B -> %ld 块\n", DISK_GB, BLKSZ, nblk);
    printf("位示图 = %ld 位 = %ld B = %ld KB\n", nblk, nblk / 8, nblk / 8 / 1024);
    printf("字长 %d 位 -> 需 %ld 个字\n", WORD, nblk / WORD);
    printf("\n");

    for (i = 0; i < 5; i++) {
        long idx = blks[i] - 1;                     /* 块号从 1 开始 */
        printf("块号 %4ld -> 字号 %5ld, 位号 %2ld\n",
               blks[i], idx / WORD, idx % WORD);
    }
    printf("\n");
    for (i = 0; i < 3; i++) {
        printf("(字号 %5ld, 位号 %2ld) -> 块号 %5ld\n",
               ws[i], zs[i], ws[i] * WORD + zs[i] + 1);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

盘面 8, 每面磁道 4096, 每道扇区 1024, 扇区 512 B
容量 = 8 x 4096 x 1024 x 512 = 17179869184 B = 16 GB
每道字节 = 1024 x 512 = 524288 B = 512 KB
转速 7200 rpm -> 一圈 8.3333 ms, 平均旋转延迟 4.1667 ms
传输率 = 524288 x 120 = 62914560 B/s = 60.00 MiB/s = 62.91 MB/s

读    512 B: 寻道 8.0 + 旋转 4.1667 + 传输 0.0081 = 12.1748 ms
读   4096 B: 寻道 8.0 + 旋转 4.1667 + 传输 0.0651 = 12.2318 ms
读  65536 B: 寻道 8.0 + 旋转 4.1667 + 传输 1.0417 = 13.2083 ms

磁盘 1 GB, 盘块 1024 B -> 1048576 块
位示图 = 1048576 位 = 131072 B = 128 KB
字长 32 位 -> 需 32768 个字

块号    1 -> 字号     0, 位号  0
块号   32 -> 字号     0, 位号 31
块号   33 -> 字号     1, 位号  0
块号  100 -> 字号     3, 位号  3
块号 1000 -> 字号    31, 位号  7

(字号     0, 位号  0) -> 块号     1
(字号     3, 位号  3) -> 块号   100
(字号    31, 位号  7) -> 块号  1000

⚠️ 三点说明：

(long)SECTOR * SPT * TRACKS * SURFACES 必须先转型——8 × 4096 × 1024 × 512 = 1.7×10^10 远超 32 位 int 上限，不转型会溢出成负数。这是"算大容量必须用 64 位"在 C 里的具体体现。
sizes[i] / rate * 1000.0 的除法顺序不能换——sizes[i] / rate 是浮点除（rate 是 double），若先把两数都取整相乘会精度崩掉。
本机无 C 编译器：此段代码逐行人工审查，并用等价的 Python 实现实跑核对，输出 21 行逐字一致。

例 2：Python——四种空闲空间管理法与成组链接法模拟

import math

print('=== ① 空闲表法: 分配与回收 ===')
free = [[12, 5], [40, 3], [100, 20]]     # [起始块号, 块数]
print('初始空闲表: %s' % free)


def alloc_first(free, need):
    """首次适应: 找第一个足够大的空闲区"""
    for e in free:
        if e[1] >= need:
            start = e[0]
            e[0] += need
            e[1] -= need
            if e[1] == 0:
                free.remove(e)
            return start
    return None


def free_area(free, start, n):
    free.append([start, n])
    free.sort()
    merged = []
    for e in free:                       # 相邻就合并
        if merged and merged[-1][0] + merged[-1][1] == e[0]:
            merged[-1][1] += e[1]
        else:
            merged.append(e[:])
    free[:] = merged


for need in [4, 2, 8]:
    s = alloc_first(free, need)
    print('  请求 %d 块 -> 起始块号 %s, 表变为 %s' % (need, s, free))
free_area(free, 12, 4)
print('  回收 (12, 4) -> 合并后 %s' % free)
print()

print('=== ② 位示图: 容量与字号位号 ===')
for cap_gb, bs, word in [(1, 1024, 32), (16, 4096, 32), (16, 4096, 64)]:
    nb = cap_gb * 1024 ** 3 // bs
    print('  %2d GB / %4d B = %8d 块 -> 位示图 %8d 位 = %7.2f KB, 字长 %d -> %d 个字'
          % (cap_gb, bs, nb, nb, nb / 8 / 1024, word, nb // word))
print('  位号公式: 字号 = (块号-1)//字长,  位号 = (块号-1)%字长,  反算 = 字号*字长+位号+1')
print()

print('=== ③ 成组链接法: 空闲块总数 10000, 每组 100 个块号 ===')
PER, N = 100, 10000
G = N // PER
usable = 99 * (G - 1) + 100
print('  组数 G = %d / %d = %d' % (N, PER, G))
print('  可分配数据块 = 99*(G-1)+100 = 99*%d+100 = %d' % (G - 1, usable))
print('  作索引用的块 = G-1 = %d' % (G - 1))
print('  校验: %d + %d = %d == %d -> %s' % (usable, G - 1, usable + G - 1, N, usable + G - 1 == N))
print()
stack = list(range(PER, 0, -1))          # 栈顶 100 项, 最后一项是下一组索引块号
print('  栈顶组初始 %d 项, 栈底 = %d, 栈顶 = %d' % (len(stack), stack[0], stack[-1]))
n = 0
while len(stack) > 1:
    stack.pop()
    n += 1
print('  连续分配 %d 个块后, 栈里只剩 %d 项 = [%d] (下一组索引块号)' % (n, len(stack), stack[0]))
print('  ★ 此时再分配 -> 把该块读入内存成为新栈顶 -> 这一次多花 1 次读盘')
print('  ★ 回收规则: 栈未满直接压栈; 栈已满(100 项) -> 把栈中 100 个块号写入新回收块,')
print('             再把"该块的块号"压栈 -> 栈变 1 项')
print()

print('=== ④ 交替编号: 需要隔几个扇区 ===')
SPT, RPM = 1024, 7200
rev_ms = 60000.0 / RPM
t_sec = rev_ms * 1000 / SPT
print('  每道 %d 扇区, 转一圈 %.4f ms -> 读一个扇区 %.4f us' % (SPT, rev_ms, t_sec))
for proc in [5.0, 8.138, 15.0, 20.0]:
    skip = math.ceil(proc / t_sec)
    print('  处理需 %6.3f us -> 跳过 %d 个扇区 (交替编号间隔 %d)'
          % (proc, max(0, skip - 1), max(1, skip)))
print()

print('=== ⑤ 四种空闲空间管理法对比 ===')
rows = [('空闲表法', '与空闲区数成正比', '顺序扫表', '要合并/分裂', '能'),
        ('空闲链表法', '0(借空闲块本身)', '沿链走, 慢', '简单', '难'),
        ('位示图法', '固定 1 位/块', '位运算, 快', '置 0/1, 简单', '能(扫连续 0)'),
        ('成组链接法', '每 100 块多 1 块', '栈顶在内存, 快', '下钻/上溢, 稍复杂', '难')]
print('  %s | %s | %s | %s | %s' % ('方法', '空间开销', '检索', '分配回收', '找连续块'))
for r in rows:
    print('  %s | %s | %s | %s | %s' % r)

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

输出对照（真实运行结果）：

=== ① 空闲表法: 分配与回收 ===
初始空闲表: [[12, 5], [40, 3], [100, 20]]
  请求 4 块 -> 起始块号 12, 表变为 [[16, 1], [40, 3], [100, 20]]
  请求 2 块 -> 起始块号 40, 表变为 [[16, 1], [42, 1], [100, 20]]
  请求 8 块 -> 起始块号 100, 表变为 [[16, 1], [42, 1], [108, 12]]
  回收 (12, 4) -> 合并后 [[12, 5], [42, 1], [108, 12]]

=== ② 位示图: 容量与字号位号 ===
   1 GB / 1024 B =  1048576 块 -> 位示图  1048576 位 =  128.00 KB, 字长 32 -> 32768 个字
  16 GB / 4096 B =  4194304 块 -> 位示图  4194304 位 =  512.00 KB, 字长 32 -> 131072 个字
  16 GB / 4096 B =  4194304 块 -> 位示图  4194304 位 =  512.00 KB, 字长 64 -> 65536 个字
  位号公式: 字号 = (块号-1)//字长,  位号 = (块号-1)%字长,  反算 = 字号*字长+位号+1

=== ③ 成组链接法: 空闲块总数 10000, 每组 100 个块号 ===
  组数 G = 10000 / 100 = 100
  可分配数据块 = 99*(G-1)+100 = 99*99+100 = 9901
  作索引用的块 = G-1 = 99
  校验: 9901 + 99 = 10000 == 10000 -> True

  栈顶组初始 100 项, 栈底 = 100, 栈顶 = 1
  连续分配 99 个块后, 栈里只剩 1 项 = [100] (下一组索引块号)
  ★ 此时再分配 -> 把该块读入内存成为新栈顶 -> 这一次多花 1 次读盘
  ★ 回收规则: 栈未满直接压栈; 栈已满(100 项) -> 把栈中 100 个块号写入新回收块,
             再把"该块的块号"压栈 -> 栈变 1 项

=== ④ 交替编号: 需要隔几个扇区 ===
  每道 1024 扇区, 转一圈 8.3333 ms -> 读一个扇区 8.1380 us
  处理需  5.000 us -> 跳过 0 个扇区 (交替编号间隔 1)
  处理需  8.138 us -> 跳过 0 个扇区 (交替编号间隔 1)
  处理需 15.000 us -> 跳过 1 个扇区 (交替编号间隔 2)
  处理需 20.000 us -> 跳过 2 个扇区 (交替编号间隔 3)

=== ⑤ 四种空闲空间管理法对比 ===
  方法 | 空间开销 | 检索 | 分配回收 | 找连续块
  空闲表法 | 与空闲区数成正比 | 顺序扫表 | 要合并/分裂 | 能
  空闲链表法 | 0(借空闲块本身) | 沿链走, 慢 | 简单 | 难
  位示图法 | 固定 1 位/块 | 位运算, 快 | 置 0/1, 简单 | 能(扫连续 0)
  成组链接法 | 每 100 块多 1 块 | 栈顶在内存, 快 | 下钻/上溢, 稍复杂 | 难

五条结论：

空闲表法分配时会"从表项头部切开"（请求 4 块，[12,5] 变成 [16,1]）；回收时必须"看前看后能不能合并"（回收 (12,4) 后与 [16,1] 拼回 [12,5]）——"分配要分裂、回收要合并"是空闲表法唯一的实现要点。 ⚠️ 更值得注意的一点：请求 2 块时 [16,1] 只有 1 块、不够大，首次适应直接跳过它去用 [40,3]，于是留下 [16,1] 和 [42,1] 两个小编号碎片——这就是"空闲表法也会产生外部碎片"的具体过程（与 os/20-contiguous.md 的动态分区完全同构）。
位示图的空间开销是"1 位/块"：1 GB / 1 KB 的盘只需要 128 KB（占 1 GB 的 0.0125%）；16 GB / 4 KB 的盘位示图 512 KB。字长从 32 位换成 64 位，字数减半但总字节数完全一样——字长只影响"怎么装"，不影响"要多少位"。
成组链接法（10000 个空闲块、每组 100）：组数 100，其中 99 个块被用作索引，真正能装数据的是 9901 块——"损失率只有 99/10000 = 0.99%"，这就是它比位示图省的原因（位示图是固定按盘容量 0.0125% 收，成组链接按"每 100 块多 1 块"收）。
连续分配 99 个块后栈里只剩 1 项（就是下一组的索引块号）——此时再分配要多花 1 次读盘。所以"成组链接法分配一块要读几次盘"的标准答案是"通常 0 次、最多 1 次"。
交替编号的间隔由"处理时间 ÷ 单扇区读取时间"决定：处理 15 μs 要隔 2 个扇区、20 μs 要隔 3 个——处理越慢，跳得越远。"环形缓冲/交错编号"的思想在 ds/02-stack-queue.md 的循环队列里出现过，这里换了个硬件场景重现。

考点

1. 必背结论

磁盘三大特点：大容量、可随机访问、断电不丢——是"唯一三者兼备"的存储设备。
结构四级：盘片（双面）→ 盘面 → 磁道 → 扇区；柱面 = 各盘面上半径相同的磁道集合。
1 张盘片 = 2 个盘面（数容量时最容易漏）。
容量 = 盘面数 × 每面磁道数 × 每道扇区数 × 扇区大小。
磁盘地址三字段：柱面号 + 盘面号（磁头号）+ 扇区号；递增顺序是"扇区号 → 盘面号 → 柱面号"（同柱面换头不用寻道）。
访问时间三分：寻道时间 $T_{s}$ （最贵）+ 旋转延迟 $T_{r}$ + 传输时间 $T_{t}$ 。
平均旋转延迟 = 转半圈 = $\frac{60}{R P M} \div 2$ ；7200 rpm → 一圈 8.3333 ms、平均旋转延迟 4.1667 ms。
传输率 = 每道字节数 × (RPM/60)。
格式化三级：低级格式化（划扇区 + 写标识/CRC，出厂做）→ 分区 → 高级格式化（建文件系统）。
MBR = 引导代码 446 B + 分区表 64 B（4 项 × 16 B）+ 结束标志 2 B = 512 B——"最多 4 个主分区"由此而来。
空闲空间管理四法：空闲表法 / 空闲链表法 / 位示图法 / 成组链接法；位示图省空间且检索快（主流），成组链接是 UNIX 的解法。
位示图换算（块号从 1、字号位号从 0）：字号 = $(块号 - 1) \div 字长$ 取整；位号 = $(块号 - 1) mod 字长$ ；反算 = 字号 × 字长 + 位号 + 1。
锚点（本章定死）：8 盘面 × 4096 磁道 × 1024 扇区 × 512 B = 16 GB；每道 512 KB；传输率 62.91 MB/s；读 512 B / 4 KB / 64 KB 的总时间 = 12.1748 / 12.2318 / 13.2083 ms。
锚点（位示图）：1 GB / 1 KB → 1048576 块 → 位示图 128 KB → 32 位字 32768 个。
锚点（成组链接，10000 块 / 每组 100）：组数 100、可分配 9901 块、索引块 99；分配一块通常读盘 0 次、最多 1 次；回收遇"栈满"→ 把栈中 100 个块号写入新回收块、再把该块号压栈（栈变 1 项）。
锚点（交替编号）：1024 扇区/道、7200 rpm → 单扇区 8.1380 μs；处理 15 μs 要隔 2、20 μs 要隔 3。

2. 高频陷阱

把"盘片数"当"盘面数"：错。1 张盘片有 2 个盘面（除非题目明说单面）。
把"柱面"当"磁道"：错。柱面是"跨盘面的同一半径磁道的集合"，柱面数 = 每面磁道数（8 盘面时柱面数与磁道数是 1:1）。
算平均旋转延迟忘了除以 2：平均来说目标扇区可能在任何位置，期望等待半圈——写成"整圈"就把延迟高估一倍。
认为"传输时间是访问时间的主要部分"：错。寻道 + 旋转占 99% 以上——本题读 4 KB 时传输只占 0.53%。
算容量时忘记转 64 位：盘面 8 × 磁道 4096 × 扇区 1024 × 512 B ≈ $1.7 \times 10^{10}$ ，超出 32 位 int——C 里不 (long) 就溢出成负数。
位示图三处起点搞混：块号从 1、字号从 0、位号从 0（要按题目原文执行）；公式里的 -1 是给"块号从 1 开始"用的。
说"字长越大位示图越小"：不准确。位示图的"位数"由盘块数决定，字长只决定"用几个字装"——总字节数不变（32 位 32768 字 = 64 位 16384 字 = 都是 128 KB）。
认为"位示图法能找连续块，所以它一定最好"：不准确。它的开销是"固定按盘容量收（1 位/块）"，盘极大时位示图本身也大（16 GB / 4 KB 盘要 512 KB）；成组链接的额外开销只有约 1%。
把"交替编号"与"错位命名"混为一谈：交替编号治"同盘面连续块来不及处理"；错位命名治"换盘面时等旋转"——一个在道内、一个在面间。
说"低级格式化 = 建立文件系统"：错。低级格式化划扇区（出厂做）；建立文件系统是高级格式化——顺序不能反。
认为"回收一个块就是把块清零"：错。只需更新位示图/空闲表/栈；块里的旧数据照旧存在。

3. 解题模板（"磁盘计算题"）

① 容量: 盘面数 x 每面磁道数 x 每道扇区数 x 扇区字节数
     注意"盘片数 x 2 = 盘面数"
② 访问时间 = 寻道 + 旋转 + 传输
     旋转 = (60 / RPM) / 2 (秒) ;  传输 = 数据量 / 传输率
     传输率 = 每道扇区数 x 扇区大小 x (RPM / 60)
③ 位示图:
     位数 = 盘块数 = 容量 / 块大小
     字节数 = 位数 / 8 ;  字数 = 位数 / 字长
     块号 -> 字号/位号: (块号-1) // 字长, (块号-1) % 字长
     (字号, 位号) -> 块号: 字号*字长 + 位号 + 1
④ 成组链接:
     每组容量 P(块号数) -> 每组实收 P-1 个可用块(链尾组 P 个)
     栈满回收: 栈中 P 个块号写入新块 -> 该块号压栈
     分配读盘次数: 通常 0 次, 下钻时 1 次
⑤ 交替编号: 间隔 = ceil(处理时间 / 单扇区读取时间)

4. 与相邻章节的接口

os/30-filesystem.md（文件系统）：本章的"盘块"就是那章的分配单位；那章的位示图/空闲表就是本章第四节的内容——两章共用同一套数据结构，只是一章从"文件"看、一章从"磁盘"看。
os/33-disksched.md（磁盘调度）：本章的"寻道时间是主要开销"是调度算法的全部动机——调度优化的就是那 8 ms。
os/32-io.md（I/O 管理）："提前读"和"磁盘缓存"两处交叉——那章讲缓冲的组织，本章讲为什么要缓冲（寻道太贵）。
ds/32-hash.md（散列）与 ds/31-btree.md（B 树）："位示图的字号位号"是一次映射；"成组链接的下钻"是一次链式查找——两种索引结构在这里都能见到。
arch/12-cache.md（Cache）：磁盘缓存与 Cache 是同一思想（局部性 + 层次存储）在不同层级上的复现；Cache 的"块要大"与本章的"盘块要大"是同一个结论的两个推导。
circuit/13-flipflop.md（触发器）：磁盘上的比特靠磁畴的两个方向表示——"二值存储"从触发器到磁盘是同一条线。

小结

磁盘 = 盘片（双面）→ 盘面 → 磁道 → 扇区；柱面 = 各面同半径磁道的集合。
容量 = 盘面数 × 每面磁道数 × 每道扇区数 × 扇区大小；磁盘地址 = 柱面号 + 盘面号 + 扇区号，递增顺序"扇区 → 盘面 → 柱面"。
访问时间 = 寻道 + 旋转 + 传输；前两项占 99%——这是"盘块要大"和"调度要优化"的共同理由。
锚点：16 GB / 每道 512 KB / 7200 rpm（一圈 8.3333 ms、旋转延迟 4.1667 ms）/ 传输率 62.91 MB/s；读 512 B 与 4 KB 只差 0.47%。
格式化三级：低级格式化 → 分区 → 高级格式化；MBR = 446 + 64 + 2 = 512 B。
空闲空间管理四法：空闲表（能找连续区）/ 空闲链表（零额外空间、慢）/ 位示图（1 位每块、快）/ 成组链接（UNIX，约 1% 开销）。
位示图锚点：1 GB / 1 KB → 1048576 位 → 128 KB → 32768 个 32 位字；字号 = $(块号 - 1) \div 字长$ 、位号 = $(块号 - 1) mod 字长$ 。
成组链接锚点：10000 块 / 每组 100 → 组数 100、可分配 9901、索引块 99；分配一块最多读盘 1 次。
加速手段：磁盘缓存 / 提前读 / 延迟写 / 交替编号 / 错位命名；交替编号间隔 = $⌈$ 处理时间 ÷ 单扇区时间 $⌉$ 。

磁盘组织与空闲空间管理

概念

原理

一、磁盘的物理结构：从盘片到柱面

二、磁盘访问时间：三部分

三、磁盘管理：格式化三级 + 引导块

四、空闲空间管理：四种记账法

五、位示图的字号位号换算（必考计算）

六、提高磁盘 I/O 速度的几条路

示例

例 1：C 实现——容量、访问时间与位示图换算

例 2：Python——四种空闲空间管理法与成组链接法模拟

考点

小结

我的笔记

评论（0）

磁盘组织与空闲空间管理 ​

概念 ​

原理 ​

一、磁盘的物理结构：从盘片到柱面 ​

二、磁盘访问时间：三部分 ​

三、磁盘管理：格式化三级 + 引导块 ​

四、空闲空间管理：四种记账法 ​

五、位示图的字号位号换算（必考计算） ​

六、提高磁盘 I/O 速度的几条路 ​

示例 ​

例 1：C 实现——容量、访问时间与位示图换算 ​

例 2：Python——四种空闲空间管理法与成组链接法模拟 ​

考点 ​

小结 ​

我的笔记

评论（0）

磁盘组织与空闲空间管理

概念

原理

一、磁盘的物理结构：从盘片到柱面

二、磁盘访问时间：三部分

三、磁盘管理：格式化三级 + 引导块

四、空闲空间管理：四种记账法

五、位示图的字号位号换算（必考计算）

六、提高磁盘 I/O 速度的几条路

示例

例 1：C 实现——容量、访问时间与位示图换算

例 2：Python——四种空闲空间管理法与成组链接法模拟

考点

小结