操作系统考点之文件系统要点总结及目录分解法

如题：2020年8月

分析：什么是目录分解法呢？详见P218，通读教材不见得有所收获，以点带面，正是总结的初衷。

先要了解什么是目录？文件符号名到文件物理地址之间的映射机制。实现了文件按名存取的一种手段。基于文件控制块（FCB)来实现控制，文件控制块的有序集合形成文件目录。这样形成的目录，查找目录时都需要读入内存，往往比较大。引出了目录分解？将目录项分解为符号目录项（次部）和基本目录项（主部）。次部记录文件名以及相应的文件号；主部包含了除文件名外文件控制块的其他全部信息。这样查找目录就变成，找次部即可，由于减小了磁盘占用空间相应的读盘次数也变少了，提高了检索的速度。这其实还是比较好理解的。具体的题目：

求占用的物理块的个数？一个物理块大小是512字节，这肯定是分母。关键是分子的求解，一共64个目录项，次部占8个字节，一共占64*8=512个字节，正好是一个物理块。

基本目录40个字节，一共是64*40=2560字节，2560/512=5，答案就是A

题目没有问访问磁盘的次数？如何计算平均访盘次数呢？原理：<详见，扩展2，平均访盘次数的计算>

扩展：

1、文件的链接结构是通过指针来链接的吗？与索引的间接索引有什么区别呢？

此问题是看到间接索引是指不在物理块中存储文件信息，而是存储装有这些信息的物理块。那么，链接结构是不是也是这个原理来呢？

链接结构是将逻辑上连续的文件分散存储在若干不连续的物理块中。在每个物理块中都设有一个指针，该指针指向后续的物理块（形成一个链表结构）。

区分：由此可见索引就是索引，存储的是文件信息，而链接结构存储的是文件本身的内容。但原理都是一样的，底层利用的都是指针。

2、平均访盘次数的计算？？？

如题：

一个文件系统中，其FCB占64B,一个盘块大小是1KB,采用一级目录。假定文件目录中有3200个目录项，则查找一个文件平均需要访问磁盘（  ）次。

分析：没有说目录分解，那么FCB的有序集合，就是目录。也就是题中所说的目录项。可以求得占用磁盘空间是3200*64，进而求得占用的盘块=3200*64/1024=200个。实际中磁盘的块大小和内存的页是一致的。假设外存只有一个目录时，调入内存需要访问磁盘一次，有两个目录，访问磁盘两次（因为第一次本身是目录，所以需要查找，把两个目录都调入内存页，第一次把第一个目录调入，第二次把第二个目录调入，所以需要访问两次磁盘）依次...,当有n个目录时，需要访问磁盘n次。一共访问次数为（1+2+...+n)，因为有n个目录，平均每个目录需要访问次数为（1+2+...+n)/n=(n+1)/2.代入得(1+2+..+200)/200=100.5次

3、文件系统要点总结：算是整体顺一遍

什么是文件系统呢？

指OS中管理文件的那一部分软件。它负责管理文件的存储、检索、更新，提供安全可靠的共享和保护手段，并为用户提供一整套方便有效的文件使用和操作方法。它在OS接口中占比例最大，是I/O系统的上层软件。文件系统面向用户的主要任务是实现文件的“按名存取”。

文件的逻辑结构？

用户眼中文件信息的组织形式叫文件的逻辑结构。

分类：无结构文件（流式），有结构文件（记录式）

无结构：文件内部的数据就是一系列二进流或字符流，如.txt文件

有结构：由一组相似的记录组成，每条记录又由若干个数据项组成。如数据库表文件。根据各条记录在逻辑上的组织形式又分为三类：1、顺序文件，记录一个接一个顺序排列，可以定长也可以不定长，在物理上可以顺序存储也可以链式存储。2、索引文件：解决不定长记录检索困难问题。方法是：建立一个定长记录的顺序索引表（每个记录对应一个索引表项），可以用不同的数据关键字建立多个索引表，用于对信息处理及时性要求比较高的场合。3、索引顺序文件，解决索引文件占用空间过大的问题。思想是：不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。如按学生姓名开头字母进行分组检索。4、多级索引顺序文件，进一步提高检索效率。如下图：

文件的物理结构？

系统眼中的文件信息组织形式。指文件在外存上的存储组织形式，它与存储介质的性能和外存的分配方式有关。要解决的是文件的分配方式问题。即文件数据怎样存放在外存中。

相对应的OS另一项磁盘管理是对空闲磁盘管理，解决的是“文件存储空间管理的问题”。

分类：

顺序分配（连续分配）：

磁盘块、内存块、文件块问题：内存与磁盘间数据交换（即读/写、磁盘I/O）都是以块为单位进行的，每次读入一块或每次写一块。并且，内存块（页）与磁盘块大小相同。文件就被分配到磁盘块中。用户通过逻辑地址操作自己的文件，OS负责实现从逻辑地址到物理地址的映射。

连续分配思想：每个文件在磁盘上占有一组连续的块。OS如何实现逻辑地址到物理地址呢？用户给出要访问的逻辑块号，OS找到该文件对应的FCB,物理块号=起始块号+逻辑块号，如下图：

链接分配：为文件分配离散的磁盘块。分为隐式链接和显示链接两种。

隐式链接

OS如何实现从逻辑地址到物理地址的转换？

用户给出要访问的逻辑块号i,操作系统找到该文件对应的FCB.找到起始块号(0号块），根据指针找到下一块，依次....所以，读入i号逻辑块，总共需要i+1次磁盘i/o.

这样的话，只支持顺序访问，不支持随机访问。指针也占用存储空间。

显式链接：思想：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT,file allocation table),并且一个磁盘仅设置一张FAT（并且，OS启动加载后，常驻内存）,FAT的各个表项在物理连续存储，且每个表项长度相同，因此“物理块号”字段可以是隐含的（由于是连续的，所以块号就是顺序的,所以是隐含的）。如下图：

