《现代操作系统》-读书笔记-第四章-文件系统

《现代操作系统》-读书笔记-第四章-文件系统

所有的计算机应用程序都需要存储和检索信息。

因此,长期存储信息有三个基本要求:

1) 能够存储大量信息。

2) 使用信息的进程终止时,信息仍旧存在。

3) 必须能使多个进程并发访问有关信息。

磁盘(magnetic disk)由于其长期存储的性质,已经有多年的使用历史。近些年,固态硬盘逐渐流行起来,因为它不仅没有易损坏的移动部件,而且可以提供快速的随机访问。相比而言,虽然磁带和光盘也被广泛使用,但是它们的性能相对较差,通常应用于备份。目前可以先把磁盘当作一种大小固定的块的线性序列,并且支持如下两种操作:

1) 读块 k;

2) 写块 k。

事实上磁盘支持更多的操作,但只要有了这两种操作,原则上就可以解决长期存储的问题。

不过,这里存在着很多不便于实现的操作,特别是在有很多程序或者多用户使用着的大型系统上(如服务器)。在这种情况下,很容易产生一些问题,例如:

1) 如何找到信息?

2) 如何防止一个用户读取另一个用户的数据?

3) 如何知道哪些块是空闲的?

就像操作系统提取处理器的概念来建立进程的抽象,以及提取物理存储器的概念来建立进程(虚拟)地址空间的抽象那样,我们可以用一个新的抽象一文件来解决这个问题。

文件是进程创建的信息逻辑单元。一个磁盘一般含有几千甚至几百万个文件,每个文件是独立于其他文件的,唯一不同的是文件是对磁盘的建模,而非对 RAM 的建模。事实上,如果能把每个文件看成一个地址空间,那么读者就能理解文件的本质了。

进程可以读取已经存在的文件,并在需要时建立新的文件。存储在文件中的信息必须是持久的,也就是说,不会因为进程的创建与终止而受到影响。一个文件只能在其所有者明确删除它的情况下才会消失。

文件是受操作系统管理的。有关文件的构造、命名、访问、使用、保护、实现和管理方法都是操作系统设计的主要内容。

文件

文件命名

文件是一种抽象机制,它提供了一种在磁盘上保存信息而且方便以后读取的方法。这种方法可以使用户不必了解存储信息的方法、位置和实际磁盘工作方式等有关细节。

文件的具体命名规则在各个系统中是不同的,不过所有的现代操作系统都允许用1至8哥字幕组成的字符串作为合法的文件名。

有些文件系统区分大小写字母,有的不区分。UNIX属于前一类,老的文件系统MS-DOS则属于后一类。

许多操作系统支持文件名用圆点隔开分为两部分,如文件名 prog. C。圆点后面的部分称为文件扩展名(file extension),文件扩展名通常表示文件的一些信息,如 MS-DOS 中,文件名由 1 至 8 个字符以及 1 至 3 个字符的可选扩展名组成。在 UNIX 里,如果有扩展名,则扩展名长度完全由用户决定,一个文件甚至可以包含两个或更多的扩展名。如 homepage. Html. Zip,这里。Html 表明 HTML 格式的一个 Web 页面,。Zip 表示该文件(homepage html)已经采用 zip 程序压缩过。一些常用文件扩展名及其含义如图 4-1 所示。

在某些系统中(如所有 UNIX 版本),文件扩展名只是一种约定,操作系统并不强迫采用它。File. Txt 的文件也许是文本文件,这个文件名更多的是提醒所有者,而不是表示传送什么信息给计算机。但是另一方面,C 编译器可能要求它编译的文件以 c 结尾,否则它会拒绝编译。然而,操作系统不关心这一点。

对于可以处理多种类型文件的某个程序,这类约定是特别有用的。例如,C 编译器可以编译、链接多种文件,包括 C 文件和汇编语言文件。这时扩展名就很有必要,编译器利用它区分哪些是 C 文件,哪些是汇编文件,哪些是其他文件。

与 UNIX 相反,Windows 关注扩展名且对其赋予了含义。用户(或进程)可以在操作系统中注册扩展名,并且规定哪个程序“拥有”该扩展名。当用户双击某个文件名时,“拥有”该文件扩展名的程序就启动并运行该文件。例如,双击 file docx 启动了 Microsoft Word 程序,并以 file. Docx 作为待编辑的初始文件。

文件结构

文件可以有多种构造方式,在图 4-2 中列出了常用的三种方式。图 4-2 a 中的文件是一-种无结构的字节序列,事实上操作系统不知道也不关心文件内容是什么,操作系统所见到的就是字节,其文件内容的任何含义只在用户程序中解释。UNIX 和 Windows 都采用这种方法。

把文件看成字节序列为操作系统提供了最大的灵活性。用户程序可以向文件中加入任何内容,并以任何方便的形式命名。操作系统不提供任何帮助,但也不会构成障碍。对于想做特殊操作的用户来说,后者是非常重要的。所有 UNIX 版本(包括 Linux 和 OS X)以及 Windows 都采用这种文件模型。

文件类型

很多操作系统支持多种文件类型。如 UNIX(当然,包括 OS X)和 Windows 中都有普通文件和目录,UNIX 还有字符特殊文件(character special file)和块特殊文件(block special file)。普通文件(regular file)是包含有用户信息的文件。图 4-2 中的所有文件都是普通文件。目录(directory)是管理文件系统 结构的系统文件。字符特殊文件和输入/输出有关,用于串行I/O 类设备,如终端、打印机、网络等。块特殊文件用于磁盘类设备。

