操作系统6-文件系统

Posted on 2025-05-01

文件系统

概述

文件

文件中常保存的信息：

基本信息：文件名、文件类型、文件组织
地址信息：卷、起始地址、使用大小、分配大小
访问控制信息：所有者、访问信息、许可的行为
使用信息：数据创建、创建者身份、最后一次读访问的日期、最后一次读用户的身份、最后一次修改的日期、最后一次修改者的身份、最后一次备份的日期、当前使用

文件(file)的属性

长期存在：文件存储在硬盘或其他辅存中，用户退出系统时文件不会丢失
进程间共享：文件有名字，具有允许受控共享的相关访问权限
结构化：取决于具体的文件系统，一个文件具有针对某个特定应用的内部结构

文件系统

文件系统(file system)是操作系统的重要组成部分，允许用户创建成为文件的数据集；

文件类型

按用途分类：系统文件/用户文件/库文件
按数据形式分类：源文件/目标文件/可执行文件
按存取控制属性分类：只执行文件/只读文件/读写文件
按组织和处理方式分类：普通文件/目录文件/特殊文件

文件系统模型

管理对象：文件，目录，磁盘存储空间
对象操作和管理的软件集合：实现文件系统的功能
文件系统接口：命令接口/程序接口

文件操作

文件系统不但提供存储数据（组织为文件）的手段，而且提供一系列对文件进行操作的功能接口。

创建文件
删除文件
打开文件
关闭文件
读文件，写文件
截断文件
设置文件读写位置…

组织结构

文件结构

文件：具有文件名的一组相似记录的集合

域：基本的数据单元，一个域包含一个值，定长或变长
记录：一组相关域的集合，定长或变长，通常包含长度域

逻辑结构：从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。

物理结构：指文件在外存上的存储组织形式。

文件系统架构

设备驱动：程序直接和外围设备或其通道通信，驱动负责启动设备上的IO操作，处理IO请求的完成
基本文件系统：物理IO层，处理磁盘间交换的数据块，操作系统关注这些块在辅存和缓冲区的位置
逻辑IO：使得用户程序能访问记录，记录必须组成块进行IO操作
文件组织：用户访问文件的方法

文件组织

堆

堆是最简单的文件组织形式

数据按它们到达的顺序被收集。
堆的目的仅仅是积累大量的数据并保存
堆文件没有结构，堆对记录的访问是通过穷举查找方式进行的。

顺序文件

每条记录都使用一种固定的格式
所有记录都具有相同的长度由相同，并且数量、长度固定的域按特定顺序组成
每个域的域名和长度是该文件结构的属性。
关键域是记录的唯一标识，记录按关键域来存储

在顺序文件中，逻辑记录的顺序：

串结构：按照记录录入的时间排序
按关键字排序：有利于提高查询速度

对顺序文件的读写：

定长记录：易于定位，可随机读取
变长记录：不易定位，只能顺序读取
维护一个日志文件log：用于存放将更新到主文件的记录。

优点：

批处理时效率是所有逻辑文件中最高的
可存在于磁带上

缺点：

交互应用时“效率低”（如要查找单个记录），尤其是对变长记录的顺序文件。
增加、删除记录涉及到排序问题，开销大。

索引顺序文件

索引顺序文件是克服顺序文件缺点的常用办法

保留顺序文件的关键特征：记录按照关键域的顺序组织
用于支持随机访问的文件索引：提供了快速接近目标记录的查找能力
溢出文件：类似于顺序文件中使用的日志文件，但溢出文件中的记录可根据它前面记录的指针进行定位

检索文件：

利用用户(程序)所提供的关键字以及某种查找算法去检索索引表
找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置。
再利用顺序查找法去查找主文件，从中找到所要求的记录。

对于有N条记录的顺序文件中，设定一个M项的索引文件，索引的关键域均匀分布在主文件中，找到某条记录平均需要在索引文件中访问O(M/2)次，在主文件平均访问O(N/2M)次，索引顺序文件组织的开销为O(M/2+N/2M), 顺序文件组织查找某条记录平均开销为O(N/2);

索引文件

顺序文件和索引顺序文件都只允许按记录的唯一关键字检索记录，这不符合某些应用需要按多个字段检索记录的要求;

