<<现代操作系统>>学习笔记之文件系统

文件系统简介

为什么需要文件系统

  1. 程序有需要存储大量信息的需求

    所有的计算机应用都需要存储和读取信息,如果将这些信息都放在地址空间中,那么信息的容量将会受到限制。

  2. 在程序关闭之后信息依然需要被保留

    如果将信息存储在地址空间中,如果进程结束,那么信息就会丢失。当进程被杀掉的时候,有些信息也需要被存储。

  3. 多个进程能同时访问信息

    如果将信息存储在地址空间,那么多个进程将无法访问这些信息。(采用进程间通信是另外一回事~~)

对长期存储器进行抽象

通常我们用来存储这些信息的设备由磁盘,固态硬盘,光盘,磁带。在这部分内容中我们只需要将这些设备看做一个提供了读某个区块(block)和写某个区块的区块序列就行。但是如果只有读写区块的操作,那么在使用中,就会非常的不方便,需要考虑很多额外的问题,比如, 如何找到数据,如何隔离不同用户的信息,如何释放数据等等。

正如操作系统将处理器抽象为进程,将主存储器抽象为地址空间,磁盘被抽象为了文件。
进程,地址空间,文件是操作系统中非常重要的三个抽象。

文件

文件命名

文件名在进程创建文件时指定,在进程结束时依然存在并可以被其他进程使用,不同的操作系统对文件名的要求不同,当前所有的操作系统都允许1-8个字母构成的文件名。通常情况下,操作系统也允许文件名包含数字和特殊字符。

UNIX的文件系统中区分文件名的大小写,MS-DOS不区分。Windows 95,Windows 98采用的是MS-DOS的文件系统FAT16, Windows 98引入了一种FAT16的扩展,称之为FAT32. Windows NT,Windows 2000,Windows XP,Windows Vista, Windows 7,Windows 8 依然支持FAT文件系统,同事也也引入了更先进的文件系统NTFS。

很多操作系统都支持两部分的文件名,包括文件名和扩展名,通过 . 来进行分割。在 UNIX 中扩展名仅仅是为了阅读方便,在 Windows 中,扩展名被赋予了意义,可以将某个文件扩展名注册为属于某软件。

文件结构

文件通常可以按照以下三种方式进行组织

  1. 字节流: UNIX Windows 采用这种方式组织文件, 在这种组织方式中, 操作系统不对文件提供额外的帮助或者阻拦, 仅仅当作一串字节序列, 提供了最大的灵活性。
  2. 记录序列: 在比较早期的主机上, 文件按照80个字符(穿孔卡为80列)或者132个字符(打印机为132列)组织成记录序列
  3. 树形结构: 这种方案可以更快的查询指定key的文件和提供下一个的操作, 在一些大型主机上使用来处理商业数据。

文件类型

在 UNIX 和 Windows 中,文件被分为普通文件和目录。目录包含了文件系统的结构。 普通文件又分为 ASCII 文件和 二进制文件

文件存取

早期的操作系统只提供了顺序存取, 值能从文件开始处依次读取文件, 后来的操作系统支持随机读取文件, 在 UNIX 和 Windows 中是通过 seek 来实现

文件属性

每个文件除了由名字和数据之外, 操作系统还为文件保存了一些其他的信息, 这些额外的信息被称为文件的属性

  1. Protection
    谁可以访问此文件
  2. Password
    访问此文件的密码
  3. Creator
    文件的创建者
  4. Owner
    文件当前的拥有者
  5. Read-only flag
    0 为读写, 1 为只读
  6. Hidden flag
    0 为普通, 1 为隐藏
  7. Syste flag
    0 为普通, 1 为系统文件
  8. Archive flag
    0 为已经备份, 1 为需要备份
  9. ASCII/binary flag
    0 为 ASCII 文件, 1 为二进制问津啊
  10. Random access flag
    0 为只能顺序读写, 1 为可以随机访问
  11. Temporary flag
    0 为普通文件, 1 为临时文件, 在进程结束时删除
  12. Lock flag
    0 表示未加锁, 非零表示文件已加锁
  13. Record length
    记录中的字节数
  14. Key position
    每条记录的偏移
  15. Key length
    key的字节数
  16. Create time
    文件创建的时间
  17. Time of last access
    文件的最后访问时间
  18. Time of last change
    文件的最后修改时间
  19. Current size
    当前文件的大小(字节数)
  20. Maximum size
    文件的最大大小(字节数)