普通文件一般分为 ASCII 文件和二进制文件。

ASCI 文件的最大优势是可以显示和打印,还可以用任何文本编辑器进行编辑。

其他与 ASCII 文件不同的是一进制文件。打印出来的二进制文件是无法理解的、充满混乱字符的一张表。通常,二进制文件有一定的内部结构,使用该文件的程序才了解这种结构。

如图 4-3 a 是一个简单的可执行二进制文件,它取自某个早期版本的 UNIX。尽管这个文件只是一个字节序列,但只有文件的格式正确时,操作系统才会执行这个文件。这个文件有五个段:文件头、正文、数据、重定位位及符号表。文件头以所谓的魔数(magic number)开始,表明该文件是一个可执行的文件(防止非这种格式的文件偶然运行)。魔数后面是文件中各段的长度、执行的起始地址和一-些标志位。程序本身的正文和数据在文件头后面。这些被装人内存,并使用重定位位重新定位。符号表则用于调试。

二进制文件的第-个例子是 UNIX 的存档文件,它由已编译但没有链接的库过程(模块)组合而成。每个文件以模块头开始,其中记录了名称、创建日期、所有者、保护码和文件大小。该模块头与可执行文件一样,也都是二。进制数字,打印输出它们毫无意义。

所有操作系统必须至少能够识别它们自己的可执行文件的文件类型。

文件访问

早期操作系统只有一种文件访问方式:顺序访问(sequential access)。进程在这些系统中可从头按顺序读取文件的全部字节或记录,但不能跳过某一些内容,也不能不按顺序读取。顺序访问文件是可以返回到起点的,需要时可多次读取该文件。在存储介质是磁带而不是磁盘时,顺序访问文件是很方便的。

当用磁盘来存储文件时,可以不按顺序地读取文件中的字节或记录,或者按照关键字而不是位置来访问记录。这种能够以任何次序读取其中字节或记录的文件称作随机访问文件(random access file)。许多应用程序需要这种类型的文件。

随机访问文件对很多应用程序而言是必不可少的,如数据库系统。如果乘客打电话预订某航班机票,订票程序必须能直接访问该航班记录,而不必先读出其他航班的成千上万个记录。

有两种方法可以指示从何处开始读取文件。一种是每次 read 操作都给出开始读文件的位置。另一种是用一个特殊的 seek 操作设置当前位置,在 seek 操作后,从这个当前位置顺序地开始读文件。UNIX 和 Windows 使用的是后一种方法。

文件属性

文件都有文件名和数据。另外,

所有的操作系统还会保存其他与文件相关的信息,如文件创建的日期和时间、文件大小等。这些附加信息称为文件属性(attribute),有些人称之为元数据(metadata)。文件的属性在不同系统中差别很大。

一些常用的属性在图 4-4 中列出,但还存在其他的属性。没有一个系统具有所有这些属性,但每个属性都在某个系统中采用。

文件操作

使用文件的目的是存储信息并方便以后的检索。对于存储和检索,不同系统提供了不同的操作。以下是与文件有关的最常用的一些系统调用:

1) create。创建不包含任何数据的文件。该调用的目的是表明文件即将建立,并设置文件的一些属性。

2) delete。当不再需要某个文件时,必须删除该文件以释放磁盘空间。任何文件系统总有一个系统调用用来删除文件。

3) open。在使用文件之前,必须先打开文件。open 调用的目的是:把文件属性和磁盘地址表装人内存,便于后续调用的快速访问。

4) close。访问结束后,不再需要文件属性和磁盘地址,这时应该关闭文件以释放内部表空间。很多系统限制进程打开文件的个数,以鼓励用户关闭不再使用的文件。磁盘以块为单位写人,关闭文件时,写人该文件的最后一块,即使这个块还没有满。

5) read。在文件中读取数据。一般地,读取的数据来自文件的当前位置。调用者必须指明需要读取多少数据,并且提供存放这些数据的缓冲区。

6) write。向文件写数据,写操作一般也是从文件当前位置开始。如果当前位置是文件末尾,文件长度增加。如果当前位置在文件中间,则现有数据被覆盖,并且永远丢失。

7) append。此调用是 write 的限制形式,它只能在文件末尾添加数据。若系统只提供最小系统调用集合,则通常没有 append。很多系统对同一操作提供了多种实现方法,这些系统中有时有 append 调用。

8) seek。对于随机访问文件,要指定从何处开始获取数据,通常的方法是用 seek 系统调用把当前位置指针指向文件中特定位置。seek 调用结束后,就可以从该位置开始读写数据了。

9) get attributes。进程运行常需要读取文件属性。例如,UNIX 中 make 程序通常用于管理由多个源文件组成的软件开发项目。在调用 make 时,它会检查全部源文件和目标文件的修改时间,实现最小编译,使得全部文件都为最新版本。为达到此目的,需要查找文件的某一些属性,即修改时间。

10) set attributes。某些属性是可由用户设置的,甚至是在文件创建之后,实现该功能的是 set attributes 系统调用。保护模式信息是一个典型的例子,大多数标志也属于此类属性。

