首页/操作系统/第 4 章 文件管理
408 计算机学科专业基础 操作系统 第 4 章

文件管理
从文件名到磁盘块

选择题 2–3 道,近年也出过综合题。计算集中在混合索引的最大文件长度、读某块要访盘几次、位示图换算、FAT 大小;概念集中在三种分配方式对比、硬链接与软链接。

全章回答一个问题:给一个路径名,OS 怎么一步步找到磁盘上的数据块?路径 → 目录 → FCB/inode → 物理块地址 → 数据。沿着这条链,每一环就是一个考点。

5 个考点模块 4 类计算 2 个交互计算器 10 张图
/home/a.txt 目录项:名 + inode 号 inode地址项 0..12 磁盘数据块
00
复习策略

考频地图

★★★★☆ 高频 选择 + 计算

文件管理概念多但都很“实在”。最容易丢分的是计算题里的边界:块号从 0 还是 1 开始、inode 在不在内存、要不要算读目录的那次 I/O——每道题读题时先把这些圈出来。

考点考频题型必须会的动作
FCB / inode、文件打开★★★☆☆选择知道 open 之后用什么访问文件
目录结构、inode 拆分★★★☆☆选择 / 计算算“查目录平均读几个盘块”
硬链接与软链接★★★★☆选择删除原文件后各自的状态、引用计数
连续 / 链接 / 索引分配★★★★★选择 / 计算对比随机访问能力与访盘次数
混合索引最大文件★★★★★计算n = 块大小 ÷ 地址项大小,逐级相加
位示图、成组链接★★★★☆选择 / 计算盘块号与 (字号, 位号) 互换
文件系统布局、VFS、挂载★★☆☆☆选择超级块、inode 区各存什么
全章一条链:路径名 → 逐级查目录 → 找到 FCB(inode) → 根据分配方式找到物理块号 → 读数据。open 的作用是把这条链的前半段只做一次,之后用文件描述符直接定位到内存中的 inode。
01
4.1 · 打基础

文件、FCB 与逻辑结构

★★★☆☆ 中频 选择题

一、文件控制块 FCB

和进程有 PCB 一样,文件有文件控制块 FCB,它是文件存在的标志。FCB 里存着文件名、类型、大小、权限、创建/修改时间、物理位置(数据存在哪些盘块)等。FCB 的有序集合就是文件目录,一个 FCB 就是一个目录项。

二、打开文件:为什么要先 open

如果每次 read 都要根据路径名一级级查目录,磁盘 I/O 会非常多。所以 OS 规定先 open:查一次目录,把 FCB 读进内存,之后的 read/write 直接用返回的文件描述符(打开文件表的索引)。

进程 A 的打开文件表 fd 0 stdin fd 1 stdout fd 3 读写指针 进程 B 的打开文件表 fd 0 stdin fd 4 读写指针 系统打开文件表(全系统一张) a.txt 的表项 FCB / inode 副本 打开计数 = 2 磁盘上的 a.txt 的 FCB open 时读入 每次 open 计数 +1,close 计数 −1 减到 0 才从表中删除(必要时写回 FCB)
图 4-1 两级打开文件表。读写指针、访问权限在进程的表里(各进程各读各的位置);FCB 副本和打开计数在系统表里。
  • open 之后再读写,不再使用文件名,而是用文件描述符;open 不会把文件内容读入内存,只读入 FCB。
  • 两个进程同时打开同一个文件,系统打开文件表中只有一项(计数为 2),但两个进程各有自己的读写指针。
  • close 的作用是删除进程表项、系统表计数减 1,而不是删除文件。

三、文件的逻辑结构:用户眼中的文件长什么样

逻辑结构是从用户角度看文件内部数据如何组织,与它在磁盘上怎么放(物理结构)无关。

类型组织方式查找第 i 条记录适合
无结构(流式)文件一串字节,没有记录概念按字节偏移源程序、可执行文件
顺序文件记录一条接一条;可按关键字排序定长记录可直接算地址;变长只能顺序找批量处理
索引文件为变长记录建一张索引表(每条记录一个表项,表项定长)查索引表即可,快变长记录,需快速随机访问
索引顺序文件记录分组,每组建一个索引项(组内顺序)先查索引找到组,再在组内顺序找大量记录
散列(直接)文件关键字经哈希函数算出地址一次计算不能顺序存取
N 条记录,顺序查找平均要比较 N/2 次。 索引顺序文件:分成 √N 组、每组 √N 条 平均查找次数 = 查索引 √N/2 + 组内 √N/2 = √N 例:N = 10000,顺序文件平均 5000 次;索引顺序文件平均 100 次
02
4.2 · 中高频