以上的属性并不是每个系统都全部拥有, 但是每个都出现在某一个操作系统中

文件的操作

  1. Create
    创建一个不含数据的文件
  2. Delete
    删除一个文件
  3. Open
    进程通过此操作打开一个文件
  4. Close
    进程通过此操作关闭一个文件
  5. Read
    从文件中读取数据,通常需要提供长度
  6. Write
    向文件中写入数据
  7. Append
    在文件结尾处添加数据, 有的操作系统不提供此操作
  8. Seek
    对于随机访问文件,通过此操作移动到某个位置
  9. Get attributes
    读取文件的属性
  10. Set attributes
    设置文件的树形
  11. Rename
    对已经存在的文件进行重命名

目录

一级目录系统与层次目录系统

一级目录系统只在早期的个人计算机上使用过, 它的优点是方案简单。
为了管理大量的文件, 需要使用层次目录系统, 几乎所有的现代文件系统都采用这种方案

路径名

  • 绝对路径: 从根目录到文件目录, 例如 /usr/ast/mailbox 表示在根目录下的usr文件夹中的ast文件中的mailbox文件
    Windows \usr\ast\mailbox
    UNIX /usr/ast/mailbox
    MULTICS >usr>ast>mailbox

  • 相对路径: 结合当前路径进行使用, 比如上个例子中, 如果当前目录为 /usr 那么 ast/mailbox 指的就是根目录下的 usr 文件夹中的 ast 文件中的 mailbox 文件

  • 当前目录: 大部分操作系统支持 “.” 表示当前目录, 读作 dot

  • 上一级目录: 使用 “..” 表示上一级目录, 读作dotdot, 在根目录下 “..” 表示它本身,还是根目录。

目录的操作

  1. Create
    创建目录, 刚被创建的目录下只有 “.” 和 “..” , 它们有操作系统创建或者少数情况下由 mkdir 程序创建
  2. Delete
    删除目录, 只有空目录能够被删除, 只有 “.” 和 “..” 会被当作是空目录。 “.” 和 “..” 通常不能被删除
  3. Opendir
    打开目录, 在打开目录之后才能读取目录。
  4. Closedir
    关闭目录
  5. Readdir
    读取目录, 会返回打开目录的下一个入口
  6. Rename
    重命名
  7. Link
    链接, 通过这项技术可以让文件出现在不同的目录
  8. Unlink
    删除目录项, 如果对一个只出现在一处的文件进行 Unlink 那么此文件会被删除, 否则的话只是删除当前这个, 其他的还会存在。 在 UNIX 下, 删除文件的系统调用实际上是Unlink

还有一种称之为符号链接, 效率会更一点, 但是能够跨越磁盘的界限。 这个的实现方式是在建立的文件名指向了被链接的文件, 操作时, 会沿着文件树找到末尾, 找到名字, 然后通过名字再搜索要真正操作的文件

文件系统的实现

文件系统实现者对于文件系统的关注点在 文件和目录是如何被存储的, 磁盘空间是怎样被管理的以及一切的一切是如何工作的

文件系统的布局

通常, 磁盘被分为多个分区, 每个分区上都由独立的文件系统。 分区0被称为 MBR(Master Boot Record), 是用来引导计算机的。
在 MBR 的结尾是分区表, 这个表给出了每个分区的起止地址, 其中一个分区会被标记为活动分区。
当计算机在引导时, BIOS 读取和执行 MBR 。 MBR 的第一件事就是找到活动分区, 读入活动分区的第一个块, 称为引导块(boot block), 然后执行。 引导块中的程序将装载该分区上的操作系统。
为了统一, 所有的分区上都有引导块, 即便此分区上并没有操作系统。并且, 现在此分区上没有操作系统不代表将来也没有。

一种可能的文件系统布局