11) rename。用户常常要改变已有文件的名字,rename 系统调用用于这一目的。严格地说,rename 系统调用不是必需的,因为先把文件复制到一个新文件中,然后删除原来的文件,就可以达到同样的目的。

使用文件系统调用的一个示例程序

本节会考察一个简单的 UNIX 程序,它把文件从源文件处复制到目标文件处。程序清单如图 4-5 所示。该程序的功能很简单,甚至没有考虑出错报告处理,但它给出了有关文件的系统调用是怎样工作的一~般思路。

例如,通过下面的命令行可以调用程序 copyfile:

copyfile abc xyz

把文件 abc 复制到 xyz。如果 xyz 已经存在,abc 会覆盖它。否则,就创建它。程序调用必须提供两个参数,它们都是合法的文件名。第一个是输人文件;第二个是输出文件。

目录

文件系统通常提供目录或文件夹用于记录文件的位置,在很多系统中目录本身也是文件。

一级目录系统

目录系统的最简单形式是在一个目录中包含所有的文件。这有时称为根目录,但是由于只有一个目录,所以其名称并不重要。在早期的个人计算机中,这种系统很普遍,部分原因是因为只有一个用户。有趣的是,世界第一台超级计算机 CDC 6600 对于所有的文件也只有一个目录,尽管该机器同时被许多用户使用。这样决策毫无疑问是为了简化软件设计。

层次目录系统

层次结构(即一个目录树)。通过这种方式,可以用很多目录把文件以自然的方式分组。

路径名

用目录树组织文件系统时,需要有某种方法指明文件名。常用的方法有两种。第一种是,每个文件都赋予一个绝对路径名(absolute path name),它由从根目录到文件的路径组成。

另一种指定文件名的方法是使用相对路径名(relative path name)。它常和工作目录(working directory)(也称作当前目录(current directory))一起使用。用户可以指定一个目录作为当前工作目录。这时,所有的不从根目录开始的路径名都是相对于工作目录的。

目录操作

不同系统中管理目录的系统调用的差别比管理文件的系统调用的差别大。为了了解这些系统调用有哪些及它们怎样工作,下面给出一个例子(取自 UNIX)。

I) create。创建目录。除了目录项“。”和“。.”外,目录内容为空。目录项“,”和“。.”是系统自动放在目录中的(有时通过 mkdir 程序完成)。

2) delete。删除目录。只有空目录可删除。只包含目录项“”和“。”的目录被认为是空目录,这两个目录项通常不能删除。

3) opendir。目录内容可被读取。例如,为列出目录中全部文件,程序必须先打开该目录,然后读其中全部文件的文件名。与打开和读文件相同,在读目录前,必须打开目录。

4) closedir。读目录结束后,应关闭目录以释放内部表空间。

5) readdir。系统调用 readdir 返回打开目录的下一个目录项。以前也采用 read 系统调用来读目录,但这方法有一个缺点:程序员必须了解和处理目录的内部结构。相反,不论采用哪一种目录结构,readdir 总是以标准格式返回一个目录项。

6) rename。在很多方面目录和文件都相似。文件可换名,目录也可以。

7) link。链接技术允许在多个目录中出现同一个文件。这个系统调用指定一个存在的文件和一个路径名,并建立从该文件到路径所指名字的链接。这样,可以在多个目录中出现同一个文件。这种类型的链接增加了该文件的 i 节点(i-node)计数器的计数(记录含有该文件的目录项数目),有时称为硬链接(hard link)。

8) unlink。删除目录项。如果被解除连接的文件只出现在一个目录中(通常情况),则将它从文件系统中删除。如果它出现在多个目录中,则只删除指定路径名的连接,依然保留其他路径名的连接。在 UNIX 中,用于删除文件的系统调用(前面已有论述)实际上就是 unlink。

最主要的系统调用已在上面列出,但还有其他一些调用,如与目录相关的管理保护信息的系统调用。

关于链接文件的一种不同想法是符号链接。不同于使用两个文件名指向同一个内部数据结构来代表一个文件,在符号链接中,一个文件名指向命名另一个文件的一个小文件。当使用这个小文件时,例如打开文件,文件系统沿着路径最终找到文件名,再用新名字启动查找文件的过程。符号链接的优点在于它能够跨越磁盘的界限,甚至可以命名在远程计算机上的文件,不过符号链接的实现并不如硬链接那样有效率。

文件系统的实现

文件系统布局

文件系统存放在磁盘上。多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。磁盘的 0 号扇区称为主引导记录(Master Boot Record, MBR),用来引导计算机。在 MBR 的结尾是分区表。该表给出了每个分区的起始和结束地址。表中的一个分区被标记为活动分区。在计算机被引导时,BIOS 读人并执行 MBR。MBR 做的第一件事是确定活动分区,读入它的第一个块,称为引导块(boot block),并执行之。引导块中的程序将装载该分区中的操作系统。为统一起见,每个分区都从一个引导块开始,即使它不含有一个可启动的操作系统。不过,未来这个分区也许会有一个操作系统的。

除了从引导块开始之外,磁盘分区的布局是随着文件系统的不同而变化的。文件系统经常包含有如图 4-9 所列的一些项目。第一个是超级块(superblock),超级块包含文件系统的所有关键参数,在计算机启动时,或者在该文件系统首次使用时,超级块会被读入内存。超级块中的典型信息包括:确定文件系统类型用的魔数、文件系统中块的数量以及其他重要的管理信息。

