【操作系统】文件管理大题总结

【操作系统】文件管理大题总结

前置知识

操作系统中的存储单位转换

b，B, KB, MB等的单位转换

• b : $bit$, 比特，位，表示二进制的0或1
• B：$Byte$, 字节，$1Byte=8bit$
• KB: 1K的Byte，千字节，$1KB=1024Byte=1024\ast 8bit$
• MB : $1Million$的Byte, 兆字节， $1MB=1024KB=1024\ast 1024Byte=1024\ast 1024\ast 8bit$
• GB : $1GB=1024MB$
• TB：$1TB=1024GB$
• 1KB = $2^{10}B$，1MB=$2^{20}B$,1G=$2^{30}B，1T=2^{40}B$

字节、字、位、比特之间的关系：

• 1位=1比特；1字=2字节；1字节=8位；1字=16位。
• 在16位的系统中:1字 = 2字节（byte）= 16（bit）
  在32位的系统中:1字 = 4字节（byte）= 32（bit）
  在64位的系统中:1字 = 8字节（byte）= 64（bit）

1、目录管理中的典型问题分析

基础例题：

【例1】在某个文件系统中，每个盘块为 512 个字节，文件控制块占 64 个字节，其中文件名占8个字节。如果索引结点编号占 2个字节，对一个存放在磁盘上的、 256 个目录项的目录，试比较引入索引结点前后，为找到其中一个文件的 FCB, 平均启动磁盘的次数。

答：在引入索结点前，每个目录项中存放的是对应文件的FCB，故256个目录共需要占用$256\ast 64/512=2^{14}/2^9=2^5=32$个盘块，因此在该目录检索到一个文件，平均启动次数为$(1+32)/2=16.5$次。
在引入索引结点之后，每个目录项只需存放文件名和索引结点编号，因此256个目录项的目录共需要占用$256\ast (8+2)/512=5$个盘块。因此找到匹配的目录项平均需要启动$(1+5)/2=3$次磁盘；而得到索引结点编号后，还需要启动磁盘将对应文件的索引结点读入内存，故平均需要启动4次磁盘。

往年真题

【例2】某文件系统的一个文件控制块（FCB）占 64 个字节，盘块大小为 2K 字节，则每个盘块可存放的 FCB 数目是多少？如果一个文件目录中有 384 个 FCB，则查找一个文件平均需要启动磁盘多少次？引入索引结点（i 结点）后，如果文件名占 14 个字节，索引结点占 2 个字节，大小为 2K 字节的盘块可存放的目录项数目是多少？为找到一个文件，平均需要启动磁盘多少次？（10 分）（2021-848真题）

(1)已知FCB占64B，盘块大小2KB，则每个盘块可存放$2KB/64B=2^{11}/2^6=2^5=32$个FCB;
(2)如果一个文件目录中有384个FCB，此时未引入索引结点，每个个目录项中存放的是对应文件的FCB,故384个FCB共需要占用$384\ast 64B/2KB=384\ast 2^6/2^{11}=384/32=12$个盘块，因此找到匹配的目录项平均需要启动$(12+1)/2=6.5$次磁盘;
(3)在引入索引结点之后每个目录项只需存放文件名和索引结点编号，故大小为2KB的盘块可以存放$2KB/(14+2)=2^{11}/2^4=2^7=128$个目录项，由于此时只占用一个盘块因此需要找到匹配的目录项需要启动$(1+1)/2=1$次磁盘，将索引结点编号读入内存还需要一次读取，平均需要启动$2$次磁盘。

2、外存的组织方式中的典型问题分析

基础例题

【例1】假定盘块的大小为 1K, 硬盘的大小为 500 MB, 采用显式链接分配方式时，FAT 需占用多少存储空间？如果文件 占用硬盘的第11、12、16、14四个盘块，试画出文件中各盘块间的链接情况及 FAT 的情况。