目录与文件共享

★★★★☆ 高频 选择 + 计算

一、目录结构的演化

结构做法解决了什么还有什么问题
单级目录全系统一张目录表实现了按名存取不能重名;查找慢;不便共享
两级目录主文件目录 MFD + 每个用户一个用户目录 UFD不同用户可重名,可做权限检查用户不能给自己的文件再分类
树形目录多级目录,路径名唯一确定文件分类清晰;绝对路径 / 相对路径(当前目录)不便于文件共享
无环图目录允许多个目录项指向同一个文件方便共享删除时要维护共享计数

相对路径的好处:从当前目录开始找,少读几层目录,减少磁盘 I/O。

二、把 FCB 拆成“目录项 + inode”

查目录时,只需要比对文件名,用不到 FCB 里的其他几十字节。如果整块 FCB 都放在目录里,一个盘块能装的目录项就很少,查一个目录要读很多块。UNIX 的做法:目录项只留“文件名 + inode 号”,其余信息放到 inode 中。

#
例:目录有 256 个文件,盘块 1 KB,FCB 64 B;拆分后目录项 16 B(文件名 14 B + inode 号 2 B)
结果
1
拆分前:一块放 1024 / 64 = 16 个 FCB,目录占 256 / 16 块
16 块
2
拆分前平均读几块才找到(第 1 块到第 16 块等概率)
(1 + 16) / 2 = 8.5 块
3
拆分后:一块放 1024 / 16 = 64 个目录项,目录占 256 / 64 块
4 块
4
拆分后平均读几块
(1 + 4) / 2 = 2.5 块
5
拆分后找到目录项还要再读 1 次 inode
平均共 3.5 次,比 8.5 少很多

磁盘上的 inode 叫磁盘索引结点;文件被打开后复制到内存的叫内存索引结点,多了引用计数、所在设备号等字段。

三、文件共享:硬链接与软链接

硬链接(基于索引结点) /a/f → inode 7 /b/g → inode 7 inode 7 count = 2 数据块地址… 删除 /a/f:count 减为 1,文件仍在 再删 /b/g:count 减为 0,才真正删除 两个名字地位完全平等,没有“原件” 不能跨文件系统(inode 号只在本分区唯一) 查找快:直接拿到 inode 号 软链接 / 符号链接(基于路径) /a/f → inode 7 /b/s → inode 9 inode 7(count = 1) inode 9:LINK 文件 内容 = "/a/f" 删除 /a/f:inode 7 被删,软链接成为 悬空链接,访问时报“找不到文件” 软链接是一个独立的新文件,有自己的 inode 可以跨文件系统、可以链接目录 访问时要按路径重新逐级查找,较慢
图 4-2 硬链接让两个目录项指向同一个 inode;软链接是一个内容为“路径名”的特殊文件。
  • 建硬链接:inode 的引用计数 +1,不新建 inode。建软链接:新建一个 inode,原文件计数不变。
  • 文件主删除文件后:硬链接用户仍能访问;软链接用户访问失败。
  • “只有文件主才能删除共享文件”是错的:对硬链接,任何一个目录项都可以删,计数为 0 时才真正释放。
03
4.3 · 计算重点

物理结构:文件分配方式

★★★★★ 必考 选择 + 计算

磁盘按块(簇)分配。文件的逻辑块 0、1、2…放到哪些物理块上,FCB 里又怎么记录?三种方式,就是内存管理里“连续分配 / 链表 / 页表”思路在磁盘上的翻版。

