Jialong's Blog
沉潜 自由 追寻幸福
现代操作系统学习日志——文件系统

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

进程运行时可以在自己的地址空间中存储一定量的信息,但存储容量易受到虚拟地址空间大小的限制。另外,进程终止时,它保存的信息也随之丢失,但对于很多应用(例如数据库)而言,有关信息必须能够保存很长时间甚至永久保留。第三个问题是经常需要多个进程同时访问同一信息,解决方法是使得信息本身独立于任何一个进程

所以,长期存储信息有以下基本要求:

  • 能够存储大量信息
  • 使用信息的进程终止时,信息仍旧存在
  • 必须能使多个进程并发访问有关信息

磁盘能够进行长期存储,我们将其当作一种大小固定的的线性序列,并且支持读块k和写块k的操作。

文件是进程创建的信息逻辑单元,一块磁盘中可以有很多文件,每个文件是独立于其他文件的,文件是对磁盘的建模,而不是对RAM的建模。

进程可以读取已经存在的文件,并在需要时建立新的文件。存储在文件中的信息必须是持久的。

文件

文件命名

大小写

有些区分、有些不区分。

扩展名

UNIX中扩展名只是一张约定,操作系统不强迫采用,是用来提醒文件所有者的。

而对于可以处理多种类型文件的程序,这类约定特别有用。例如C编译器可以编译、链接多种文件,这是扩展名就很必要。

另外,Windows关注扩展名并且对其赋予了含义,用户或进程可以在操作系统中注册扩展名,并规定哪个程序拥有该扩展名。

文件结构

  • 无结构的字节序列(Windows和Unix采用这种方法)
  • 具有固定长度记录的序列
  • 由一棵树构成的文件结构,每个记录不必具有相同长度,记录的固定位置上有一个键字段(在一些处理商业数据的大型计算机上广泛应用)

文件类型

  • 普通文件
    • ASCII文件。优势是可以显示和打印,可以用任何文本编辑器进行编辑
    • 二进制文件。有一定的内部结构,使用该文件的程序才了解这种结构,只有文件格式正确,操作系统才会执行。详细例子见书上。
  • 目录:管理文件系统结构的系统文件

另外,Unix还具有:

  • 字符特殊文件。与I/O有关,用于串行I/O设备。
  • 块特殊文件。用于磁盘设备

两个普通文件的例子:一个可执行文件、一个存档文件。详情见书上。

文件访问

  • 顺序访问
  • 随机访问文件
    • read操作给出开始读文件的位置
    • 用seek操作设置当前位置(Windows和UNIX使用这种方式)

文件属性

除了文件名和数据外的与文件相关的信息,称为文件属性元数据。这些信息在不同系统中有着很大差异。主要具有以下属性类别:

  • 文件保护相关的属性。创建者、所有者、口令等。
  • 标志。用于控制或启动某些特殊属性。
  • 用关键字查找记录的文件中的属性:记录长度、键的位置和长度等。
  • 创建时间相关属性。
  • 当前大小

文件操作

与文件有关的最常用的一些系统调用

  • create
  • delete
  • open
  • close
  • read
  • write
  • append。write的限制格式,只能从文件末尾添加数据。
  • seek
  • get attributes
  • set attributes
  • rename

一个文件系统调用实现复制的简单程序

详情见书上。

目录

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

一级目录

有时也称为根目录。只有一个目录,部分原因是只有一个用户。这种目录系统常用于嵌入式装置中。

层级目录系统

使用层次结构(即一个目录树)。可以把文件以自然的方式进行分组,每个而用户可以为自己的目录树拥有自己的私人根目录。用户可以创建任意数量的子目录。

路径名

  • 绝对路径名
  • 相对路径名(又称工作目录)

支持层次目录结构的大多数操作系统在每个目录中有两个特殊目录项...,常常读作dot和dotdot。dot指当前目录,dotdot指的是其父目录。使用一些与目录相关的命令时可以使用这两个目录项。

目录操作

这里以UNIX为例。

  • create(有时通过mdir完成)
  • delete:删除目录,只有空目录可以删除。
  • opendir
  • closedir
  • readdir
  • rename
  • link。链接技术允许多个目录中出现同一个文件。这种类型的链接增加了文件的i节点(i-node)计数器的计数,有时称为硬链接。
  • unlink。删除目录项。

文件系统的实现

文件系统布局

文件系统布局

文件系统存放在磁盘上,多数磁盘划分为一个或多个分区每个分区有一个独立的文件系统

磁盘的0号扇区称为主引导记录(Master Boot Record,MBR),用来引导计算机。

MBR的结尾是分区表,该表给出了每个分区的起始地址和结束地址。

计算机被引导时,BIOS读入并执行MBR,确定活动分区,读入其第一个块,称为引导块,并执行之。引导块中的程序将装载该分区中的操作系统。为了统一,每个分区都从一个引导块开始。