由题解可知，该硬盘共有$500MB/1KB=500\ast 1024KB/1KB=500\ast 1024=500K$个盘块,故 FAT 中共有 500 K个表项：如果盘块从1开始编号，为了能保存最大的盘块号500K，则该表项最少需要19位，将它拓展为半个字节的整数倍后，可知每个 FAT 表项需20位，即2.5个字节。因此， FAT 需占用的空间大小为$2.5\ast 500KB=1250KB$。
文件中各个盘块间的链接关系情况 FAT 的情况如图所示；

【例2】请分别解释在连续分配方式、隐式链接分配方式、显式链接分配方式和索引分配方式中如何将文件的字节偏移量 3500 转换为物理块号和块内位移量（设盘块大小为1KB ，盘块号需占4个字节）。

首先，将字节偏移量转换成逻辑块号个块内位移量：
$3500/1024$得商为3，余数为428，即逻辑块号为3，块内位移量428。
（1）在连续分配方式中，可从相应文件的FCB中的到分配给该文件的起始地址如$a_0$,故字节偏移量3500对应的物理盘块号为$a_0+3$，块内位移量为428。
（2）在隐式链接分配方式中，由于每个盘块需留出 个字节（如最后的 4个字节）来存放分配给文件的下一个盘块的块号，因此字节偏移量 3500 的逻辑块号为 $3500/1020$ 的商 3，块内位移量为余数 440。
从相应文件的FCB中可获得分配给该文件的首个盘块的块号，如$b_0$，然后可通过读第$b_0$块，获得分配给文件的第1个盘块的块号，如$b_1$，再从$b_1$块得到第2块的块号，如$b_2$，再从$b_2$块得到第3块的块号，如$b_3$，如此，便可得到字节偏移量 3500应的物理块号 $b_3$, 而块内位移量则为 440。
（3）在显示链接方式中，可从文件的FCB中得到分配给该文件的首个盘块的块号如$c_0$,同（2）便可得到字节偏移量 3500应的物理块号 $c_3$, 而块内位移量则为 428。
（4）在索引分配方式中，可从文件的 FCB 中得到索引表的地址。从索引表的第项（距离索引表首字节 12 字节的位置）可获得字节偏移量}500 对应的物理块号，而块内位移量为 428。

【例3】存放在某个磁盘上的文件系统，采用混合索引分配方式，其 FCB 中共有 13个地址项，第 0~9 个地址项为直接地址，第 10 个地址项为一次间接地址，第 11 个地址项为二次间接地址，第 12 个地址项为三次间接地址。如果每个盘块的大小为 512 字节，若盘块号需要用 个字节来描述，而每个盘块最多存放 170 个盘块地址：
(1) 该文件系统允许文件的最大长度是多少？
(2) 将文件的字节偏移量 5000，15000，150000 转换为物理块号和块内偏移量。
(3) 假设某个文件的 FCB 已在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？

（1）该文件系统中一个文件的最大长度可达：$10+170+170\ast 170+170\ast 170\ast 170=4942080块=4942080\ast 512=2471040K$字节
（2）①5000/512 得到商为 9, 余数为 392, 即字节偏移量 5000 对应的逻辑块号为 9,块内偏移量为 392 。由于$9<10$, 故可直接从该文件的 FCB 的第 个地址项处得到物理盘块号，块内偏移量为 392。
②15000/512 得到商为 29, 余数为 152, 即字节偏移量 1_5000 对应的逻辑块号为 29,内偏移量为 152 。由于$10\le 29<10+170$，而$29-10=19$，故可从FCB的第10个地址项，即一次间址中得到一次间址块的地址；读入一次间址块并从它的第19项）中获得对应的物理盘块号，块内偏移
③150000/512 得到商为 292, 余数为 496, 即字节偏移量 150000 对应的逻辑块号为 292,块内偏移量为 496 。由于$10+170\le 292<10+170+170\ast 170$ ，而$292-(10+170)=112$，$112/170$ 得到商为 0, 余数为 112, 故可从 FCB的第11个地址项，即二次间址中获得二次间址块的地址，读入二次间址块，并从它的第0项中获得一个一次间址块的地址
，再读入该一次间址并从它的第112项中获得对应的物理盘块号，块内位移量为496。
（3) 由于文件的 FCB 已在内存，为了访问文件中某个位置的内容，最少需要1次访问磁盘（即可通过直接地址直接读文件盘块），最多需要 次访问磁盘（第1次是读三次间址块，2次是读二次间址块，第3次是读一次间址块，第4次是读文件盘块）。

