操作系统 | 学习笔记 | 王道 | 4.1 文件系统基础

4.文件管理

4.1 文件系统基础

4.1.1 文件的基本概念

1. 定义

   文件是以计算机硬盘为载体的存储在计算机上的信息集合，在用户进行的输入、输出中，以文件位基本单位。

   文件管理系统是实现的文件的访问、修改和保存，对文件维护管理的系统。

2. 文件的组成

   • 存储空间：用于存储数据
   • 标签：便于对数据的分类和索引
   • 访问权限：不同用户对数据有不同的访问权限

3. 文件的结构

   • 数据项

     ：是文件系统中最低级的数据组织形式，可分为以下两种类型：

     • 基本数据项：用于描述一个对象的某种属性的一个值，是数据中的最小逻辑单位。
     • 组合数据项：由多个基本数据项组成。

   • 记录：是一组相关的数据项的集合，用于描述一个对象在某方面的属性。

   • 文件：是指由创建者所定义的、具有文件名的一组相关元素的集合，分为有结构文件和无结构文件两种。

     • 在有结构的文件中，文件由若干个相似的记录组成，如一个班的学生记录；
     • 无结构文件则被视为一个字符流，比如一个二进制文件或字符文件。

4.1.2 文件控制块和索引结点

• 文件控制块

  

• 索引节点

  

1. 文件的属性

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

2. 文件控制块FCB

   文件控制块（FCB）是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取"。

   操作系统通过文件控制块（FCB）来维护文件元数据。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。下图为一个典型的FCB。

   

   FCB包含以下信息：

   • 基本信息：如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
   • 存取控制信息：包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
   • 使用信息：如文件建立时间、上次修改时间等。

   一个文件目录也被视为一个文件，称为目录文件。

3. 索引结点

   在检索目录时，只用到了文件名，因此有的系统采用文件名与文件描述分开的方法，使文件描述信息单独形成一个称为索引结点的数据结构，简称 i 结点（inode)。

   在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。

   假设一个FCB为64B，盘块大小是1KB，则每个盘块中可以存放16个FCB（FCB必须连续存放），若一个文件目录共有640个FCB，则查找文件平均需要启动磁盘20次。

   而在UNIX系统中，一个目录项仅占16B，其中14B是文件名，2B是 i 结点指针。在1KB的盘块中可存放64个目录项。这样，可使查找文件的平均启动磁盘次数减少到原来的1/4，大大节省了系统开销。

   • 磁盘索引结点

     它是指存放在磁盘上的索引结点。每个文件有一个唯一的磁盘索引结点，主要包括以下内容：

     • 文件主标识符，拥有该文件的个人或小组的标识符。
     • 文件类型，包括普通文件、目录文件或特别文件。
     • 文件存取权限，各类用户对该文件的存取权限。
     • 文件物理地址，每个索引结点中含有13个地址项，即iaddr(0)～iaddr(12)，它们以直接或间接方式给出数据文件所在盘块的编号。
     • 文件长度，指以字节为单位的文件长度。
     • 文件链接计教，在本文件系统中所有指向该文件的文件名的指针计数。
     • 文件存取时间，本文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间。

   • 内存索引结点

     它是指存放在内存中的索引结点。当文件被打开时，要将磁盘索引结点复制到内存的索引结点中，便于以后使用。在内存索引结点中增加了以下内容：

     • 索引结点编号，用于标识内存索引结点。
     • 状态，指示 i 结点是否上锁或被修改。
     • 访问计数，每当有一进程要访问此 i 结点时，计数加1；访问结束减1。
     • 逻辑设备号，文件所属文件系统的逻辑设备号。
     • 链接指针，设置分别指向空闲链表和散列队列的指针。

4.1.3 文件的操作

