第六章：文件管理
6.1 文件的基本概念
文件是计算机中信息存储的基本单位——用户和OS通过文件来组织和管理数据。
文件的属性：
- 文件名：人类可识别的标识。
- 类型：如.exe, .txt, .jpg。
- 位置：指向文件在设备上的位置的指针。
- 大小：字节数。
- 保护：访问控制信息（读/写/执行权限）。
- 时间戳：创建、修改、访问时间。
文件操作：创建、打开、读、写、关闭、删除。
6.2 文件的逻辑结构
从用户角度看到的文件组织形式。
| 结构 | 描述 | 优点 | 缺点 |
|---|---|---|---|
| 顺序文件 | 记录按顺序排列 | 访问快（尤其定长记录） | 增/删困难 |
| 索引文件 | 建立索引表（关键字→指针） | 支持随机访问 | 额外索引开销 |
| 索引顺序文件 | 先分组，每组建索引 | 结合两者优点 | 较复杂 |
6.3 文件的物理结构
从OS角度看在磁盘上如何组织文件数据。
| 结构 | 描述 | 优点 | 缺点 |
|---|---|---|---|
| 连续分配 | 文件数据存在连续的磁盘块上 | 访问快（顺序和随机都高效） | 有外部碎片，扩展困难 |
| 链接分配 | 每个数据块存有指向下一块的指针 | 无外部碎片，扩展方便 | 随机访问慢，指针占用空间 |
| 索引分配 | 文件有一个索引块，记录所有数据块的位置 | 支持随机访问，扩展方便 | 索引块占用空间 |
链接分配的两种方式：
- 隐式链接：每个数据块存有指向下一块的指针。只能顺序访问。
- 显式链接（FAT——文件分配表）：将所有磁盘块的链接指针单独放在内存的FAT表中。在FAT中查找下一块非常快（内存访问）。
📌 408考点提示：FAT是常考内容——FAT本质是一张表，每个表项存放对应磁盘块的下一块指针。FAT存储在内存中，所以通过FAT查找速度很快。
索引分配中的三个层次：
- 单级索引：一个索引块记录所有数据块号——文件大时需要多个索引块。
- 多级索引：如二级索引，索引块指向多个索引块——支持超大文件。
- 混合索引（Unix的inode）：结合直接块（快速访问小文件）+ 单级/多级索引块（支持大文件）。
💡 记忆技巧：连续≈链表（顺序访问快但难扩展），链接≈链表+指针，索引≈图书目录（查目录找内容）。
6.4 目录结构
目录（文件夹） 是文件的索引，每个目录项包含文件名和指向文件的指针。
6.4.1 单级目录
所有文件在一个目录中。问题：命名冲突（不能重名），不适合多用户。
6.4.2 两级目录
每个用户有自己的文件目录（UFD），系统有主文件目录（MFD）。解决了命名冲突，但不支持子目录。
6.4.3 树形目录（最常用）
从根目录→子目录→文件，形成树形结构。用户用绝对路径（从根开始）或相对路径（从当前目录开始）访问文件。典型：Unix/Linux/Windows。
目录操作：创建/删除目录、列出目录、改变当前目录等。
当前目录：每个进程有一个当前目录，相对路径基于当前目录解析。
6.4.4 无环图目录
在树形目录的基础上增加共享（用链接等方式），使多个目录可以指向同一文件。注意避免循环（环）——引入共享后可能导致循环目录，要防止。
6.5 文件共享
| 方式 | 原理 | 特点 |
|---|---|---|
| 硬链接（基于索引结点的共享） | 多个目录指向同一个索引结点（inode）。每个文件有link count，删除到0才真正删除文件 | 不能跨文件系统，不能链接目录 |
| 软链接/符号链接（基于路径名的共享） | 创建一个新文件（.lnk/符号链接），内容指向目标文件的路径 | 可跨文件系统，原文件删除后链接失效 |
📌 408考点提示：硬链接和软链接的区别是常见选择题。硬链接共享inode（同一文件多个名），软链接是独立的文件（指向另一个文件）。
6.6 文件保护
访问控制：为每个文件设置访问控制列表（ACL）或权限位。
Unix权限模型（简洁）：
- 三类用户：owner（文件主）、group（同组用户）、others（其他人）。
- 三种权限：r（读）、w（写）、x（执行），用二进制表示：rwx = 111 = 7。
6.7 文件系统实现
6.7.1 文件系统的布局
典型磁盘分区（卷）的文件系统布局：
| 区域 | 内容 |
|---|---|
| 引导块 | 引导信息（MBR/GPT） |
| 超级块 | 文件系统的全局信息（大小、块数、空闲块数等） |
| 空闲块管理 | 空闲块位图/空闲链表 |
| i节点区（inode） | 存放所有文件的索引结点 |
| 数据区 | 文件数据块 |
6.7.2 目录实现
线性列表：简单但查找慢（O(n)）。 哈希表：查找快（O(1)），但需要处理冲突，可能不适合大目录。
6.7.3 FAT文件系统
FAT表中的每一项对应一个磁盘块，值表示下一块的块号（或用特殊值标记文件结束/坏块/空闲）。
FAT计算：假设磁盘块大小为4KB，磁盘容量为32GB，则FAT需要多少项？
- 块数 = 32GB/4KB = 8M（8×10^6）项
- 若每项用4字节（32位，可表示2^32个块），则FAT大小 = 8M × 4B = 32MB
6.7.4 Unix/Linux i节点（inode）
inode是文件的索引结点，包含文件的属性信息和指向数据块的指针。文件名和inode是分开存放的（文件名在目录中，inode在inode区）。
典型的inode结构（混合索引）：
- 12个直接块指针
- 1个一级间接块指针
- 1个二级间接块指针
- 1个三级间接块指针
假设块大小=4KB，指针占4B，则：
- 一个间接块可存 = 4KB/4B = 1024个指针
- 直接块可存 = 12 × 4KB = 48KB
- 一级间接可存 = 1024 × 4KB = 4MB
- 二级间接可存 = 1024 × 1024 × 4KB = 4GB
- 三级间接可存 = 1024 × 1024 × 1024 × 4KB = 4TB
6.8 磁盘结构
磁盘的物理结构：
- 磁道：盘面上的同心圆。
- 扇区：磁道上的一段弧，是磁盘读写的基本单位（通常512B）。
- 柱面：所有盘面上同一半径的磁道集合。
- 磁头：每个盘面有一个读写磁头。
磁盘访问时间 = 寻道时间 + 旋转延迟 + 传输时间
- 寻道时间：磁头移动到目标磁道的时间（最慢的部分，占总时间的70%以上）。
- 旋转延迟：目标扇区旋转到磁头下的时间（平均半圈旋转时间）。
- 传输时间：读写数据的时间。
6.9 磁盘调度算法
磁盘调度的核心目标是减少寻道时间。
| 算法 | 策略 | 特点 |
|---|---|---|
| FCFS（先来先服务） | 按请求顺序 | 简单但寻道时间长 |
| SSTF（最短寻道时间优先） | 选离当前磁头最近的请求 | 平均寻道时间较短，但可能产生"饥饿"（远处的请求很难被服务） |
| SCAN（电梯算法） | 磁头单向移动，沿途服务所有请求 | 解决了饥饿问题，但扫到一端才折返 |
| C-SCAN（循环扫描） | 只单向服务，到一端后快速返回 | 更均匀的等待时间 |
| LOOK | SCAN的改进——到最远请求处就折返，不用扫到底 | 比SCAN效率更高 |
| C-LOOK | C-SCAN的改进——到最远请求处就返回起点 | 比C-SCAN效率更高 |
💡 记忆技巧：SCAN/电梯算法就像电梯——一直往上直到没人按了再往下。LOOK是SCAN的优化版——电梯送到最高层有人的楼层就掉头，不用到楼顶。
📌 408考点提示：磁盘调度算法的寻道计算是408常考的计算题。关键：明确磁头当前位置和方向，计算寻道长度。
6.10 磁盘的管理
格式化：分为低级格式化（物理格式化——划分扇区）和高级格式化（逻辑格式化——写入文件系统结构）。
分区：将一个物理磁盘划分为多个逻辑分区（每个分区有自己的文件系统）。
引导块：磁盘的第一个扇区（MBR）包含引导代码和分区表。
坏块管理：磁盘出厂时就有坏道/坏块，控制器通过备用扇区替换坏块（也称为"扇区备份"）。
6.10.1 磁盘缓存与RAID
磁盘缓存：在内存中划分一块区域作为磁盘块的缓存，减少磁盘访问次数。
RAID（冗余磁盘阵列）：
- RAID 0：条带化——数据分块到多个磁盘，读写快但无冗余。
- RAID 1：镜像——数据完全复制到两个磁盘，有冗余但存储利用率低。
- RAID 5：条带+奇偶校验——一个磁盘损坏可恢复，空间利用率较高。
- RAID 10：条带+镜像——性能和冗余兼备。
6.10.2 文件系统的性能优化
块缓存（Buffer Cache/Page Cache）：在内存中缓存最近访问的文件块。Linux使用Page Cache统一管理文件和磁盘缓存。
提前读取（Read-ahead）：OS预测进程的访问模式，提前将后续磁盘块读入缓存，减少等待时间。
延迟写入（Delayed Write）：写操作先写入缓存，稍后批量写入磁盘——提高性能，但增加了断电丢数据的风险。
示例题
示例1（磁盘调度）：磁头在50号磁道，磁头正向磁道号增加方向移动。请求队列：98, 183, 37, 122, 14, 124, 65, 67。求SCAN和C-SCAN的寻道长度。
SCAN（电梯算法）： 方向：从50向大号移动。 服务顺序：65, 67, 98, 122, 124, 183 → 到199（最末尾）→ 折返 → 37, 14 寻道长度 = (65-50)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)+(199-183)+(199-37)+(37-14) = 15+2+31+24+2+59+16+162+23 = 334
C-SCAN： 方向：从50向大号移动。 服务顺序：65, 67, 98, 122, 124, 183 → 到199后直接跳到0 → 14, 37 寻道长度 = (65-50)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)+(199-183)+(199-0)+(14-0)+(37-14) = 15+2+31+24+2+59+16+199+14+23 = 385
示例2（FAT计算）：磁盘块大小1KB，磁盘容量40GB，FAT32中每项占4字节，问FAT表需要占多少空间？
解： 块数 = 40GB / 1KB = 40 × 2^20 = 40M 块 FAT表大小 = 40M × 4B = 160MB
如果用FAT16（每项2字节）：
- 每项2B → 只能表示65536个块
- 最大可管理容量 = 65536 × 1KB = 64MB
- 所以FAT16无法管理40GB的磁盘——这就是FAT32出现的必要性。
示例3（inode混合索引）：Unix文件系统中，块大小4KB，指针4B，有12个直接块、1个一级间接、1个二级间接。求： (1) 单个文件的最大大小 (2) 访问文件中的第5000个字节需要几次磁盘访问（假设inode在内存中）
解： (1) 每个间接块可存指针数 = 4KB/4B = 1024个 最大大小 = 12×4KB + 1024×4KB + 1024²×4KB = 48KB + 4MB + 4GB ≈ 4.048GB
(2) 第5000个字节：
- 前12个直接块覆盖：12×4096=49152字节
- 5000 < 49152，所以落在直接块中
- 块号 = 5000/4096 = 1（第2个直接块，偏移5000-4096=904）
- 需要1次磁盘访问（读数据块——inode已在内存）
示例4（目录结构相关）：在树形目录中，使用绝对路径和相对路径查找文件是什么区别？假设当前目录是/usr/bin，要访问文件/usr/bin/gcc和/usr/share/doc/readme，请分别用绝对路径和相对路径表示。
解： 绝对路径从根目录开始：/usr/bin/gcc, /usr/share/doc/readme。 相对路径从当前目录开始：
- /usr/bin/gcc → 在当前目录下直接访问 gcc（相对路径 = gcc）
- /usr/share/doc/readme → 先用 .. 回到 /usr，然后进入 share/doc/readme（相对路径 = ../share/doc/readme）
相对路径更短但依赖于当前目录。系统根据当前目录的inode位置解析相对路径——先找到当前目录的inode，再逐级查找子目录项。
示例5（文件物理结构分析）：一个文件大小为8000字节，磁盘块大小为1024字节。请分析该文件在使用连续分配、链接分配、索引分配时分别占用的磁盘块数和需要几次磁盘访问才能访问到第7000个字节。
解： 文件需要 8000/1024 = 7.8125 ≈ 8个磁盘块。
(1) 连续分配：
- 占用8个连续的磁盘块。
- 第7000个字节在第7块（块号=7000/1024=6，从0计）。
- 访问第7块只需1次磁盘访问（直接计算块号=起始块号+6）。
(2) 链接分配（隐式链接）：
- 占用8个磁盘块，每块末尾4字节存放下一块指针。
- 实际可用数据每块=1024-4=1020字节。
- 重新计算：需要8000/1020≈7.84，需要8块，但第8块只用了8000-7×1020=860字节。
- 要访问第7000个字节，需要顺序读块：块0→块1→...→块6（读7次才能到达第7块），加上读取第7块本身——共8次磁盘访问。速度极慢！
(3) 索引分配：
- 占用8个数据块+1个索引块=9个磁盘块。
- 索引块存8个指针（占8×4=32字节，远小于1024字节）。
- 访问第7000个字节：先读索引块（1次），找到第7块地址，再读第7块（1次）——共2次磁盘访问。
对比总结：连续分配访问最快（1次），但扩展困难；链接分配扩展方便但顺序访问极慢；索引分配介于两者之间（2次），支持随机访问且扩展方便。
本章小结
文件管理涉及文件的组织方式、目录结构、磁盘空间管理和磁盘调度。重点掌握：三种物理结构（连续/链接/索引）的对比和适用场景、FAT表的计算、inode混合索引的分析（408计算题常考）、磁盘调度算法的寻道计算、硬链接和软链接的区别。注意FAT和inode是两种不同的文件系统实现方式——FAT是"显式链接"的代表，inode是"索引分配"的代表。