五天自学完王道考研-操作系统第四章文件管理

本文主要是介绍五天自学完王道考研-操作系统第四章文件管理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

初始文件管理

在这里插入图片描述

一个文件有哪些属性?

文件名:由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
标识符:一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
类型:指明文件的类型
位置:文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见)
大小:指明文件大小
创建时间、上次修改时间、文件所有者信息
保护信息:对文件进行保护的访问控制信息

文件内部的数据应该怎样组织起来？（文件的逻辑结构）

在这里插入图片描述

无结构文件

无结构文件:文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。
无明显的逻辑结构
如:Windows操作系统中的.txt文件。

有结构文件

有结构文件:由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。
如:数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID)

根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。

根据有结构文件中的各条记录在逻辑上如何组织,可以分为三类：

顺序文件

顺序文件:文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。
各个记录在物理上可以顺序存储或链式存储。
在这里插入图片描述

在这里插入图片描述

结论:定长记录的顺序文件,若物理上采用顺序存储，则可实现随机存取;
若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录)

一般来说，“顺序文件”指的是物理上顺序存储的顺序文件。
顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

索引文件

在这里插入图片描述
索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。
可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。
可以用不同的数据项建立多个索引表。
每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

索引文件的缺点:每个记录对应一个索引表项，因此索引表可能会很大。
比如:文件的每个记录平均只占8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。
索引顺序文件中，同样会为文件建立一张索引表，一组记录对应一个索引表项。
索引顺序文件的索引项也不需要按关键字顺序排列,这样可以极大地方便新表项的插入

为了进一步提高检索效率，可以为顺序文件建立多级索引表。

文件之间应该怎样组织起来？（文件的目录结构）

文件控制块(实现文件目录的关键数据结构)

文件控制块FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。
FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等)，存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。

最重要，最基本的还是文件名、文件存放的物理地址。

需要对目录进行哪些操作?
搜索:当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
创建文件:创建一个新文件时，需要在其所属的目录中增加一个目录项
删除文件:当删除一个文件时，需要在目录中删除相应的目录项
显示目录:用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
修改目录:某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项(如:文件重命名)

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。

单级目录实现了“按名存取”，但是不允许文件重名。

两级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory)和用户文件目录(UFD，User Flie Directory) 。
主文件目录记录用户名及相应用户文件目录的存放位置
用户文件目录由该用户的文件FCB组成

允许不同用户的文件重名。文件名虽然相同,但是对应的其实是不同的文件。

用户(或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。
各级目录之间用“/”隔开。
从根目录出发的路径称为绝对路径。

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。

允许不同目录下的文件重名

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

无环图目录结构

在这里插入图片描述
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享同一目录下的所有内容)。
需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。
只有共享计数器减为0时，才删除结点。
注意:共享文件不同于复制文件。
在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

索引结点(对文件控制块的优化)：包含除了文件名之外的文件描述信息

在这里插入图片描述

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。
相比之下内存索引结点中需要增加一些信息，比如:文件是否被修改、此时有几个进程正在访问该文件等。

在这里插入图片描述

文件应如何存放在外存中？（文件的物理结构）

在这里插入图片描述

连续分配：每个文件在磁盘上占有一组连续的块。

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项(FCB)
物理块号=起始块号＋逻辑块号
当然，还需要检查用户提供的逻辑块号是否合法(逻辑块号≥长度就不合法)

优点:支持顺序访问和直接访问（即随机访问)；连续分配的文件在顺序访问时速度最快
缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片

链接分配

链接分配采取离散分配的方式，可以为文件分配离散的磁盘块。
分为隐式链接和显式链接两种。

隐式链接

在这里插入图片描述
隐式链接——除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
优点:很方便文件拓展，不会有碎片问题，外存利用率高。
缺点:只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接

在这里插入图片描述

显式链接——把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，FileAllocation Table)。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
优点:很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。
相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
缺点:文件分配表的需要占用一定的存储空间。

索引分配

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，
索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表-―建立逻辑页面到物理页之间的映射关系）。
索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

链接方案

多层索引

混合索引

在这里插入图片描述

操作系统如何管理外存中的空闲块？（文件存储空间管理）

存储空间的划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
存储空间的初始化：将各个文件卷划分为目录区、文件区
·目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息
·文件区用于存放文件数据

空闲表法：适用于“连续分配方式”