1. 文件的基本操作

   文件属于抽象数据类型。为了正确地定义文件，需要考虑可以对文件执行的操作。操作系统提供系统调用，它对文件进行创建、写、读、重定位、删除和截断等操作。

   • 创建文件（create系统调用）

     • 为新文件分配必要的外存空间；
     • 在目录 中为之创建一个目录项，目录项记录了新文件名、在外存中的地址及其他可能的信息。

     

   • 删除文件（delete系统调用）

     • 先从目录中检索指定文件名的目录项
     • 然后释放该文件所占的存储空间，以便可被其他文件重复使用，并删除目录条目。

     

   • 读文件（read系统调用）（读指针）

     • 对于给定文件名，搜索目录以查找文件位置。
     • 系统维护一个读位置的指针。
     • 每当发生读操作时，更新读指针。

     

   • 写文件（write系统调用）

     • 对于给定文件名，搜索目录以查找文件位置。
     • 系统必须为该文件维护一个写位置的指针。
     • 每当发生写操作时，便更新写指针。

     

     一个进程通常只对一个文件读或写，因此当前操作位置可作为每个进程当前文件位置的指针。

     由于读和写操作都使用同一指针，因此节省了空间，也降低了系统复杂度。

   • 重新定位文件

     也称文件定位。搜索目录以找到适当的条目，并将当前文件位置指针重新定位到给定值。

     重新定位文件不涉及读、写文件。

   • 截断文件

     允许文件所有属性不变，并删除文件内容，将其长度置为0并释放其空间。

   这6个基本操作可以组合起来执行其他文件操作。例如，一个文件的复制，可以创建新文件、从旧文件读出并写入新文件。

2. 文件的打开与关闭

   • 打开文件（open系统调用）

     • 过程：调用open根据文件名搜索目录，将指明文件的属性（包括该文件在外存上的物理位置)，从外存复制到内存打开文件表的一个表目中，并将该表目的编号（也称索引）返回给用户。

     打开文件时并不会把文件数据直接读入内存。“索引号”也称“文件描述符”。

     打开以后，所有的read，write都是对文件描述符进行操作，而不是文件名

     打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作。

     

     如上图所示，在多个不同进程同时打开文件的操作系统中，通常采用两级表：整个系统表和每个进程表。

     • 整个系统的打开文件表包含FCB的副本及其他信息。
     • 每个进程的打开文件表根据它打开的所有文件，包含指向系统表中适当条目的指针。

     一旦有进程打开了一个文件，系统表就包含该文件的条目。当另一个进程执行调用open时，只不过是在其文件打开表中增加一个条目，并指向系统表的相应条目。

   

   • 关闭文件（close系统调用）
     • 1.将进程的打开文件表相应表项删除
     • 2.回收分配给该文件的内存空间等资源
     • 3.系统打开文件表的打开计数器count减1，若count=0，则删除对应表项。

   系统打开文件表为每个文件关联一个打开计数器（OpenCount)，以记录多少进程打开了该文件。

   文件名不必是打开文件表的一部分，因为一且完成对FCB在磁盘上的定位，系统就不再使用文件名。对于访问打开文件表的索引，UNIX称之为文件描述符，而Windows称之为文件句柄。
   因此，只要文件未被关闭，所有文件操作就通过打开文件表来进行。

   通常不管是系统还是进程的打开文件表在创建文件后都不会存储文件名，一般都用文件描述符

   • 打开文件信息
     • 文件指针。系统跟踪上次的读写位置作为当前文件位置的指针，这种指针对打开文件的某个进程来说是唯一的，因此必须与磁盘文件属性分开保存。
     • 文件打开计数。计数器跟踪当前文件打开和关闭的数量。因为多个进程可能打开同一个文件，所以系统在删除打开文件条目之前，必须等待最后一个进程关闭文件。
     • 文件磁盘位置。大多数文件操作要求系统修改文件数据。查找磁盘上的文件所需的信息保存在内存中，以便系统不必为每个操作都从磁盘上读取该信息。
     • 访问权限。每个进程打开文件都需要有一个访问模式（创建、只读、读写、添加等）。该信息保存在进程的打开文件表中，以便操作系统能够允许或拒绝后续的I/O请求。

   

4.1.4 文件保护

文件保护通过口令保护、加密保护和访问控制等方式实现。其中，口令和加密是为了防止用户文件被他人存取或窃取，而访问控制则用于控制用户对文件的访问方式。

