文件管理

相信的心就是你的魔法！

初识文件管理

文件——一组有意义的信息/数据集合。

文件的属性：

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

文件内部组织

• 无结构文件：由一些二进制或字符流组成，又称“流式文件”。
• 有结构文件：由一组相似的记录组成，又称“记录式文件”。
  • 文件由一条条记录组成
    • 记录由一个个数据项组成。

文件之间如何组织

操作系统提供的功能

• 创建文件：creat系统调用
• 读文件：read系统调用
• 写文件：write系统调用
• 删除文件：delete系统调用
• 打开文件：open系统调用
• 关闭文件：close系统调用

文件如何存放在外存

其他由操作系统实现的文件管理功能

文件共享：多个用户可以共享使用一个文件。

文件保护：如何保证不同的用户对文件有不同的操作权限。

文件的逻辑结构

逻辑结构：在用户看来文件内部的数据应该是如何组织起来的。

物理结构：在操作系统看来，文件的数据是如何存放在外存中的。

无结构文件

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

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

有结构文件

由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字。

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

有结构文件的逻辑结构：

• 顺序文件
• 索引文件
• 索引顺序文件

顺序文件

文件中的记录一个接一个地顺序排列(逻辑上)，记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。

串结构：

• 记录之间的顺序与关键字无关。

顺序结构：

• 记录之间的顺序按关键字顺序排列。

存储结构

链式存储：无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后查找。

顺序存储：

• 可变长记录：无法实现随机存储。每次只能从第一个记录开始依次往后查找。
• 定长记录：可实现随机存取。第i个记录存放的相对位置是i*L
  • 若采用串结构：无法快速找到某个关键字对应的记录。
  • 若采用顺序结构：可以快速找到某个关键字对应的记录(如二分查找)

索引文件

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字二分查找。

每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

可以用不同的数据项建立多个索引表，实现多个字段的快速检索。

索引顺序文件

索引顺序文件中，同样会为文件建立一张索引表，但不同的是；并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。

在上图的示例中，学生记录按照学生姓名的开头字母进行分组。每个分组就是一个顺序文件，分组内的记录不需要按关键字进行排序。

多级索引顺序文件

可以为顺序文件建立多级索引表。例如，对于一个含$10^6$个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组。故低级索引表有$10^4$个表项，再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故索引表中共有100个表项。

文件目录

文件控制块(FCB)

目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个放在该目录下的文件。

目录文件中的一条记录就是一个文件控制块。

FCB中包含了文件的基本信息(文件名、物理地址、逻辑结构、物理结构等)，存取控制信息(是否可读/可写、禁止访问的用户名单等)，使用信息(如文件建立时间、修改时间等)。

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

需要对目录进行的操作：

• 搜索
• 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项。
• 删除文件：当删除一个文件时，需要在目录中删除相应的目录项。
• 显示目录：用户可以请求显示目录的内容
• 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项。

目录结构——单级目录结构

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

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才允许建立文件，并将新文件对应的目录项插入目录表中。

目录结构——两级目录结构

两级目录结构，分为主文件目录和用户文件目录。

• 允许不同用户的文件重名。
• 可以通过目录实现访问限制。
• 仍不可对用户自己的文件分类

目录结构——多级目录结构

从根目录出发称为绝对路径。

系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表，如寻找文件 /照片/2015-08/自拍.jpg，整个过程需要3次读磁盘的IO操作。

当前目录(解决上述问题)：

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

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

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录(共享同一目录下的所有内容)。

共享计数器：当两个用户共享同一个文件时，可以为文件设置一个共享计数器。用于记录此时有多少个地方在共享该节点。用户提出删除节点的请求时，只是删除该用户的FCB，并使共享计数器减1，并不会直接删除共享节点。

只有共享计数器减为0时，才删除节点。

索引节点(FCB的改进)

在查找各级目录时，只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表瘦身来提升效率。在目录表中只保留文件名与索引节点的指针。

其他信息全部存在索引节点中。

带来的好处：

假设一个FCB是64B，磁盘块的大小为1KB，则每个盘块中只能存放16个FCB。若一个文件目录中共有640个目录项，则共占用640/16 = 40个磁盘块。因此按照某文件名检索该目录，平均需要查询320个目录项，平均启动磁盘20次。

若使用索引节点机制，文件名占14B，索引节点指针占2B，则每个盘块可以存放64个目录项，那么按文件名检索目录平均只需要读320/64 = 5个磁盘块。

• 磁盘索引节点：存放在外存中的索引节点。
• 内存索引节点：当索引节点放入内存后。
  • 内存索引节点需要增加一些信息
    • 记录文件是否被修改
    • 有几个进程正在访问该文件。

文件的物理结构

文件分配方式

