OS-09 磁盘存储器管理

一、外存分配方式

磁盘上的文件如何存放？不同的分配方式对文件访问的性能和磁盘空间的利用率有直接影响。

连续分配：为每个文件分配一组连续的磁盘块。就像在图书馆里把一本书的每一页按顺序放在相邻的书架上——读起来很顺畅，但想插入新内容就麻烦了。连续分配支持高效的顺序访问和直接访问，但会产生外部碎片（类似内存管理中的碎片问题），且文件扩展困难。

链接分配：文件的每个数据块中包含指向下一个数据块的指针，形成一个链表。这种方式没有外部碎片，文件可以随需扩展。但缺点是只能顺序访问，无法直接访问文件的中间部分。链接分配又分为隐式链接（指针存储在数据块中，用户不可见）和显式链接（使用文件分配表FAT集中管理链接信息）。

索引分配：为每个文件建立一个索引块，索引块中存放文件所有数据块的地址列表。这种方案既支持高效的随机访问，又没有外部碎片，是最灵活的分配方式。缺点是引入了索引块的开销。

二、文件分配表（FAT）计算

FAT表采用的显式链接的变体。整个磁盘只有一个FAT表，其中每个条目对应一个磁盘块，存储的是该块的下一个块号。

例题：磁盘分区大小为4GB，磁盘块大小为4KB，问FAT表至少需要多少位宽？FAT表占多少空间？

磁盘块总数 = 4GB / 4KB = 2^32 / 2^12 = 2^20 = 1,048,576 块
FAT表位宽 = ⌈log₂(1,048,576)⌉ = 20位
FAT表大小 = 1,048,576 × 20 / 8 ≈ 2.5MB

三、混合索引结构

混合索引是Unix/Linux采用的外存分配方式。它结合了直接索引和多重间接索引的优点。

以Unix为例（块大小1KB，地址项4B）：

• 直接索引：10个直接地址项，覆盖0-9号数据块
• 一级间接索引：1个间接地址项，覆盖10-265号数据块
• 二级间接索引：1个二级间接项，覆盖266-65793号数据块
• 三级间接索引：1个三级间接项，覆盖更大范围

访盘次数计算：访问一个磁盘块需要几次磁盘I/O？

• 直接索引中的块：1次（直接读数据块）
• 一级间接索引中的块：2次（读间接索引块→读数据块）
• 二级间接索引中的块：3次（读二级间接块→读一级间接块→读数据块）

例题：块大小1KB，地址项4B，直接索引10项，一级/二级/三级间接各1项，求最大文件长度。

每块可存储地址数 = 1024/4 = 256个
直接索引容量 = 10 × 1KB = 10KB
一级间接容量 = 256 × 1KB = 256KB
二级间接容量 = 256 × 256 × 1KB = 64MB
三级间接容量 = 256 × 256 × 256 × 1KB = 16GB
最大文件长度 ≈ 16.06GB

四、磁盘调度算法

磁盘的I/O速度远慢于内存和CPU，因此磁盘调度的目标是最小化磁头的移动距离——特别是寻道时间。

先来先服务（FCFS）：按请求到达顺序依次服务。公平但效率很低，磁头可能在一个很大的范围内来回移动。

最短寻道时间优先（SSTF）：每次选择离当前磁头最近的请求处理。效率比FCFS高，但可能导致远处的请求长时间得不到服务（饥饿现象）。

电梯算法（LOOK）：磁头沿一个方向移动，处理沿途的请求，到达该方向的最远请求点后反向。类似于电梯的运行方式——在上行途中只处理上行请求。

循环扫描算法（C-LOOK）：单向移动，到达最远端后直接跳回最近端（不处理反向请求）。这样保证了所有磁道有相对均匀的等待时间。

例题：请求队列 [98, 183, 37, 122, 14, 124, 65, 67]，当前磁头位置53，用SSTF计算平均寻道长度。

当前53，最近的是65（距离12），然后是67（2），37（30），14（23），98（84），122（24），124（2），183（59）
移动路径：53→65→67→37→14→98→122→124→183
总寻道长度：12+2+30+23+84+24+2+59 = 236
平均寻道长度 = 236/8 = 29.5