① 连续分配 目录项:a.txt起始 4,长度 3 2 3 4 5 6 7 逻辑块 i → 物理块 起始 + i 一次算出,随机访问最快 ② 隐式链接 目录项:b.txt首块 9,末块 25 916 161 125 25-1 每块末尾存“下一块号”;要读第 i 块必须从头顺着指针读 i + 1 块,只能顺序访问 ③ 显式链接(FAT) 目录项:b.txt起始块 9 FAT(整个磁盘一张,常驻内存) 块 125 块 916 块 161 块 25-1 结束 链接指针从数据块中拿出来,集中放在 FAT 表里 FAT 在内存:沿链查找不需访盘 读第 i 块 → 只需 1 次磁盘 I/O,支持随机访问 代价:FAT 占内存,表项数 = 磁盘总块数 ④ 索引分配 目录项:c.txt索引块 19 索引块 19 [0] 9[1] 16[2] 1… 索引块相当于这个文件的“页表”:第 i 项 = 第 i 个逻辑块的物理块号 随机访问:读索引块 + 读数据块;无外部碎片 代价:每个文件至少占一个索引块,小文件浪费
图 4-3 四种物理结构。考试最爱问:哪种支持随机访问(连续、FAT、索引)?哪种有外部碎片(连续)?读第 i 块要几次 I/O?
方式目录项记录随机访问读第 i 块的磁盘 I/O(设 FCB 已在内存)碎片 / 扩展
连续起始块、长度支持,最快1 次外部碎片;文件难以增长
隐式链接首块、末块不支持i + 1 次(i 从 0 起)无外部碎片;指针占空间;一个指针坏了后面全丢
显式链接 FAT起始块支持1 次(FAT 已在内存)无外部碎片;FAT 占内存
索引索引块号支持2 次(索引块 + 数据块);多级索引 k 级为 k + 1 次无外部碎片;索引块开销

FAT 大小怎么算

#
例:磁盘 16 GB,块大小 4 KB
结果
1
磁盘块数 = 16 GB ÷ 4 KB = 2³⁴ ÷ 2¹²
2²² 块
2
FAT 表项要能存一个块号:22 位,按字节取整
3 B
3
FAT 表项数 = 磁盘块数
2²² × 3 B = 12 MB

一、索引块不够用怎么办

一个索引块能放的地址项是有限的:n = 块大小 ÷ 地址项大小。例如 1 KB 块、4 B 地址项 → n = 256,单个索引块只能管 256 KB 的文件。三种扩展:

  • 链接方案:多个索引块链起来(大文件要顺着索引块链找)。
  • 多级索引:一级索引块的每项指向一个二级索引块,二级索引块再指向数据块。两级可管 256 × 256 × 1 KB = 64 MB;但读任何一块数据都要 3 次 I/O。
  • 混合索引(UNIX):小文件用直接地址,大文件才用间接,兼顾两者。

二、混合索引(必考计算)

inode 中的 13 个地址项 i_addr[0] 直接 i_addr[1] 直接 … 共 10 个直接 i_addr[9] 直接 [10] 一次间接 [11] 二次间接 [12] 三次间接 数据块 数据块 索引块 数据块 ×n 索引块 索引块 ×n 数据块 ×n² 索引块 ×n ×n² 数据块 ×n³ 直接:10 块 读一块数据:1 次 I/O 一次间接:n 块 2 次 I/O 二次间接:n² 块,3 次 I/O 三次间接:n³ 块,4 次 I/O n = 块大小 ÷ 地址项大小,例如 1 KB ÷ 4 B = 256
图 4-4 UNIX 混合索引。“读一块数据需要几次 I/O”在 inode 已读入内存的前提下:直接 1 次、一次间接 2 次、二次间接 3 次、三次间接 4 次。
最大文件长度 = (直接项数 + n + n² + n³) × 块大小 n = 块大小 ÷ 地址项大小 例:块 1 KB,地址项 4 B,10 个直接 + 一、二、三次间接各 1 个 n = 256 = (10 + 256 + 65 536 + 16 777 216) × 1 KB ≈ 16 GB(其中直接 10 KB、一次间接 256 KB、二次间接 64 MB、三次间接 16 GB)

