1. 文件管理这章在卷面上的真实位置以及它为什么最容易看会做错操作系统在统考里总共35分文件管理这一章通常稳定吃下8到12分个别年份能冲到15分左右。它的特点很鲜明概念不难代码几乎没有但是计算题和边界条件特别多属于那种第一遍看觉得就这第二遍做题开始怀疑人生的章节。我在前面几轮复习里真正反复栽跟头的不是进程同步那堆信号量而是这里的一堆第几块几次I/O多少字节。所以这篇东西不打算把王道书从头抄一遍那种笔记你看目录就够了。我想做的是把这一章里真正会考、真正容易错、以及错在哪的地方拆开讲。你看完应该能做到三件事拿到一道文件分配的计算题知道从哪下手看到混合索引最大文件长度不再套错公式对位示图和成组链接法这种看起来抽象的东西能自己在纸上推一遍。先说清楚这一章在整本书里的位置关系。文件管理是承上启下的一章往上它接着内存管理因为打开文件表本质是内存里的数据结构往下它连着I/O管理因为磁盘调度、磁盘访问时间在第5章还会再出现一次。所以你在这一章学到的索引节点目录项磁盘块后面都会被反复调用。反过来如果你这一章糊弄过去第5章的磁盘调度和文件系统实现部分会跟着一起崩。1.1 分值分布和出题偏好从历年真题看这一章的出题方式大概分三类。第一类是概念选择题考目录结构、文件逻辑结构、共享方式的定义属于送分但要背准。第二类是计算题集中在索引分配的最大文件长度、隐式链接的I/O次数、位示图换算、成组链接法的分配回收这类题一旦出就是大题里的一个问或者一道独立小题。第三类是综合分析比如结合打开文件表问进程间共享文件的语义或者结合磁盘调度算寻道时间。我把这三类的备考优先级排个序计算题 概念辨析 综合分析。原因是计算题有固定套路练熟了就是稳拿分概念辨析容易在两个近义词之间纠结综合分析一般分值高但覆盖面广靠平时积累。1.2 看得懂却做不对的三个根源第一个根源是把逻辑结构和物理结构混成一件事。用户眼里的文件是一串连续的字节磁盘上的文件可能被切得七零八落。题目问访问第i个逻辑块和访问第i个物理块是两个完全不同的问题前者是逻辑地址后者才涉及磁盘I/O。很多人第一遍读题就把这两个搞混了。第二个根源是I/O次数算错多算或少算。隐式链接读第i块要i次磁盘访问这个大家都知道但题目往往会加一句目录项已经在内存中索引块已调入内存这时候次数就要减。考的就是你知不知道哪些数据结构常驻内存。第三个根源是忽略了参数的默认约定。位示图的字号位号从0开始还是从1开始盘块号从0开始还是从1开始如果题目没写你得按教材约定来写错了整道题全错。这种亏我吃过不止一次。提示做这一章的计算题养成先在草稿纸上写下盘块号起始值、字号起始值、字长、地址项大小这几个参数的习惯再动笔算。参数没列清楚就开算十有八九要返工。2. 逻辑结构与物理分配用户看到的一串数字和磁盘上真实的排布先立一个基本框架。文件在用户眼里有它的组织形式这叫逻辑结构文件在磁盘上实际怎么摆放这叫物理结构也叫文件的分配方式。这两套账是分开记的考试也分开考。很多人失分就是因为答索引文件的时候答成了索引分配一字之差答的是两个层面的东西。2.1 逻辑结构的几种组织方式和它们的适用场景逻辑结构分两大类无结构文件和有结构文件。无结构文件就是流式文件一串字节流没有内部划分比如我们平时写的txt、C源码文件。它的优点是没有额外结构开销查找只能靠遍历或者外部索引。有结构文件是记录式文件由一条条记录组成每条记录有若干数据项。有结构文件再往下分三种组织顺序文件记录按某种顺序排列可以是定长记录也可以是变长记录。定长记录的顺序文件支持随机访问因为第i条记录的偏移量能直接算出来偏移 i × 记录长度。变长记录就只能从头扫。索引文件给记录建一张索引表表项记录记录长度 记录起始地址。有索引表就能随机访问代价是多维护一张表而且索引表本身要占空间。索引顺序文件把记录分组每组建一个索引项组内还是顺序查找。这是顺序和索引的折中检索效率比纯顺序高索引表又比纯索引小。考试常考的是顺序文件的检索效率分析。假定定长记录顺序文件有N条记录平均检索长度是N/2索引顺序文件把N条分成N^0.5组组内平均检索N^0.5/2组间索引检索...这里教材给的结论是平均检索长度约等于根号N。你记住这个数量级差异就行不用背推导。2.2 连续、隐式链接、显式链接、索引四种分配的代价对比这是本章的计算核心。我用一张表把四种方式的特征摆出来然后逐个说坑。分配方式是否支持随机访问是否有外部碎片文件能否动态增长典型代表连续分配支持有困难早期系统隐式链接不支持无容易早期链式文件显式链接FAT支持无容易FAT文件系统索引分配支持无容易UNIX类文件系统连续分配读第i块是最快的物理块号 起始块号 i一次I/O搞定。但它的致命伤是外部碎片和扩展困难。文件要变长后面那块可能已经被别的文件占了只能整体搬家。这个搬家的代价在题目里经常体现为需要移动多少块。隐式链接的目录项只存首块号和尾块号每一块末尾留出几个字节放指向下一块的指针。它的好处是没有碎片、能随时扩展坏处是只能顺序访问而且指针占了数据块的空间导致实际可用容量变小。这个指针占空间是常考的点比如每块大小1KB指针占4B问有效数据是多少答案是1020B不是1024B。显式链接把所有的指针集中到一张表里这张表就是FAT文件分配表。FAT整张开机就调入内存所以查链不用访问磁盘这是它相对隐式链接最大的优势。目录项里存的是起始块号顺着FAT查就能找到整条链。FAT的表项数等于磁盘块总数这个数字题目会给。索引分配给每个文件单独建一张索引表索引表放在一个专门的索引块里目录项存索引块地址。访问第i块先读索引块拿到第i块的物理地址再读数据块。2.3 隐式链接的I/O次数一道小题的完整推导来看一道典型题。某文件系统采用隐式链接分配磁盘块大小1KB每个块的末尾用4字节存下一块指针。目录项已在内存中问读取文件第5块需要多少次磁盘I/O。推导过程目录项在内存里面有首块地址所以访问第1块只需1次I/O读到第1块的同时获得第2块的地址访问第2块再1次I/O获得第3块地址……依此类推读到第5块总共5次I/O。如果题目改成目录项不在内存那就先要读目录1次再读5个块总共6次。如果改问读取第5块和第6块这种连续访问后面那块可以在读第5块时顺便拿到地址只需要接着读还是6次5次找链1次读第6块本身注意第6块的地址在读第5块时已经拿到。这些细节每年都有变体核心逻辑就是隐式链接每走一步都要一次磁盘访问因为下一块的地址藏在当前块里。如果换成显式链接FAT在内存读第5块就是查内存里的FAT链找到物理地址再1次磁盘I/O读数据块总共1次。这个对比几乎每年都以某种形式出现你一定要把FAT在内存这个前提刻进脑子里。3. 混合索引的最大文件长度参数一变答案全变索引分配一般不会单独考它总是以混合索引的形式出现在大题里问这个文件系统支持的最大文件长度是多少。这是本章性价比最高的一个考点因为公式固定只要参数算对分数稳拿。3.1 UNIX混合索引的地址项布局UNIX类的索引节点inode里有一组地址项通常是这样分配的10个直接地址项1个一级间接1个二级间接1个三级间接。含义是直接地址项直接指向一个数据块。一级间接项指向一个索引块这个索引块里全是指向数据块的地址。二级间接项指向一个索引块这个索引块里指向的又是一批索引块。三级间接项再往下套一层。理解了间接就是多一层跳转这件事剩下的全是乘法。3.2 从4KB块、4B地址项推最大文件长度设磁盘块大小4KB4096B每个地址项占4B。那么一个索引块能装多少个地址4096 ÷ 4 1024个。于是直接部分10 × 4KB 40KB一级间接1024 × 4KB 4MB二级间接1024 × 1024 × 4KB 4GB三级间接1024 × 1024 × 1024 × 4KB 4TB最大文件长度 40KB 4MB 4GB 4TB。考试写这个表达式一般就给分如果要具体数字注意GB/TB是按1024还是1000算按题目要求来。注意算索引块能装多少个地址时用块大小除以地址项大小得到的是地址项个数也就是能指向多少个数据块。别把它和字节数搞混。3.3 参数一变结果全变常见变体对照考试不会永远给你4KB和4B常见变体有这些磁盘块大小地址项大小每索引块地址数一级间接二级间接三级间接4KB4B10244MB4GB4TB1KB4B256256KB64MB16GB4KB8B5122MB1GB512GB这类表建议你自己动手算一遍而不是背。因为变体还可能改直接地址项个数比如把10个改成12个或者把间接级数改成只有两级。你只要抓住每索引块地址数 块大小 ÷ 地址项大小这一条主线其他都是分支。还有一个容易被忽略的点如果文件采用多级索引访问一个数据块可能需要多次读索引块。比如访问三级间接覆盖的数据块要先读三级索引块、二级索引块、一级索引块再读数据块总共4次I/O假设都不在内存。这个I/O次数也经常和最大文件长度一起考。4. FCB、索引节点和目录一次open背后内存里多了什么目录这一节概念多但都是死记真正需要理解的是文件控制块、索引节点、目录项之间的关系以及文件打开后内存里的数据结构变化。4.1 FCB里装了什么索引节点为什么要把文件名拆出去FCB文件控制块是操作系统管理文件用的数据结构里面装着文件的元信息文件名、物理位置、逻辑结构、物理结构、存取控制信息、使用信息等等。目录本质上是FCB的集合查找文件就是逐个比较FCB里的文件名。问题在于如果用FCB直接当目录项那每次查目录都要把整个FCB调入内存FCB太大检索效率低。于是UNIX把FCB拆成两部分文件名单独拿出来做目录项文件的其他描述信息组成索引节点inode目录项里只留文件名加一个inode号。这样查目录时目录项小一个磁盘块能装很多个目录项检索快找到之后再根据inode号去读inode。这是典型的用一层间接换检索效率的设计。inode又分磁盘inode和内存inode。磁盘inode是持久化的开机不动内存inode是文件被打开时复制到内存的多了引用计数、状态位这些运行时信息。这个区分在多用户共享文件时会考。4.2 open之后内存里多了什么两级打开文件表这是我认为本章最值得反复看的一节因为它把文件和进程的关系讲清楚了。一次open调用的大致流程是进程按路径名检索目录跨过每级目录找到目标目录项拿到inode然后系统把inode调入内存如果没在在系统打开文件表里建立一条表项进程自己再维护一张进程打开文件表表项指向系统表里的那一条返回给用户一个文件描述符fd这个fd就是进程打开文件表的下标。所以是两级结构进程打开文件表每个进程一张存fd到系统表项的指针 系统打开文件表全系统一张存文件inode、读写位置、引用计数等。这样设计的好处多个进程打开同一个文件时系统表里只有一条记录各进程的表项指向它共享读写位置等信息。引用计数记录有几个进程在用它最后一个close时才真正释放系统表项。考点来了如果父进程fork之后子进程继承fd父子进程共享系统打开文件表项那么读写位置是共享的一个进程读了一段另一个进程接着读。而如果两个进程各自独立open同一个文件则各有一条系统表项读写位置互不影响。这个差别几乎每年都考。4.3 硬链接和软链接在目录项层面的差别文件共享实现有两种方式硬链接多个目录项指向同一个inodeinode里有个链接计数比如2表示有两个目录项指向它。删除其中一个目录项计数减一减到0才真正删除文件。硬链接不能跨文件系统因为inode号只在单个文件系统内唯一。软链接符号链接新建一个文件内容是目标文件的路径名。它有自己的inode是一个独立的文件。删除原文件软链接还在但指向失效悬空链接。软链接可以跨文件系统。考试问法通常是访问软链接文件需要几次读磁盘硬链接文件被删除后其他链接还能不能用。记住软链接要多一次读它自己内容路径名的过程硬链接直接指向同一inode。5. 空闲空间管理位示图和成组链接法是两个必考计算点磁盘上空闲块怎么记有好几种方法。空闲表法和空闲链表法属于理论介绍位示图和成组链接法是实操和中高频考点。我把重点放在后两个。5.1 位示图换算从盘块号到字号位号的推演位示图就是用一个二进制位对应一个磁盘块0表示空闲1表示占用也有的反过来看题目。所有位排成一个矩阵每行n位叫一个字字有字号位有位号。核心公式盘块号、字号、位号都从0开始字长n位已知盘块号b求字号 b ÷ n整除位号 b mod n已知字号i、位号j求盘块号 i × n j如果题目规定从1开始那就要在结果上加减1。这是最大的坑。比如盘块号从1开始字长16问盘块100对应哪个字的哪一位字号 (100-1) ÷ 16 6从0开始位号 (100-1) mod 16 3从0开始。如果你直接用100代入就会得到字号6、位号4错一位。我建议做这类题时在草稿纸上写一个小的对应关系验证一下比如把第1个盘块代进去看结果是不是第一个字第一位对了再算大的。另外位示图本身占多少磁盘空间也常考位示图需要的字数 总盘块数 ÷ 字长再乘以每个字的字节数。比如磁盘有1024个块字长32位4字节那么需要1024÷3232个字占32×4128字节。5.2 成组链接法的分配与回收逐步拆解成组链接法看着最吓人其实就一个核心思想把空闲块分成若干组每组的信息存在一个空闲块里用一个栈把这些信息串起来。具体来说系统超级块里有一个空闲块号栈假设能放100个盘块号。栈里存的是第一组空闲块号。栈中特殊的一点是会留一个位置存下一组的盘块号同时记录本组还有多少个空闲块。分配过程从栈顶取一个空闲块号分配给文件。正常情况下栈里还有多个元素直接取栈顶下移。如果栈里只剩最后一个元素也就是那个指向下一组的块号就先把这个块读入内存把里面的信息下一组的盘块号和数量压入栈然后再分配这个块。回收过程把释放的空闲块号压入栈顶。如果栈没满直接压入。如果栈已满就把栈中现有的100个空闲块号全部写入这个新回收的块然后清空栈把这个新回收的块号压入栈此时栈里只有它一个它作为新一组的头里面存着原栈的全部内容。这里最容易搞混的是分配时栈空之前要先加载下一组而回收时栈满要先把当前栈内容写到一个块里。两个方向的特殊处理是对称的抓住栈满/栈空是边界条件这个点画个图在草稿纸上模拟两三次就懂了。提示成组链接法一定要自己动手画一个小例子比如总共30个空闲块每组10个然后模拟分配5次、回收5次看栈怎么变。光看书记不住。5.3 空闲表法和空闲链表的适用边界空闲表法用一张表记录每个连续空闲区起始块号 块数分配时可以用首次适应、最佳适应这些策略跟内存的动态分区分配几乎一样所以它的问题是外部碎片和表长不定。空闲链表法分两种空闲盘块链一个块一个节点和空闲盘区链一个连续区一个节点。盘块链分配回收简单但链长盘区链效率高但管理复杂。这三种考得少但选择题会考定义和适用场景。比如问哪种方法适合文件频繁创建删除的场景答案是成组链接法或位示图因为不产生碎片且管理开销稳定。6. 磁盘组织与调度从柱面地址到寻道时间的完整链条最后一节把磁盘这块和文件管理连起来讲。因为文件的物理块最终要落到具体的柱面、盘面、扇区上磁盘调度算法直接决定了多次磁盘访问的总时间。6.1 磁盘物理地址的构成与访问时间的三个部分磁盘的物理地址通常表示为柱面号盘面号扇区号。为什么要这么排因为同一柱面的不同盘面可以并行读写磁头一起动所以把相邻的数据放在同一柱面的不同盘面上读取时不用移动磁臂效率高。一次磁盘读写的总时间 寻道时间 旋转延迟 传输时间。寻道时间磁臂移动到目标柱面的时间。这个是调度算法要优化的主要对象。旋转延迟目标扇区转到磁头下方的时间平均等于半圈时间 1 ÷ (2 × 转速)。转速如果是r转/秒那就是1/(2r)秒。传输时间读写数据的时间 要传输的字节数 ÷ 传输速率。计算题一般是给转速比如6000转/分、每磁道字节数、请求序列和当前磁头位置让你算总时间。转速单位要换算6000转/分 100转/秒平均旋转延迟就是1/(2×100)5ms。6.2 六种调度算法的答题套路与寻道距离计算磁盘调度算法有六个算法思路特点FCFS按请求顺序公平但性能差SSTF优先最近可能饥饿SCAN电梯来回扫到最边缘才反向C-SCAN单向扫回头不服务请求处理更均匀LOOK到最远请求就反向SCAN的改进C-LOOK单向扫到最远请求回头C-SCAN的改进做这类题标准步骤是先按当前磁头位置和移动方向画一条数轴标出所有请求柱面号然后按算法规则排出访问顺序最后相邻两点距离相加得到总寻道距离。SCAN和LOOK的差别经常考SCAN要一直移到磁盘最边缘才开始反向即使边缘外没有请求LOOK则在最远的请求处就反向。如果题目给了最大柱面号就用SCAN如果只给了一串请求多半是LOOK。这一点不看清楚就会多算一段距离。举个简化例子说明思路当前磁头在100向磁道号增大方向移动请求序列为55、58、39、18、90、160、150、38、184。如果是SCAN且最大柱面为199要走到199再反向路径是100→150→160→184→199→90→58→55→39→38→18如果是LOOK到184就反向路径是100→150→160→184→90→58→55→39→38→18。后者少走了184到199那段来回。总距离就是把相邻两点差值的绝对值加起来。C-SCAN还有个小坑它回来的时候不服务所以从最大端返回最小端的那段距离只算一次直接跳回起点方向再从头扫。有的题目会把这个空跑的距离算进去有的不算一定要看题目对寻道的定义。讲完了这些我个人最大的体会是文件管理的计算题没有一道是难在思想上的全是难在细节和参数约定上。我复习到第三轮才慢慢形成一个习惯就是每做一道题先在草稿纸上列出题目给的所有参数和默认约定尤其是盘块号起始值、数据结构是否在内存这些列清楚了再动笔。这个习惯帮我省下的分比多背十个概念还多。另外成组链接法和混合索引这两个点建议你不要只看书一定要自己拿纸模拟一遍分配回收和索引查找的全过程手过一遍和眼过一遍是两个完全不同的掌握程度。