接着是文件系统中空闲块的信息,例如,可以用位图或指针列表的形式给出。后面也许跟随的是一”组 i 节点,这是一个数据结构数组,每个文件一个,i 节点说明了文件的方方面面。接着可能是根目录,它存放文件系统目录树的根部。最后,磁盘的其他部分存放了其他所有的目录和文件。

文件的实现

文件存储实现的关键问题是记录各个文件分别用到哪些磁盘块。不同操作系统采用不同的方法。

1、连续分配

最简单的分配方案是把每个文件作为一连串连续数据块存储在磁盘上。每个文件都从一个新的块开始。如果最后一块不足一整块,这样会浪费一些空间。

连续磁盘空间分配方案有两大优势。首先,实现简单,记录每个文件用到的磁盘块简化为只需记住两个数字即可:第一块的磁盘地址和文件的块数。给定了第一块的编号,一个简单的加法就可以找到任何其他块的编号。

其次,读操作性能较好,因为在单个操作中就可以从磁盘上读出整个文件。只需要一次寻找(对第一个块)。之后不再需要寻道和旋转延迟,所以,数据以磁盘全带宽的速率输入。可见连续分配实现简单且具有高的性能。

连续分配的缺点是:

随着时间的推移,磁盘会变得零碎。开始时,碎片并不是问题,因为每个新的文件都在先前文件的结尾部分之后的磁盘空间里写人。但是,磁盘最终会被充满,所以要么压缩磁盘,要么重新使用空洞所在的空闲空间。前者由于代价太高而不可行;后者需要维护一个空洞列表,这是可行的。但是,当创建一个新的文件时,为了挑选合适大小的空洞存人文件,就有必要知道该文件的最终大小。

2、链表分配

存储文件的第种方法是为每个文件构造磁盘块链表,如图 4-11 所示。每个块的第一个字作为指向下一块的指针,块的其他部分存放数据。

与连续分配方案不同,这一方法可以充分利用每个磁盘块。不会因为磁盘碎片(除了最后一块中的内部碎片)而浪费存储空间。同样,在目录项中,只需要存放第一块的磁盘地址,文件的其他块就可以从这个首块地址查找到。

另一方面,在链表分配方案中,尽管顺序读文件非常方便,但是随机访问却相当缓慢。要获得块 n,操作系统每一次都必须从头开始,并且要先读前面的 n-1 块。显然,进行如此多的读操作太慢了。

而且,由于指针占去了一些字节,每个磁盘块存储数据的字节数不再是 2 的整数次幂。虽然这个问题并不是非常严重,但是怪异的大小确实降低了系统的运行效率,因为许多程序都是以长度为 2 的整数次幂来读写磁盘块的。由于每个块的前几个字节被指向下一个块的指针所占据,所以要读出完整的一个块大小的信息,就需要从两个磁盘块中获得和拼接信息,这就因复制引发了额外的开销。

3、采用内存总的表进行链表分配

如果取出每个磁盘块的指针字,把它们放在内存的一个表中,就可以解决上述链表的两个不足。内存中的这样一个表格称为文件分配表(File Allocation Table, FAT)。

按这类方式组织,整个块都可以存放数据。进而,随机访问也容易得多。

这种方法的主要缺点是必须把整个表都存放在内存中。对于 1 TB 的磁盘和 1 KB 大小的块,这张表需要有 10 亿项,每一项对应于这 10 亿个磁盘块中的一个块。每项至少 3 个字节,为了提高查找速度,有时需要 4 个字节。根据系统对空间或时间的优化方案,这张表要占用 3 GB 或 2.4 GB 内存。上述方法并不实用,显而易见,FAT 的管理方式不能较好地扩展并应用于大型磁盘中。而正是最初的 MS-DOS 文件系统比较实用,并仍被各个 Windows 版本所完全支持。

4、i节点

最后一个记录各个文件分别包含哪些磁盘块的方法是给每个文件赋予一个称为 i 节点(index -node)的数据结构,其中列出了文件属性和文件块的磁盘地址。图 4-13 中是一个简单例子的描述。给定节点,就能找到文件的所有块。相对于在内存中采用表的方式而言,这种机制具有很大的优势,即只有在对应文件打开时,其 i 节点才在内存中。如果每个 i 节点占有 n 个字节,最多 k 个文件同时打开,那么为了打开文件而保留 i 节点的数组所占据的全部内存仅仅是 kn 个字节,只需要提前保留这么多空间即可。

这种数据结构比文件分配表(FAT)所占据的空间要小。它与磁盘大小无关。

I 节点的一个问题是,如果每个节点只能存储固定数量的磁盘地址,那么当一个文件所含的磁盘块的数目超出了 i 节点所能容纳的数目怎么办?一个解决方案是最后一个“磁盘地址”不指向数据块,而是指向一个包含额外磁盘块地址的块的地址,如图 4- 13 所示。更高级的解决方案是:可以有两个或更多个包含磁盘地址的块,或者指向其他存放地址的磁盘块的磁盘块。

目录的实现

在读文件前,必须先打开文件。打开文件时,操作系统利用用户给出的路径名找到相应目录项。目录项中提供了查找文件磁盘块所需要的信息。因系统而异,这些信息有可能是整个文件的磁盘地址(对于连续分配方案)、第一个块的编号(对于两种链表分配方案)或者是 i 节点号。无论怎样,目录系统的主要功能是把 ASCII 文件名映射成定位文件数据所需的信息。

