文件系统总览概述
① 进程就是运行的程序
② 根目录会在开机时读入内存并常驻内存
③ 若采用FAT,则FAT表也会在开机时读入内存并常驻内存
④ 文件inode结点读入内存后会立刻返回一个文件标识符fd
补充：
若要打开的文件不在根目录下则需要先到外存中的目录，比如要读取的文件B的路径是/File/A/B，则需要先查常驻在内存的根目录找到A的inode并调入，再才能找到B的inode。
零、部分考点处理方法整理
1、多层索引
- ① 要会根据多层索引 、 混合索引的结构计算出文件的最大长度
- （ Key ： 各级索引表最大不能超过一个块） ；
- ② 要能自己分析访问某个数据块所需要的读磁盘次数
- （ Key ： FCB 中会存有指向顶级索引块的 指针 ，因此可以根据 FCB 读入顶级索引 块。 每次读入下一级的索引块都需要一次读磁盘操作。 另外， 要注意题目条件 —— 顶级索引块是否已调入内存）
例题：
【2010年计算机联考真题】
设文件索引结点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4B，若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度是( )。
【解析】
【解析】
B，若索引结点未在内存中，则D。
2、read系统调用
仅open系统调用的参数需包含文件的名称，read直接使用文件描述符。
open系统调用将文件目录项读入内存，read系统调用将文件内容读入内存。
3、物理结构是否支持随机访问
比起索引结构，连续结构的随机访问更快（连续结构可直接计算出想要访问的数据所在的物理地址，而索引结构还需要查索引表，更耗时)。
4、位示图相关计算
【2015年计算机联考真题】文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的32～127号块中，每个盘块占1024个字节，盘块和块内字节均从0开始编号。假设要释放的盘块号为409612，则位图中要修改的位所在的盘块号和块内字节序号分别是() 。
注：
- 容易懵圈的几个术语：目录vs文件目录vs目录文件
①目录=文件目录。
②目录文件是对这个目录进行描述的文件，是存放在外存中的数据。
③“目录”可以理解为windows系统中的一个文件夹，而“目录文件”是描述这个文件夹中内容的文件。
应用题解构引例：
1、有结构文件：由文件记录组成。
2、一个MP3文件的基本逻辑格式：
1）MP3 Frame：相当于文件的记录、struct结构体，一个Header + 一个Data。
2）Mp3Header大小固定32bit，Mp3Data不固定（取决于采样率、码率 xxxbps 每秒钟多少个kb）。
3）使用Mp3文件时，用户提供的是逻辑地址。
4）听歌时，若快进60s，则会定位到其逻辑地址。而OS会根据Header的信息将逻辑地址转换为物理地址。
一、FAT文件系统（Windows DOS系统）—— FAT文件表、显式链接
1、物理结构：链接分配（显式链接：FAT文件分配表来说明某物理块对应的磁盘块）
2、硬盘结构
引导块：开机后由CPU中的ROM区的BIOS芯片执行自举程序后，
FAT文件分配表：文件分配表相当于数据结构中的静态链表，存储在磁盘中的固定位置，指明某文件第几块分别在磁盘的什么地方。
根目录：存放在FAT表之后的固定位置：操作系统在完成一系列开机操作时以根目录为起点逐层往下寻找相应文件并执行（开机时操作系统将根目录读入内存中，并且常驻内存，即查询和访问根目录无需进行磁盘操作）
3、
FCB和根目录开机就读入内存。
FCB确定文件块首地址， FAT确定块间关系。
FAT文件系统打开文件的过程（OPEN系统调用）
开机时，假设OS会将 根目录 的信息读到内存的11号页框中，FAT文件分配表读到内存的0号页框中。
场景1、文件的打开操作
若 QQ音乐进程 想打开 B.Mp3
① 用户进程使用 open 系统调用，指明路径。
② OS访问内存中的根目录，发现三个FCB，其中B和用户想要打开的文件的文件名相同，获得其起始块号。
③ 查询FAT文件分配表，可以知道B文件的任何一个快在啥地方。
总结：
①查目录，获得文件所对应的FCB文件目录项，从而得到文件起始块号x
②查FAT分配表，从x块号出发，从而得到文件每一个逻辑块所存储的物理块号，根据用户需求，将相应物理块读入用户的地址空间，再完成地址的映射。
场景2、文件的读操作
若B.mp3文件大小为2.5kB，时长为2.5min，若用户进程想要访问 B.mp3 的最后0.5min（因程序员知道文件的逻辑结构，即知道是需要第三块）：
OS会通过查询 FAT 表，找到应该读的磁盘的第三个逻辑块：磁盘的8号块，读入内存。同时映射到进程虚拟地址空间（OS会建立起虚拟地址和内存空间的映射）
发出OPEN系统调用后，OS会返回一个 文件描述符 fd。相当于文件的指针。read通过 fd 便可直接访问某个调入内存的块。
总结：文件的读操作本质上是对文件不同的逻辑地址的读操作。
场景3、查目录过程
1）若某进程想要打开Dm文件，并read Dm 2块：
①打开 open( /A /Dm) —— 本质就是寻找FCB
（1）OS从根目录中找到了A目录文件（在内存中，不需访问磁盘）。
（2）A目录文件由n个FCB组成，占用3个磁盘块存储。
目录A所在的 磁盘5、6、7块全部读入内存（3次读磁盘）。
（3）查找是否有Dm的FCB即目录项，再获得其起始块号。
（4）查询FAT，从而得到Dm两个逻辑块对应的物理块号。
总结：
② 读入 read ( fd，2块)
读入Dm的两个m和k号块（2次读磁盘）
Q：一个open，一个read发生了几次读磁盘？
答案：5次
优化：目录文件A的三个块不需要全部读入内存。
优化后：1次
2）若某进程想要对G文件进行read操作：
①open( /C / F / G)
（1）OS从根目录中找到了C目录文件（在内存中，不需访问磁盘）。
（2）读入C目录文件，查找F子目录文件，获得其起始块号。（1次读磁盘）
（3）读入F子目录文件，查找要访问的目标文件G的起始块号。
问题1：如何确定目录文件需要占多少个块?
A1: (目录项的数量*每个目录项的大小) / 块大小
问题2：目录文件A必须占用连续的磁盘块吗?
A2:不用！如果目录文件A继续变大，还需要新的磁盘块，那么通过查FAT表即可确定，哪些磁盘块是空闲的，把空闲磁盘块分配给文件A使用即可。当然，本来文件A的最后一块是7号块，如果给A再分配一个新的块，就需要修改FAT表的7号表项，指向这个新的块号。
问题3：为什么根目录要存放在磁盘的固定位置?
A3：因为开机的时候，需要从根目录出发，找到操作系统初始化相关的各种文件。因此，只要根目录存放在固定位置，那么开机时候取这个固定位置读入根目录的数据即可。
问题4：简述操作系统是如何使⽤FAT表的？
A4：开机时，就会把整个FAT表读⼊内存，系统运⾏过程中，该表会⼀直常驻内存，也就是说，查FAT表不需要读磁盘，内存⾥本来就有这个表。系统运⾏过程中，如果要访问某个⽂件，则⾸先要找到这个⽂件对应的⽬录项，从⽬录项中找到⽂件的起始块号，再根据起始块号查FAT表，从⽽确认⽂件的后序那些块存放在哪⾥。
问题5：FAT表中，每个表项的⼤⼩对⽂件系统有什么影响？
问题6：若进程想要访问某文件，为什么必须将其先映射到进程的虚拟地址空间中？
举个例子：c语言中我们定义的指针所指向的地址是进程的虚拟地址。我们不知道进程被映射到了哪个物理页框中。
若进程想要访问某文件，则必须将其先放置到进程的虚拟地址空间中。实际访问时，OS会将其转换成物理地址进行访问。
注：这里的块号都为物理块。
1、操作系统的视角下只有物理块号这个概念，即它将外存（磁盘）分成一个个的物理块。
2、磁盘和设备驱动程序的视角下才有盘号这个概念，设备驱动程序将操作系统发来物理块号转化为具体的磁盘的盘块号、扇区号、柱面号。
早期 微软 的DOS系统的FAT文件系统中，每个FCB目录项包含的信息过多，若目录项很多，目录文件会占据太多盘块，上文提到，查找某个目标文件的FCB需要将上级目录的逻辑块一块一块读入内存，这样的话，仅查询目录的过程 IO次数 就太多次啦。
这个时候，UNIX 就采用了另一种方式：inode索引结点的策略。
因为查询目录的过程仅需查询文件名，从而可将目录项瘦身：
每个文件的目录项值包含文件名和索引结点。
二、UFS文件系统（UNIX系统）—— 位示图、混合索引
1、物理结构：索引分配（混合索引）
2、位示图（bit map）：
这个位示图，每个bit 对应⼀个物理块。1表示不空闲，0表示空闲
3、inode区：
3、 由于Unix⽂件系统采⽤了“索引节点”，因此每个⽬录项只需包含 “⽂件名、inode号”，⽂件的具体属性包含在 inode 中。
4、如果一个磁盘块用于存储索引表，则通常将其称为“索引块”﹔如果一个磁盘块用于存储文件的数据，则通常将其称为“数据块”；
5、每一张索引表需要刚好占满一个块，因此，若每个磁盘块大小为4KB，每个索引项4B，则一张索引表包含1024个索引项
UFS文件系统打开文件的过程（OPEN系统调用）
场景1、进程打开Dm文件过程 open( / A / Dm) ：
①从开机已经调入的内存的根目录下找到A，获得目录文件A的 inode号 。
②根据 inode号 从inode区中找到对应结点，并将inode结点读入内存。（1次读磁盘，但在实际应用中会连续多读几个结点，从历年真题看来，默认需要一次读磁盘操作将其读入内存）
③将A文件的两个逻辑块所在的6号块、7号块读入内存（根据Dm是否在6或7中，若在6中读入一次，否则两次；根据题目具体分析）
③假设在7号块的目录项中寻找Dm的目录项，确定inode结点编号5。
④再从inode区中将5号索引结点读入内存。
总结：
①根目录文件常驻内存，首先查内存中的根目录，找到目录项A。
②根据目录项A可知，文件A对应1号inode结点，因此要将1号inode结点从磁盘读入内存。
③根据刚读入的1号inode结点，可知文件A的索引信息，也就是知道了文件A的每一个块存储在什么位置，接下来可读入目录文件A的第一块（6号物理块)〉。
④尝试查找目录项Dm，如果没找到，那么还需要读入目录文件A的第二块(7号物理块)。
⑤找到目录项Dm之后，根据目录项记录的inode号，将Dm的inode结点从磁盘读入内存
⑥根据Dm的inode结点，读入Dm的第—块(m号物理块)、第二块(k号物理块)
场景2、若进程想要read文件Dm的第3.2KB（假设每个磁盘块1KB，已知Dm占用两个块即2KB）
OS将会拒绝此次请求 —— 访问越界。
场景3、若进程想要read文件Dm的第1.5KB（此为逻辑地址，即第二个块）
OS将Dm第二块所在的 物理块k 调入内存。
—— 因此也可以看出 混合索引 的物理结构是支持随机访问的。
场景4、若进程想要read文件H的第11.5KB（此为逻辑地址，即第12个块）
1）open( /C/F/H)过程
①根目录文件常驻内存，首先查内存中的根目录，找到目录项C。
②根据目录项C可知，文件C对应7号inode结点，因此要将7号inode结点从磁盘读入内存。
③根据刚读入的7号inode结点，可知文件C的索引信息，接下来可读入目录文件C实际数据所在的第一块（9号物理块)〉。
④根据目录项F可知，文件F对应4号inode结点，因此要将4号inode结点从磁盘读入内存。
⑤根据刚读入的4号inode结点，可知文件F的索引信息，接下来可读入目录文件F的第一块（14号物理块)〉。
⑥根据目录项H可知，文件F对应10号inode结点，因此要将10号inode结点从磁盘读入内存。找到目的文件的inode结点并调入内存后，open调用结束，并返回一个 文件描述符 *fd。
2）read第十二块
① 0~9号块直接索引。若访问第12块，则一级索引表读入内存。
②读入第23号块。
场景5、若进程想要read文件Z的第6154号块
1）open(/C/F/Z)
同场景4的open中的①②③④⑤读入目录文件F的第一块（14号物理块)。
⑥根据目录项Z可知，文件F对应11号inode结点，因此要将11号inode结点从磁盘读入内存。
open调用结束，并返回一个 文件描述符 *fd。
2）read 文件Z的第6154块。
①0~9块直接索引。每⼀张索引表需要刚好占满⼀个块，因此，若每个磁盘块⼤⼩为4KB，若每个索引项4B，则⼀张索引表包含1024个索引项。从而一级间接索引 10~1034 块。
则通过二级索引查找第6154块。
根据其中的⼆级间接索引，找到存放在24号块中的第⼀级 索引表：（6154-1034）/ 1024 = 5；
②通过24号块中的第5个索引项，找到存放在30号块的第⼆级索引表，并读入内存；
③最后通过30号块的第1024个索引项，找到⽂件Z的第6154个数据块，也就是28号磁盘块，并读入内存。
注：此文件最多包含多少块？
Q：进程读写文件之前，首先需要做什么？
A：进程读写文件之前，先open。open的本质是查要访问的文件的目录项。接下来就可以访问文件的某个逻辑地址。这个逻辑地址就是程序员所给出的逻辑地址。
而OS根据不同文件系统会将想要访问的逻辑地址转换为物理地址。
找目录项的过程，根据不同文件系统会有些区别。FAT文件系统找到了FCB之后就相当于知道了文件的所有信息，而UFS文件系统，找到了目录项之后，只是知道了索引结点的编号，还需要把索引结点读入内存，才能知道文件的索引信息。
三、与其他章节的联系
1、每个进程都有自己的虚拟地址空间。不一定所有的页面都会使用。
2、各个进程可以使用页表映射的方式共享一片内核区。从而实现进程间通信。
3、一级页表常驻内存。
4、OS实现进程管理
就绪态进程和阻塞态进程队列存放在内核区的页面中。
若某P1进程使用P操作（系统调用），且资源不能分配时，则OS将会把其PCB挂到阻塞队列中，并从就绪队列中选择一个进程上处理机。
5、进程通信方式（一定通过系统调用）
P1数据从用户区复制一份到内核区，则P2的用户区会从内核区复制一份。
注：若进程间通信使用共享内存的方式通信会有些不同，mmap。用户区映射到同一个物理页框中。
6、进程调度的底层原理
进程内核区会有一个页面实现调度算法，从而根据调度规则去就绪队列等内容。
7、什么时候会引起调度？
1）假设P1通过系统调用，终止本进程，则该系统调用会被OS捕获，执行trap指令，指令执行流会跳到某个特定的地址（系统调用入口程序）判断需要何种服务，再跳转到服务代码的部分。
2）假设进程的某指令访问未在内存中的页面，则会触发缺页异常(内中断)。
发生某种异常时，PSW标志信息或某专门异常寄存器会发生变化，OS检测到异常后，会统一跳转到某地址（可理解为异常入口程序，判断异常号），再根据异常号跳转到相应处理程序。
驻留集信息会存放在PCB中，若缺页异常从磁盘调入到内存时，驻留集已满，则需执行页面置换算法（内核区某段区域）。
8、内存映射文件
操作系统 | 内存文件映射 —— 文件到内存的映射_西皮呦的博客-CSDN博客
附图：两个进程共享页面
IO管理相关内容
假设某用户请求删除文件 “D:/ 工作目录 / 学生信息 . xlsx” 的最后 100 条记录。
1. 用户需要通过操作系统提供的接口发出上述请求 —— 用户接口
2. 由于用户提供的是文件的存放路径， 因此需要操作系统一层一层地查找目录， 找到对应的目录 项 —— 文件目录系统
3. 不同的用户对文件有不同的操作权限， 因此为了保证安全， 需要检查用户是否有访问权限 —— 存取控制模块（存取控制验证层）
4. 验证了用户的访问权限之后， 需要把用户提供的“记录号”转变为对应的逻辑地址 —— 逻辑文 件系统与文件信息缓冲区
5. 知道了目标记录对应的逻辑地址后， 还需要转换成实际的物理地址 —— 物理文件系统
6. 要删除这条记录， 必定要对磁盘设备发出请求 —— 设备管理程序模块
7. 删除这些记录后， 会有一些盘块空闲， 因此要将这些空闲盘块回收 —— 辅助分配模块
write系统调用：属于设备独立型软件。只能得到需要操作的磁盘块，但不知道此块在哪个扇区？磁道？盘面？需要进一步调用驱动程序入口。
驱动程序才会定位到磁盘的磁头移动等操作。
每个设备都有一个设备控制器，从而定位。
四、408真题
【2011年计算机联考真题】
某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
(1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求说明理由。为定位文件数据块需要FCB中设计哪些相关描述字段?
(2)为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。
【解析】
1）
在本题所述场景中，不需要对文件进行“增/删/改”的操作，因此应该使用连续分配方式，可以使文件访问效率最高，存储空间利用率最高。
为了定位文件数据块，需要在FCB中记录文件的<起始块号，块数>或<起始块号，结束块号>
2）将所有的FCB集中存放，文件数据块集中存放。在按名查找文件名时，只需访问存储FCB的几个块。可减少磁头移动和磁盘I/o次数。
若与对应文件数据块存放，那么想要查找A之后的文件，必须从A的FCB开始获得其长度之后，才能找到文件B的PCB，再读入内存，如法炮制，显然，io次数增多。
Key：已写入的文件不可修改
连续分配——优点∶支持随机访问，随机访问速度最快，且存储空间利用率最高;缺点∶文件数据的增/删/改”不方便。
链式分配——优点︰文件数据的“增/删/改”方便;缺点∶“查”不方便，不支持随机访问，只能顺序访问，需要使用额外的存储空间来存放磁盘块之间的链接指针;
索引分配——优点∶文件数据的“增/删/改”方便，也支持随机访问，但随机访问速度不如连续分配方式;缺点∶索引表的存放需要消耗额外的存储空间。
【2012年计算机联考真题】
某文件系统空间的最大容量为4TB(1TB=2^40B)，以磁盘块为基本分配单位。磁盘块大小为1KB。支件控制块（FCB）包含一个512B的索引表区。请回答下列问题。
1）假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节?
2）假设索引表区采用如下结构:第0~7字节采用<起始块号,块数>格式表示文件创建时预分配的连续存储空间，其中起始块号占6B，块数占2B;剩余504字节采用直接索引结构，一个索引项占6B，那么可支持的单个文件最大长度是多少字节?为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。
【解析】
1）
系统空间最大容量4TB=2^42 B → 最多2^42 / 1KB =2^32个 磁盘块
直接索引结构：每个文件一张索引表索引表的每个表项指向一个磁盘块
→ 最少 32 位 → 最少占4B → 物理块号4B
最大有没有可把4TB全部分配给一个文件呢？注意 还有索引表区的限制。
索引表区最多存有 512B / 4B = 128 个 FCB → 最多被分配128个磁盘块 → 最大长度128KB
2）
①剩余504字节对应 504B / 6B = 84 个FCB → 最多被分配84个磁盘块 → 大小84KB
0~7字节：每个字节所表示分配块数最多为：2^2B = 2^16块 = 大小 2^16*1KB = 64MB
→最大长度 64MB+84KB
②合理的起始块号和块数所占字节数分别为4，4（或1，7或 2，6或3，5）。
理由∶块数占4B或以上，就可表示4TB大小的文件长度，达到文件系统的空间上限。
为了使单个文件的长度达到最大，应使连续区的块数字段表示的空间大小尽可能接近系统最大容量4TB。分别设起始块号和块数分别占4B，这样起始块号可以寻址的范围是个磁盘块，共4TB，即整个系统空间。同样的，块数字段可以表示最多
个磁盘块，共4TB。
不理解：为什么不最大可能的满足直接索引？
【2014年计算机联考真题】
文件F由200条记录组成，记录从1开始编号。用户打开文件后，欲将内存中的一条记录插入到文件F中，作为其第30条记录。请回答下列问题，并说明理由。
1）若文件系统采用连续分配方式，每个磁盘块存放一条记录，文件F存储区域前后均有足够的空闲磁盘空间，则完成上述插入操作最少需要访问多少次磁盘块? F的文件控制块内容会发生哪些改变?
2）若文件系统采用链接分配方式，每个磁盘块存放一条记录和一个链接指针，则完成上述插入操作需要访问多少次磁盘块?若每个存储块大小为1KB，其中4字节存放链接指针，则该文件系统支持的文件最大长度是多少?
【解析】
1） 下列是连续分配的磁盘块使用情况。
现在需要将一条记录插入到文件F 中，作为其第 30 条记录，也就是插入到第 29 条记录的后面。这需要向前移动文件的前 29 条记录。移动后如下图， 其中灰底（红字）的磁盘块存储的是插入的记录。
向前移动文件的前29 条记录，每条记录需先读一次，然后写到其前一块磁盘块需 29×2=58 次。
然后需要将新记录写到腾出的那个磁盘块中， 作为该文件的第 30 条记录。
故总共需要 58+1=59 次。
由于文件的起始位置前移了一个磁盘块，同时文件也增加了一条记录，
因此F的文件控制块中的文件的起始位置和文件长度会发生改变。
注：若向后移动，则次数过多。
2）
这就需要先找到第29条橙色文件记录的磁盘块，然后获得第 30 条橙色文件记录的磁盘块地址 （需读磁盘 29 次）。
再为该记录分配一个空闲磁盘块， 将该紫色记录以及第 30 条橙色文件记录的磁盘块地址写入其中，再将该块写入磁盘（需写磁盘 1 次）。 最后还需要修改第 29 块的链接指针，指向新的插入块，并将第 29 块写回磁盘（需写磁盘 1 次）。
故共需要 29+1+1=31 次。
由于每个磁盘块大小为 1KB，其中 4 个字节存放链接指针， 因此用于存放文件的空间为（ 1KB-4B）。
又 4 个字节的指针的地址空间为。
因此该文件系统支持的文件最大长度是（1024-4） B× = 4080GB
【2016年计算机联考真题】
某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。
(1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。
(2）若FAT的每个表项仅存放簇号，占2字节，则FAT的最大长度为多少字节?该文件系统支持的文件长度最大是多少?
(3）系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。
(4）假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇?
【解析】
1）两个目录文件dir和dir1的内容如下表所示。（3分）
【评分说明】每个目录项的内容正确给1分，共3分。
2）
由于FAT的簇号为2个字节，即16比特，因此在FAT表中最多允许216（65536）个表项，一个FAT文件最多包含216（65536）个簇。
FAT的最大长度为216×2B=128KB。（1分）
文件的最大长度是2^16×4B=256MB。（1分）
【评分说明】若考生考虑到文件结束标志、坏块标志等，且答案正确，同样给分。
3）
在FAT的每个表项中存放下一个簇号。
file1的簇号106存放在FAT的100号表项中，（1分）注：不要写第100号。
簇号108存放在FAT的106号表项中。（1分）
4）
先在dir目录文件里找到dir1的簇号，然后读取48号簇，得到dir1目录文件。
接着找到file1的第一个簇号，据此在FAT里查找file1的第5000个字节所在的簇号106，最后访问磁盘中的该簇。
因此，需要访问目录文件dir1所在的48号簇，（1分）及文件file1的106号簇。（1分）
注：
1、簇(Win)和块(UNIX、LINUX)是一样的。
2、
实际应用中，一般要用一个特殊的数表示文件结尾（EOF, end offile），如:OxFFFF
还要用一个特殊的数标记空闲簇,如:Ox0000
【2018年计算机联考真题】
某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。
(1）该文件系统能支持的最大文件长度是多少?(给出计算表达式即可。)
(2）文件系统用1M（1M=2^20)个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个图像文件?
(3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文系统获取F1和F2最后一个簇的簇号需要的时间是否相同?为什么?
【解析】
1）
一个簇中包含 4KB / 4B = 1K 个inode（注意：这里是除以地址项大小）
直接地址项对应簇数：1
一级间接：一级索引表对应64个簇：1K
二级间接：1K x 1K
三级间接：1K x 1K x 1K
则最大长度为：(8+1×1024+1×1024^2+ 1×1024^3)×4KB = 32KB+4MB+4GB+ 4TB
注：多级间接地址项索引的是一个簇，簇里都是地址项，而不是索引节点。然后根据地址项索引物理块。
2）
最多可存放 512M x 4KB / 5600 个图像文件数据？？？
（上当了！错误！你给我记住！OS给文件分配空间是以簇/块为单位的！）
因此OS为5600B的图像文件分配的空间应该为两个簇。
则最多可存放 512M x 4KB / 8KB = 2^28 个图像文件。（数据区上限）
最多可存放 1M x 4KB / 64B = 2^26 个文件索引结点（inode上限）
取较小者：2^26个 = 64M个
3）
文件F1的大小为6KB即2个簇，因此获取文件F1的最后一个簇的簇号只需要访问索引结点的直接地址项。
文件F2大小为40KB即10个簇，因此获取F2的最后一个簇的簇号还需要将一级索引表读入内存。综上，需要的时间不相同。
五、补充易错点
1、磁盘块
磁盘块分两种：
①磁盘数据块：存放数据
②磁盘索引块：存放索引指针(地址项)。磁盘块大小/地址项(索引指针)大小=每个磁盘块能存放的索引指针个数
一个磁盘块，题目中一般为1KB。
2、混合索引：直接地址索引、一级间接地址索引、二级间接地址索引
1）直接地址索引 / 直接地址项：
对应一个磁盘数据块(一个簇)
对应一个一级磁盘索引块，然后这个磁盘索引块中的每一个地址项，都对应一个磁盘数据块。
3）二级间接地址索引：
对应一个两级磁盘索引块。①二级间接地址索引，先指向一个一级磁盘索引块。②然后一级磁盘索引块中的每一个地址项，对应一个二级磁盘索引块。③二级磁盘块中的每一个地址项，对应一个磁盘数据块。
例题1：10年29.
分析：
一个磁盘块中最多有 256B/4B =64个地址项
①4个直接地址索引：就是4个地址项。4×256B
②2个一级地址索引：就是2个磁盘索引块。2×64×256B
③1个二级地址索引：就是1个二级磁盘索引块。1×64×64×256B
总共：(4+2×64+64×64)×256B/1024=1057KB
答案：C
例题2：15年29.
分析：
先求一个磁盘索引块能存放的索引指针个数：1KB/4B=256个。
①直接索引指针10个：能指到10个磁盘数据块，文件偏移量 0-10KB
②一级索引指针1个：能指到1个磁盘索引块，此磁盘索引块有256个地址项。进而指到256个磁盘数据块。文件偏移量 10KB-266KB。
③二级索引指针1个：能指到1个磁盘索引块，进而指到256个磁盘索引块，再指到256×256个磁盘数据块。266KB-266KB+64MB
1234<10KB，直接索引直接访问1次磁盘数据块。
266KB<307400<64MB，需要找二级索引，访问2次磁盘索引块，1次磁盘数据块
答案：B
相关内容补充来源于
操作系统 考研习题 详细解析（2）_Z_timer的博客-CSDN博客_某计算机系统中的磁盘有300个柱面