从上图我们可以看出来, 在整个磁盘上, 包含了 MBR 和各个分区, 在 MBR 的末端由分区表。 在每个分区中, 又包含了下面这些项

  • Superblock, 包含了文件系统的关键信息, 通常在操作系统启动或者文件系统第一次被使用的时候会读入内存, 通常包含了一个魔数来区分文件系统的类型, 文件系统中的区块数量和一些其他的管理信息。
  • Free space mgmt, 文件系统的空闲块信息, 可以通过位图或者链表来实现
  • I-nodes, i 节点信息, 可能是一个结构体数组, 每个文件一个, 存储了文件的各方面信息
  • Root dir, 根目录
  • Files and directories, 文件和目录

以上只是一种可能的结构, 不同的文件系统可能是有区别的

文件的实现

连续分配

此方案中, 文件被存储在一段连续的磁盘块中, 假如磁盘分为1kb每块, 那么一个50kb的文件会被存储在连续的50个块中, 新的文件会从一个新的块开始存储。 如果文件的大小导致存不满一个块, 那么剩余的空间将会被浪费掉。
连续分配方案有两个明显的优点,

  1. 简单易实现, 跟踪文件存储的块只需要记录下文件占据的第一个块的磁盘地址和块的数量就行了。
  2. 读性能非常好, 由于读取整个文件只需要对磁盘进行一次读操作。 只需要一次seek操作, 因此可以达到磁盘读取的最大带宽。

但是呢, 连续分配方案也具有严重的缺点,
随着使用时间的增加, 磁盘会产生碎片。 由于当文件从磁盘移除时, 会产生一些空闲的块, 文件系统并不会通过拷贝文件来消除这些空闲的块, 因此随着时间越来越长, 磁盘就变成了很多文件和很多洞。 同时, 创建文件的时候, 因为需要被填入某个洞中, 那么就需要提前知道文件的大小, 如果预设的文件大小太小, 那么程序可能就会因为空间不够用了结束掉。
尽管如此, 连续分配还是有应用场景的, 比如在 CD-ROMs 中, 因为通常, 在这种场景之下, 文件的大小都是已知的和不可改变的。
DVDs的使用上会更复杂一点, 因为通常一部90分钟的电影由4.5G大, 但是由于在 UDF(Universal Disk Format) 中, 采用一个 30bit 的数字来表示文件长度, 30位只能表示1GB的大小, 因此电影会被存储为几个1GB大小的文件, 每个文件是相邻的。 每个逻辑文件对应的物理块称为extents。

链表分配

此方案中, 文件被存储为磁盘块的链表, 每个块的第一个字长被用来当作指针指向下一个块, 剩下的用来存储数据。
通过链表分配, 就不会产生磁盘碎片了, 浪费掉的仅仅是最后一个block未被填满的空间。 同时, 目录只需要存储第一个block的地址就行了。
不过, 随机访问的性能会变差, 读取中间的块需要从第一个块开始遍历。
由于每个block的头部使用了一个字长当作指针使用, 因此存储数据的容量就不在是2的整数次幂, 这会导致性能的下降。

在内存中采用表的链表分配

这种方案就是将链表的地址存储在了内存的一个表当中, 我们假设用了个数组来存储这个表, 比如我们A文件所占用的块是4->7->2->10->12, 那么在这个数组中, a[4] = 7, a[7] = 2, a[2] = 10, a[10] = 12, a[12] = -1, 这个表称为 FAT(File Allocation Table)
通过这种组织方式, 磁盘上的 block 都用来存储数据了, 同时, 随机访问也更简单了, 因为内存的读取是要比磁盘读取快很多的。

此方案的缺陷就是由于整个表需要一直保存与内存中, 如果磁盘很大的话,就需要很大的内存来存储这个表, 所以 FAT 方案不适合用在大磁盘上, 这个是 MS-DOS 最初的文件系统

I-nodes

这种方案为每个文件关联一个i节点(index-node), i节点中包含了文件属性和文件块的磁盘地址。通过给出的i节点,就可以找到存储文件的块。与跟在内存中存储一个链表信息的table相比,这个方案的好处在于内存中只需要存储打开文件的i节点。

