一、整体概述1.外存管理两大核心任务已用磁盘块管理文件数据如何存放在磁盘上 → 文件物理结构/文件分配方式本节重点。空闲磁盘块管理磁盘空闲空间如何分配与回收后续章节。2. 基础前置知识磁盘块物理块磁盘被划分为大小相等的存储单元统一编号0、1、2……磁盘与内存的数据交换以块为单位。多数系统会让磁盘块大小 内存页面大小简化内外存数据交互。文件逻辑块文件的逻辑地址空间划分为等大的逻辑块文件逻辑地址 逻辑块号 块内地址类比内存「页号页内地址」。示例磁盘块大小1KB1MB文件 1024KB分为 1024个逻辑块块号 0~1023。核心工作操作系统负责将逻辑块号映射为物理块号块内地址无需转换。三大文件分配方式文件在磁盘的存储分为三类连续分配、链接分配、索引分配其中链接分配细分隐式链接、显式链接FAT。二、连续分配顺序分配1.核心思想一个文件占用磁盘上一组连续的物理块逻辑相邻的块物理位置也相邻。2. 目录项FCB记录内容文件目录项中仅需保存两个信息•文件起始物理块号•文件占用块数文件长度3. 地址映射公式物理块号 起始块号 逻辑块号例文件起始块号4访问逻辑块号2 → 物理块号 426。系统同时会校验逻辑块号是否越界防止非法访问。4. 访问特性同时支持 顺序访问 随机直接访问。5. 优缺点✅ 优点1.顺序访问速度最快物理块连续磁头移动距离最短磁盘IO开销小。2. 支持随机访问地址计算简单。❌ 缺点1.文件拓展困难文件后方物理块若被占用只能整体迁移文件开销极大。2. 产生外部磁盘碎片离散空闲小块无法分配给大文件磁盘利用率低。3. 碎片处理只能用「紧凑」需要大量移动数据耗时高。三、链接分配离散分配整体思想文件拆分到离散的物理块通过指针将所有块串联起来无外部碎片文件拓展方便。分为隐式链接、显式链接两类。一隐式链接1.结构规则FCB目录项记录文件起始块号、结束块号。每个物理块内部预留空间存放下一个块的指针最后一块指针标记为结束无后继。指针对用户透明。2. 地址访问流程访问逻辑块号i必须从起始块开始依次读取 0~i-1 号块顺着指针找到第i块。•访问第i块需要执行 i1 次磁盘IO。3. 访问特性仅支持顺序访问不支持随机访问查找效率低。4. 优缺点✅ 优点1.物理块离散分配无外部碎片磁盘利用率高。2.文件拓展简单直接分配空闲块挂在链表尾部修改FCB结束块号即可。❌ 缺点1.不支持随机访问随机查找效率极低。2.每个块需要额外空间存储指针占用存储资源。3.链条断裂风险任意一块损坏后续所有数据都无法访问。补充题目只写「链接分配」未特殊说明时默认指隐式链接。二显式链接FAT 文件分配表1.核心结构整张磁盘仅设置一张全局文件分配表FAT一个磁盘分区对应一张FAT表。FAT表常驻内存开机读入全程不换出表项数量 磁盘总物理块数。表项作用记录每一个物理块的下一块物理块号文件末尾块标记特殊值如-1。FCB仅记录文件起始物理块号。2. 地址访问流程根据文件名找到FCB获取文件起始块号。在内存FAT表中顺着表项查找后继块号全程无需访问磁盘。3. 访问特性同时支持顺序访问 随机访问查询效率远高于隐式链接。4. 优缺点✅ 优点1.无外部碎片文件拓展方便。2.FAT常驻内存查表速度快支持随机访问。❌ 缺点整张FAT表需要占用大量内存空间磁盘分区越大FAT表开销越高。四、索引分配1.核心思想离散分配物理块为每一个文件单独建立一张索引表类比内存页表。索引表记录「逻辑块号 → 物理块号」的映射关系。分类索引块存放索引表的磁盘块。数据块存放文件真实数据的磁盘块。FCB目录项仅记录该文件索引块的物理块号。区分显式链接是整个磁盘一张FAT表索引分配是每个文件一张独立索引表。2. 基础索引单级索引1访问流程从FCB读出索引块号将索引块读入内存。查询索引表直接得到目标逻辑块对应的物理块号。读取目标数据块。2访问特性支持随机访问文件拓展简单新增数据块同步追加索引表项即可。3局限性单个磁盘块容量有限能存放的索引项数量固定。举例磁盘块1KB单个索引项占4B → 单块最多存放 256个索引项仅能对应256个数据块。若文件过大索引表无法存入单个索引块需使用扩展方案索引链接方案、多级索引、混合索引。3. 索引表过大的三种解决方案方案1索引链接方案•规则索引表拆分为多个索引块索引块之间用指针链接。•缺点访问靠后的索引项需要顺序读取前面所有索引块磁盘IO次数多效率低。方案2多级索引多层索引•原理和多级页表一致一级索引块指向二级索引块大文件可继续拓展三级、四级索引。•核心考点1计算文件最大长度前提每一个索引块能存放的索引项数量固定。例单块存256个索引项二级索引最大数据块数 256 × 256三级索引最大数据块数 256 × 256 × 256•核心考点2计算磁盘IO次数若顶级索引块未载入内存K级索引 → 访问数据共需要 K1 次磁盘读操作。•缺点无论文件大小都要走完多级索引流程小文件访问IO次数偏多。方案3混合索引主流方案•原理结合「直接索引 一级间接索引 二级间接索引……」兼顾大小文件效率。a.直接索引索引项直接指向数据块访问最快小文件优先使用。b.一级间接索引索引项指向单层索引块再由索引块指向数据块。c.二级/多级间接索引用于超大文件。•优势a.小文件使用直接索引磁盘IO次数少访问速度快。b.多级间接索引支撑超大文件兼顾容量。•核心考点a.分段计算文件最大长度直接索引区各级间接索引区总和。b.按逻辑块号所在区间判断使用哪类索引计算对应磁盘IO次数。五、四大分配方式综合对比复习重点补充易错点链接分配默认指隐式链接做题需注意题干描述。显式链接一个磁盘分区 一张FAT表FAT常驻内存。索引分配一个文件 一张独立索引表。多级/混合索引两大必考题型文件最大长度计算、访问磁盘IO次数计算。六、小节总结1.外存以磁盘块为基本读写单位文件逻辑地址划分为逻辑块系统完成逻辑块→物理块映射。2.连续分配连续块速度快、有碎片、难扩容。3.链接分配离散块隐式链接块内自带指针仅顺序访问。显式链接全局FAT表常驻内存支持随机访问。4.索引分配每个文件独立索引表支持随机访问大文件可采用链接索引、多级索引、混合索引优化。5.混合索引是现代系统主流完美适配日常「小文件居多、存在超大文件」的场景。