OS-4 文件管理

前言

一个文件有哪些属性？

文件名。（note：同一目录下不允许有重名文件）
标识符。（os用来区分不同文件内部名称，对用户无意义）
文件类型。
文件位置。
- 文件存放的位置，让用户使用的。
- 在外存中的地址，让os使用的，用户不可见。
AND 大小、创建时间、保护信息等等。

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

无结构文件
有结构文件

文件之间应该怎样组织起来？– 目录结构⭐

目录 – 就是我们平时见到的文件夹

目录本质是一种有结构文件

（从上往下看）文件应该如何存放到外存？– 文件的物理结构⭐

类似于内存，外存也被分成一个一个块。

OS同样需要将逻辑地址（逻辑块号，块内地址）转化为外存的物理地址（物理块号，块内地址）。

（从下往上看）OS应该向上提供哪些功能？– 一系列系统调用

还有

打开文件【读写文件之前，需要“打开文件”】（open系统调用）

关闭文件【读写文件结束后，需要“关闭文件”】（close系统调用）

其他需要由OS实现的文件管理功能

OS如何管理外存中的空闲块（存储空间的管理）

文件共享。

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

回顾

文件的逻辑结构(2)

无结构文件

文件内部数据是一系列二进制流或者字符流组成，又称“流式文件”。

EG：txt文件。

有结构文件

由一组相似的记录组成，称为“记录式文件”。

每条记录又由若干项数据项组成。
- 其中，每条记录有一个数据项作为“关键字”（作标识id）
根据各条记录长度是否相等，分成定长记录和可变长记录。

有结构文件的逻辑结构(3)

==①顺序文件==
==②索引文件==
==③索引顺序文件==

顺序文件

逻辑上是顺序排列的。

影响因素：

物理上顺序存储 /或者/ 链式存储。（默认顺序存储）
记录可变长或者定长。
按是否根据关键字排列：
- 顺序结构：记录之间按关键字顺序排列。
- 串结构：记录之间的顺序与关键字无关。（一般按记录存入时间排序）

假设已知文件起始地址。

Q1：是否能快速知道第i个记录对应的地址？（能否随机查找）

Q2：是否能快速找到某个关键字对应记录存放的位置？（能否按关键字查找，即快速检索）

Answer

（顺序存储，定长记录 √）

（顺序存储，定长记录，顺序结构√）

（一般题目说的“顺序文件”，都是指 – 顺序存储的顺序结构的文件）

索引文件

前言：对于可变长文件，顺序文件的随机查找很麻烦。

新增一张索引表。（索引表本身是定长记录的顺序存储文件，所以方便随机查找哈哈哈）

优点：适合快速处理消息的场合。

缺点：增删记录时还需对索引表进行修改。

索引顺序文件

前言：如果每个记录都对应一个索引表项，那么索引表将会很大。

不是==一个记录==对应一个索引表项。

而是==一组记录==对应一个索引表项。（eg一张表记录同一个形式的学生）

进一步提高查找效率：多级索引顺序文件（适合超大数据）

（若索引表也按照顺序排序，也可实现快速检索）

回顾

文件目录

==一个文件对应一个FCB，一个FCB就是一个目录项，多个FCB组成文件目录。==

文件控制块/FCB/目录项

目录本身就是一种有结构文件。

目录由一条条记录组成。
- 每条记录对应一个，放在该目录下的文件。
- ==一条记录就是一个“文件控制块FCB”==

目录项中包含了文件的基本信息【文件名，文件的物理地址，文件访问权限等等】

对目录的基本操作

目录结构(4)

整个系统只建立一张目录表。每个文件占一个目录项。

缺点：

不允许文件重名。
不适合多用户操作系统。

解决了单级目录不允许重名的问题

主文件目录：记录用户名以及用户文件目录的存放位置。

用户文件目录：保存用户的文件。

缺点：用户不能对自己的文件进行分类，不够灵活。

绝对路径：从根目录出发的路径。

相对路径：从当前目录出发的路径。

绝对路径查找的过程：

从外存读入根目录的目录表。找到“照片”目录的存放位置。
从外存中读入对应的目录表。找到“2015-08”目录的存放位置。
从外存中读入对应的目录表。找到文件“xx.jpg”的存放位置。
3次读磁盘I/O操作。【很费时】

