操作系统文件管理：物理结构、目录检索与磁盘I/O计算全解析

我一直觉得《操作系统》课程里文件管理是那种“上课听得很轻松、考试一做题就现原形”的章节。进程同步好歹能靠 PV 原语画出套路内存管理翻来覆去就是那么几个置换算法到了文件管理这里概念铺天盖地文件、目录、FCB、索引节点、位示图、成组链接法……猛一看像是文科背诵可真考到“读某个文件的第 5 块需要几次磁盘 I/O”“这个文件系统最大能支持多大文件”这种题不会算就是不会算。这篇内容打算把文件管理这一章从头到尾理一遍配套课后典型题的解题套路再把我自己复习时踩过的坑和记混过的概念一并交代清楚。适合正在学《操作系统 慕课版》、准备期末考的同学也适合想让文件系统知识体系变得更完整的人参考。1. 先把文件系统要解决的四个问题摆上桌1.1 用户看到的文件和系统看到的文件是两回事很多人学文件管理觉得散是因为没意识到这一章本质上在回答四个问题——文件怎么组织、文件怎么存、文件怎么找、文件怎么保护。把这四个问题挂到脑子里后面所有知识点都会各就各位。用户视角的文件很简单双击 Word 图标看到一篇论文在终端敲cat看到一段文本。可操作系统底层看到的不是“一篇论文”而是一堆二进制位散落在磁盘的不同扇区里。文件管理模块的职责就是把用户这种“按名字访问的逻辑文件”和磁盘上“按块号存储的物理记录”之间那一大段距离填平。理解这一点第二章的三种物理结构、第三章的目录检索、第四章的空闲空间管理全都是围绕“填平这段距离”展开的。1.2 文件的属性管文件先要知道文件长什么样文件是计算机系统中信息的一种组织形式是存放在存储介质上的一组相关信息的集合。但“一组信息”这个词太抽象系统要管理它必须先给文件“建档”——也就是一组属性。通用的文件属性包括文件名、标识符系统内部的唯一 ID、类型、位置文件在存储介质上的物理地址、大小、创建/修改时间、所有者信息和保护信息等。这里有个容易忽略的细节文件的“类型”不只是后缀名那么简单。从文件系统角度看普通文件、目录文件、链接文件、设备文件都是“文件”但它们的内部结构和管理方式完全不同。目录本身就是一个文件这个认知在第三章很重要现在先记住。1.3 逻辑结构是用户视角物理结构是系统视角文件的逻辑结构是从用户角度看到的文件组织形式主要分三类顺序文件记录一个接一个地排列定长记录可以直接算偏移地址变长记录只能顺序扫描。索引文件为每条记录建立一个索引项适合变长记录和随机访问但索引表本身占空间。索引顺序文件把记录分组组内顺序存放组间用索引表索引是前两者的折中。典型例子就是教材里常说的“ISAM”思想。物理结构则是文件在磁盘上到底怎么存放的连续分配、链接分配或索引分配。我见过太多同学把逻辑结构和物理结构混着答考“文件的逻辑结构有哪几种”非要写连续分配这种失分最冤枉。记住一句话逻辑结构是“文件看起来像什么”物理结构是“文件实际存在哪”。2. 三种物理分配方式这是全章最密集的考点区2.1 连续分配简单粗暴但碎片无情连续分配的逻辑最朴素每个文件占一组连续的磁盘块。目录项里只需要记录两个信息——起始块号和文件长度占多少块。因为是连续存放所以文件的第 i 块可以直接算出来起始块号 i随机访问性能非常好顺序读速度也快磁盘寻道时间短。但它的缺点也让人头疼。第一要给文件找到一个足够大的连续空间磁盘空间经过反复分配回收之后会产生大量外部碎片明明总空闲空间够却存不下一个新文件。第二文件长度是固定的想动态增长很难增长时必须整体挪位置。所以连续分配最适合“一次性写成、后续只读”的场景比如光盘、ROM 里的文件系统。考试里如果考连续分配大概率是配合第四章的空闲表法一起出有一个空闲分区表按首次适应或最佳适应算法给文件找空间。这类题关键是把空闲区间的起始块号和长度算清楚注意分配后要修改或删除对应表项。2.2 链接分配把碎片变成链却牺牲了随机访问链接分配的基本思想是文件可以存放在任意不连续的磁盘块中每一块都保存一个指向下一块的指针这样文件在磁盘上形成一个链表。它彻底解决了外部碎片问题文件也可以随时扩展。链接分配又分两种这是高频区分点。隐式链接每个盘块的末尾存放下一个盘块的地址目录项记录首块号和末块号。缺点非常明显只能从头开始顺序访问想读第 5 块就得先读第 1、2、3、4 块随机访问性能极差。而且链上任何一块的指针坏了整个文件后半部分就全丢了可靠性差。显式链接把指向下一块的指针统一存到一张“文件分配表”FAT里而不是放在每个盘块里。目录项只需要记录起始块号访问第 i 块时直接在 FAT 表里查表就能找到下一块的块号。因为查表本身就是内存操作FAT 常驻内存所以随机访问性能比隐式链接好很多。FAT 就是 Windows 老用户熟悉的 FAT32 文件系统的核心机制。典型题型假设 FAT 在内存中文件 F 占用的盘块号依次为 10、15、20、25、30现在要读文件第 4 块从 0 开始编号需要几次磁盘 I/O思路FAT 在内存所以查表不需要磁盘 I/O。要读第 4 块的数据最终必须把第 4 块所在的磁盘块读进内存所以只需要 1 次磁盘 I/O。这种题必须看清楚前提条件——如果 FAT 不在内存每次查 FAT 都可能触发磁盘读答案就完全不同了。做题先画圈标“FAT 是否在内存”这是血的教训。2.3 索引分配用一张索引表换随机访问能力索引分配为每个文件建立一张索引表表中存放文件所有盘块的块号目录项指向索引表。因为索引表本身也是一个磁盘块所以要想访问文件数据第一件事是先读索引块。单级索引一个文件对应一个索引块适合中小型文件。但小文件也会占一个完整的索引块空间浪费明显。假如磁盘块大小 4KB一个文件只有 1KB数据占 1 块索引块也得占 1 块存储开销直接翻倍。多级索引当文件大到单级索引块装不下所有盘块号时就用“索引块指向索引块”的方式扩展。二级索引的索引块里存的是若干一级索引块的块号每个一级索引块再存数据块号。这样能索引的数据块数量呈指数级增长但访问次数也会增加一级索引访问 1 个索引块 1 个数据块二级索引要访问 2 个索引块 1 个数据块。混合索引Unix System V 的设计也是很多教材最爱考的点。它把索引地址分成几个档次12 个直接地址直接指向数据块、1 个一级间接地址、1 个二级间接地址、1 个三级间接地址。这样小文件用直接地址零额外索引开销大文件逐步升级到间接寻址。计算题假设磁盘块大小 4KB地址项占 4B一个索引块可存放的地址数为4KB / 4B 1024个。那么12 个直接地址可寻址12 × 4KB 48KB一级间接可寻址1024 × 4KB 4MB二级间接可寻址1024 × 1024 × 4KB 4GB三级间接可寻址1024 × 1024 × 1024 × 4KB 4TB文件最大长度就是四者相加。这类题永远不会超纲关键就是把“每个索引块能放多少条地址项”算出来剩下的只是乘法。2.4 三种分配方式怎么选一张对照表划清界限分配方式目录项内容随机访问外部碎片文件扩展典型应用连续分配起始块号 长度好有难光盘、只读文件系统隐式链接首块号 末块号差无易早期系统显式链接FAT首块号较好无易FAT32、exFAT索引分配索引块地址好无易Unix/Linux 文件系统有个高频判断题是“FAT 属于索引分配”。错FAT 属于链接分配的显式链接形式只不过把指针集中到一张表里本质还是“链式指针”不是索引表。这个概念记错后面做题全乱。3. 目录检索与“一次磁盘 I/O”的故事3.1 FCB 和 inode一次聪明的解耦文件系统要管理文件必须给每个文件建一个文件控制块FCB。FCB 里包含文件名、文件类型、权限、属主、大小、时间戳、物理位置等几乎全部元数据。目录文件就是由若干个 FCB 组成的。你打开一个目录本质上是把这个目录文件的内容读出来逐个对比里面的 FCB。问题在于如果 FCB 太大目录文件的体积也会变得很大。查找某个文件时系统需要把整个目录文件逐块读入内存对比文件名即使你只需要“文件名 物理位置”这两项信息也得把一串冗余元数据一起读进来磁盘 I/O 次数直线上升。Unix 的索引节点inode对这个问题的处理非常漂亮把 FCB 拆成两部分——目录项里只保留文件名和 inode 编号其余元数据全部放进 inode。查目录时只需要读目录项找到 inode 编号后再按需读 inode。因为目录项长度大大缩小一个磁盘块能容纳的目录项数量变多同样的目录内容占用的磁盘块就少了检索效率自然提升。3.2 单级、两级、树形、无环图目录结构的演进逻辑目录结构不是一开始就长现在这样的。单级目录所有文件都放在同一个目录下实现最简单但整个世界只有一个目录不同用户不能有同名文件命名冲突和文件管理混乱不可避免。两级目录第一级是主文件目录第二级是各用户的用户文件目录。用户之间隔离了命名空间但同一个用户内部还是“一锅粥”且无法对文件做更细的分类。树形目录这也是现代操作系统的标准姿势。目录可以嵌套子目录文件用路径名唯一标识例如/usr/home/doc/report.pdf。系统查找文件时按路径逐级查找目录项每个路径分量对应一次目录检索。无环图目录它解决了多用户共享文件的问题。试想两个用户都想用同一个目录树下的公共目录如果只靠树形结构只能复制一份文件副本同步更新很麻烦。无环图目录允许不同目录项指向同一个文件或子目录从而共享文件而不产生内容副本。但要注意有向图里不能出现环否则路径解析会进入死循环。系统需要用引用计数等手段管理链接。3.3 查询文件耗几次 I/O千万别数错这是期末试卷的经典计算题。核心规则是查找路径/usr/ast/mbox时要把“usr”目录文件读入内存找到“ast”这个目录项再把“ast”目录文件读入内存找到“mbox”目录项最后再根据 mbox 的物理地址读文件数据。因此目录检索本身需要“路径深度减一”次磁盘 I/O根目录常驻内存时根目录不用读盘读文件数据再需要一次。很多题目会加大难度假设磁盘块大小 4KB每个目录项占 64B那么一个磁盘块能放4KB / 64B 64个目录项。如果某个目录文件超过 64 个目录项它就会占多个磁盘块检索这个目录时要把所有块都读进来才能确认“找不到”或“找到”。题目一旦带了这个条件I/O 次数就不再等于目录层数而是等于“路径上每个目录文件实际占用的磁盘块数之和”。我把这类题做了个小模板先算每个目录文件有多少个目录项、占几块再逐级累加块数量最后加上读文件数据块的 1 次 I/O。只要分母每个目录项占多少字节和分子目录项个数不抄错这种题基本白给。4. 空闲空间管理四件套空闲表、空闲链表、位示图、成组链接4.1 空闲表法和空闲链表法适合小规模场景空闲表法把磁盘所有空闲区记录在一张表里每条记录包含空闲区起始块号和长度。分配空间时查找满足大小的空闲区首次适应、最佳适应、最差适应分配后修改表项回收时做相邻空闲区的合并。它是连续分配方式的好搭档因为只有连续分配才需要“找一个连续的空闲区”。空闲链表法有两种空闲盘块链以盘块为单位链成一条链和空闲盘区链以连续空闲区为单位链接。后者可以按“首次适配”分配一个盘区但链表遍历效率不高随着空闲块增多查找时间会变长所以更适合中小型系统。4.2 位示图法考试最爱考的计算模块位示图Bitmap的思路非常直观用一串二进制位表示磁盘所有盘块的使用情况每一位对应一个盘块1 表示已分配0 表示空闲。比如一个 1GB 的磁盘盘块大小 4KB共有 262144 个盘块位示图只需要262144 / 8 32768B 32KB非常节省空间。考试计算题的核心是字号、位号和盘块号的换算。设每个字长 n 位字号和位号都从 0 开始编号盘块号也从 0 开始那么盘块号 b 对应的字号i b / n位号j b % n反过来字号 i、位号 j 对应的盘块号b i × n j典型例题系统字长为 32 位盘块号从 0 开始编号请问盘块号 2023 对应字号多少位号多少i 2023 / 32 63 j 2023 % 32 2023 - 63 × 32 7所以是字号 63、位号 7。分配盘块时将位示图对应位从 0 改为 1回收盘块时将对应位从 1 改为 0。这里有个易错点如果题目说“字号从 1 开始位号从 1 开始”那公式就要变成盘块号 (i - 1) × n (j - 1)。做题第一步永远是看下标从 0 还是从 1 开始我曾在“字长 16 位、求盘块号 200 对应字位”这种简单题上因为没注意下标规定白丢过 5 分。4.3 成组链接法大型文件系统为什么选它位示图虽然省空间但整个位示图可能仍然很大而且要在内存中维护或频繁读写磁盘。对于大型文件系统更经典的做法是成组链接法Unix 早期文件系统用的就是它。成组链接法的核心思想是“分而治之”把磁盘空闲块分成若干组比如每组 100 块。系统在内存中维护一个“超级块空闲栈”里面保存当前正在使用的这一组空闲块号。每组的第一块号最小的那块用来记录下一组的空闲块号列表和下一组首块号这样组与组之间通过“每组的首块”串成链。分配空闲盘块时从栈顶弹出一个块号当栈空时说明本组已用完系统把本组第一块中记录的“下一组信息”读入内存栈再继续分配。回收空闲盘块时把块号压入栈顶如果栈已满则把当前栈信息写入回收的盘块建立新组。它比空闲链表法好在哪分配空闲块时不需要遍历整条链只在栈空时才有一次读盘换取新组回收时间样是 O(1) 级别非常适合大容量磁盘。考试里如果问“在成组链接法中分配一个空闲块最多需要几次磁盘 I/O”答案的关键是看栈是否为空——栈非空时 0 次额外 I/O栈空时需要一次磁盘 I/O 把下一组信息读进来如果有更复杂的题目会让块号恰好也是下一组首块那还要多算一次。4.4 四种空闲管理方式选型对拍方式核心结构分配/回收开销适用场景空闲表法连续空闲区表查找表 合并相邻区连续分配的小型系统空闲链表法空闲块链遍历链中小型系统位示图法位图O(1) 按位操作中大型系统、现代文件系统成组链接法组栈 组间链接栈空/栈满时才读盘大型文件系统这也顺带解释了为什么现代文件系统之间差异那么大——空闲空间管理方式直接决定了文件系统在频繁增删文件时的表现。5. 文件共享与保护别再用“快捷方式”一句话带过5.1 硬链接和软链接本质上不是一回事文件共享就是为了让多个用户或进程访问同一个文件而不必各自保存一份副本。Unix 系统里两种共享方式经常被考到。基于索引节点的硬链接两个目录项指向同一个 inodeinode 里有一个链接计数 link count。创建硬链接时计数加 1删除一个目录项时计数减 1只有计数归 0 才真正删除文件数据和 inode。这就是为什么你ln一个文件后在两个路径都能看到相同的内容且任意一个目录项删掉都不影响另一个访问。符号链接软链接它不是一个“文件的另一个名字”而是一个全新的独立文件文件内容是目标文件的路径名。访问软链接时系统会按路径再去解析目标文件。它更接近 Windows 的快捷方式但有一个致命特点如果原文件被删除软链接就成了悬空链接访问会报错而硬链接只要 inode 还在即使原目录项被删内容依然通过其他链接存在。考题常见问法某文件有两个硬链接和一个符号链接删除原文件后哪些链接还能访问文件内容答案是硬链接可以符号链接不行。理解 inode 生命周期就能轻松答对。5.2 口令、加密、访问控制表保护力度决定成本文件保护要解决的是“谁可以对此文件做什么”常见三种手段方式原理优点缺点口令保护访问时输入口令实现简单、开销低口令易泄露、权限粒度粗加密保护文件存储时加密读取需密钥数据泄露也无法直接读取加解密消耗 CPU访问控制表ACL按用户/组/其他分配读、写、执行权限控制粒度细、灵活管理开销较高考试里更喜欢考 ACL 权限表示比如 Linux 的-rwxr-xr--三组权限位分别对应属主、同组用户、其他用户或者 Windows 的文件访问控制表。记住“口令保护防君子不防小人加密保护防泄露不防篡改ACL 主防越权访问”就够了。6. 课后典型题实战把计算题型一次做透6.1 题型一显式链接FAT的磁盘 I/O 次数题目某文件系统采用 FAT 管理文件存储空间FAT 常驻内存。文件 F 按顺序占用了磁盘块 20、30、25、35、40。请问读取文件 F 第 3 个盘块从 1 开始编号的内容需要多少次磁盘 I/O解析FAT 在内存中查 FAT 表不需要读磁盘。题目问的是“读取第 3 个盘块的内容”最终必须把该盘块的数据读入内存所以磁盘 I/O 次数为 1。如果题目改成“FAT 不在内存”那么每查一次 FAT 表项都可能需要把 FAT 所在磁盘块读入内存。因为多个 FAT 表项可能分布在同一个 FAT 块里实际次数需要看 FAT 块的组织方式。很多教材简化处理把“查一次 FAT 表”算作一次磁盘 I/O看到题干的“假设”条件就知道该用哪种约定。6.2 题型二混合索引能支持多大的文件题目某文件系统采用 Unix 混合索引结构磁盘块大小 1KB每个盘块号占 4B直接地址 12 个一级间接、二级间接、三级间接各 1 个。求单个文件最大长度。解析每个索引块可容纳的地址数 1KB / 4B 256 个 直接地址12 × 1KB 12KB 一级间接256 × 1KB 256KB 二级间接256 × 256 × 1KB 64MB 三级间接256 × 256 × 256 × 1KB 16GB 最大文件长度 12KB 256KB 64MB 16GB ≈ 16.06GB这类题最大的坑是单位换算尤其是 MB、GB 的二进制换算按 1024 走。我用一个笨办法先统一把地址项数量和块大小化成“个数 × 大小”的形式最后再合并有效避免少乘一次 1024。6.3 题型三多级目录检索的磁盘 I/O 次数题目某文件系统采用树形目录结构磁盘块大小 4KB每个目录项 128B根目录常驻内存。请检索文件/usr/doc/report.txt已知 usr 目录文件占 1 个磁盘块doc 目录文件占 2 个磁盘块report.txt 占 1 个磁盘块。不考虑文件数据块的读取目录检索本身需要几次磁盘 I/O解析根目录常驻内存查找“usr”这一级不需要读根目录所在磁盘块。之后读 usr 目录文件 1 块再读 doc 目录文件 2 块所以在目录树上定位 report.txt 共需要1 2 3次磁盘 I/O。若题目要求读取文件内容则还需要额外加 1 次读数据块总共 4 次。这道题我当年错得很冤因为根目录常驻内存这个条件我把根目录那次也算进去了多加了 1 次。考试时看到“常驻内存”四个字先画下来。6.4 题型四位示图的分配与回收题目某文件系统位示图每个字长 16 位字号、位号、盘块号均从 0 开始。现在需要为文件分配盘块号 50 对应的盘块请指出应把哪一字的哪一位修改为多少若回收盘块号 80应修改哪一位解析盘块号 50 字号 i 50 / 16 3 位号 j 50 % 16 2 分配时应将位示图第 3 字第 2 位由 0 改为 1。 盘块号 80 字号 i 80 / 16 5 位号 j 80 % 16 0 回收时应将第 5 字第 0 位由 1 改为 0。注意题目如果给的是“第几字”而不是“字号”可能从 1 开始计数那就要把算出来的下标加 1。这类题照着模板走一般很容易拿满分。7. 考前盘点高频考点、易混概念和我的复习节奏7.1 高频考点优先级排序我把文件管理这章在历年期末卷里的出镜率排了个序复习可以按这个顺序投入精力三种物理分配方式的原理、优缺点与现场计算几乎必考混合索引/多级索引的最大文件长度计算高频计算题位示图字号位号与盘块号换算、分配回收操作高频计算题目录检索方式与磁盘 I/O 次数计算中高频成组链接法的分配回收流程中频简答/选择都可能硬链接与软链接的区别inode 与链接计数的关系高频选择题FCB 与索引节点的区别目录结构的演进低频但概念题爱考7.2 易混概念对照考前 10 分钟只看这张表易混概念一句话区分逻辑结构 vs 物理结构逻辑结构是用户眼中文件的组织形式物理结构是文件在磁盘上的存放方式隐式链接 vs 显式链接隐式链接指针藏在数据块里不能随机访问显式链接指针集中存 FAT 表随机访问靠查表FAT 表 vs 索引块FAT 是链接分配的指针表索引块是索引分配中属于每个文件的块号表FCB vs inodeFCB 把元数据和文件名放一起目录项大inode 把两者拆分目录项小、检索快树形目录 vs 无环图目录树形是严格父子关系无环图允许共享但需要引用计数防循环位示图 vs 成组链接位示图用位图记录所有块的使用状态成组链接用栈加组间链接记录空闲块7.3 说说我自己的复习顺序我复习文件管理时用的顺序是先花半小时把教材的流程图和结构图画一遍画出“文件系统层次结构”到“物理分配方式”的关系再集中做课后题中的计算题最后把错题对应的概念抄到一张 A4 纸上考前只看这张纸。实际操作中最有用的一个习惯是把每一个计算题型都总结成“一行公式 一个关键前提”。比如位示图那类题就写“先看下标从 0 还是 1再算字位分配置 1 回收置 0”FAT 题就写“看 FAT 是否常驻内存查表不读盘读数据才读盘”。考试看到题目先套前提条件后动笔正确率能明显提升。另外课后题不要只“看”答案一定要自己闭卷算一遍。我见过不少同学拿着答案看的时候觉得全会真到考场上发现混索引的最大长度算错一位、位示图的字位号搞反都是因为当时没有亲手推演过。章末习题不多值得每道题都动笔写完整过程错题标出来考前再看一遍比考前临时抱佛脚效率高太多。