除了从引导块开始,磁盘分区的布局随着文件系统的不同而变化。文件系统通常包含:超级块、空闲空间管理、i节点、根目录、其他文件和目录

文件的实现

连续分配

把每个文件作为一连串连续数据块存储在磁盘中。

优点:记录每个文件的位置较为简单,只要记住第一块的磁盘地址文件块数;读操作性能好,只需要一次寻找(一个块)。

缺点:会产生碎片。

CD-ROM和DVD使用的就是这种方法。

链表分配

为每个文件构造磁盘块链表,即每个块的第一个字作为指向下一块的指针,块的其他部分存储数据。

这一方法可以中分利用每个磁盘块。

这种分配方法中,顺序读文件十分方便,但随机访问相当缓慢(例如随机读取一个大文件中的一个具体的块)。另外,指针占去了一些字节,每个磁盘块存储数据的字节数不再是2的整数次幂。这样怪异的大小降低了系统的运行效率。

采用内存中的表进行链表分配

取出每个磁盘块的指针字,把他们放在内存的一个表中,可以解决上述链表的不足。可以从一个块开始,顺着链走到最后,找到一个文件的全部磁盘块。内存中这样的一个表格称为文件分配表(File Allocation Table,FAT)。

这种方法的缺点是要把整个表都存放在内存中,例如对于一个1TB的磁盘和1KB大小的块,这张表需要有10亿项,每项至少3字节,这张表要占用2.4GB内存,显然并不实用。所以FAT方式不能较好地扩展并应用于大型磁盘中,只是在最初的MS-DOS文件系统比较实用。

i节点(索引)

给每个文件赋予一个称为i节点的数据结构,其中列出了文件属性文件块的磁盘地址

只有在对应文件打开时其i节点才在内存中,如果每个i节点占有n个字节,最多K个文件同时打开,那么为了打开文件而保留i节点的数组所占的全部内存仅仅是kn个字节,只需提前保留这么多空间即可。

这个数组通常比FAT占据的空间要小。因为保留所有磁盘块的链表的表大小正比于磁盘自身的大小。而i节点在内存中数组的大小正比于要同时打开文件的数量,与磁盘空间无关。

i节点的一个问题是如果一个文件所含的磁盘块的数目超出i节点所能容纳的数据怎么办。解决方法为:

  • 最后一个磁盘地址不指向数据块,指向一个包含额外磁盘块地址的块的地址
  • 可以有两个或更多个包含磁盘地址的块,或者指向其他存放地址的磁盘块的磁盘块。NTFS采用了相似的方法。
  • 链接方案:将多个索引块链接起来
  • 多层索引:第一层索引块指向第二层的索引块,第二层的索引块再指向文件块。两层索引允许的最大文件为4GB
  • 混合索引:系统既采用直接地址,又采用单级索引或两级索引分配方式

目录的实现

读文件前必须先打开文件。操作系统利用用户给出的路径名找到相应的目录项。目录项中提供了查找文件磁盘块所需的信息,因系统而异,可以是上一节中介绍的几种方法对应的信息,如整个文件的磁盘地址(连续分配)、第一个块的编号(两种链表分配方案)、i节点号。(最新的操作系统使用i节点实现文件,每个目录项只引用i节点的目录)

目录系统的主要功能就是把ASCII文件名映射成定位文件数据所需的信息

与此相关的问题是在何处存放文件属性,共有两种方式:

  • 直接存放在目录项

目录中有一个固定大小的目录项列表,每个文件对应一项,其中包含文件名、文件属性的结构体以及说明磁盘块位置的一个或多个磁盘地址。

  • 存放在i节点

采用i节点系统采用的方式,不存放在目录项中。这种情形下目录项会更短:只有文件名和i节点号,这种方法更好。

实现可变长的长文件名的方法

  • 一种方法是放弃所有目录项一样大。每个目录项有一个固定部分,这个固定部分以目录项长度开始,后面是固定格式的数据,包括各种属性,最后才是一个任意长度的实际文件名。为了使每个目录项从字的边界开始,每个文件名被填充成整数个字。这种方法的缺点是一走文件后引入了一个长度可变的空闲,下一个文件不一定适合这个空隙。另外,一个目录项可能分布在多个内存页面,读取文件名时可能发生缺页。
  • 另一种方法是使目录项有固定长度,文件名存放在目录后面的堆中。优点是移走一个文件的目录项后,另一个文件的目录项可以适合这个空隙。另外要对堆进行管理,处理文件名时还可能出现缺页。

加速查找文件名的方法

在每个目录中使用散列表进行查找。一般使用拉链法处理散列表的冲突。

另一种加快大型目录查找速度的方法是将查找结果存入高速缓存。

共享文件

通过链接来实现不同目录的用户共享同一个而文件,这样,文件系统本身就是一个有向无环图DAG而不是一棵树,这使得文件系统维护变得复杂,但也是必须付出的代价。