与此密切相关的问题是在何处存放文件属性。每个文件系统维护诸如文件所有者以及创建时间等文件属性,它们必须存储在某个地方。一种显而易见的方法是把文件属性直接存放在目录项中。很多系统确实是这样实现的。这个办法用图 4-14 a 说明。在这个简单设计中,目录中有一个固定大小的目录项列表,每个文件对应一项,其中包含一个(固定长度)文件名、一个文件属性的结构体以及用以说明磁盘块位置的一个或多个磁盘地址(至某个最大值)。

对于采用 i 节点的系统,还存在另一种方法,即把文件属性存放在 i 节点中而不是目录项中。在这种情形下,目录项会更短:只有文件名和 i 节点号。这种方法参见图 4-14 b。后面会看到,与把属性存放到目录项中相比,这种方法更好。

处理可变长度文件名字的另一种方法是,使目录项自身都有固定长度,而将文件名放置在目录后面的堆中,这一方法的优点是,当一个文件目录项被移走后,另一个文件的目录项总是可以适合这个空隙。当然,必须要对堆进行管理,而在处理文件名时缺页中断仍旧会发生。另一个小优点是文件名不再需要从字的边界开始。

目录的查找,可以使用散列表来加速查找。一种完全不同的加快大型目录查找速度的方法是,将查找结果存人高速缓存。在开始查找之前,先查看文件名是否在高速缓存中。如果是,该文件可以立即定位。当然,只有在查询目标集中在相对小范围的文件集合的时候,高速缓存的方案才有效果。

共享文件

当几个用户同在一个项目里工作时,他们常常需要共享文件。其结果是,如果一个共享文件同时出现在属于不同用户的不同目录下,工作起来就很方便。这样,文件系统本身是一个

有向无环图(Directed Acyclic Graph, DAG)而不是一棵树。将文件系统组织成有向无环图使得维护复杂化,但也是必须付出的代价。

共享文件是方便的,但也带来一些问题。如果目录中包含磁盘地址,则当链接文件时,必须把 C 目录中的磁盘地址复制到 B 目录中。如果 B 或 C 随后又往该文件中添加内容,则新的数据块将只列人进行添加工作的用户的目录中。其他的用户对此改变是不知道的。所以违背了共享的目的。

有两种方法可以解决这一问题。在第一种解决方案中,磁盘块不列人目录,而是列人一个与文件本身关联的小型数据结构中。目录将指向这个小型数据结构。这是 UNIX 系统中所采用的方法(小型数据结构即是 i 节点)。

在第二种解决方案中,通过让系统建立一个类型为 LINK 的新文件,并把该文件放在 B 的目录下,使得 B 与 C 的一个文件存在链接。新的文件中只包含了它所链接的文件的路径名。当 B 读该链接文件时,操作系统查看到要读的文件是 LINK 类型,则找到该文件所链接的文件的名字,并且去读那个文件。与传统(硬)链接相对比起来,这一方法称为符号链接(symbolic linking)。

日志结构文件系统

不断进步的科技给现有的文件系统带来了更多的压力。特别是 CPU 的运行速度越来越快,磁盘容量越来越大,价格也越来越便宜(但是磁盘速度并没有增快多少),同时内存容量也以指数形式增长。而没有得到快速发展的参数是磁盘的寻道时间(除了固态盘,因为固态盘没有寻道时间)。所以这些问题综合起来,便成为影响很多文件系统性能的一个瓶颈。为此,Berkeley 设计了一种全新的文件系统,试图缓解这个问题,即日志结构文件系统(Log structured File System, LFS)。在这一节里,我们简要描述 LFS 是如何工作的。如果需要了解更多相关知识,请参阅(Rosenblum 和 Ousterhout, 1991)。

促使设计 LFS 的主要原因是,CPU 的运行速度越来越快,RAM 内存容量变得更大,同时磁盘高速缓存也迅速地增加。进而,不需要磁盘访问操作,就有可能满足直接来自文件系统高速缓存的很大一部分读请求。从上面的事实可以推出,未来多数的磁盘访问是写操作,这样,在一些文件系统中使用的提前读机制(需要读取数据之前预取磁盘块),并不能获得更好的性能。

更为糟糕的情况是,在大多数文件系统中,写操作往往都是零碎的。一个 50 us 的磁盘写操作之前通常需要 10 ms 的寻道时间和 4 ms 的旋转延迟时间,可见零碎的磁盘写操作是极其没有效率的。根据这些参数,磁盘的利用率降低到 1%以下。

日志文件系统

虽然基于日志结构的文件系统是一个很吸引人的想法,但是由于它们和现有的文件系统不相匹配,所以还没有被广泛应用。尽管如此,它们内在的一个思想,即面对出错的鲁棒性,却可以被其他文件系统所借鉴。这里的基本想法是保存一个用于记录系统下一步将要做什么的日志。这样当系统在完成它们即将完成的任务前崩溃时,重新启动后,可以通过查看日志,获取崩溃前计划完成的任务,并完成它们。这样的文件系统被称为日志文件系统,并已经被实际应用。微软(Microsoft)的 NTFS 文件系统、Linux ext3 和 ReiserFS 文件系统都使用日志。OS X 将日志文件系统作为可选项提供。