如何分配磁盘块:与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。
同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
如何回收磁盘块:与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：①回收区的前后都没有相邻空闲区;②回收区的前后都是空闲区;③回收区前面是空闲区;④回收区后面是空闲区。
总之，回收时需要注意表项的合并问题。

空闲链表法

在这里插入图片描述

空闲盘块链：适用于离散分配的物理结构

操作系统保存着链头、链尾指针。
如何分配:若某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。
如何回收:回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

空闲盘区链：离散分配、连续分配都适用

操作系统保存着链头、链尾指针。
如何分配:若某文件申请K个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区,分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。
如何回收:若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻,将回收区作为单独的一个空闲盘区挂到链尾。

位示图法：离散分配、连续分配都适用

位示图:每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。
如何分配:若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”;②根据字号、位号算出对应的盘块号，将相应盘块分配给文件;③将相应位设置为“1”。
如何回收:①根据回收的盘块号计算出对应的字号、位号;②将相应二进制位设为“0”

在这里插入图片描述

成组链接法：UNIX采用的策略，适合大型文件系统

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。
UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。
并且要保证内存与外存中的**“超级块”数据一致**。

文件的基本操作

创建文件

·进行Create系统调用时，需要提供的几个主要参数:
1．所需的外存空间大小(如:一个盘块，即1KB)
2．文件存放路径（“D:/Demo”)
3．文件名(这个地方默认为“新建文本文档.txt”)
·操作系统在处理Create系统调用时，主要做了两件事:
1．在外存中找到文件所需的空间(结合上小节学习的空闲链表法、位示图、成组链接法等管理策略，找到空闲空间)
2．根据文件存放路径的信息找到该目录对应的目录文件(此处就是D:/Demo目录)，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

删除文件

·进行Delete系统调用时，需要提供的几个主要参数:
1．文件存放路径（“D:/Demo”)
2．文件名(“test.txt”)
·操作系统在处理Delete系统调用时，主要做了几件事:
1.根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。
2.根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。(回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同，需要做不同的处理)
3.从目录表中删除文件对应的目录项。

打开文件

·在很多操作系统中，在对文件进行操作之前，要求用户先使用open系统调用“打开文件”，需要提供的几个主要参数:
1.文件存放路径(“D:/Demo”)
2.文件名(“test.txt”)
3.要对文件的操作类型（如:r只读;rw读写等)
·操作系统在处理open系统调用时，主要做了几件事:
1.根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的的目录项，并检查该用户是否有指定的操作权限。
2.将目录项复制到内存中的“打开文件表”中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。

系统的”打开文件表“：整个系统中只有一张；打开计数器字段记录此时有多少个进程打开了此文件
用户进程的”打开文件表“： ”访问权限“、“读写指针”：记录该进程对文件的读写操作进行到的位置

关闭文件

·进程使用完文件后，要“关闭文件”
·操作系统在处理Close系统调用时，主要做了几件事:
1.将进程的打开文件表相应表项删除
2.回收分配给该文件的内存空间等资源
3.系统打开文件表的打开计数器count减1，若count = 0，则删除对应表项。

读文件

进程使用read系统调用完成读操作。
·需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据(如:读入1KB）、指明读入的数据要放在内存中的什么位置。
·操作系统在处理read系统调用时，会从读指针指向的外存中,将用户指定大小的数据读入用户指定的内存区域中。

写文件

进程使用write系统调用完成写操作。
·需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如:写出1KB）、写回外存的数据放在内存中的什么位置
·操作系统在处理write系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。
在这里插入图片描述

文件共享

基于索引结点的共享方式（硬链接)

在这里插入图片描述

基于符号链的共享方式（软链接)

在这里插入图片描述

文件保护

口令保护

为文件设置一个“口令”，用户请求访问该文件时必须提供“口令”。
口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件
优点:保存口令的空间开销不多，验证口令的时间开销也很小。
缺点:正确的“口令”存放在系统内部，不够安全。

加密保护

使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密。
优点:保密性强，不需要在系统中存储“密码”
缺点:编码/译码，或者说加密/解密要花费一定时间。

访问控制

在每个文件的FCB(或索引结点）中增加一个访问控制列表（Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。
精简的访问列表:以“组”为单位，标记各“组”用户可以对文件执行哪些操作。当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。
优点:实现灵活，可以实现复杂的文件保护功能