第四章文件管理是408统考里那种“看着简单、一做就错”的典型章节。我第一次刷王道这一章的时候目录结构、索引结点、混合索引这些概念都能顺口背下来结果一遇到“该文件最大长度是多少字节”“访问某个偏移量需要几次磁盘访问”这类题照样卡壳。后来才想明白这一章真正难的不是背概念而是把概念换算成具体的数字和次数——你得清楚地知道一个字节的数据从进程发起 read 调用到落盘中间到底经过了几层、查了几张表、读了几次盘。这一章的内容量在408里算中等偏上三大部分文件系统基础、文件系统实现、磁盘组织与管理。概念辨析题偏爱考索引结点与FCB的区别、硬链接与软链接、目录检索的访盘次数计算题则集中在位示图换算、索引结点寻址范围、FAT表大小、磁盘调度算法的寻道长度。这两类题的解题套路都非常固定练熟之后属于“送分题”但如果第一遍只是划划线、抄抄笔记考场上大概率会在细节上栽跟头。这篇内容我按自己复习时的顺序整理从考点拆解一路写到易错点速查中间所有计算过程都摊开写方便你直接对照复现。1. 第四章到底难在哪先摸清考点分布再动手1.1 考纲拆解与权重判断文件管理这一章在408卷面上的存在感是有规律的。选择题通常占1到2道偶尔3道分值4到6分大题出现的概率相对低但一旦和内存管理、I/O管理交叉出题一道题就能拉开十几分。更关键的是这一章和后面I/O管理的磁盘部分是有重叠的磁盘调度、磁盘访问时间计算、磁盘缓存这些内容两章都能出复习的时候完全可以合并处理省下不少时间。从知识点颗粒度上看大致可以分成三层。最底层是概念层文件、目录、FCB、索引结点、逻辑结构、物理结构这些是必须能用自己的话讲清楚的因为它们会渗透进所有计算题里。中间层是机制层文件的共享与保护、文件系统的层次结构、空闲空间管理的四种方法、磁盘调度的五种算法这一层需要理解“为什么这么设计”死记硬背容易混。最上层是计算层位示图与盘块号换算、索引结点寻址范围、FAT表占用空间、磁盘访问时间与寻道长度这一层需要动手算光看是不行的。我自己的判断是纯粹的概念题分值在下降带计算的选择题在上升尤其是索引结点相关的计算这两年出现的频率明显变高。所以复习顺序上我会建议把计算相关的模块提前趁脑子清醒的时候啃。1.2 我的复习顺序先骨架后血肉直接按教材目录一章一节往下看效率其实不高因为文件管理的知识点是网状结构不是线性的。我后来改用一条主线串联一个文件从被创建、被打开、被读写的完整生命周期。顺着这条主线依次追问文件被创建时系统要给它分配一个描述结构FCB/索引结点这个结构放在哪、装了什么内容多个文件怎么组织在一起目录结构文件的逻辑结构怎么定顺序、索引、索引顺序文件的物理结构怎么选连续、链接、索引磁盘块不够用的时候怎么分配和回收空闲空间管理读写请求来了怎么排顺序磁盘调度不同用户怎么隔离权限文件保护同一个文件怎么被多个进程共用文件共享。把这条线走通一遍再回头去看教材的章节顺序就会发现原本零散的知识点都挂在这根线上了。教材的层次结构图用户接口、文件目录系统、存取控制验证模块、逻辑文件系统与文件信息缓冲区、物理文件系统、辅助分配模块、设备管理程序其实就是这条主线的另一种表达只不过它从系统实现的角度切了一层。提示不要一上来就背层次结构图的七层名字那个顺序在理解不清的时候很难记。先把“文件的一生”讲顺层次结构图自然就记住了。2. 文件与目录把最容易混淆的概念钉死2.1 文件的逻辑结构与存取方式逻辑结构是“用户看到的文件长什么样”物理结构是“存储介质上实际怎么放”。这两者最容易混我当初就把索引文件和索引分配搅在一起做题时直接选错。逻辑结构分两大类无结构文件和有结构文件。无结构文件就是流式文件比如一串字节流源程序、可执行文件、图片都属于这类文件内部不再划分记录长度以字节为单位。有结构文件又叫记录式文件由一条条记录组成记录长度可以定长也可以变长。有结构文件里再分四小类。顺序文件是最常见的记录按顺序排列定长记录的顺序文件可以随机存取变长记录的顺序文件只能从头顺序查找平均查找次数是 (N1)/2N 是记录条数。索引文件为每条记录建一张索引表索引表本身是定长的所以可以先查索引表定位记录位置再直接取记录查找次数大幅降低代价是索引表本身占空间而且索引表需要额外维护。索引顺序文件是前两者的折中把记录分组组内用顺序文件组间建索引平均查找次数大约是 (1√N)/2 量级兼顾了空间和效率。散列文件用哈希函数映射记录位置查找接近 O(1)但不支持顺序遍历。判断该用哪种结构本质是在“查找效率”和“空间开销”之间做取舍。记录条数少、访问随机性强、对空间敏感就选索引顺序记录条数极多、几乎只做顺序读用顺序文件加合适的块大小需要极快定位且不关心顺序考虑散列。顺序文件还有两个容易忽略的细节串结构是按存入时间排列记录顺序与关键字无关顺序结构是按关键字排列便于按关键字检索。另外顺序文件在磁带上只能顺序存取在磁盘上可以随机存取这个区别经常出现在选择题的干扰项里。2.2 目录项、FCB与索引结点为什么要把文件名单独拎出来目录的本质是“文件名到文件物理位置的映射表”。最早的做法是每个目录项直接存放一个完整的 FCBFCB 里包含文件名、文件类型、物理位置、逻辑结构、物理结构、存取控制、建立时间等一大堆信息。问题是 FCB 太大了一个盘块只能装很少几个目录项检索一个文件时可能要读好几个盘块磁盘I/O次数多。于是有了索引结点inode方案把 FCB 拆成两部分文件名放在目录项里其余的描述信息全部搬到索引结点里目录项里只保留“文件名 索引结点指针”。这样目录项的体积急剧缩小一个盘块能装下几倍甚至十几倍的目录项检索时读盘的块数显著减少。这就是为什么现代文件系统基本都采用索引结点。举个具体的数假设一个 FCB 占 64B一个目录有 128 个文件盘块 1KB。不拆分的话每个盘块放 16 个 FCB需要 8 个盘块平均检索一个文件要读 4 个盘块。拆分之后假设目录项缩到 16B文件名 12B 索引结点指针 4B一个盘块能放 64 个目录项128 个文件只需要 2 个盘块平均读 1 个盘块就能定位。这个差距在连锁目录的多级查找里会被放大因为每一级目录都要省这一次读盘。多级目录的检索访盘次数是可以直接算的。设目录树深度为 d每一级目录都要读一次盘假设目录项不大一级目录只占一个盘块那么检索一个文件总共需要 d1 次访盘最后还要读索引结点所在盘块。这个“d1”是选择题里反复出现的结论。2.3 硬链接与软链接的五个维度对比文件共享有两种实现方式考试里几乎每年都要考一次。硬链接基于索引结点的共享多个目录项指向同一个索引结点。索引结点里有一个链接计数 count每增加一个硬链接 count 加 1删除一个目录项 count 减 1只有 count 减到 0 时文件才真正被回收。硬链接的本质是“同一个文件有多个名字”。软链接符号链接利用符号链实现共享新建一个文件文件内容就是目标文件的路径字符串。访问软链接时系统读出路径再按路径逐级去查找找到目标文件的索引结点。软链接本质是“指向文件的指针”。两者的区别可以归纳成下面这张表对比维度硬链接软链接存储内容指向同一索引结点的目录项独立文件内容是目标路径索引结点计数影响 count共享同一个 inode自己有自己的 inodecount 独立跨文件系统不支持支持链接目录一般不允许允许原文件删除后文件仍存在数据不丢链接变成悬空链接访问报错访问开销低直接拿到 inode高需按路径重新查找循环问题不会产生可能产生循环链接这里有个细节容易错删除硬链接只是删掉一个目录项、count 减一数据块不释放只有当最后一个硬链接被删除count 归零系统才会释放索引结点和数据块。而软链接被删除时只是删掉了那个存路径的小文件本身跟目标文件毫无关系。注意有些题目会问“删除文件后另一个链接还能不能访问”看到“硬链接”答能看到“软链接”答不能这是最稳的判断依据。3. 文件系统实现从系统调用到磁盘块3.1 七层结构各自在忙什么教材给的文件系统层次结构从上到下依次是用户接口、文件目录系统、存取控制验证模块、逻辑文件系统与文件信息缓冲区、物理文件系统、辅助分配模块、设备管理程序。很多人觉得这七层是纯背诵内容其实每一层对应的是“一次文件操作过程中的一个步骤”理解了流程就自然记住了。我用一次“读文件”来串一下。用户在程序里调用 read请求先通过用户接口进入系统文件目录系统把用户给的文件名或文件描述符翻译成对应的 FCB 或索引结点存取控制验证模块检查当前用户有没有读权限逻辑文件系统与文件信息缓冲区把“读第几个字节到第几个字节”这种相对位置转换成“需要哪些逻辑块”物理文件系统把逻辑块号转换成物理块号辅助分配模块负责在需要时分配新块或回收旧块设备管理程序最后驱动磁盘完成实际的数据传输。这七层的顺序反过来就是写文件的流程只不过方向变成了从逻辑到物理再到设备。背的时候记住“越往下越接近硬件”这个原则就够了。3.2 三种物理结构的取舍逻辑物理结构解决的是“文件的数据块在磁盘上怎么排”。三种基本方式各有明显短板考试里喜欢考的就是这些短板。连续分配文件占用的磁盘块在物理上连续。优点是访问快磁头移动少支持顺序访问和直接访问随机访问寻址简单。缺点是文件难以动态增长因为文件后面那块空间可能已经被别的文件占了另外反复创建删除会产生大量外部碎片需要紧凑整理成本很高。所以连续分配一般用在一次写入、很少修改的场景比如早期的磁带和光盘。链接分配文件块散落在磁盘各处每块末尾存下一个块的指针。隐式链接下目录项里存首块指针和尾块指针用户只能从头开始顺序读取想访问第 100 块就得先读前 99 块效率极低而且只要中间某一块的指针损坏后面的数据就全丢了。显式链接也就是 FAT把指针从数据块里抽出来集中放在一张文件分配表里。FAT 在系统启动时就整体调入内存查下一块只需要访问内存不需要额外读盘所以显式链接支持随机访问。代价是 FAT 表本身要常驻内存磁盘越大表越大。索引分配为每个文件建一张索引表表里按顺序记录该文件所有数据块的块号。索引表也存放在磁盘块里称为索引块。索引分配支持随机访问不会产生外部碎片文件也容易扩展。问题在于每个文件都得配一个索引块小文件也要占一整块空间浪费索引块本身也可能很大大文件需要多级索引。三种结构的对比可以用下表快速区分结构随机访问文件扩展外部碎片额外空间开销连续分配支持困难有无链接分配隐式不支持容易无每块存指针链接分配显式/FAT支持容易无FAT 常驻内存索引分配支持容易无每文件一个索引块3.3 FAT表大小的计算套路FAT 相关的计算题非常好拿分套路只有一条公式FAT 表项数 磁盘总块数FAT 表总大小 表项数 × 每个表项占用的字节数。举个例子某磁盘容量 200MB盘块大小 1KBFAT 每个表项占 4B问 FAT 需要多大内存。盘块总数 200MB ÷ 1KB 200 × 1024 204800 块。表项数就是 204800FAT 大小 204800 × 4B 819200B 800KB。如果这个 FAT 要常驻内存就相当于系统启动后先吃掉 800KB 内存。反过来问也常见若 FAT 表最多只能占用 1MB 内存表项 4B盘块 1KB问磁盘最大容量是多少。表项数 1MB ÷ 4B 262144磁盘容量 262144 × 1KB 256MB。这里有个隐藏的坑FAT 表项位数决定了它最多能表示多少个块。若表项是 12 位最多表示 2¹² 4096 个块表项是 16 位最多 65536 个块。经典的 FAT16 就是因为表项只有 16 位所以支持的块数上限是 65536块大小 32KB 时最大分区才 2GB。理解了这个看到“为什么 FAT16 最大只支持 2GB 分区”这类题就知道怎么答了。提示FAT 相关的题先确认“表项数 盘块数”这个前提再确认表项字节数最后乘一下就行不要被“簇”这个概念绕晕。一个簇包含若干个盘块FAT 记录的是簇号如果题目给的是簇大小就先算簇的数量。4. 磁盘调度算法五道题的完整推演4.1 磁盘访问时间的三个组成部分一次磁盘读写的时间由三块组成寻道时间 旋转延迟 传输时间。寻道时间是把磁头从当前位置移动到目标磁道所需的时间这部分取决于磁盘调度算法也是唯一能被算法优化的部分。旋转延迟是磁头等到目标扇区转到下方所需的时间平均等于旋转半圈的时间也就是 1/(2r)r 是转速单位是转每秒。传输时间是实际读写数据的时间公式是 b/(rN)b 是每次读写的字节数N 是一条磁道上的字节总数。拿一组具体数算一遍磁盘转速 7200 r/min换算成 120 r/s。平均旋转延迟 1/(2×120) ≈ 4.17ms。若每条磁道有 512 个扇区、每个扇区 512B那么一条磁道的字节数 N 512 × 512B 256KB。现在要读 4KB 数据传输时间 4KB ÷ (120 × 256KB) 4096 ÷ 31457280 ≈ 0.13ms。对比一下就清楚了一次随机读取里寻道时间通常在毫秒到十几毫秒量级旋转延迟几毫秒传输时间只有零点几毫秒。所以磁盘性能的瓶颈在寻道这就是为什么要专门设计调度算法来减少磁头移动距离。4.2 用一组数据把五种算法跑一遍下面这组数据我自己推演过好几遍每一步都写出来你可以直接跟着算。设定磁道号范围 0 到 199磁头当前位于 143 号磁道请求队列按到达顺序为 86, 147, 91, 177, 94, 150, 102, 175, 130。FCFS先来先服务按到达顺序依次处理。143→8657→14761→9156→17786→9483→15056→10248→17573→13045累加得 576156868356487345 565。SSTF最短寻道时间优先每次从当前磁头位置出发选距离最近的请求。143 附近147 距离 4130 距离 13先选 147。147 之后150 距离 3选 150。150 之后130 距离 20175 距离 25选 130。130 之后102 距离 28选 102。102 之后94 距离 8选 94然后 913、865。86 之后剩下 175 和 177先 17589再 1772。累加 432028835892 162。SCAN扫描算法电梯算法选一个方向一直走到底再折返。这里假设磁头初始向磁道号增大的方向移动。143→147→150→175→177→199到达最外端距离 199-143 56。然后折返向下199→130→102→94→91→86→0距离 199-0 199。总计 56199 255。C-SCAN循环扫描只在一个方向上服务请求走到端点后直接回到另一端重新开始返回途中不服务。143→147→150→175→177→199距离 56从 199 直接跳到 0距离 199再从 0 向上服务 86距离 86。总计 5619986 341。LOOK / C-LOOK和 SCAN、C-SCAN 类似区别是不走到物理端点只走到最远的那个请求就折返。LOOK 向大号方向143→147→150→175→177距离 34折返向下 177→130→102→94→91→86距离 91。总计125。C-LOOK 在此基础上从 177 直接回到最小请求 86距离 91再向上服务 91、94、102、130距离 44总计 349144 169。整理成表更直观算法服务顺序总寻道长度FCFS143→86→147→91→177→94→150→102→175→130565SSTF143→147→150→130→102→94→91→86→175→177162SCAN143→147→150→175→177→199→130→…→86→0255C-SCAN143→…→199→0→86341LOOK143→147→150→175→177→130→102→94→91→86125C-LOOK143→…→177→86→91→94→102→130169从结果能看出两个规律。第一SSTF 的寻道长度通常很短但它会导致“饥饿”——远离磁头当前位置的请求可能一直得不到服务。第二SCAN 和 C-SCAN 的寻道长度不一定最优但它们保证了每个磁道位置被服务的最大等待时间是可预期的这在通用系统里比“平均最短”更重要。C-SCAN 比 SCAN 多走一趟回程寻道长度更大但它的响应时间更均匀适合请求负载重的场景。4.3 调度算法的评价与饥饿问题评价一个调度算法不能只看总寻道长度还要看两个指标平均寻道长度和响应时间的方差。FCFS 公平但性能差SSTF 性能好但公平性差可能出现饥饿SCAN 和 LOOK 在性能与公平之间取得平衡C-SCAN 和 C-LOOK 进一步优化了公平性代价是多走一段空程。这里有个常考的细节SCAN 算法中磁头到达端点后折返折返的那一刻其实刚刚服务过端点附近的请求所以端点附近的请求等待时间最短而中间位置的请求等待时间最长。这一点如果题目问“SCAN 算法中哪个磁道位置的请求平均等待时间最长”答案就是磁道中间位置。注意做题时一定要看清题目给的是 SCAN 还是 LOOK是走到端点还是走到最远请求。这个区别直接决定结果差多少我见过太多人在这里白白丢分。5. 空闲空间管理与高频计算题5.1 位示图一次搞懂行列与块号的换算磁盘上的空闲块怎么记录有四种常见方法空闲表法、空闲链表法、位示图法、成组链接法。位示图法是用一个二进制位对应一个盘块0 表示空闲1 表示已分配有的系统反过来看题目定义。整个位示图可以看作一个二维数组每一行是一个字假设字长 n 位那么第 i 行第 j 列行、列都从 1 开始计数对应的盘块号就是(i-1)×n j。如果行列从 0 开始公式就变成i×n j。这个公式一定要记死因为题目可能在“从 0 开始”和“从 1 开始”之间来回切换。我的做法是先确定题目给的编号起点再代入不要在脑子里默算。举个完整的例子某文件系统用位示图管理磁盘空间字长 32 位磁盘容量 1GB盘块大小 1KB。问位示图需要多少个字占多少字节。盘块总数 1GB ÷ 1KB 1024 × 1024 2²⁰ 1048576 块。每个盘块对应 1 位总共需要 1048576 位。按 32 位一个字字数 1048576 ÷ 32 32768 个字占用字节数 32768 × 4B 128KB。反过来也能算若已知某盘块号是 1024从 0 开始编号求它在位示图中的位置。字号 1024 ÷ 32 32位号 1024 % 32 0所以是第 32 个字的第 0 位。如果题目编号从 1 开始那就先把盘块号减 1 再算。5.2 成组链接法与UNIX的空闲块栈成组链接法是 UNIX 系统采用的方法思路是“分组 链接”。把空闲盘块分成若干组每组 100 个每组的第一个空闲块当作“栈顶”用来记录下一组空闲块的块号和数量这一组剩余的 99 个块才是真正可用的空闲块。系统在超级块里保存第一组的信息分配时从栈顶弹出用完一组就顺着指针去下一组。这个方法的关键在于超级块中保存的是当前可用的一组空闲块信息。如果超级块丢失整个文件系统的空闲块管理就乱了所以 UNIX 会对超级块做备份。考试里成组链接法主要考两点一是问“超级块中存放了多少个空闲块的信息”答案是从某一组的信息加上下一组的指针二是问“分配完当前组后系统怎么动作”答案是读取栈顶块中记录的下一组信息把它调入超级块。空闲表法和空闲链表法相对简单。空闲表法用一张表记录每个连续空闲区间的起始块号和长度分配时用首次适应或最佳适应策略会产生外部碎片空闲链表法把空闲块或空闲区间串成链表空闲盘块链每个块存一个指针空闲盘区链每个盘区存指针和长度。这几种方法的核心差异在于“记录空闲信息的空间开销”和“分配连续空间的难易程度”之间的权衡。5.3 索引结点寻址范围一道题吃透混合索引这道题型的套路非常固定先看一道完整例题。某文件系统的索引结点中有 13 个地址项其中 10 个是直接地址项1 个一级间接、1 个二级间接、1 个三级间接。每个地址项占用 4B磁盘块大小为 4KB。求该文件系统支持的最大文件长度是多少。第一步算一个索引块能装多少个地址项4KB ÷ 4B 1024 个。第二步逐项累加能寻址的数据块数10 个直接地址项对应 10 个数据块即 10 × 4KB 40KB。一级间接它指向一个索引块索引块里能装 1024 个地址项对应 1024 个数据块即 1024 × 4KB 4MB。二级间接一级索引块里的每个地址项都指向一个二级索引块每个二级索引块又能装 1024 个地址项所以对应 1024² 1048576 个数据块即 1048576 × 4KB 4GB。三级间接同理对应 1024³ 个数据块即 1024³ × 4KB 4TB。最大文件长度 40KB 4MB 4GB 4TB约等于 4TB 多一点。接着是第二问若要访问文件中偏移量为 5000000 字节约 4.77MB处的数据需要几次磁盘访问。先算这是第几个逻辑块5000000 ÷ 4096 1220.7所以是第 1220 号逻辑块从 0 开始。然后判断落在哪一层0 到 9 号块用直接地址10 到 1033 号块用一级间接1034 号开始进入二级间接。1220 大于 1033所以落在二级间接范围内。访问路径是先在内存中找到索引结点假设索引结点已经在内存读文件时通常已经打开文件索引结点会常驻内存然后读一级间接索引块再读二级间接索引块最后读目标数据块。一共3 次磁盘访问。这里有个容易踩的坑很多人会把读索引结点也算进去但题目通常会说明“索引结点已在内存中”或者“文件已打开”这两种情况下索引结点不需要再读盘。如果题目明确说从打开文件开始算那就要加上读索引结点和读目录项的访盘次数。还有一类变形题是“给出的地址项配置不同求最大文件长度”比如 12 个直接项加 3 级间接或者地址项是 6B、盘块是 2KB 等等方法完全一样先算每块能装几个地址项再按幂次累加。6. 我踩过的坑与复习节奏建议6.1 高频易错点速查表这一章我整理了五个反复踩到的坑做成了速查表考前扫一遍能救回不少分。易错点正确理解把索引文件的索引表和索引分配的索引块搞混索引表属于逻辑结构索引块属于物理结构认为硬链接会复制文件内容硬链接只增加目录项数据块共享位示图换算忘记起点行、列从 1 开始时用 (i-1)×nj从 0 开始时用 i×nj磁盘调度忘记区分 SCAN 和 LOOKSCAN 走到物理端点LOOK 走到最远请求算磁盘访问次数时把索引结点也算进去索引结点在内存时不计入访盘次数再补一个细节FCB 和索引结点的关系是“FCB 是完整描述信息索引结点是把描述信息从目录项中抽出来单独存放”。所以索引结点是 FCB 的一个子集不能说两者是完全并列的概念。6.2 做真题时的复盘方法这一章光看教材是不够的必须做题而且要按题型归类做。我的做法是准备三个本子或者三个文档一个记概念辨析一个记计算过程一个记错题原因。做题时强制自己把每一步的计算写出来包括“为什么这一步要乘 4KB”、“为什么这里跳过 1024 个块”不允许跳步。写完整了才能发现自己是真正理解了还是碰巧选对了。做完一套题之后不要只看正确率要标记每道题“我是靠记忆做对的还是靠推导做对的”。靠记忆做对的题隔一周再回去看一遍因为记忆会遗忘靠推导做对的题说明这块知识已经内化了可以降低复习频率。计算题还有个小技巧换一组数据自己重新出题。比如把索引结点的地址项从 13 个改成 15 个把盘块大小从 4KB 改成 1KB重新算一遍最大文件长度和访盘次数。这个动作看似多余但它能帮你把公式的真正含义搞清楚而不是死记某个固定答案。再补一个很多人忽略的点空闲空间管理的四种方法不要只记名字要能说出各自的优缺点和适用场景。空闲表法适用于连续分配、会产生外部碎片空闲链表法没有连续分配的限制但分配连续区间困难位示图法方便找到连续空闲块、也方便统计空闲块总数但位示图本身要占内存成组链接法兼顾了效率与空间适合大容量磁盘。考试喜欢用“某场景适合用哪种方法”来出选择题背名字没用还是要理解机制。