典型问法:“文件 inode 已在内存,要读该文件偏移 300 000 B 处的数据,需要几次磁盘 I/O?”→ 先算逻辑块号 ⌊300000 / 1024⌋ = 292;直接区覆盖块 0–9,一次间接覆盖 10–265,292 落在二次间接区 → 需要读一级索引块、二级索引块、数据块,共 3 次。在上面的计算器里输入偏移可以核对。

  • “地址项大小”要先算:若题目只给磁盘总块数,地址项至少要 ⌈log₂ 块数⌉ 位,再向上取整到字节。
  • 算 I/O 次数时看清 inode/FCB 是否已在内存;若不在,每种情况都要 +1。
  • 隐式链接读第 i 块是 i + 1 次(i 从 0 开始),但若题目块号从 1 开始,就是 i 次。
  • FAT 的表项数 = 磁盘块数,而不是文件数。
04
4.4 · 中高频

空闲空间管理

★★★★☆ 高频 选择 + 计算

文件要新分配块时,OS 得知道哪些块是空的。四种记账方法:

方法怎么记分配 / 回收特点
空闲表法每个连续空闲区一项:(起始块号, 块数)同内存动态分区:首次/最佳适应;回收时合并相邻区适合连续分配
空闲链表法空闲盘块链:每个空闲块存下一空闲块号;空闲盘区链:每个空闲区串起来从链头摘 / 挂到链尾盘块链简单但分配多块时要多次操作
位示图法每块一个二进制位,0 空闲 / 1 已分配(或反之)找 0 位、置 1;回收置 0占空间小,可放内存;最常考计算
成组链接法空闲块分成若干组,每组的块号记在前一组的某个块里见下UNIX 使用;适合大型文件系统

一、位示图

位示图是一个二维的位矩阵,每行一个“字”(n 位)。按行优先编号,盘块号 b 与 (字号 i, 位号 j) 一一对应:

编号都从 0 开始: i = ⌊b ÷ n⌋, j = b mod n, b = n × i + j 编号都从 1 开始: i = ⌊(b − 1) ÷ n⌋ + 1, j = (b − 1) mod n + 1, b = n × (i − 1) + j

考试最容易错的就是起点:题目可能“字号从 0、位号从 0、盘块号从 1”混着来。最稳妥的做法:先统一换成“从 0 开始”算,再按题目要求加回去。

二、成组链接法

超级块(内存中) 空闲块数 3 201 ←链接块 202 203 盘块 201 空闲块数 3 301 ←链接块 302 303 盘块 301(最后一组) 空闲块数 2 0 ←结束标记 402 分配:超级块里还有多块 → 直接取一个非链接块;只剩链接块(如 201)时 → 先把 201 的内容读入超级块,再把 201 分配出去。 回收:超级块没满 → 直接记入;满了 → 把超级块内容写入被回收的块,该块成为新的链接块,超级块只记它一个。
图 4-5 成组链接法(为了画得下,每组只画了 3 块;UNIX 实际每组 100 块)。超级块相当于一个“空闲块号栈”。
05
4.5 · 中低频

文件系统布局、保护与 VFS

★★☆☆☆ 低频 选择题

一、一块磁盘上的文件系统长什么样

MBR引导 + 分区表 分区 1 分区 2 分区 3 引导块启动该分区的 OS 超级块块数、块大小、空闲数… 空闲空间管理位示图 / 成组链接 i 结点区所有 inode 根目录 + 其他文件和目录数据区
图 4-6 磁盘与分区上的文件系统布局。内存中还会有:安装(挂载)表、目录缓存、系统打开文件表、进程打开文件表。

格式化分两步:物理(低级)格式化把磁盘划分成扇区,写好扇区头尾的控制信息;逻辑(高级)格式化在分区上建立文件系统,即写入超级块、空闲空间管理结构、根目录等。

二、文件系统的层次

层次(从上到下)做什么
用户调用接口提供 create、open、read 等系统调用
文件目录系统根据路径名查目录,管理 FCB 和打开文件表
存取控制验证检查用户对文件是否有相应权限
逻辑文件系统与文件信息缓冲区把要读写的记录号 / 字节偏移转换成逻辑块号
物理文件系统把逻辑块号转换成物理块号(用分配方式)
辅助分配模块 / 设备管理模块管理空闲块;调用磁盘驱动真正读写

三、虚拟文件系统 VFS 与挂载

用户进程:open / read / write(统一接口) VFS 虚拟文件系统超级块对象 · inode 对象 · 目录项对象 · 文件对象 ext4 FAT32(U 盘) NTFS NFS(网络)
图 4-7 VFS 向上提供统一的系统调用接口,屏蔽下层不同文件系统的差异;每种文件系统要实现 VFS 规定的函数。