采用多索引的结构，成为查找条件的每个域都可能有一个索引;

完全索引：包含主文件中每条记录的索引项
部分索引：只包含那些有感兴趣域的记录的索引项

特点：

建立有序的索引表，查找很快，提高了速度，增加了存储开销(索引文件);
增、删记录时，对索引表作相应的修改

note:有时删除文件可能只是删除了其索引,这也是利用某些软件可以找回删除文件的原因；

直接或散列文件

而对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。

这是目前应用最为广泛的一种直接文件，它利用Hash 函数(或称散列函数)，可将记录键值转换为相应记录的地址。

存储空间管理

文件分配方法

连续分配：连续分配是指在创建文件时，给文件分配一组连续的块。以该方式管理的文件称为连续文件，可采用紧缩技术整理；

优点：简单、容易实现，对于顺序文件，能很快检索文件中的数据块,连续读/写多个数据块内容时，性能较好。
缺点：它不利于文件尺寸的动态增长，该分配方案可能会导致磁盘碎片，严重降低外存空间的利用率。

链式分配：为文件分配非连续的若干数据块，数据块之间用指针相连，，以该方式管理的文件称为链接文件，包含隐式链接和显式链接；

隐式链接：在文件目录的每个目录项中都须含有指向链接文件第一个盘块和最后一个盘块的指针，文件目录表中有start块号，每块中有下一块号；只适合于顺序访问，对随机访问效率低，可靠性差
显式链接：把用于链接文件各物理块的指针，显式地存放在内存的一张链接表中（整个磁盘仅设置一张）。查找在内存中进行，由于分配给文件的所有盘块号都放在该表中，故把该表称为文件分配表FAT(File Allocation Table)；
优点：链接分配技术不要求文件存储到彼此相邻的数据块中，消除连续分配引起的碎片，提高了外存空间的利用率。能适应文件尺寸的动态增长。
缺点：对于随机存取却相当低效，局部性原理不再适用；

索引分配：每个文件在文件分配表中存在一个一级索引，文件每个分区在索引上都有一个表项

空闲空间管理方法

位示图法：
- 每一位对应一个磁盘块。位的值为0或1，分别表示磁盘块空闲，或磁盘块已分配；
- 利用位表容易找到一个或一组空闲盘块  位表适合于以上各种文件分配方法；
- 位表很小，可以装入内存；
链接空闲区
- 每个空闲分区包含一个指向下一个分区的指针，并记载分区大小
- 无空闲分区表空间开销
- 适合于各种文件分配方法
- 若每次分配一个磁盘块，则可取空闲分区链的第一个盘块进行分配，并调整空闲分区链首指针和分区链大小
- 若采用可变分区法，可用首次适应算法，从链表头开始查找，找到的第一个适合的分区则可分配，然后调整空闲分区链首指针和分区链大小
索引
- 将空闲分区视为文件，按文件存储空间分配法为空闲分区建立索引
- 索引表中为每一个空闲分区建立一个索引项
- 为可变分区建立索引比为磁盘块建立索引效率高
- 适合于各种文件分配法
空闲块列表
- 在这种方法中，每块都指定一个序号，所有空闲块的序号保存在磁盘的一个保留区中。
- 两种有效技术把该表一小部分保存到内存中：将表看作堆栈/FIFO队列；

文件目录管理

文件目录

有的系统将其中部分信息保存在文件头部，只将一些必要信息如文件名、文件大小、外存中的存储位置等保存在文件目录中；

典型操作：查找、创建文件、删除文件、显示目录、修改目录

管理要求：实现“按名存取”，提高对目录的检索速度，文件共享，允许文件重名

文件控制块和索引结点

文件控制块(file control block, FCB):用于描述和控制文件的数据结构,用于记载文件在内存中的使用情况;

基本信息类：文件名，文件物理位置，文件逻辑结构，文件的物理结构
存取控制类信息：权限
使用信息：记录信息，如日期等

索引结点：包含文件描述信息，把文件名与文件描述信息分开，在文件目录中的每个目录项仅由文件名和指向该文件所对应的 i 结点的指针所构成。目录结构