1. 口令保护

   为文件设置一个“口令”，用户想要访问文件时需要提供口令，由系统验证口令是否正确。

   实现开销小，但“口令”一般存放在FCB或索引结点中（也就是存放在系统中）因此不太安全

2. 加密保护

   用一个“密码“对文件加密，用户想要访问文件时，需要提供相同的“密码“才能正确的解密

   安全性高，但加密解密需要耗费一定的时间（Eg：异或加密）

3. 访问控制

   • 访问类型

     对文件的保护可从限制对文件的访问类型中出发。可加以控制的访问类型主要有以下几种。

     • 读。从文件中读。
     • 写。向文件中写。
     • 执行。将文件装入内存并执行。
     • 添加。将新信息添加到文件结尾部分。
     • 删除。删除文件，释放空间。
     • 列表清单。列出文件名和文件属性。

     此外还可以对文件的重命名、复制、编辑等加以控制。这些高层的功能可以通过系统程序调用低层系统调用来实现。保护可以只在低层提供。

   • 访问控制

     解决访问控制最常用的方法是根据用户身份进行控制。而实现基于身份访问的最为普通的方法是，为每个文件和目录增加一个访问控制列表（Access-Control List，ACL），以规定每个用户名及其所允许的访问类型。

     • 优点：可以使用复杂的访问方法，
     • 缺点：长度无法预计并且可能导致复杂的空间管理，

     使用精简的访问列表可以解决这个问题，精简的访问列表采用拥有者、组和其他三种用户类型。

     • 拥有者。创建文件的用户。
     • 组。一组需要共享文件且具有类似访问的用户。
     • 其他。系统内的所有其他用户。

     文件主在创建文件时，说明创建者用户名及所在的组名，系统在创建文件时也将文件主的名字、所属组名列在该文件的FCB中。用户访问该文件时，

     • 若用户是文件主，按照文件主所拥有的权限访问文件；
     • 若用户和文件主在同一个用户组，则按照同组权限访问，
     • 否则只能按其他用户权限访问。

4.1.5 文件的逻辑结构

从用户角度看到的文件系统

文件的逻辑结构是从用户观点出发看到的文件的组织形式。文件的物理结构（存储结构）是从实现观点出发看到的文件在外存上的存储组织形式。

文件的逻辑结构与存储介质特性无关，它实际上是指在文件的内部，数据逻辑上是如何组织起来的。

1. 无结构文件（流式文件，如.txt文本文件）

   无结构文件将数据按顺序组织成记录并积累、保存，它是有序相关信息项的集合，以字节（Byte）为单位。

   • 只能通过穷举搜索的方式访问记录。
   • 其管理简单，用户操作方便。
   • 对基本信息单位操作不多的文件适于采用字符流的无结构文件。例如源程序文件、目标代码文件等。

2. 有结构文件（记录式文件，如数据库表文件）

   

   • 顺序文件

     文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。

     各个记录在物理上可以顺序存储或链式存储。

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

     • 顺序存储：

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

       若采用串结构，记录之间的顺序与关键字无关，无法快速找到某关键字对应的记录

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

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

     优点：读写一大批文件时，效率最高。适用于顺序存储设备（磁带）

     缺点：不方便增加、删除记录

   

   • 索引文件

     • 索引表：高效查询变长记录文件。索引表本身是定长记录的顺序文件，因此可以快速找到第ⅰ个记录对应的索引项。

       

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

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

   • 索引顺序文件

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

     • 将记录分组，每组对应一个素引表项
     • 检素记录时先顺序查索引表，找到分组，再顺序查找分组
     • 当记录过多时，可建立多级素引表

     

     如上图所示，主文件名包含姓名和其他数据项。

     • 姓名为关键字，索引表中为每组的第一条记录（不是每条记录）的关键字值，用指针指向主文件中该记录的起始位置。
     • 索引表只包含关键字和指针两个数据项，所有姓名关键字递增排列。
     • 主文件中记录分组排列，同一个组中的关键字可以无序，但组与组之间的关键字必须有序。
     • 查找一条记录时，首先通过索引表找到其所在的组，然后在该组中使用顺序查找，就能很快地找到记录。

   • 直接文件或散列文件（Hash File）

     给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。这种映射结构不同于顺序文件或索引文件，没有顺序的特性。

     散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。