【例4】文件系统，采用混合索引分配方式，其 FCB 中共有 13 个地址项，每个盘块的大小为 512 字节，请回答下列问题：
(1) 如果每个盘块号只需要用2个字节来描述，则该系统需要设置几次间址项？
(2) 如果每个盘块号需要用3个字节来描述，并允许每个盘块中存放 170 个盘块地址，而且，系统采用 10 个直接地址项、1个一次间址项、1个二次间址项和 1个三次间址项，则对某个长度为 18 000 001 字节的文件，它需占用多少个盘块？

(1) 如果盘块地址只需用 个字节来描述，则该磁盘系统中盘块的数目将小于等于泸，即 65 536 块，故文件的大小也不会超过 65 536 块；而每个盘块中可存放 256 个盘块号，因此系统最多只要用到2次间址。实际上，使用一个一次间址项和一个二次间址项后，允许文件的最大长度已达 $11+256+256\ast 256$ 块，已经超出了该磁盘系统中实际的盘块数目。
(2) 根据题意，该文件的最后一个字节的字节偏移量为 18 000 000, $18000000/512$
的商为 35 156, 因此该文件的最后一块的逻辑块号为 35 156。
由于$10+170+170\ast 170\le 35156<10+170+170\ast 170\ast 170\ast 170\ast 170$
故该文件不仅需要使用十个直接地址项，还需要使用一次、二次及三次间址项。又因为$35156-(10+170+170\ast 170)=6076$ ，$6076/(170\ast 170)$得到商为 0, 余数为 6076, 得知该文件在三次间址时还需要1个二次间址块；而余数 $6076/170$ 得到商为 35 、余数为 126, 可知该文件在三次间址时还需要 36 个一次间址块。因此该文件需要：三次间址块 = 1 个,二次间址块： $1+1=2个$，一次间址块： $36+170+1=207$个，数据块： $(35\ast 170+127)+170\ast 170+170+10=35157$，故共需要 35 367 个物理盘块。

王道课后题

【例5】有一个文件系统如图A所示，图中的方框表示目录，圆圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设FCB,普通文件组织成索引文件。目录表指示下一级文件名及其磁盘地址（各占2B,共4B）。下一级文件是目录文件时，指示其第一个磁盘块地址。下级文件是普通文件时，指示其FCB的磁盘地址。每个目录的文件磁盘块的最后4B供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512B,与普通文件的一页等长。

普通文件的FCB组织如图B所示。其中，每个磁盘地址占2B,该文件前10页的地址。第11个地址指示一级索引表地址，一级索引表中的每个磁盘地址指示一个文件页地址；第12个地址指示二级索引表地址，二级索引表中的每个地址指示一个一级索引表地址；第13个地址指示三级索引表地址，三级索引表中的每个地址指示一个二级索引表地址。请问：
（1） 一个普通文件最多可有多少个文件页？
（2） 若要读文件J中的某一页，最多启动磁盘多少次？
（3） 若要读文件W中的某一页，最少启动磁盘多少次？
（4） 根据（3）,为最大限度地减少启动磁盘的次数，可采用什么方法？此时，磁盘最多启动多少次？