逻辑块

OS如何实现文件逻辑块号到物理块号的映射？

跟隐式链接一样，首先找到FCB,从目录项中找到起始块号，查询FAT,往后找到i号逻辑块对应的物理块号。可见，逻辑块号转成物理块号的过程不需要读磁盘。

显式分配文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要访问之前的0 · i-1号逻辑块），访问速度要快很多。

题目没有明确说是隐式或显式，默认指是隐式链接，如下题：

设有一个记录文件，采用链接分配方式，逻辑记录的固定长度是100B,在磁盘上存储时采用记录成组分解技术。盘块长度是512B。如果该文件的目录项已经读入内存，则对第22个逻辑记录完成修改后，共启动了磁盘（    ）次。

分析：首先弄明白成组分解是如何分解的。磁盘块大小是512B，逻辑记录是100B,二者并没有整数倍的关系，因此才会引入成组分解技术。也就是说5个逻辑记录（共500B）存在一个磁盘块，剩下的12B就不用了。因此，第22个逻辑记录存在第五个物理块（5*512B,才能装下22*100B)。链接分配，需要从第一个磁盘块开始读，也即这个FCB存储的磁盘的物理地址是第一块的盘号。启动磁盘块1，磁盘块2，…，磁盘块5共5次，将磁盘块5读入主缓冲区后，分解得到物理记录。对内存记录进行操作–修改，注意，修改完成后要写回到磁盘，故再一次访问磁盘因此，共启动磁盘6次。

索引分配：

思想：为每个文件建立一张索引表，索引记录文件的各个逻辑块对应的物理块（实现逻辑页面到物理页面的映射），索引存放磁盘块称为索引块，文件数据存放的磁盘称为数据块。

与显式链接的区别：

FAT是一个磁盘对应一张表，而索引是一个文件对应一张索引表。

OS如何实现逻辑块到物理块的转换呢?

用户给出要访问的逻辑块号i,OS找到FCB,FCB中有存储了索引块的块号。根据索引块号找到索引表存放位置，从外存读入内存，查找索引表即可i号逻辑块在外存中的存放位置。一个索引块装不下的解决方案：链接方案：思想是将索引块链接起来存放。如下图：

若要找到i号索引，必须先依次读入0 ~i-1号索引块，导致磁盘I/O次数过多，查找效率低下。

多层索引：思想：类似于多级页表，使第一层索引块指向第二层索引块。还可以再扩展。如下图：二级索引

图中，磁盘块大小为1kB,每个索引占4B,所以一个磁盘块可以放256个索引。主要明白，索引里面放的什么？存放的是逻辑块对应的磁盘块号，因为只是一个块号（指针）所以内容就是这个块的大小，所以最后一级索引指向内容的大小是1kB.

可根据逻辑块号算出查找索引表的哪个表项。如1026号逻辑块，则1026/256 = 4，1026%256 = 2，可先将一级索引表调入内存，查询4号表项，将其对应二级索引表调入内存，再查询二级索引表2号表项即可知道1026号逻辑块存入的磁盘号了。同时也可以得出：采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。

混合索引：思想：多种索引分配方式结合。如下图：

总结：

文件支持随机访问是指采用这种逻辑结构文件，可以根据记录号直接算出该记录对应的逻辑地址（逻辑块号，块内地址）。如：每块大小1kB,定长记录长度为16B,因此一块有1kB/16B=64个记录。则逻辑块号m = i/64,块内地址n = (i%64)*16;i号逻辑地址=（m,n).

文件目录：管理文件最为重要的依据

FCB:

包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等）、存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（文件建立时间、修改时间等）。最重要最基本，还是文件名、文件存放物理地址

FCB的有序集合就是文件目录；单级目录如下图：

只是实现“按名存取",但不允许文件重名。显然是不适用于多用户OS.

二级目录结构：思想：目录分为两级：一级称为主文件目录，给出用户名，用户子目录所在的物理位置；二级称为用户文件目录（又称用户子目录），给出该用户所有文件的FCB

多级目录结构（树形目录结构）思想：对二级目录简单扩充可得三级或三级以上的多级目录结构，即允许每一级目录中的FCB要么指向文件，要么指向下一级子目录即可。这是当今主流OS普遍采用的目录结构。如下图：

绝对路径：从要目录出发的路径。如/照片/08/me.jpg,先从外存读入根目录的目录表；找到”照片“目录存放位置，再从外存读入对应的目录表，找到”08“目录的存放位置，再从外存读入对应的文件目录表，找到me.jpg文件。需要3次访问外存。

相对路径：从当前目录出发的路径。适用于访问同一路径下多个文件情形。提升访问效率，减少磁盘i/o次数。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了"无环图目录结构"如下图：

原理：可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一个目录下的所有内容）。每个共享点设置一个共享计数器，用于记录此时有多少个地方共享该结点。用户提出删除结点的请求时，只删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。

文件寻址：根据FCB物理地址等信息，求出文件的任意记录或字符在存取介质上的地址。

目录分解法：在查找各级目录过程中，只需要用到”文件名"这个信息，只有文件名匹配时，才需要读出文件的其他信息。所以才分了次部和主部两部分，通过查找次部，将索引点调入内存，通过索引点找到主部（文件各种信息）。

最后

以上就是故意白云为你收集整理的操作系统考点之文件系统要点总结及目录分解法的全部内容，希望文章能够帮你解决操作系统考点之文件系统要点总结及目录分解法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。