4.1.6 文件的物理结构

从os的角度看文件系统

文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。

文件分配对应于文件的物理结构，是指如何为文件分配磁盘块。常用的磁盘空间分配方法有三种：连续分配、链接分配和索引分配。

1. 连续分配

   连续分配方法要求每个文件在磁盘上占有一组连续的块。磁盘地址定义了磁盘上的一个线性排序，这种排序使作业访问磁盘时需要的寻道数和寻道时间最小。

   • 物理块号=起始块号+逻辑块号
   • 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快。
   • 缺点：不方便文件拓展、存储空间利用率低、会产生磁盘碎片（外部碎片）。
     • ①文件长度不宜动态增加，因为一个文件末尾后的盘块可能已分配给其他文件，一旦需要增加，就需要大量移动盘块。
     • ②为保持文件的有序性，删除和插入记录时，需要对相邻的记录做物理上的移动，还会动态改变文件的长度。
     • ③反复增删文件后会产生外部碎片（与内存管理分配方式中的碎片相似）。
     • ④很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。
   • 访存次数：访问第n条记录需访问磁盘1次

2. 链接分配

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

   访问第n条记录需访问磁盘n次

   • 隐式链接

     除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

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

     指针在盘块当中，要知道下一块的话就必须读这块，会产生读磁盘操作，降低了一定的访问效率

   • 显式链接

     把用于链接文件各物理块的指针显式地存放在文件分配表（FAT）中。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。

     • 优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。
     • 缺点：文件分配表的需要占用一定的存储空间。
     • 结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问ⅰ号逻辑块时，并不需要依次访问之前的0~ｉ-1号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

   相比于隐式，逻辑块号到物理块号不需要读磁盘操作，文件访问效率更高

   • 文件分配表：FAT不仅记录了文件分配信息（显示链接），还“兼职”做了空闲块管理

     每个表项中还会存放下一块盘块号

     

3. 索引分配

   索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

   

   索引表的 逻辑块号 可以是隐含的，进一步节约空间；

   • 链接方案

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

     

     缺点：需要顺序访问，当文件很大时，查我效率低下

   • 多层索引

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

     

     采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

     缺点：即使是小文件，访问数据块也需受K+1次读磁盘

   • 混合索引

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

     

     

     所允许的文件最大长度：设有N0个直接地址项；N1个一次间接地址项；N2个二次间接地址项；每个盘块大小M字节；盘块号占m个字节，公式如下：
     $$文件最大长度=(N_0+N_1\cdot \frac{M}{m}+N_2\cdot (\frac{M}{m}{)}^2)\cdot M$$
     优点：对于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）

   • 总结

     

4.1.7 本节小结

1）什么是文件？

文件是以计算机硬盘为载体的存储在计算机上的信息集合，它的形式多样。

2）单个文件的逻辑结构和物理结构之间是否存在某些制约关系？

文件的逻辑结构是用户可见的结构，即从用户角度看到的文件的全貌。文件的物理结构是文件在存储器上的组织结构。它和文件的存取方法以及存储设备的特性等都有着密切的联系。单个文件的逻辑结构和物理结构之间虽无明显的制约或关联关系，但是如果物理结构选择不慎，也很难体现出逻辑结构的特点，比如一个逻辑结构是顺序结构，而物理结构是隐式链接结构的文件，即使理论上可以很快找出某条记录的地址，而实际仍需在磁盘上一块一块地找。
学到这里时，读者应能有这样的体会：现代操作系统的思想中，处处能见到面向对象程序设计的影子。本节我们学习的一个新概念一—文件，实质上就是一个抽象数据类型，也就是一种数据结构，若读者在复习操作系统之前已复习完数据结构，则遇到一种新的数据结构时，一定会有这样的意识：要认识它的逻辑结构、物理结构，以及对这种数据结构的操作。