==查找完，读入节点也需要访问一次磁盘的！==（total = 3 + 1 = 4)

树形目录结构

优点：很方便对文件分类。

缺点：不便于实现文件的共享。（solution：无环图目录结构）

不同的文件名可以指向同一个文件（甚至是同一个目录），实现文件共享。

每个共享文件设置一个共享计数器，用于记录此时有多少在共享该文件。

（共享文件不是复制文件。eg如果有用户修改了文件，其他用户看得到文件的变化）

索引节点（FCB的改进）

FCB不必保存那么多信息，仅保存文件名就行，别的信息放到索引节点里面。

==这样子每个目录项就小了很多，一个磁盘块能放入很多的目录项，文件需要的磁盘块数少了，查找文件时！需要的磁盘IO也少了。==

当找到文件名对应的目录项后，才需要将索引节点都调入内存，从索引节点里面找到文件在外存中的存放位置，从而找到文件。

存放在外存中的索引节点称为“磁盘索引节点”，放入内存的索引节点称为“内存索引节点”。
（内存索引节点有：文件是否被修改，访问计数（有几个进程正在访问文件）等信息）
（磁盘索引节点有：链接计数（硬链接数量）等信息）

Note：查找文件需要访问磁盘，查找到文件后，将其索引节点读入内存，也需要访问磁盘！

目录的检索算法

顺序检索：采用的方法。

散列（哈希）检索：速度快，但是有冲突和溢出的缺点。

目录检索得到的是逻辑地址哦，需要进一步读磁盘，查找索引节点里面的物理位置信息。

回顾

文件物理结构(3)

– 对非空闲磁盘块的管理

文件的逻辑地址，以块的形式放入磁盘。

==磁盘块 == 物理块 ≠ 内存块== （不过大小相同）

连续分配

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

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

优点：支持顺序访问和随机访问。

缺点：不方便文件拓展。会产生磁盘碎片，空间利用率低。

不方便文件拓展：比如文件中间插入一块，需要将后面的所有盘块往后移动一块，产生很多IO操作。而别的两种方式只需修改指针或者索引，不需要移动盘块。

链接分配

A.隐式链接

用指针连接磁盘块。

文件目录项：记录了存放的起始块号，和结束块号和长度。

题目未指明，默认是隐式链接而不是显示链接。

优点：方便文件拓展。不会有碎片问题。

缺点：不支持随机访问，查找效率低。指针消耗一点点存储空间。

AND 逻辑块号转为物理块号的过程，磁盘IO过多。

例题：8个记录L1-L8，现在在L5L6之间插入一个Lx（已在内存中），需要进行的磁盘操作：5次读盘（L1-L5），2次写盘（写入空磁盘+修改L5磁盘的指针）【CPU 无法直接访问磁盘等外设的存储单元，所有对磁盘数据的操作都必须通过内存作为中介】

B.显式链接

有一个文件分配表（FAT）【一个磁盘只有一个，常驻内存】

因为FAT表项在物理上连续存储，所以“物理块号”字段可以隐含。

把链接各个文件的指针放在表里。

文件目录项：只需要记录文件的起始块号。

优点：方便文件扩展。没有碎片问题。支持随机访问

AND 逻辑块号转为物理块号的过程，不需要磁盘IO，文件的访问效率更高

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

索引分配(3)

每一个文件都有一个索引表。

索引表记录了文件各个逻辑块对应的物理块。

索引块在哪里，在每一个磁盘块中。

从文件目录可以找到索引块放在几号磁盘块，之后就可以找到磁盘块中的索引表了。

优点：可以随机访问。文件拓展方便。

缺点：索引表会占用一点存储空间。

若文件太大，导致索引表太大，可采用的方案

①链接方案

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

缺点：若需要访问文件的最后一个逻辑块，必须找到最后一个索引块（第256个索引块），即需先顺序地读入前255个索引块。

②多级索引

建立多级索引（原理类似多级页表）。使第一层索引块指向第二层的索引块。
Note：各层索引表大小不能超过一个磁盘块。
K层索引结构，（且顶级索引表未引入内存），访问一个数据块只需要K+1次读磁盘操作。

③混合索引

混合的索引方式。

