第四章文件管理
一、文件逻辑结构
按照逻辑结构，文件可划分为：无结构文件、有结构文件
1.无结构文件
无结构文件：文件内部的数据是一系列二进制流或字符流组成。又称“流式文件”。
2.有结构文件
有结构文件：由一组相似的记录组成，又称“记录式文件”。
如：数据库表文件，每条记录有一个数据项可作为关键字。根据记录长度是否相等，可分为定长记录和可变长记录。
有结构文件按记录的组织形式可分为：顺序文件、索引文件、索引顺序文件
(1)顺序文件
顺序文件：文件中的记录一个接一个地顺序排列，记录可以是定长的也可以是可变长的。
各记录在物理上可以是顺序存储或链式存储。
一般顺序文件指的是物理上顺序存储的顺序文件。
顺序文件按照是否与关键字有关分为：
①串结构：记录之间的顺序与关键字无关，通常按照记录存入的时间决定记录的顺序
②顺序结构：记录之间的顺序按照关键字排序。
注：只有定长记录的顺序存储，才可实现随机存取。
(2)索引文件
索引文件：建立一张索引表，为每个主文件的记录在索引表中分别设置一个表项，包含索引号、长度、指针(逻辑起始地址)。索引表本身是定长记录的顺序文件，可以快速找到第i个记录对应的索引项。可以将关键字作为索引号内容。每当增加/删除记录时，需要对索引表进行修改。索引表具有很快的检索速度，因此主要用于信息处理的及时性要求较高的场合。
(3)索引顺序文件
索引顺序文件：是顺序文件和索引文件相结合。建立一张索引表，一组记录对应一个索引表项。
为了进一步提高检索效率，当记录过多时，可以建立多级索引文件。
二、文件目录
文件目录即是操作系统的“文件夹”。
目录本身就是一种结构文件，由一条条记录组成。文件中一条记录就是一个**“文件控制块(FCB)”**。
FCB实现了文件名和文件之间的映射，使用户可实现“按名存取”。FCB包含了文件的：
基本信息：文件名、物理地址、逻辑地址、物理结构等
存取控制信息：是否可读/可写、禁止访问的用户名单等
使用信息：文件的建立时间、修改时间等
2.1目录结构—单级目录结构
早期操作系统整个系统重只建立一张目录表，每个文件占一个目录项。实现了“按名存取”，但是不允许文件重名。在检查一个文件时，需要检查目录表中有没有重名文件。单级目录结构不适用于多用户操作系统。
2.2目录结构—两级目录结构
早期多用户操作系统，采用两级目录结构。分为主文件目录和用户文件目录。不同用户的文件允许重名。文件名虽然相同，但是对应的其实是不同文件。也可以在目录上实现访问限制。
2.3目录结构—多级目录结构
多级目录结构又称树形目录结构。用户要访问某个文件时要用文件路径名标识文件，各级目录之间用“ / ” 隔开。从根目录出发的路径称为“绝对路径”。从当前目录出发的路径称为“相对路径”。相对路径检索文件可以减少磁盘I/O次数。树形目录结构可以很方便对文件进行分类，层次结构清晰，有效地进行文件管理和保护。但不便于实现文件共享。
2.4目录结构—无环图目录结构
无向图目录结构：在树形目录结构的基础上，增加一些指向同一节点的有向边。可以方便实现多用户之间文件共享。可以用不同的文件名指向同一个文件，甚至可以指向同一个目录。需要为每个共享结点设置一个共享计数器，记录此时有多少个地方在共享该结点。用户提出删除结点请求时，只删除用户的FCB，并使共享计数器减1，不会直接删除共享结点，当共享计数器为0时才删除。
注：共享文件不同于复制文件，在共享文件中，由于用户指向的是同一个文件，只要一个用户修改了数据，那么都会看到文件数据的变化。
2.5索引结点(FCB的改进)
在查找各级目录的过程只需要用到“文件名”，因此通过引用索引结点来保存除文件名外的文件描述信息。
当找到文件名对应目录项时，才需要将索引结点调入内存。索引结点中记录了文件的各种信息，包括文件在外存的存储位置。存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为”内存索引结点“。因此，内存索引结点中需要增加一些信息。如：文件是否被修改、此时有几个进程正在访问该文件等。
三、文件的物理结构
操作系统需要对磁盘块进行管理：对非空闲磁盘块的管理(存放文件数据的磁盘块)、对空闲磁盘块的管理(文件存储空间管理)
文件分配方式有：连续分配、链接分配、索引分配
为了方便文件数据管理，文件的逻辑地址空间也被分为了一个个的文件块。
3.1连续分配
连续分配：要求每个文件在磁盘上占有一组连续的块
用户给出要访问的逻辑块号，物理块号=起始块号+逻辑块号。连续分配方式支持顺序访问和直接访问(随机访问)。在读取某个磁盘块时，需要移动磁头。访问两个磁盘块相隔越远，移动磁头所需时间就越长。所以连续分配文件在顺序读/写时速度最快。物理上采用连续分配的文件不方便拓展。并且存储空间利用率低，会产生难以利用得磁盘碎片。
3.2链接分配(隐式链接)
链接分配采用离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接、显式链接。
采用链接分配(隐式链接)方式，只支持顺序访问，不支持随机访问，查找效率低。采用链接分配(隐式链接)方便文件拓展，不会有碎片问题，外存利用率高。
3.3链接分配(显示链接)
用于链接文件的各物理块的指针显式地放在一张表中。也就是文件分配表(FAT)。
逻辑块号转成物理块号过程不需要读取磁盘操作。所以比隐式链接访问速度快。采用显式链接方式，支持顺序访问，也支持随机访问。不产生外部碎片。
四、文件存储空间管理
4.1空闲表法
空闲表法：用一个空闲盘块表来记录空闲的盘块。适用于连续分配方式。
分配和回收磁盘块：与内存管理中动态分区分配类似。
4.2空闲链表法
空闲链表法分为：空闲盘块链、空闲盘区链。
①空闲盘块连
操作系统保存着链头、链尾指针。分配：从联投开始一次摘下K个盘块分配，并修改空闲链的链头指针。回收：回收盘块一次挂到链尾，并修改空闲链的链尾指针。适用于离散分配的物理结构。
②空闲盘区链
操作系统保存着链头、链尾指针。
分配：按照一个算法规则，从链头开始检索找到合适的磁盘区分配给文件。
若没有合适的文件，可以把不同盘区的盘块同时分配给一个文件。分配后修改相应的链指针。
回收：若回收和某个空闲盘区相邻，将回收区合并到空闲盘区中。
若没有和空闲盘区响铃，将回收期作为单独的空闲盘区挂到链尾。
离散分配、连续分配都适用。为一个文件分配多个盘块效率高。
4.3位实图法
每个二进制位对应一个盘块，位示图一般用于连续“字”来表示，如下例是一个字的字长为16位，字中每一位对应一个盘块。”0“表示空闲，“1”表示已分配。
分配：顺序扫描位示图，找到相应的空闲空间分配给文件，并置为“1”表示已分配回收：根据回收盘块好计算出相应的位置，置“0”。连续分配、离散分配都适用。
4.4成组链接法
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。
UNIX系统采用了成组链接法队磁盘空闲块进行管理：
问卷目录区中专门用一个磁盘块作为“超级块“，当系统启动时需要将超级块读入内存，并保证内存和外存的超级块数据一致。
超级块：记录了下一组空闲盘块的数量，还有空闲块号。
五、文件的基本操作
操作系统为文件提供功能：创建文件create、删除文件delete、读文件read、写文件write、打开文件open、关闭文件close。
注：读/写操作之前需要打开文件，读/写操作结束需要关闭文件。
5.1创建文件
需要参数：所需外存空间大小、文件存放路径、文件名操作系统主要工作：在外存中找到文件所需的空间、创建该文件对应的目录项。
5.2删除文件
需要参数：文件存放路径、文件名操作系统主要工作：找到文件名对应的目录项、回收文件占用磁盘块、删除文件对应目录项
5.3打开文件
需要参数：文件存放路径、文件名、文件操作类型
操作系统主要工作：找到文件名对应的目录项、将目录项复制到内存中的“打开文件表”，并将编号返回给用户，用户使用打开文件表编号来指明要操作的文件。
在系统打开文件表中，有一个打开计数器，记录此时有多少个进程打开了此文件。
5.4关闭文件
进程使用完文件之后关闭文件，操作系统主要工作：
①将进程打开文件表相应表项删除
②回收分配的内存资源
③文件表打开计数器count减1，若count=0，删除对应表项
5.4读文件
操作系统主要工作：使用read系统调用完成读操作，从指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
5.4写文件
操作系统主要工作：使用write系统调用完成写操作，从用户指定的内存区域中，将指定大小数据写回写指针指向的外存。
六、文件共享
操作系统为用户提供共享功能，可以让多个用户共享地使用同一个文件。文件共享方式：基于索引结点的共享方式(硬链接)、基于符号链接的共享方式(软连接)
注：共享：多个用户共享一个文件，意味着系统中只有一份文件数据。在某个用户修改时，其他用户也看到变化。
复制：若每个用户都复制了同一个文件，系统中会有好几份文件数据。某个用户修改自己那份数据时，其他用户没影响。
6.1基于索引结点的共享方式
这种共享方式以多个文件目录链接到该索引结点上。
若某个用户决定“删除”文件，只是把用户目录中与该文件对应目录项删除，且索引结点的count减1。若count>0，还有其他用户在使用文件，不能把文件数据删除。若count=0，系统负责删除文件。
6.2基于符号链接的共享方式
这种共享方式，新建了一个Link类型文件，记录了目标文件的存放路径。类似于Windows操作系统的“快捷方式”。若目标文件删除，操作系统已经找不到此路径下的文件，所以这个路径失效了。
七、文件保护
操作系统为了保护文件数据的安全，有：口令保护、加密保护、访问控制
7.1口令保护
为文件设置一个口令，用户请求访问该文件时必须提供“口令”。口令一般存放在FCB中或者索引结点中，用户访问文件前需要先输入口令。优点：保存口令的空间开销不多，验证口令的开销时间也很小。缺点：正确的口令存放在系统内部，所以不够安全。
7.2加密保护
使用某个密码对文件进行加密，访问文件时需要提供正确的密码才能对文件进行正确的解密。优点：保密性强，不需要在系统中存储密码缺点：编码/译码，也就是加密/解密需要花费一定时间。
7.3访问控制
在文件的FCB中增加一个访问控制表，该表中记录了各个用户可以对文件执行的操作。访问类型：读、写、执行、添加、删除、列表清单(列出文件名和文件属性)。优点：实现灵活，可以实现复杂的文件保护功能。
八、文件系统层次结构
1.用户接口：用户需要通过操作系统提供接口发出请求
2.文件目录系统：由于用户提供的是文件的存放路径，因此操作系统需要一层一层查找目录找到对应目录项
3.存储控制模块：不同用户对文件有不同操作权限，为了保证安全，需要检查用户的权限
4.逻辑文件系统与文件信息缓冲区：验证了用户的访问权限后，需要把用户提供记录号转变为逻辑地址
5.物理文件系统：有了逻辑地址还需要转为物理地址
6.设备管理程序模块：要删除一条记录，需要磁盘设备发出请求
7.辅助分配模块：删除记录后，需要将空闲盘块进行回收。
八、文件系统层次结构
[外链图片转存中…(img-NOAGGBl9-1695460500972)]
1.用户接口：用户需要通过操作系统提供接口发出请求
2.文件目录系统：由于用户提供的是文件的存放路径，因此操作系统需要一层一层查找目录找到对应目录项
3.存储控制模块：不同用户对文件有不同操作权限，为了保证安全，需要检查用户的权限
4.逻辑文件系统与文件信息缓冲区：验证了用户的访问权限后，需要把用户提供记录号转变为逻辑地址
5.物理文件系统：有了逻辑地址还需要转为物理地址
6.设备管理程序模块：要删除一条记录，需要磁盘设备发出请求
7.辅助分配模块：删除记录后，需要将空闲盘块进行回收。
参考书籍：计算机操作系统(第四版）——汤小丹；王道操作系统复习指导 参考视频：王道计算机考研操作系统