文件块/磁盘块

类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。

同样的，在外存管理中，文件的逻辑地址空间也被分为了一个一个的文件块。

连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。

文件目录中记录存放的起始块号和长度：

物理块号 = 起始块号 + 逻辑块号

优点：

• 支持顺序访问
• 支持直接访问/随机访问
• 磁盘顺序读写时间最快

缺点：

• 连续分配的文件不方便拓展
• 利用率低，会产生难以利用的磁盘碎片

链接分配——隐式链接

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

目录：

存储结构：

优点：

• 支持顺序访问
• 方便拓展文件

缺点：

• 不支持随机访问
• 查找的效率很低

链接分配——显式链接

把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表(FAT, File Allocation Table)。

目录：

假设某个新创建的文件”aaa”依次存放在磁盘块。2->5->0->1。

文件分配表FAT：

物理块号	下一块
0	1
1	-1
2	5
3
4
5	0
…	…

一个磁盘仅需设置一张FAT。开机时，将FAT读入内存并常驻内存。

物理块号字段可以隐含

优点：

• 逻辑块号转化为物理块号的过程不需要读磁盘操作。
• 支持顺序访问，也支持随机访问(在内存中先找到地址再去访问磁盘)。
• 访问速度快

缺点：文件分配表会占用一定的存储空间。

索引分配

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

目录：

存储结构：

索引表的逻辑块号可以是隐含的。

优点：

• 支持随机访问
• 方便实现文件拓展

缺点：索引表需要占用一定的空间。

针对超大文件的解决方案

链接方案

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

问题：当文件很大时，查找速率逐渐退化。最差时有N块索引表需要N次IO。

索引分配

多层索引：建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层索引块。还可以根据文件大小的要求再建立第三层、第四层索引表。

N层索引表只需要IO N+1次。

问题：当我访问一个小文件时，也需要3次IO。

混合分配

混合分配：多种索引分配方式的结合。例如：一个文件的顶级索引表中，即包含直接地址索引(直接指向数据块)，又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)。

访问0-7号逻辑块：2次读磁盘

访问8-263：3次读磁盘

重点：

• 要学会根据多层索引、混合索引的结构计算出文件的最大长度
  • Key: 各级索引表最大不能超过一个块
• 要能自己分析访问某个数据块所需要的读磁盘次数
  • Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。
• 注意题目条件：顶级索引块是否已调入内存

空闲磁盘块管理

存储空间的划分与初始化

存储空间管理——空闲表法

如何分配磁盘块：

• 与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。

如何回收磁盘块：

• 与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况：

  1. 回收区的前后都没有相邻空闲区
  2. 回收区的前后都是空闲区
  3. 回收区前面是空闲区
  4. 回收区后面是空闲区

  回收时需要注意表项的合并问题。

空闲链表法

空闲盘块链：以盘块为单位组成一条空闲链。

空闲盘区链：以盘区为单位组成一条空闲链。

空闲链表法

系统保存着链头、链尾指针。

如何分配：某文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲的链尾指针。

空闲盘区链

系统保存着链头、链尾的指针。

如何分配：可以采用首次适应、最佳适应等算法。

• 按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。
• 页可以将不同盘区的盘块同时分给一个文件。注意：分配后可能要修改相应的链指针、盘区大小等数据。

如何回收：

• 若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。
• 若回收区没有和任何空闲盘区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

为一个文件分配多个盘块时效率更高。

位示图法

位示图法：每个二进制位对应一个盘块。

0代表空闲，1代表已分配。

位示图一般用连续的“字”来表示，如本例中一个字的字长是16位，字中的每一位对应一个盘块。因此可以用(字号，位号)对应一个盘块号。

盘块号：b = n * i + j

字号：i = b/n

位号：j = b%n

连续分配和离散分配都适用。

如何分配：若文件需要K个块

1. 顺序扫描位示图，找到K个相邻或不相邻的“0”
2. 根据字号、位号算出对应的盘块号，将相应盘块分配给文件。
3. 将相应位设置为1。

如何回收：

1. 根据回收的盘块号计算出对应的字号、位号
2. 将相应二进制位设为0

成组链接法

文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存。并且要保证内存与外存中的超级块数据一致。

• 分组存储：将n个空闲块分为一组。
• 组内索引：当前组的第一个空闲块中，存储了该组中其他n-1个空闲块地址。
• 组间链接：当前组的最后一个空闲块中，记录了下一组空闲块的地址，从而将不同的组链接起来。

如何分配：

1. 分配1个空闲块：
   • 检查第一个分组的块数是否足够。1 < 100，因此是足够的。
   • 分配第一个分组中的第一个空闲块，并修改相应数据。
