第4章-文件管理-文件系统(上)

• 初识文件管理

• 文件的属性

• 操作系统向上提供的功能

• 从上往下看，文件应如何存放在外存

• 文件的逻辑结构

• 顺序文件

• 索引文件

• 索引顺序文件

• 多级索引顺序文件

• 有结构文件

• 文件目录

• 单级目录结构

• 两级目录结构

• 多级目录结构（树形目录结构）

• 无环图目录结构

• 文件控制块

• 目录结构

• 索引结点（FCB改进）

• 文件的物理结构

• 连续分配

• 链接分配

• 索引分配

• 文件块、磁盘块

• 文件分配方式

第4章-文件管理-文件系统(上)

初识文件管理

文件的属性

1. 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件。同一目录下不允许有重名文件

2. 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称

3. 类型：指明文件的类型

4. 位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）

5. 大小：指明文件大小

6. 创建时间、上次修改时间、文件所有者信息

7. 保护信息：对文件进行保护的访问控制信息

无结构文件（如文本文件）：由一些二进制或字符流组成，又称“流式文件”

有结构文件（如数据库表）：由一组相似的记录组成，又称“记录式文件”

有结构文件中，各个记录间应该如何组织的问题——应该顺序存放？还是用索引表来表示记录间的顺序？——这是“文件的逻辑结构”重点要探讨的问题

操作系统向上提供的功能

• 创建文件：点击新建后，图形化交互进程在背后调用了create系统调用

• 读文件：将文件数据读入内存，才能让CPU处理（双击后，记事本应用程序通过操作系统提供的“读文件”功能，即read系统调用，将文件数据从外存读入内存，并显示在屏幕上）

• 写文件：将更改进的文件数据写回外存（在机身应用程序中编辑文件内容，点击“保存”后，记事本应用程序通过操作系统提供的写文件功能，即write系统调用，将文件数据从内存写回外存

• 删除文件：点了“删除”之后，图形化交互进程通过操作系统提供的“删除文件”功能，即delete系统调用，将文件数据从外存中删除

• 打开文件：open系统调用

• 关闭文件：close系统调用

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

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

从上往下看，文件应如何存放在外存

与内存一样，外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据（如1B），每个存储单元对应一个物理地址

类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”，每个磁盘块的大小是相等的，每块一般包含2的整数次幂个地址。同样类似的是，文件的逻辑地址也可以分为（逻辑块号，块内地址），操作系统同样需要将逻辑地址转为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块的大小

操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但它依然需要占用1KB的磁盘块。外存中的数据读入内存时同样以块为单位

文件的逻辑结构

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的

类似于数据结构的“逻辑结构”和“物理结构”。如“线性表”就是一种逻辑结构，在用户看来，线性表就是一组有先后关系的元素序列，如a,b,c,d,e…“线性表”这种逻辑结构可以用不同的物理结构实现，如顺序表/链表。顺序表的各个元素在逻辑上相邻，在物理上页相邻；而链表的各个元素在物理上可以是不相邻的。因此，顺序表可以实现“随机访问”，而“链表”无法实现随机访问

可见，算法的具体实现都与逻辑结构物理结构有关（文件也一样，文件的具体实现与文件的逻辑结构、物理结构都有关）

有结构文件

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

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

• 有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种

顺序文件

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

• 串结构：记录之间的顺序与关键字无关（通常按记录存入的时间决定记录的顺序）

• 顺序结构：记录之间的顺序按关键字顺序排列

假设：已经知道了文件的起始地址（也就是第一个记录存放的位置）

1. 思考1：能否快速找到第i个记录对应的地址？（即能否实现随机存取）

2. 思考2：能否快速找到某个关键字对应的记录存放的位置

• 顺序存储——逻辑上相邻的记录物理上也相邻（类似于顺序表）

• 若采用串结构，无法快速找到某关键字对应的记录