为了看清这个问题的实质,考虑一个简单、普通并经常发生的操作:移除文件。这个操作(在 UNIX 中)需要三个步骤完成:

1) 在目录中删除文件;

2) 释放 i 节点到空闲 i 节点池;

3) 将所有磁盘块归还空闲磁盘块池。

在 Windows 中,也需要类似的步骤。不存在系统崩溃时,这些步骤执行的顺序不会带来问题;但是当存在系统崩溃时,就会带来问题。假如在第一步完成后系统崩溃。i 节点和文件块将不会被任何文件获得,也不会被再分配;它们只存在于废物池中的某个地方,并因此减少了可利用的资源。如果崩溃发生在第二步后,那么只有磁盘块会丢失。

如果操作顺序被更改,并且 i 节点最先被释放,这样在系统重启后,i 节点可以被再分配,但是旧的目录人口将继续指向它,因此指向错误文件。如果磁盘块最先被释放,这样一个在 i 节点被清除前的系统崩溃将意味着一个有效的目录入口指向一个 i 节点,它所列出的磁盘块当前存在于空闲块存储池中并可能很快被再利用。这将导致两个或更多的文件分享同样的磁盘块。这样的结果都是不好的。

日志文件系统则先写一个日志项,列出三个将要完成的动作。然后日志项被写入磁盘(并且为了良好地实施,可能从磁盘读回来验证它的完整性)。只有当日志项已经被写人,不同的操作才可以进行。当所有的操作成功完成后,擦除日志项。如果系统这时崩溃,系统恢复后,文件系统可以通过检查日志来查看是不是有未完成的操作。如果有,可以重新运行所有未完成的操作(这个过程在系统崩溃重复发生时执行多次),直到文件被正确地删除。

为了让日志文件系统工作,被写入日志的操作必须是幂等的,它意味着只要有必要,它们就可以重复执行很多次,并不会带来破坏。像操作“更新位表并标记 i 节点 k 或者块 n 是空闲的”可以重复任意次。同样地,查找一个目录并且删除所有叫 foobar 的项也是幂等的。相反,把从 i 节点 k 新释放的块加人空闲表的末端不是幂等的,因为它们可能已经被释放并存放在那里了。更复杂的操作如“查找空闲块列表并且如果块 n 不在列表就将块 n 加入”是幂等的。日志文件系统必须安排它们的数据结构和可写人日志的操作以使它们都是幂等的。在这些条件下,崩溃恢复可以被快速安全地实施。

为了增加可靠性,一个文件系统可以引人数据库中原子事务(atomic transaction)的概念。使用这个概念,一组动作可以被界定在开始事务和结束事务操作之间。这样,文件系统就会知道它或者必须完成所有被界定的操作,或者什么也不做,而没有其他选择。

NTFS 有一个扩展的日志文件系统,并且它的结构几乎不会因系统崩溃而受到破坏。自 1993 年 NTFS 第一次随 Windows NT-起发行以来就在不断地发展。Linux 上有日志功能的第一个文件系统是 ReiserFS,但是因为它和后来标谁化的 ext2 文件系统不相匹配,它的推广受到阻碍。相比之下,ext3— 一个不像 ReiserFS 那么有野心的工程,也具有日志文件功能并且和之前的 ext2 系统可以共存。

虚拟文件系统

绝大多数 UNIX 操作系统都使用虚拟文件系统(Virtual File System, VFS)概念尝试将多种文件系统统一成一个有序的结构。关键的思想就是抽象出所有文件系统都共有的部分,并且将这部分代码放在单独的一层,该层调用底层的实际文件系统来具体管理数据。大体上的结构在图 4-18 中有阐述。

文件系统管理和优化

磁盘空间管理

文件通常存放在磁盘上,所以对磁盘空间的管理是系统设计者要考虑的一个主要问题。存储一个有 n 个字节的文件可以有两种策略:分配 n 个字节的连续磁盘空间,或者把文件分成很多个连续(或并不一定连续)的块。在存储管理系统中,分段处理和分页处理之间也要进行同样的权衡。

正如我们已经见到的,按连续字节序列存储文件有一个明显问题,当文件扩大时,有可能需要在磁盘上移动文件。内存中分段也有同样的问题。不同的是,相对于把文件从磁盘的一个位置移动到另一个位置,内存中段的移动操作要快得多。因此,几乎所有的文件系统都把文件分割成固定大小的块来存储,各块之间不一定相邻。

1、块大小

一旦决定把文件按固定大小的块来存储,就会出现一一个问题:块的大小应该是多少?按照磁盘组织方式,扇区、磁道和柱面显然都可以作为分配单位(虽然它们都与设备相关,这是一种负面因素)。在分页系统中,页面大小也是主要讨论的问题之一。

拥有大的块尺寸意味着每个文件,甚至一个 1 字节的文件,都要占用一整个柱面,也就是说小的文件浪费了大量的磁盘空间。另一方面,小的块尺寸意味着大多数文件会跨越多个块,因此需要多次寻道与旋转延迟才能读出它们,从而降低了性能。因此,如果分配的单元太大,则浪费了空间;如果太小,则浪费时间。

从历史的观点来说,文件系统将大小设在1~4KB之间,但现在随着磁盘超过了1TB,还是将块的大小提升到64KB并且接受浪费的磁盘空间,这样也许更好。磁盘空间几乎不再会短缺了。