2. 分配100个空闲块：
   • 检查第一个分组的块数是否足够
   • 当把最后一个磁盘块分配出去时，需要把磁盘块中的数据复制到超级块中。

如何回收：

1. 假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块。
   • 直接插入第一个分组即可。
2. 假设第一个分组已经满了，还需要回收一块。
   • 需要将 超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

文件的基本操作

创建文件

进行Create系统调用时，需要提供的几个主要参数：

• 所需的外存空间大小
• 文件存放路径
• 文件名

操作系统的主要操作：

• 在外存中找到文件所需的空间。
• 在目录中创建该文件对应的目录项。

删除文件

提供的参数：

• 文件存放路径
• 文件名

操作系统执行Delete系统调用时，主要做了几件事：

• 从对应目录中删除文件名对应的目录项。
• 根据该目录项记录的文件在外存的位置、文件大小等信息，回收文件占用的磁盘块。

打开文件

用户在对文件进行操作前，需要执行open系统调用，需要的主要参数：

• 文件存放路径。
• 文件名。
• 对文件的操作类型。(r只读；rw读写)

操作系统的工作：

• 从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限。
• 将目录项复制到内存中的“打开文件表”中。并对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件(效率提升)。
• 系统打开文件表中的打开计数器+1。

进程与操作系统，各有自己的打开文件表：

• 打开计数器：记录打开文件的进程的数量。

关闭文件

进程使用完文件后，要关闭文件。

操作系统close调用的功能：

• 将进程的打开文件表相应表项删除。
• 回收分配给该文件的内存空间等资源。
• 系统打开文件表的打开计数器count-1，若count = 0，则删除该表项。

读文件

read系统调用需要的参数：

• 指明哪个文件(提供文件的索引号即可)
• 指明要读入多少数据。
• 指明读入的数据要存放在内存中的什么位置。

read系统调用的功能：

• 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

写文件

将更改过的文件数据写回外存。

wirte系统调用的参数：

• 指明是哪个文件
• 写多少数据
• 写回外存的数据存放在内存中的什么位置。

write系统调用的功能：

• 会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

文件共享

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件。

基于索引节点的共享方式(硬链接)

回顾索引节点

索引节点，是一种文件目录的瘦身策略。由于检索文件时只需要用到文件名，因此可以将除了文件名之外的其他信息放到索引节点中。这样目录项就只需要包含文件名、索引节点指针。

硬链接共享方式

让不同用户的目录项指向同一个索引节点。

count值：

• 若count = 2：此时有两个用户目录项链接到该索引结点上
• 若某个用户决定删除该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引节count值减1。
• 若count > 0：还有别的用户要使用该文件，暂时不能删除文件数据。
• 若count = 0 时系统将删除文件。

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

软链接是一个独立的文件，里面保存的是”目标文件的路径”

• 删除软连接不会影响目标文件
• 删除目标文件后，软链接会失效。

文件保护

口令保护

为文件设置一个”口令”(如”123456”)，用户请求访问该文件时必须提供”口令”。

优点：保存口令的空间开销不多，验证口令的时间开销也很小。

缺点：正确的”口令”存放在系统内部，不够安全。

加密保护

使用某个密码对文件进行加密，在访问时需要提供正确的密码才能对文件进行正确的解密。

优点：保密性高，不需要在系统中存储密码。

缺点：编码/译码，需要花费一定的时间。

访问控制

在每个文件的FCB(或索引节点)中增加一个访问控制列表(Access-Control List, ACL)，该表中记录了各个用户可以对该文件执行哪些操作。

缺点：当用户很多时，文件访问控制列表很长。

精简的访问列表

以组为单位，标记各组用户可以对文件执行哪些操作。

如：分为系统管理员、文件主、文件主的伙伴、其他用户几个分组。

当某用户想要访问文件时，系统会检查该用户所属的分组是否会有相应的访问权限。

文件系统的层次机构

文件系统的全局结构(布局)

物理格式化

物理格式化，即低级格式化——划分扇区，检测坏扇区，并用备用扇区替换坏扇区。

硬盘在后台自动完成坏扇区替换，而操作系统完全察觉不到

逻辑格式化

逻辑格式化后，磁盘分区，完成各分区的文件系统初始化。

文件系统在内存中的结构

虚拟文件系统

虚拟文件系统(VFS)：

• 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异。

• VFS要求下层的文件系统必须实现某些规定的函数功能。

• 每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件。

  

文件系统挂载

文件系统挂载：即文件系统安装/装载。

如何将一个文件系统挂载到操作系统。

文件系统挂载的工作：

1. 在VFS中注册新挂载的文件系统。(内存中的挂载表)
2. 新挂载的文件系统，要向VFS提供一个函数地址列表
3. 将新文件系统加载到挂载点。