• 若采用顺序结构，可以快速找到某关键字对应的记录（如折半查找）

• 可变长记录：无法实现随机存取，每次只能从第一个记录开始往后查找

• 定长记录：可实现随机存取。记录长度为L，则第i个记录存放的相对位置是i*L。

• 链式存储——逻辑上相邻的记录物理上不一定相邻（类似于链表）无论是定长/可变长记录，都无法实现随机存取，每次只能从第一个记录开始依次往后找

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

一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

索引文件

对于可变长记录文件，要找到第i个记录，必须先顺序地查找签i-1条记录，到那时很多应用场景又必须使用可变长记录，如何解决这个问题？

索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。

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

另外，可以用不同的数据项建立多个索引表。如学生信息表中，可用关键字“学号”建立一张索引表，也可以用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。

索引顺序文件

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

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

多级索引顺序文件

为进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对一个含10^6个记录的文件，可先为该文件建立一张低级索引表，每100个记录分为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为建立其顶级索引表，故顶级索引表中共有100个表项

文件目录

文件控制块

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

目录文件中的一条记录就是一个“文件控制块（FCB)”

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

FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”

需要对目录进行哪些操作？

1. 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项

2. 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项

3. 删除文件：当删除一个文件时，需要在目录中删除相应的目录项

4. 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性

5. 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

目录结构

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立了一张目录表，每个文件占一个目录项。单机目录实现了“按名存取”，但是不允许文件重命名

显然，单级目录结构不适用于多用户操作系统

两级目录结构

早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User File Directory）

多级目录结构（树形目录结构）

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

从当前目录出发的称为相对路径。使用相对路径访问可以减少读磁盘IO操作的次数

无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图，可以更方便地实现多个用户间的文件共享

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

需要为每个空闲节点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB，并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点

注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化

索引结点（FCB改进）

其实在查找各级目录的过程中只要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息，因此可以考虑让目录表“瘦身”来提升效率

当找到文件名对应的目录项时，才需要将索引结点调入内存。索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等

文件的物理结构

文件块、磁盘块

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

内存与磁盘之间的数据交换（即读/写操作、磁盘IO）都是以“块”为单位进行的。即每次读入一块，或每次写出一块

在内存管理中，进程的逻辑地址空间被分为一个一个页面。同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式

文件分配方式

连续分配

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

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）

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

当然，还需要检查用户提供的逻辑块号是否合法（逻辑块号\ge长度就不合法）

可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问）

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间久越长。因此连续分配的文件在顺序读/写时速度最快

物理上采用连续分配的文件不方便拓展

物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价

总结：

• 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快

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

链接分配

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

• 隐式分配

目录中记录了文件存放的起始块号和结束块号。当然也可以增加一个字段来表示文件的长度。除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的。

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）

从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置……以此类推因此，读入i号逻辑块，总共需要i+1次磁盘IO。

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB

结论：采用链式分配（隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高

• 显式链接

显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）

注意：一个磁盘仅设置一张FAT，开机时，将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此“物理块号”字段可以是隐含的。

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项FCB

从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作

结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i号逻辑块），由于块号的转换过程并不需要访问磁盘，因此相比于隐式链接方式来说，访问速度快很多。显式链接也不会产生外部碎片，可以很方便地对文件进行拓展

索引分配

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

在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对应一张

如何实现文件的逻辑块号到物理块号的转换？

用户给出要访问的逻辑块号i，操作系统找到该文件的目录项FCB，从目录项FCB可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可知i号逻辑块在外存中的位置

可见，索引分配方式可以实现随机访问，文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）

但是索引表需要占用一定的存储空间

若每个磁盘块1KB，一个索引表项4B，则一个磁盘块只能存放256个索引项。如果一个文件的大小超过了256块，那么一个磁盘块时装不下整个文件的索引表的，如何解决这个问题？

1. 链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘IO次数过多，查找效率低下

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

   缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘

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

   优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少