2、记录空闲块

一旦选定了块大小,下一个问题就是怎样跟踪空闲块。有两种方法被广泛采用,如图 4-22 所示。第一种方法是采用磁盘块链表,链表的每个块中包含尽可能多的空闲磁盘块号。对于 1 KB 大小的块和 32 位的磁盘块号,空闲表中每个块包含有 255 个空闲块的块号(需要有一个位置存放指向下一个块的指针)。考虑一个 1 TB 的磁盘,拥有 10 亿个磁盘块。为了存储全部地址块号,如果每块可以保存 255 个块号,则需要 400 万个块。通常情况下,采用空闲块存放空闲表,这样不会影响存储器。

另一种空闲磁盘空间管理的方法是采用位图。n 个块的磁盘需要 n 位位图。在位图中,空闲块用 1 表示,已分配块用 0 表示(或者反之)。对于 1 TB 磁盘的例子,需要 10 亿位表示,即需要大约 130000 个 1 KB 块存储。很明显,位图方法所需空间较少,因为每块只用一个二进制位标识,而在链表方法中,每一块要用到 32 位。只有在磁盘快满时(即几乎没有空闲块时)链表方案需要的块才比位图少。

3、磁盘配额

为了防止人们贪心而占有太多的磁盘空间,多用户操作系统常常提供一-种强制性磁盘配额机制。

其思想是系统管理员分给每个用户拥有文件和块的最大数量,操作系统确保每个用户不超过分给他们的配额。

文件系统备份

做磁带备份主要是要处理好两个潜在问题中的一个:

1) 从意外的灾难中恢复。

2) 从错误的操作中恢复。

文件系统的一致性

影响文件系统可靠性的另一个问题是文件系统的一致性。很多文件系统读取磁盘块,进行修改后,再写回磁盘。如果在修改过的磁盘块全部写回之前系统崩溃,则文件系统有可能处于不一一致状态。如果一些未被写回的块是 i 节点块、目录块或者是包含有空闲表的块时,这个问题尤为严重。

为了解决文件系统的不一致问题,很多计算机都带有一个实用程序以检验文件系统的一致性。例如,UNIX 有 fsck,而 Windows 用 scandisk。系统启动时,特别是崩溃之后的重新启动,可以运行该实用程序。

文件系统性能

优化文件系统的性能常见方法有:

1、高速缓存

最常用的减少磁盘访问次数技术是块高速缓存(block cache)或者缓冲区高速缓存(buffer cache)。在本书中,高速缓存指的是一- 系列的块,它们在逻辑上属于磁盘,但实际上基于性能的考虑被保存在内存中。

管理高速缓存有不同的算法,常用的算法是:检查全部的读请求,查看在高速缓存中是否有所需要的块。如果存在,可执行读操作而无须访问磁盘。如果该块不在高速缓存中,首先要把它读到高速缓存,再复制到所需地方。之后,对同一个块的请求都通过高速缓存完成。

一些操作系统将高速缓存与页缓存集成,这种方式在支持内存映射文件的时候特别吸引人。如果一 个文件被映射到内存上,则它其中的一些页就会在内存中,因为它们被要求按页进人。这些页面与在高速缓存中的文件块几乎没有不同。在这种情况下,它们能被以同样的方式来对待,也就是说,用一个缓存来同时存储文件块与页。

2、块提前读

第二个明显提高文件系统性能的技术是:在需要用到块之前,试图提前将其写入高速缓存,从而提高命中率。特别地,许多文件都是顺序读的。如果请求文件系统在某个文件中生成块 k,文件系统执行相关操作且在完成之后,会在用户不察觉的情形下检查高速缓存,以便确定块 k+1 是否已经在高速缓存。如果还不在,文件系统会为块 k+1 安排一个预读,因为文件系统希望在需要用到该块时,它已经在高速缓存或者至少马上就要在高速缓存中了。

当然,块提前读策略只适用于实际顺序读取的文件。对随机访问文件,提前读丝毫不起作用。相反,它还会帮倒忙,因为读取无用的块以及从高速缓存中删除潜在有用的块将会占用固定的磁盘带宽(如果有“脏”块的话,还需要将它们写回磁盘,这就占用了更多的磁盘带宽)。那么提前读策略是否值得采用呢?文件系统通过跟踪每一个打开文件的访问方式来确定这一点。

3、减少磁盘臂运动

高速缓存和块提前读并不是提高文件系统性能的唯一方法。另一种重要技术是把有可能顺序访问的块放在一起,当然最好是在同一个柱面上,从而减少磁盘臂的移动次数。当写一个输出文件时,文件系统就必须按照要求一次一次地分配磁盘块。如果用位图来记录空闲块,并且整个位图在内存中,那么选择与前一块最近的空闲块是很容易的。如果用空闲表,并且链表的一部分存在磁盘上,要分配紧邻着的空闲块就困难得多。

磁盘碎片整理

在初始安装操作系统后,从磁盘的开始位置,一个接一个地连续安装了程序与文件。所有的空闲磁盘空间放在一个单独的、与被安装的文件邻近的单元里。但随着时间的流逝,文件被不断地创建与删除,于是磁盘会产生很多碎片,文件与空穴到处都是。结果是,当创建一个新文件时,它使用的块会散布在整个磁盘上,造成性能的降低。