共享也带来一些问题。若目录中包含磁盘地址,当链接文件时,必须把A目录中的地址复制到B目录,如果A或B随后又向目录中添加了内容,则新的数据块将只列入进行添加工作的用户目录中,其他用户对此不知情。解决这个问题的方法有两种:

  • 磁盘块不列入目录,而是列入一个与文件本身关联的小型数据结构,目录指向这个小型数据结构。UNIX中使用的就是i节点
  • 符号链接法,又称软链接法。系统建立一个类型为LINK的新文件,将其存放在A的目录下,使得A与B的一个文件存在链接。新文件中只包含了它所链接的文件的路径名。当A读该链接文件时,操作系统看到要读的文件类型为LINK,则找到该文件所链接的文件的名字,去读那个文件。符号链接法的问题是需要额外的开销,必须读取包含路径的文件,然后要一部分一部分地扫描路径,直到找到i节点。这些操作需要很多次额外的磁盘访问,并且每个符号链接都需要额外的i节点。

日志结构文件系统

解决磁盘寻道时间没有快速发展但其他部件例如CPU、内存容量快速发展而带来的性能瓶颈。

Berkeley设计了一种全新的文件系统来缓解这个问题,就是日志文件系统(Log-Structured File System,LFS)。

促使LFS设计的主要原因是,CPU运行速度越来越快,内存容量变得更大,同时磁盘高速缓存也迅速增加,进而,不需要磁盘访问操作,就有可能满足直接来自文件系统高速缓存的很大一部分读请求。因此,未来多数磁盘访问的是写操作。

更糟糕的是大多数文件系统中写操作往往都是零碎的,而一个50us的写操作前需要等待10ms的寻道时间和4ms的旋转延迟时间,可见零碎的写操作是没有效率的。根据上面的数据,磁盘的利用率下降到了1%以下。

在UNIX文件系统上创建一个新的文件时,为了写这个文件,必须写该文件目录的i节点、目录块、文件的i节点以及文件本身。这些写操作都可能被延迟,那么如果在写操作完成前发生司机,就可能在文件系统中造成严重不一致性。因此i节点的写操作一般是立即完成的。

处于这一原因,LFS的设计者决定重新实现一种文件系统,在面对一个大部分由零碎的随机写操作组成的任务时,同样能充分利用磁盘带宽。思想史将整个磁盘结构化为一个日志,每隔一段时间或由=有特殊要求时,被缓冲在内存中的所有未决的写操作都被放到一个单独的段,作为在日志末尾的一个邻接段写入磁盘,该段包含i节点、目录块、数据块等,每段开始都是段的摘要,说明段中包含的内容。

日志文件系统

借鉴日志结构文件系统的实际应用,基本思想是保存一个用于记录系统下一步要做什么的日志。这样当系统在完成它们即将完成的任务前崩溃时,重新启动后,可以通过查看日志,获取崩溃前计划完成的任务,并完成它们。

微软的NTFS、Linux ext3等文件系统都支持使用日志。

虚拟文件系统

在同一个操作系统下可能使用很多不同的文件系统。Windows有一个主要的NTFS文件系统,但也包含老的FAT-32或FAT-16驱动器或分区,并且不时需要一个CD-ROM或DVD。Windows通过指定不同盘符来处理这些不同的文件系统。当一个进程打开一个文件,盘符是显式或隐式存在的,所以Windows知道向哪个文件系统传递请求,不需要整合不同类型文件系统。

相比之下,现代UNIX系统将多种文件系统整合到一个统一的结构中。从用户的观点看,只有一个文件系统层级,他们事实上是多种不相容的文件系统,对用户和进程不可见。

绝大多数UNIX操作系统都使用虚拟文件系统(Virtual File System, VFS)。关键思想就是抽象出所有文件系统共有的部分,并将这部分单独的代码放在单独一层。

虚拟文件系统

文件系统管理和优化

磁盘空间管理

把文件分割成固定大小的块来存储。

块大小

根据文件的大小来确定。

记录空闲文件块

共有两种方法被广泛使用:

  • 磁盘块链表

链表的每个块中包含尽可能多的空闲磁盘块号。通常情况下,采用空闲块存放空闲表,这样不会影响存储器。

  • 位图

n个块的磁盘需要n位位图。位图中,空闲块用1表示,已分配块用0表示。

文件系统备份

文件系统的一致性

文件系统性能

许多文件系统采用一些措施来改善性能。

高速缓存

把一系列的块存放在内存中。确定块是否在内存中的方法是使用散列表,将设备和磁盘地址进行散列操作,然后在散列表中查找。

高速缓存的调入调出原理与Cache一样。

块提前读取

需要用到块以前,试图提前将其写入高速缓存,从而提高命中率。

减少磁盘臂运动

磁盘碎片整理

移动文件使它们相邻,并把所有的空闲空间放在一个或多个大的连续区域内。Windows中的defrag程序就是从事这个工作的。

固态硬盘不需要这类操作。


最后修改于 2021-12-07