（1）一个普通文件最多可有的文件页数$10+256+256\ast 256+256\ast 256\ast 256=16843018$。
（2）由图可知，目录A和D中的目录项都只有两个，因此这两个目录文件都只占用一个物理块。要读文件J中的某一页，要从根目录中读到目录文件A的磁盘地址，再从目录文件A中读入目录文件D的磁盘地址，再从目录文件D中找出文件J的FCB读入内存（已访问磁盘3次），在最坏情况下，该访问页存放在三级索引下，这时需要一级地址读三级索引块，才能得到文件J的地址（已访问磁盘6次），最后读入文件J的相应页，共访问磁盘7次。
（3）同理（2）从根目录访问到C->D->I>U->W，此时已将W的FCB读入内存，在最好情况下，要访问的页在FCB的前10个直接块中，按照直接块指示的地址读文件W的相应页面，因此共访问磁盘6次。
（4）①可将W挂在根目录的最前面的目录项中，此时可直接在根目录中找到W的FCB，最差情况下，需要的W文件的那个页挂在FCB的三级索引下，因此读3个索引块需要访问磁盘3次（已访问磁盘4次）得到该页的物理地址，再去读这个页即可（己访问磁盘5次）。此时，磁盘最多启动5次。②也可设置U为当前目录，也可直接访问W的FCB，同①一样的效果。

【例6】.某个文件系统中，外存为硬盘。物理块大小为512B,有文件A包含598条记录，每条记录占255B,每个物理块放2条记录。文件A所在的目录如下图所示。文件目录采用多级树形目录结构：由根目录结点、作为目录文件的中间结点和作为信息文件的树叶组成，每个目录项占127B,每个物理块放4个目录项，根目录的第一块常驻内存。试问：

（1）若文件的物理结构采用链式存储方式，链指针地址占2B,则要将文件A读入内存,至少需要存取几次硬盘？
（2）若文件为连续文件，则要读文件A的第487条记录至少要存取几次硬盘？
（3） —般为减少读盘次数，可采取什么措施，此时可减少几次存取操作？

（1）由于每个物理块放4个目录项，因此root/目录下分为两个物理块，又因为根目录的第一块常驻内存（bin、dev、etc、boot可直接获得），故访问root/下读盘一次，usr/目录下需要读盘两次，he/目录下读盘一次，dir/下读入A读盘一次，共读盘5次。由于$255\ast 2+2=512$可知一个物理块在链式存储结构下可放2条记录及下一个物理块地址，而文件A共有598条记录，因此读取A的所有记录所需的读盘次数为$598/2=299$,所以将文件A读到内存至少需读盘$299+5=304$次。
2） 当文件为连续文件时，找到文件A同样需要5次读盘，且知道文件A的地址后通过计算只需一次读盘即可读出第487条记录，所以至少需要5 + 1=6次读盘。
（3）两种方法 ①FCB分解法（索引节点法）②设置当前目录
为减少因查找目录而读盘的次数，可采用索引结点方法。若一个目录项占16B,则一个盘块可存放512/16 = 32个目录项，与本题一个盘块仅能存放4个目录相比，可使因访问目录而读盘的次数减少1/8。对查找文件的记录而言，可用一个或多个盘块来存放该文件的所有盘块号，即用链接索引方法；一个盘块可存放$512/2-1=255$个盘块号，留下一个地址用来指向下一个存储盘块号(索引块)的磁盘块号。这样，就本题来说，查找目录时需启动5次磁盘。文件A共有299个盘块，则查找文件A的某一记录时需两次取得所有盘块号，再需最多启动一次磁盘即可把A中的任意一条记录读入内存。所以，查找一条记录最多需要8次访盘，而原来的链接方法查找一条记录时，读盘次数为6~304。

往年真题

1、某文件系统要存储的文件大小有以下统计规律：(2022-848真题)

（1）文件大小≤1KB占40％

（2）1KB＜文件大小≤6KB占30％

（3）6KB＜文件大小≤128KB占20％

（4）128 KB＜文件大小≤768KB占8％

（5）768 KB＜文件大小≤16MB占2％。

假设该文件系统的磁盘块大小为1024字节，盘块的编号最长为4字节，文件描述结构中可存放10个盘块编号。设计目标是使访问文件时具有尽可能小的平均访问磁盘次数，请为该系统设计文件的物理结构，用图文描述其设计思想，并计算其平均访问磁盘次数。（10分）