磁盘性能可以通过如下方式恢复:移动文件使它们相邻,并把所有的(至少是大部分的)空闲空间放在一个或多个大的连续的区域内。Windows 有一个程序 defrag 就是从事这个工作的。Windows 的用户应该定期使用它,当然,SSD 盘除外。

磁盘碎片整理程序会在一个在分区末端的连续区域内有大量空闲空间的文件系统上很好地运行。这段空间会允许磁盘碎片整理程序选择在分区开始端的碎片文件,并复制它们所有的块放到空闲空间内。这个动作在磁盘开始处释放出一个连续的块空间,这样原始或其他的文件可以在其中相邻地存放。这个过程可以在下一大块的磁盘空间上重复,并继续下去。

文件系统实例

MS-DOS 文件系统

MS-DOS 文件系统是第一个 IBM PC 系列所采用的文件系统。它也是 Windows 98 与 Windows ME 所采用的主要的文件系统。Windows 2000、Windows XP 与 Windows Vista 上也支持它,虽然除了软盘以外,它现在已经不再是新的 PC 的标准了。但是,它和它的扩展(FAT-32) 一直被许多嵌人式系统所广泛使用。大部分的数码相机使用它。许多 MP3 播放器只能使用它。流行的苹果公司的 iPod 使用它作为默认的文件系统,尽管知识渊博的骇客可以重新格式化 iPod 并安装一个不同的文件系统。使用 MS-DOS 文件系统的电子设备的数量现在要远远多于过去,并且当然远远多于使用更现代的 NTFS 文件系统的数量。

UNIX V7 文件系统

即使是早期版本的 UNIX 也有一个相当复杂的多用户文件系统,因为它是从 MULTICS 继承下来的。

CD-ROM文件系统

CD-ROM 的文件系统为一次性写介质设计的,所以非常简单。例如,该文件系统不需要记录空闲块,这是因为一旦光盘生产出来后,CD-ROM 上的文件就不能被删除或者创建了。下面我们来看看主要的 CD-ROM 文件系统类型以及对这个文件系统的两种扩展。尽管只读光盘已经过时,但它仍旧是一种简单的存储手段,应用于 DVD 和蓝光光盘的文件系统也是基于 CD-ROMS 开发出来的。

有关文件系统的研究

文件系统总是比操作系统的其他部分吸引了更多的研究,如今也是这样。FAST、MSST 和 NAS 这些会议的大部分内容都在讨论文件和存储系统。在标准的文件系统被完全理解的同时,还有很多后续研究,包括备份(Smaldone 等人,2013; Wallace 等人,2012)、高速缓存(Koller 等人;Oh,2012; Zhang 等人,2013 a)、安全删除数据(Wei 等人,2012)、文件压缩(Harnik 等人,2013)、Flash 文件系统(No, 2012; Park 和 Shen, 2012; Narayanan, 2009)、性能(Leventhal,2013; Schindler 等人,2011)、RAID (Moon 和 Reddy, 2013)、可靠性和错误恢复(Chidambaram 等人,2013; Ma 等人,2013; McKusic, 2012; Van Moolenbroek 等人,2012)、用户级文件系统(Rajgarhia 和 Gehani, 2010)、一致性验证(Fryer 等人,2012) 和版本文件系统(Mashtizadeh 等人,2013)。只检测文件系统内部情况也是一个研究课题(Harter 等人,2012)。

安全是个永久的课题(Botelho 等人,2013; Li 等人,2013 c; Lorch 等人,2013)。相比之下,一个很热的新课题是云文件系统(Mazurek 等人,2012; Vrable 等人,2012)。另一个最近受到关注的领域是起源(provenance) -追溯数据的历史,包括它们自哪里来,谁拥有它们,以及它们是如何转换的(Ghoshal 和 Plale, 2013; Sultana 和 Bertino, 2013)。在法律的驱使下,公司对保证数据安全和长期可用也非常感兴趣(Baker 等人,2006)。最后,其他研究者也在重新思考文件系统堆栈(Appuswamy 等人,2011)。

小结

从外部看,文件系统是一组文件和目录,以及对文件和目录的操作。文件可以被读写,目录可以被创建和删除,并可将文件从一个目录移到另一个目录中。大多数现代操作系统都支持层次目录系统,其中,目录中还有子目录,子目录中还可以有子目录,如此无限下去。

而在内部看,文件系统又是另一番景象。文件系统的设计者必须考虑存储区是如何分配的,系统如何记录哪个块分给了哪个文件。可能的方案有连续文件、链表、文件分配表和 i 节点等。不同的系统有不同的目录结构。属性可以存在目录中或存在别处(比如,在 i 节点中)。磁盘空间可以通过位图的空闲表来管理。通过增量转储以及用程序修复故障文件系统的方法,可以提高文件系统的可靠性。文件系统的性能非常重要,可以通过多种途径提高性能,包括高速缓存、预读取以及尽可能仔细地将一个文件中的块紧密地放置在一起等方法。日志结构文件系统通过大块单元写入的操作也可以改善性能。

文件系统的例子有 ISO 9660、MS-DOS 以及 UNIX。它们之间在怎样记录每个文件所使用的块、目录结构以及对空闲磁盘空间管理等方面都存在着差别。

说点什么

This site uses Akismet to reduce spam. Learn how your comment data is processed.

  Subscribe  
提醒