磁盘索引结点：包含文件主标识，文件类型，文件存取权限，物理地址，文件长度，连接（共享）计数，存取时间等；
内存索引结点：文件打开后，将磁盘索引结点的内容部分或全部子集拷贝到内存，并增加以下内容：编号，状态，共享计数，逻辑设备号，链接指针

目录结构

单级目录结构：所有用户的全部文件目录保存在一张目录表中，每个文件的目录项占用一个表项，目录项中主要记载的信息有：文件名及扩展名，文件的物理地址，其它属性，如文件长度、建立日期、文件类型等

优点：简单且按名存取

缺点：查找速度慢，不允许重名，不便于实现文件共享；
两级目录结构：每一个用户建立一个单独的用户文件目录UFD，再建立一个主文件目录MFD。在主文件目录中，每个用户目录文件都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针

优点：提高了检索目录的速度，在不同的用户目录中，可以使用相同的文件名，不同用户还可使用不同的文件名来访问系统中的同一个共享文件
树型目录结构：

主目录在这里被称为根目录，把数据文件称为树叶，其它的目录均作为树的结点

路径名：从树的根（即主目录）开始，把全部目录文件名与数据文件名，依次地用“/”连接起来，即构成该数据文件的路径名

工作目录：即当前目录，进程对各文件的访问都相对于“当前目录”而进行，通常称为相对路径。

增加目录：在用户要创建一个新文件时，只需查看在自己的 UFD及其子目录中，有无与新建文件相同的文件名。若无，便可在UFD或其某个子目录中增加一个新目录项。

删除目录：例如Linux中，不删除非空目录rmdir如果该目录内包含文件或子目录，系统会拒绝执行删除操作,可删除非空目录rm -r在尝试删除一个目录时，即使该目录内包含文件或子目录，系统也会允许执行删除操作

目录查询技术

过程：文件名-目录项（FCB）或索引结点-盘块号-启动磁盘-驱动程序

例如查询：/usr/ast/mbox

根中得usr的索引结点号6
6中得usr目录文件为132#
132#中得/usr/ast的索引结点是26
26中的/usr/ast目录文件中406#
406#中得/usr/ast/mbox的索引结点是60
60中得/usr/ast/mbox的物理地址

FAT文件系统

早期的MS-DOS采用FAT12,后演变为FAT16,在windows95和98中升级成FAT32；

FAT12：以盘块为基本分配单位，每个分区设置两张文件分配表FAT1,FAT2,系统设置文件分配表FAT，在 FAT 的每个表项中存放下一个盘块号；当达到文件尾的时候，存入0xFFF，标志结束

为了适应更大容量的磁盘，因而以簇为单位进行分配，簇越小磁盘浪费的空间就越小；
簇一般由2n个盘块组成，与扇区的数量、磁盘容量的大小直接有关
对所允许的磁盘容量存在着严重的限制，虽然可以用继续增加簇的大小来提高所允许的最大磁盘容量，但随着支持的硬盘容量的增加，相应的簇内碎片也将随之成倍地增加。

FAT16： FAT 表的宽度增至16 位，最大表项数将增至$2^{16}$个，此时便能将一个磁盘分区分为$2^{16}$个簇。可以管理的最大分区空间为(1<<16 )×64 ×512B = 2048 MB