i节点的示例

如何处理每个文件需要可变动的文件块的数量,从上图来看就是i节点中的格子数量是变化的

一种解决方案是如上图展示的那样,最后一项中不存储磁盘block的地址,存储一个包含了更多磁盘块的磁盘快的地址

目录的实现

目录实现的是当我们给出目录的路径的时候,操作系统需要路径对应的文件块,对于连续分配方案,需要找到的是文件的第一个块。对于链表方案需要找到第一个磁盘块的序号。对于i节点方案,需要找到文件对应的i节点序号。
目录系统的主要功能就是将 ASCII 的文件名对应到定位数据的信息

属性的存储位置

  1. 存在目录里,每个目录包含了一个列表,每项对应一个文件,包含了文件名,文件的属性和磁盘地址
  2. 对于使用i节点的文件系统, 属性被存储在i节点中,因此目录中只存放文件名和i节点序号

变长文件名的的实现

  1. 限制最大长度,比如255字节,用0来标示结尾。
  2. 将所有名字存在一起,文件入口处指定为文件名的位置,可以省略掉文件结尾标志。

文件名的查找

  1. 线性搜索
  2. hash表
  3. 使用缓存

共享文件

如果直接复制文件的磁盘地址,那么当一边发生改变时,另外一边是看不见的,因此通常由以下两种解决方法

  1. 路径中保存的不是文件的磁盘快而是一段额外的信息,比如说i节点,共享文件的时候共享i节点就行
  2. 通过在链接的路径下建立一个新文件,这个文件存储着被链接路径的路径名。这种称为符号链接(Symbolic linking), 也叫软链接

日志结构文件系统(Log-Structure File System)

这种文件系统主要解决的问题是随着CPU越来越快,存储器越来越大,读文件的操作很多时候都是通过从缓存中读取,所以写操作成为了文件系统的瓶颈。同时,在频繁写入小文件的时候,由于要修改文件的i节点,路径的i节点,路径的磁盘块,导致了写小文件的时候大量时间消耗在了seek和旋转磁盘的操作上。

LFS文件系统是将整个磁盘看做一个文件,所有写的操作先在内存中组成一个单一的segment,然后再将此segement写如磁盘log的最后面。这样的话,i节点也是散落在磁盘的各处的,所以使用了一个i节点map,通过i节点map来找到i节点。
为了防止文件未被写入磁盘系统就崩溃了,因此i节点是直接写入磁盘的。

为了对磁盘进行整理和压缩,以便清楚已经删除的内容,写入新的内容,LFS文件系统会开启一个清理线程,此线程会扫描磁盘,从第一个segment开始,读取概要查看本segement中有哪些i节点和文件,然后根绝i节点映射表查看哪些i节点和文件还在使用,如果没由使用了就将信息丢弃,如果还在使用就更新i节点并重新写入memory中,然后将新的segement写入文件最后,并将之前的标记为未使用。

日志文件系统(Journaling File System)

继承了日志结构文件系统的思想,增加在系统崩溃时的鲁棒性,先通过日志记录下将要进行的操作,如果系统崩溃了,可以通过日志继续完成操作。微软的NTFS,LINUX的ext3,ReiserFs和都采用了这种方式,OS X上也提供了日志文件系统作为可选项。

虚拟文件系统

同一个操作系统上可能由不同的文件系统,Windows上使用 C: D: 的方式来区分, UNIX把不同的文件系统倾向于将不同的文件抽象成统一的结构。
通常采用了VFS(virtual file system)来实现,抽象层向用户提供posix接口,供用户层进行调用,同事文件系统向抽象层注册一系列函数使得VFS能调用这些函数来完成磁盘的读取。

虚拟文件系统

通过虚拟文件系统read的例子

文件系统的管理和优化

磁盘空间管理

块的大小

很显然,块的大小越大,那么浪费的磁盘空间越大,但是性能会越好

空闲块的跟踪

有两种方式来记录空闲快

  • 链表
  • 位图

文件系统备份

文件系统的一致性

文件系统的性能

磁盘碎片的整理