优点：小文件只需较少的读磁盘次数(直接寻址）。中文件可以一次间接寻址。大文件可以二次间接寻址。

（Linux系统的inode结构）

回顾

①会根据多级索引，混合索引的结构计算出文件的最大长度。

②能自己计算某个数据块所需要的读磁盘数。

文件逻辑结构 VS 物理结构

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

由用户决定

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

由操作系统，根据存储器的特性决定
- 如磁带只能顺序存取，所以只能用顺序存储（连续分配或者隐式链接分配）
- 如磁盘可以随机存取，可以用不同的存储方式。
且OS负责将逻辑地址转为物理地址

容易混淆的地方

文件内部，各条记录链式存储：由创建文件的用户自己设计。

文件整体，用链接分配：由OS决定。

索引文件：从用户视角看，整个文件依然是连续存放的。

空闲磁盘块的管理

– 存储空间的管理之一。

存储空间划分和初始化

将物理磁盘划分为一个个的文件卷（/ 逻辑卷 / 逻辑盘）

每个文件卷进一步划分：

目录区：存放文件目录信息（FCB）
文件区：存放文件数据

（Note：有的系统支持多个物理卷组成一个超大文件卷）

空闲存储空间管理方法(4)

①空闲表法

用一个空闲表记录当前的空闲情况。（哪一个空闲盘有多少块空闲块）

适用于连续分配方式。

如何分配磁盘块：

与内存管理的动态分区分配类似。用一些算法为文件分配某一个区间（首次适应，最佳适应，最坏适应等等）

如何回收磁盘块：

与内存管理的动态分区分配类似。just合并！

②空闲链表法

空闲盘块链

以盘块为单位组成一条空闲链。
每一个空闲盘块中有指向下一个空闲盘块的指针。
适用于离散分配的物理结构。

空闲盘区链

以盘区为单位组成一条空闲链。
空闲盘区中有指向下一个空闲盘区的指针，和盘区的长度。
不仅适用于离散分配，也适用于连续分配的物理结构。

③位示图法

位示图的一个二进制位对应一个盘块。**==（字号，位号）与盘块号一一对应。==**

计算：盘块号 –（字号，位号）的相互转换。
注意从0开始还是从1开始。

==是位bit，不是字节Byte==

如何进行磁盘块的分配：

顺序扫描位示图。
根据字号，位号算出对应的盘块号。

如何回收磁盘块：

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

④成组链接法

适合大型文件系统。

==超级块==：每个超级块以及普通块，都记录了下一组空闲盘块数（普通块存在上限），和下一组空闲块号。

如何分配：

（超级块已读入内存）
检查第一个分组（不是超级块哦）的块数是否足够。
够：分配第一个分组中的x个空闲块，并修改相应数据。
如果第一个分组的数据all分出去了，需要其拥有的下一个组的分配信息复制到超级块中。

如何回收：

第一个分组没满，插到第一个分组中。
第一个分组满了，创建新的第一个分组。同时超级块的数据复制到新第一分组中，并修改超级块的数据。

回顾

文件的基本操作

打开文件 open系统调用⭐

==在外存中找到指定文件的目录项==

==复制目录项到内存中的“打开文件表”中，==

【打开文件表：已打开的文件信息的表，将指明文件的属性从外存复制到内存，再使用文件时直接返回索引。】

==并将“打开文件表”的索引号（⭐文件描述符）返回给用户。==

==之后用户使用该文件描述符来指要操作的文件。==

（用户首次访问某文件时，必须先通过系统调用open将其打开）

每一次open都会在：

进程的打开文件表中增加一个对应表目。
系统打开文件表只有在文件第一次被打开时才增加一个表目FCB。（FCB 在该过程中被读入内存）

open（）需要的几个主要参数：文件名，文件存放路径。

两种 “打开文件表”

系统打开文件表：里面主要是，编号，文件名，外存地址，打开计数器等。
进程打开文件表：里面主要是，编号，文件名，读写指针，访问权限，系统表索引号等。

关闭文件

将文件当前的控制信息从内存写回磁盘。（不是将文件数据写回磁盘。写文件操作才会写回磁盘（不考虑延迟写））
将进程打开的文件表相应表项删除。
回收分配给该文件的内存空间等资源。
系统打开文件表的打开计数器count-1，若count=0，则删除对应表项。

创建文件

步骤：

① 在外存中找到文件所需的空闲空间。
②（根据文件存放路径的信息找到该目录对应的目录文件，）在目录中创建该文件对应的目录项。

删除文件

读文件

按文件描述符，在打开文件表中找到文件的目录项。

（先）按存取控制说明检查访问的合法性。

（后）根据目录项中该文件的逻辑和物理组织形式，将逻辑记录号转成物理块号。

向驱动设备发出IO请求，完成数据交换。

写文件

回顾

文件共享

硬链接（基于索引结点）

当open调用的不同文件互为硬链接时，所打开的文件实体是一样的。（指向同一个索引节点）

建立硬链接时，引用计数值+1。

删除文件时，硬链接引用计数值-1（若值不为0，则不能删除此文件，因为还有其他硬链接指向此文件）

Note：

用户进程的打开文件表关于同一个文件不一定相同。
例如不同进程对同一文件的访问权限，当前读写位置指针可能不同。
硬链接查找速度快于软链接，因为其直接通过指针访问。

软链接（基于符号链）

查询多级目录，多次IO ，比较耗时。

建立符号链接时，引用计数值设置为1，不受链接文件的影响（即删除操作对于符号链接是不可见的，其值还是1）

（只不过以后在通过符号链接访问时，会发现文件不存在，到时候再删除符号链接）

回顾

文件保护

1.口令保护

2.加密保护

3.访问控制

对文件的访问控制，由 用户访问权限+文件属性 共同限制。

在FCB（或索引节点）中增加一个 **==访问控制表ACL==**。

表中记录了各个用户可以对该文件执行哪些操作。

精简版本的访问列表：以组为单位，而不是以个体为单位。

（一般分成三类：拥有者，组，其他）

回顾

文件系统

从用户看，引入文件系统的目的是，实现对文件的按名存取。

文件系统的层次图（opt）

文件系统的布局

文件系统在外存中的结构

1
2
3

主引导记录MBR：位于磁盘0号扇区。
分区表：记录各分区的起始与结束地址，并标记一个为活动分区。
MBR首先识别活动分区，随后读取该分区的第一个扇区，即引导块。

引导块：负责加载并启动该分区的操作系统。
超级块：存储文件系统的所有关键信息。（EG分区总块数，块大小，空闲块数量及其指针，空闲i节点数量及指针等）
空闲块信息：记录未分配的磁盘块。通常以位示图或者空闲链表实现。
i节点：每个文件对于一个i节点，其中完整描述了文件的各种属性。
根目录：作为整个目录树的起点。

文件系统在内存中的结构

内存中的挂载表
内存中目录项的缓存
系统打开文件表
进程打开文件表

虚拟文件系统

虚拟文件系统特点：

①向上层用户进程提供统一标准的系统调用接口。（屏蔽底层具体文件系统的实现差异）
②VFS要求下层的文件系统必须实现某些规定的函数功能，如open/read。

存在的问题：不同的文件系统，表示文件数据结构各不相同。打开文件后，其在内存中的表示就不同。

③每打开一个文件，VFS 在系统打开文件表中新建一个表项（含偏移量），但 ==vnode== 只在文件首次被访问时创建，后续打开复用已有 vnode。

VFS将其中的公共特性封装为四种对象：

VFS对象	创建时机	作用
超级块对象	文件系统挂载时	描述文件系统元数据（总块数、inode数、空闲块等）
V节点对象	文件首次被访问时	表示一个已打开的文件（含inode信息、操作函数指针）
目录项对象	路径遍历过程中	缓存路径名到vnode的映射（如 `"a.txt"` → vnode）
文件对象	每次 `open()` 调用	记录当前偏移量、打开模式、指向vnode的指针

文件系统挂载

文件系统的安装 / 装载 – 如何将一个文件系统挂载到OS中？

Note：同一个设备可以被挂载到多个不同挂载点，但同一个挂载点在同一时刻只能挂载一个设备。

Other

Unix操作系统中，文件的信息放在索引节点，而不是 超级块（描述文件系统的）中。

异步IO：发出IO请求后，系统不必等待IO完成，继续执行别的任务，IO完成再通知系统。这种方法可以提高CPU利用率。

为什么有的数据结构需要用数组实现？ – 因为需要随机存取。比如文件分配表，页表，中断向量表。

前言