由题意可知盘块大小为1024B，盘块编号长度4B，故一个盘块可存放256个盘块号。
1、对于文件大小小于6KB的部分（70%），可设6个直接地址项，共占6KB。
2、对于文件大小大于6KB小于768KB的部分（28%），可设三个一级间接地址项，共$256\ast 3\ast 1KB=786KB$。
3、对于文件大小大于768KB小于16MB的部分（2%），可设一个二级间接地址共$256\ast 256\ast 1KB=64MB＞16MB$，可覆盖大于768KB小于16MB的部分。
平均访盘次数为$0.7\ast 1+0.28\ast 2+0.02\ast 3=1.32$次

2、某系统的文件物理结构采用多级索引结构。索引结点共设置 13 个地址项，其中 0 到 9 项为直接地址项，后 3 项分别为一级、二级、三级间接地址。逻辑块和物理块大小均为 1K字节，磁盘盘块地址占 16 位。(10 分)（2023-848）
（1）请画出该文件系统文件索引结构示意图。
（2）列出计算该文件系统允许的最大文件的长度计算表达式。
（3）读取一个长 256256 字节的文件的全部数据，共需读盘多少次？

（1）如上图所示
（2）已知逻辑块和物理块均为1KB，故每个盘块的大小为$1KB=2^{10}B$，又因为磁盘盘块地址占16位也即2B，故每个盘块最多存放$2^{10}/2=2^9$个盘块地址，故最大文件长度：$10+2^9+2^9\ast 2^9+2^9\ast 2^9\ast 2^9块=(10+2^9+2^{18}+2^{27})\ast 2^{10}B=134480394B$
（3）$256256/2^{10}$得到商为250余数为256，即对应逻辑块号250，块内偏移量为256，共占用251个磁盘块，由于$10\le 250<10+2^9$ ，而$251-10=241$，故需要读直接地址10次，读FCB一次，再读251个一次间址下的直接地址，共252次。

3、某文件系统空间的最大容量为4TB （ $1TB=2^{40}B$ ）,以磁盘块为基本分配单位。磁盘块大小为1KB。文件控制块（FCB）包含一个512B的索引表区。请回答下列问题:(2012统考真题)
（1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件的最大长度是多少字节？
（2）假设索引表区采用如下结构：第0~ 7字节采用〈起始块号，块数〉格式表示文件创建时预分配的连续存储空间。其中起始块号占6B,块数占2B,剩余504B采用直接索引结构，一个索引项占6B,则可支持的单个文件的最大长度是多少字节？为使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。

（1）系统空间最多存放$4TB/1KB=2^{32}$个磁盘块。需要$32bit/8=4B$来表示索引表项中的块号；可支持单个文件的最大长度$512/4=128$个表项，最多$128KB$
（2）所求的单个文件最大长度一共包含两部分：预分配的连续空间和直接索引区。连续区块数占2B，共可表示$2^{16}$个磁盘块，即$2^{26}B$。直接索引区共$504B/6B=84$个索引项，所以该系统可支持的单个文件最大长度是$2^{26}B+84KB$。
为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽可能接近系统最大容量4TB。分别设起始块号和块数占4B这样起始块号可以寻址的范围是$2^{32}$个磁盘块，共4TB,即整个系统空间。同样，块数字段可以表示最多$2^{32}个$磁盘块，共4TB;

3、文件存储空问管理中的典型问题分析

基础例题

【例1】有一计算机系统利用如图所示的位示图（行号、列号都从 开始编号）来管理空闲盘块。如果盘块从 开始编号，每个盘块的大小为 1KB。

(1) 现要为文件分配两个盘块，试具体说明分配过程；
(2) 若要释放磁盘的第 300 块，应如何处理？