挂载(mount):把一个新的文件系统接入现有的目录树,挂到某个目录(挂载点)下。步骤:在 VFS 中注册新文件系统 → 在内存的挂载表中加一项(含超级块信息)→ 把挂载点目录与新文件系统的根目录关联起来。

四、文件保护

方法做法优缺点
口令保护访问时要提供口令,口令存在 FCB / 系统中开销小;口令存在系统里,不够安全
加密保护用密钥对文件内容加密,读时解密保密性强;编码解码耗时
访问控制为每个文件建访问控制表 ACL,记录各用户(组)的权限;UNIX 精简为文件主 / 同组 / 其他 × rwx最常用、灵活

口令和密码都是防止未授权访问;访问控制可以做到“谁能读、谁能写”的细粒度控制。考题常问:“对一个文件的访问,常由哪两者共同限制?”——用户访问权限和文件属性。

06
实战

真题与自测

★★★★☆ 收口 选择 + 计算

一、真题问法

问法 1:“某文件系统采用索引节点,块大小 4 KB,地址项 4 B,inode 中有 10 个直接地址、1 个一次间接、1 个二次间接。单个文件最大长度是多少?”→ n = 1024;(10 + 1024 + 1024²) × 4 KB ≈ 4 GB + 4 MB + 40 KB。

问法 2:“文件采用隐式链接分配,FCB 已在内存,要读第 i 块(从 0 编号)需要几次 I/O?换成连续分配 / 索引分配呢?”→ i + 1 次 / 1 次 / 2 次。

问法 3:“用户删除了某文件,其硬链接 / 软链接还能访问吗?”→ 硬链接能,软链接不能。

问法 4:“位示图字长 32 位,盘块号 100 对应第几字第几位?”→ 从 0 起:100 / 32 = 3 余 4 → 字号 3、位号 4。

问法 5:“在文件被打开后,再读写时使用的是:文件名 / 文件描述符 / FCB 地址 / 目录项?”→ 文件描述符。

二、折叠自测

1. 为什么要“打开”文件?打开时把什么读进内存?

避免每次读写都按路径查目录。打开时根据路径找到 FCB(inode),复制到内存的系统打开文件表,并在进程打开文件表中建一项,返回文件描述符。文件内容不会因为 open 而读入。

2. 哪种物理结构不支持随机访问?

隐式链接分配。要访问第 i 块必须从第一块开始顺着指针读。连续、FAT 显式链接、索引都支持随机访问。

3. 连续分配有什么问题?

会产生外部碎片;文件长度难以动态增加(后面的块可能被占用);创建时就需要知道文件大小。

4. 块 2 KB、地址项 4 B、只有一个一次间接索引块,文件最大多大?

n = 2048 / 4 = 512,最大文件 512 × 2 KB = 1 MB。

5. 软链接文件被删除,原文件受影响吗?原文件被删除,软链接怎样?

删除软链接本身不影响原文件。原文件被删除后,软链接仍存在,但成为悬空链接,访问失败。

6. 位示图字号、位号都从 1 开始,字长 16 位。盘块号 b(从 1 开始)= 50 对应哪一位?

i = ⌊49 / 16⌋ + 1 = 4,j = 49 mod 16 + 1 = 2,即第 4 字第 2 位。

7. 把 FCB 拆成目录项和 inode 的好处是什么?

目录项变小,一个盘块能放更多目录项,目录占的块数减少,查目录时读盘次数减少,提高检索速度。

8. FAT 表的表项数由什么决定?

由磁盘(分区)的物理块数决定,每块一项,与文件个数无关。

三、考前速览

五句话

FCB 是文件存在的标志,FCB 集合就是目录。
open 后用文件描述符,不再用文件名。
n = 块大小 ÷ 地址项大小,逐级是 n、n²、n³。
隐式链接 i + 1、连续 1、索引 2。
硬链接加计数,软链接新建文件。

五个易错

① 位示图编号起点要统一。
② inode 是否在内存决定 I/O 次数是否 +1。
③ 只有连续分配有外部碎片。
④ FAT 项数 = 磁盘块数。
⑤ 两个进程打开同一文件,读写指针各自独立。