当磁盘容量迅速增加时，如果再继续使用FAT16，由此所形成的簇内碎片所造成的浪费也越大。(簇越大，一般磁盘的碎片就越多

FAT32: FAT32保留扇区的数目默认为32个而不是FAT16的1个

FAT32的根目录等同于普通的文件;
根目录储在分区内可寻址的任意簇内，不过通常根目录是最早建立的
根目录下的所有文件及其子目录在根目录的文件目录表 FDT中都有一个“目录项”，系统以32个字节为单位进行目录文件所占簇的分配，因此32个扇区的根目录FDT 最多可以记录32*512/32=512个文件或子目录。
DATA区是实际的文件和目录数据存储的区域，它占据了分区的绝大部分。 每个簇只能被一个文件占有，因而常常文件的尾部会出现不可利用的空间，所以簇越大，文件数目越多时，零头就越多，造成资源浪费，因此簇的大小不应该太大。FAT32采用4KB的簇的大小。
不能采用太小的单位进行分配。如采用大小为512B的扇区管理会增加FAT表的项数，对大文件存取增加消耗，文件系统效率不高

文件系统格式化

格式化程序并没有把DATA区的数据清除，只是重写了 FAT表而已，至于分区硬盘，也只是修改了MBR和 DBR，绝大部分的DATA区的数据并没有被改变;
因而进行上述操作后，数据仍然可以得到恢复

NTFS文件系统

使用了64 位磁盘地址;
很好地支持长文件名;
具有系统容错功能;
提供了数据的一致性;

磁盘组织:以簇作为磁盘空间分配和回收的基本单位,卷上簇的大小称为“卷因子”（一个簇包含2n个盘块）,对于簇的定位，采用逻辑簇号LCN和虚拟簇号VCN进行的。

文件组织：在NTFS 中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT中。卷中的每个文件作为一条记录，在MFT 表中占有一行，其中还包括MFT 自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。 NTFS 文件不能被FAT 等文件系统所存取，缺乏兼容性。文件通过主文件表（MFT）来确定其在磁盘上的存储位置。主文件表是一个对应的数据库，由一系列的文件记录组成–卷中每一个文件都有一个文件记录（对于大型文件还可能有多个记录与之相对应）。NTFS卷上的每个文件都有一个64位（bit）称为文件引用号（File Reference Number，也称文件索引号）的唯一标识。文件引用号由两部分组成：一是文件号，二是文件顺序号。NTFS使用逻辑簇号（Logical Cluster Number，LCN）和虚拟簇号（Virtual Cluster Number，VCN）来进行簇的定位。LCN是对整个卷中所有的簇从头到尾所进行的简单编号。VCN则是对属于特定文件的簇从头到尾进行编号，以便于引用文件中的数据。VCN可以映射成LCN，而不必要求在物理上连续。

文件系统结构：

启动扇区文件$BOOT位于磁盘头部，$BOOT中包含 MFT的位置数据。
主文件表索引的第一个文件为$MFT。主文件的每一个表项表示一个文件索引，每个文件索引由一系列的属性组成。

NTFS元文件: MFT的前16个元数据文件非常重要，为了防止数据的丢失， NTFS系统在该卷文件存储部分的正中央对它们进行了备份。

MFT中的第1个记录就是MFT自身;
由于MFT文件本身的重要性，为了确保文件系统结构的可靠性，系统专门为它准备了一个镜像文件$MftMirr，也就是MFT中的第2个记录。
第3个记录是日志文件$LogFile。该文件是NTFS为实现可恢复性和安全性而设计的。当系统运行时NTFS 就会在日志文件中记录所有影响NTFS卷结构的操作，包括文件的创建和改变目录结构的命令，例如复制，从而在系统失败时能够恢复NTFS卷。
第4个记录是卷文件$Volume，它包含了卷名、被格式化的卷的NTFS版本和一个标明该磁盘是否损坏的标志位。
第5个记录是属性定义表$AttrDef，其中存放了卷所支持的所有文件属性，并指出它们是否可以被索引和恢复等;
第6个记录是根目录（\），其中保存了存放于该卷根目录下所有文件和目录的索引。在访问了一个文件后， NTFS就保留该文件的MFT引用，第二次就能够直接进行对该文件的访问
第7个记录是位图文件$Bitmap。NTFS卷的分配状态都存放在位图文件中，其中每一位（bit）代表卷中的一簇，标识该簇是空闲的还是已被分配了的，由于该文件可以很容易的被扩大，所以NTFS的卷可以很方便的动态的扩大，而FAT格式的文件系统由于涉及到FAT表的变化，所以不能随意的对分区大小进行调整。
第8个记录是引导文件$Boot，它是另一个重要的系统文件。
第9个记录是坏簇文件$BadClus，它记录了磁盘上该卷中所有的损坏的簇号，防止系统对其进行分配使用。
第10个记录是安全文件$Secure，它存储了整个卷的安全描述符数据库。NTFS文件和目录都有各自的安全描述符，为了节省空间，NTFS将具有相同描述符的文件和目录存放在一个公共文件中。
第11个记录为大写文件$UpCase，该文件包含一个大小写字符转换表。
第12个记录是扩展元数据目录$Extended metadata directory。
第13个记录是重解析点文件$Extend\$Reparse

Linux文件系统

Linux是一个unix类操作系统,用EXT2文件系统结构,以下是查找文件的过程

当访问一个文件时，通过文件名在“目录表”中查到其“索引节点号”。
通过“索引节点号”查“索引节点表”。
通过“索引节点表”得到其“索引节点”；
通过索引节点得到文件数据所在位置

EXT2文件系统的物理结构：整个盘卷由多个数据块组构成。一个数据块代表一个文件系统

超级块：存储着描述文件系统大小和形状的基本信息；
组描述符：描述它的数据结构。（块位图大小、索引节点位图大小、索引节点表大小、空闲块数、空闲索引节点数、已用目录数等重要信息）；
块位图：描述了该块组中数据块空间的使用情况，在数据块分配和数据块撤销时使用；
索引节点位图：描述了该块组索引节点表所占空间的信息，在索引节点的分配和撤销中使用；
索引节点表：记录了本块组中索引节点集合；
数据块：用于存放文件数据；

EXT2的目录

一个文件对应有一个目录项；
目录项包含该文件对应的索引节点号、文件名、名字长度等信息；
目录是一些特殊的文件，称为目录文件，其中包含了该目录下所有文件的目录项集合。

EXT2的索引节点

Mode：用户拥有的权限r,w,e
Owner Information：文件或目录所有者的用户和组标识符
Size：文件大小
Timestamps：索引节点建立的时间和索引节点最后修改的时间
Data blocks：描述文件的数据块

文件控制块

当打开一个EXT2文件时，把要打开文件的管理控制信息从辅存的目录项和索引节点中读到内存，形成FCB，并将该FCB的地址以一个文件描述符（FD）的形式返回给用户进程;
根据FD可获得文件的描述信息,通过这些信息用户可对实际物理文件进行操作

linux的虚拟文件系统VFS: 将实际的文件系统的数据结构转换成统一的内存VFS的数据结构来兼容多种文件系统类型

数据缓存：任何一个从块设备中读取的数据块或者往块设备中写入的数据块都要通过缓存，缓存中的数据块是以拥有此数据块的设备的设备标识符和缓冲区的块号来唯一标识的；
1. 空闲的缓冲区链表
2. 非空闲的缓冲区：由指针数组构成的散列表，散列表中hash值由设备的标识符和数据块的块号产生的，表中的指针指向具有相同hash值的缓冲区。
缓冲区的状态类型：clean,locked,dirty,shared, unshared

bdflush守护进程: 使用bdflush内核守护进程来完成缓存管理,在系统启动时作为一个系统的线程运行，在大部分时间中，此守护进程都处于睡眠状态，等待系统中被改动的数据块缓冲区的数量增大到一定的值，bdflush守护进程将被唤醒,任务是当缓存中被改动的缓冲区数量太多时，提供一个管理功能
索引结点缓存：索引节点缓存可以加快对系统中文件的存取,使用散列表实现，表项的hash值是通过索引节点号和存储文件系统的物理设备号计算出来的，各表项指向具有相同hash值的VFS索引节点链表的指针。

操作：如果系统在索引节点缓存中找到索引节点，那么此索引节点的计数器将加1，表明又有一个进程在使用该索引节点。否则，系统必须申请一个空闲的VFS索引节点，系统读取该索引节点到内存缓存。如果系统已经没有可分配的空闲索引节点时，那么必须查找一个已用的索引节点，将那些用户计数器为0 的索引节点重新分配（说明系统中没有任何进程正在使用这些索引节点），一些非常重要的索引节点，如文件系统的根目录索引节点，它们的索引节点计数器总是大于0，以保证永远不能被重新分配。不论用什么方法找到一个新的索引节点，系统都必须调用一个特殊的子程序来把实际文件的信息添加到此索引节点中。当向新的索引节点中写入信息时，锁定此索引节点，将索引节点计数器置为1，直到索引节点中的信息写完后，再解锁。如果它被锁定时，则其他需要访问该索引节点必须等到解锁后才能进行。
目录缓存：为了加速对常用目录的存取， VFS维护一个两层LRU目录缓存链表。目录缓存包括一个散列表，表的hash值由设备号和目录名来计算，每个表项指向具有相同hash值的目录缓存链表的指针。当读取一个目录时，目录的详细信息将添加到目录缓存中