（1) 为某文件分配两个盘块的过程如下：
①顺序检索位示图，从中找到第一个值为0的二进制位，得到其行号i = 2, 列号j = 2;
②计算出位所对应的盘块号：$b=i\ast 16+j+l=2\ast 16+2+1=35$
③修改位示图，令：$map[2,2]=l$, 并将对应块 35 分配给文件。
按照同样的方式，可找到第3行、第6列的值为0的位，转换为盘块号55, 将位的值修改为1,并将 55 号盘块分配给文件。
(2) 释放磁盘的第 300 块时，应进行如下处理：
①计算出磁盘第 300 块所对应的二进制位的行号i和列号j:
$i=(300-l)/16=18,j=(300-1)$
②修改位示图，令： $map[18,11]=0$, 表示对应块为空闲块。

【例2】假定一个盘组共有100个柱面，每个柱面上有16个磁道，每个磁道分成4个扇区。
（1）整个磁盘空间共有多少个存储块？
（2）若用字长32位的单元来构造位示图，共需要多少个字？
（3）位示图中第18个字的第16位对应的块号是多少？（假设字号，位号，块号都从1开始）

（1）整个磁盘空间共有$100\ast 16\ast 4=6400$个存储块。
（2）位示图应为6400个位，若用字长32位的单元来构造位示图，共需要$6400/32=200$个字。
（3）位示图中第18个字的第16位(即$i=18,j=16$)对应的块号为$32\ast (18-1)+16=560$。

往年真题

【例3】（2022-848） 页式虚拟存储管理采用位示图技术，设主存有 16384 块，采用 32 位的 512 个字作为位示图。若块号、字号和位号（从高位到低位）分别从 1. 0. 0 开始。试计算：5998 块对应的字号和位号；198 字的 20 位对应于哪一块？

5998 块对应 186 字的 13 位。198 字的 20 位对应 6389 块。
根据公式，有行号 i = (b - 1) DIV n = 5997 / 32 = 187，
列号 j = ( b - 1) % n = 5997 % 32 = 13
（逆推：盘块号 b = n * i + j + 1 = 32 * 187 + 13 + 1 = 5998）
所以，5998 块对应 187 字 13 位。
（2）因为字号和位号都是从 0 开始，块号从 1 开始，
所以，198 字的 20 位对应 198 * 32 + 20 + 1 = 6357 块。

【例4】（2020-848） 某个系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态如图所示：
(1) 该磁盘中目前还有多少个空闲盘块？
(2) 请简述磁盘块的分配过程。
(3) 在为某个文件分配 个盘块后，系统要删除另一文件，并回收它所占的 个盘块：700 711 703 788 70 1,写出回收后，空闲盘块号栈的情况。

（1）从图中可以看出，目前系统共有四组空闲盘块，第一组为 块，第二、三组分别为 100 块，第四组虽记为 100 块，但除去结束标记 后实际只有 99 块，故空闲盘块总数为 301 块。
（2）(2) 磁盘块的分配过程如下：首先检查超级块空闲盘块号栈是否已上锁，若已上锁则进程睡眠等待；否则，核心在给超级块的空闲盘块号栈上锁后，将 s_n free 减1,若 s_n free仍大于0, 即第一组中不只一个空闲盘块，则将 s_ free[ s _ free] 中登记的（即空闲盘块号栈栈顶的）空闲盘块分配出去；若 s_n free为0, 即当前空闲盘块号栈中只剩最一个空闲盘块，由于该盘块中登记有下一组空闲盘块的盘块号和盘块数，因此先必须将该盘块的内容读入超级块的空闲盘块号栈中，然后再将该盘块分配出去。若s_nfree o, 而且栈底登记的盘块号为 0, 则表示系统已无空闲盘块可分配。分配操作结束时，还需将空闲盘块号栈解锁，并唤醒所有等待其解锁的进程。
(3) 进行上述的分配和回收操作后，空闲盘块号栈的栈顶指针s_nfree 的值为 4, 而空闲盘块号栈中依次登记着盘块号 711, 703, 788, 701, 其中 701 登记在栈顶。

注：上面是题解答案，本题详解请参考这个博客：实例讲解成组链接法

参考书目

• 《计算机操作系统（第4版）》(汤小丹)
• 《计算机操作系统（第4版）》学习指导与题解(梁红兵，汤小丹编著)
• 《2024王道计算机操作系统考研复习指导》