第二十一讲 文件系统

文件系统和文件

_文件系统和文件

• 文件系统是操作系统中管理持久性数据的子系统, 提供数据存储和访问功能
  • 组织、检索、读写访问数据
  • 大多数计算机系统都有文件系统
  • Google 也是一个文件系统

文件系统是我们在操作系统中负责持久数据保存的子系统, 提供数据存储和访问功能.

具体说起来, 它是如何来组织持久保存的这些数据, 这些数据的组织放到文件系统当中的数据, 我如何来进行检索, 检索到了之后对于里面的数据我如何对它进行读写访问, 这是它的基本功能.

在我们现在用到的计算机系统里, 只要涉及数据的持久保存, 那么通常情况下它都会有文件系统.

广义的来讲, 我们现在用到的谷歌也是一个文件系统, 它在这里负责网上大量数据的保存和检索, 在这里面它最主要的功能还是信息的检索.

• 文件是具有符号名, 由字节序列构成的数据项集合
  • 文件系统的基本数据单位
  • 文件名是文件的标识符号

这里一个主要特征它是有文件名, 然后它的基本组成是一个字节序列.

文件是文件系统的基本数据单位, 也就说我存到文件系统当中的数据, 最小这个单位是以文件形式存在的

在这里面文件的名字是文件的标识符号. 我们在标识一个文件的时候, 通常情况下就用文件名来表示.

文件系统的功能

• 分配文件磁盘空间
  • 管理文件块 (位置和顺序)
  • 管理空闲空间 (位置)
  • 分配算法 (策略)

文件系统的功能, 首先第一个是为文件分配磁盘空间, 也就是说我这里面管理一个文件, 它到底存放到磁盘上的什么位置. 除了位置之外我们还会有一个顺序, 这是已经分配的用来存数据的这些文件块.

再有一个是空闲空间的管理, 在磁盘上有很多数据块, 可以用来存储数据. 那么这些数据块没存数据的时候, 这些数据库都分布在什么位置, 这是我们这里管理空闲空间需要解决的问题. 我们需要记住它的位置, 这里不需要它的顺序, 因为空闲的空间里面, 这个顺序对我们来说是没用意义的.

再一个就是分配算法, 跟我们前面讲到的内存管理有类似的地方. 我在磁盘上有很多的空闲的磁盘块, 这时候我要分配一部分磁盘块来存文件数据的时候, 这时候我选择哪一块. 这地方的选择策略就是我们的分配算法.

• 管理文件集合
  • 定位 : 文件及其内容
  • 命名 : 通过名字找到文件
  • 文件系统结构 : 文件组织方式

第二项功能是管理文件集合.

我有很多文件之后, 这些文件我怎么来管理它.

首先在这里要提供的一项功能是定位, 也就是说我给你一个文件名, 你需要告诉我这个文件名所对应的文件在哪, 找着它的位置读出它的内容, 这是定位需要做的.

第二个功能是说命名. 我们需要根据名字来找到文件, 这个名字比如说在计算机里面, 我们很多时候是用数字表示, 但这个数字对于人记忆是不方便的, 而文件系统里面持久保存的数据, 通常情况下是要人能够理解, 这时候我们会给它一个命名. 命名的方式在不同的文件系统当中会有一些不同的做法和相应的一些限制.

第三个是说, 我如何把这些文件组织成一个整体, 那就是我们的文件系统结构, 文件的组织方式, 不同的需求这种组织方式会不一样.

• 数据可靠和安全
  • 安全 : 多层次保护数据安全
  • 可靠
  • 持久保存文件
  • 避免系统崩溃、媒体错误、攻击等

第三个是说我持久保存数据, 就有一个数据可靠和安全问题.

首先安全是指文件系统里面, 通常情况下从多个层次提供了数据安全的保护机制

第二个是可靠. 也就是说的数据要想持久保存, 如果说在保存过程当中系统崩溃了, 存储介质出错了, 或者说有其它攻击, 这时怎么办. 在文件系统里也会提供一系列的机制来对可靠性进行某种程度的增强.

这是文件系统提供的几个功能

文件属性

• 文件属性
  • 名称, 类型, 位置, 大小, 保护, 创建者, 创建时间, 最近修改时间......

文件属性是指我们前面已经说到的名字, 除了名字之外还有的一些其它信息. 比如说这个文件是什么类型的, 是一个可执行文件, 是一个文本文件等等这样一些信息. 然后这个文件存在什么地方. 它有多大. 什么样的用户可以对它进行访问, 这是我们这里的保护机制. 然后文件是谁创建的. 最开始的创建时间和最后一次修改时间......

这些呢, 在不同的文件系统里面, 维护了不同的文件属性. 这些属性起了什么样的作用呢.

这些属性是为了方便访问的.

---

为了更方便地访问, 我们把文件里的信息分成两部分.

• 文件头 : 文件系统元数据中的文件信息
  • 文件属性
  • 文件存储位置和顺序

这里存的主要内容是我们这里的属性和文件的存储位置和顺序

有了这些文件头的信息之后, 我就能知道我要读写的文件数据到底在哪, 是些什么.

文件描述符

下面我们来讨论文件描述符这个基本的概念.

文件描述符是指打开的文件, 它在内存当中所维护的相关信息.

打开文件和文件描述符

首先我们来讨论一下打开文件的过程

• 文件访问模式
  • 进程访问文件数据前必须先 "打开" 文件

    f = open(name,flag);
    ...
    read(f,...);
    ...
    close(f);

我在读写数据之前, 我必须打开文件, 这是我们通常情况下你写的程序里面的文件访问的模式. 打开然后进行读或者写的操作, 完成之后一个关闭, 我就不再对这个文件进行操作了.

• 内核跟踪进程打开的所有文件
  • 操作系统为每个进程维护一个打开文件夹
  • 文件描述符是打开文件的标识

针对于这种模式呢, 在操作系统内核当中, 维护了打开文件的相关信息, 也就是说它会跟踪进程打开的文件. 所谓的跟踪就是在内核当中维护了一个打开文件表, 这个文件表里的每一项对应一个打开的文件. 这时候我给它一个标识, 就是文件描述符.

为啥我不直接用文件的标识呢, 原因在于打开文件的数目和你的文件系统里面的文件数目是有数量级的差别的. 这样的话我可以给它一个更简单的标识来方便我们访问.

_文件描述符

• 操作系统在打开文件表中维护的打开文件状态和信息
  • 文件指针
  • 最近一次读写位置
  • 每个进程分别维护自己的打开文件指针
  • 文件打开计数
  • 当前打开文件的次数
  • 最后一个进程关闭文件时, 将其从打开文件表中移除
  • 文件的磁盘位置
  • 缓存数据访问信息
  • 再有就是访问权限
  • 每个进程的文件访问模式信息

---

这里面的信息首先第一个是文件指针. 我们在读写文件的时候, 最后一次读写的位置, 每个进程都维护自己的打开文件指针. 也就相当于我有一个文件, 有多个进程对它进行读写, 在读的时候你的这个指针, 每个进程只是跟自己的指针相关联, 另外的一个进程读写相同的文件, 这时候你的文件指针不随着它的读写而发生改变. 这就是每个进程分别维护自己的打开文件指针.

---

除了文件指针之外, 还有一个是文件打开计数. 这里指的是当前这个文件打开的次数, 记录这个次数的意思是在于, 最后一个进程关闭文件的时候, 那么就可以将这个文件从打开文件表中去除了, 这是打开文件计数.

---

同时还有就是文件在磁盘上的位置, 这时候我们会把一部分磁盘上的文件的内容缓存到内存中. 所以这时候我要记录文件在磁盘上的位置, 你下次再读的时候我就可以利用内存当中缓存的数据让你进行访问

---

再有就是访问权限. 每个进程访问文件的时候, 它是以什么样的方式来进行访问. 你比如说只读, 可读可写

文件的用户视图和系统视图

为了能够通过文件系统来实现对文件的访问, 我们有必要来讨论一下文件从用户和系统的角度来看, 它是个什么样的. 这就是我们这里说到的文件的用户视图和系统视图.

• 文件的用户视图
  • 持久的数据结构

用户视图是指, 我们用户进程看到的文件是什么样. 这里面呢, 文件是持久的数据结构, 这是你应用进程, 需要读写文件里的数据的时候, 这些数据是有结构的, 这是我们这里想看到的.

• 系统访问接口
  • 字节序列的集合 (UNIX)
  • 系统不关心存储在磁盘上的数据结构

但是从系统的角度来讲, 它并不关心这个事, 所以系统提供了一个文件的访问接口. 在这里面呢, 文件变成了一个字节序列了. 当然对这一点的理解, 不同的系统会有一些差别, 在 unix 系统与 linux 系统这一类的系统里, 它认为文件内容是字节的序列

操作系统并不关心存储在磁盘上的数据这些数据的格式, 这个是你应用程序需要关心的.

• 操作系统的文件视图
  • 数据块的集合
  • 数据块是逻辑存储单元, 而扇区是物理存储单元
  • 块大小 <> 扇区大小

这就是我们这里的系统视图, 也就是说它把文件视为是数据块的集合.

说到数据块, 这有两个, 我们访问的数据块和磁盘的扇区有关系但也有区别.

数据块是逻辑的存储单位, 可能由多个扇区组成; 而扇区是物理的存储单元. 数据块的大小和扇区的大小可能不太一样, 通常情况下是几个扇区构成一个数据块, 特别是对于容量比较大的磁盘来说是这样的.

用户视图到系统视图的转换

有了用户的视角和系统的视角, 那这时候它们之间的转换怎么来做呢.

我们先来看一个文件读写的例子.

• 进程读文件
  • 获取字节所在的数据块
  • 返回数据块内对应部分

进程读文件的时候, 首先读取你对应的这个内容所在的那个数据块, 整块读出来. 也就是说磁盘的访问它具有这样一个特征 : 磁盘的最小访问单位只能是块, 我不能对块中单独的字节进行读或者写. 也就是说你想读出一个字节, 必须把整块读出来; 想写一个字节, 也必须把整块重新写.

我们读出字节所在的数据块, 然后把其中需要的内容返回给进程, 这是你的读操作.

• 进程写文件
  • 存取数据块
  • 修改数据块中对应部分
  • 写回数据块

而进程的写文件操作呢, 它是先读取相应的数据块, 也就是说你要写那个位置所对应的那一块的内容全部读出来, 然后修改相应块中的对应内容. 修改完毕之后把整块写回去.

• 文件系统中的基本操作单位是数据块
  • 例如, getc() 和 putc() 即使每次只访问 1 字节的数据, 也需要缓存目标数据 4096 字节

这是写操作. 对于这种情况呢, 我们在这里面从用户视图到系统视图就有一个转换, 这个转换过程当中的一个重要的特征就是文件系统当中的操作, 它的操作的基本单位是数据块.

有了这个操作之后, 我们在这里就会有这样一个特征 : 你即使只读一个字节, 也需要把整块读出来.

所以我们读写数据的时候我们有一种优化, 就是一块的内容, 我看有没有可能把它充分利用起来.

访问模式

• 操作系统需要了解进程如何访问文件

在具体讨论内容的时候, 我们还有一个问题需要在这里讨论, 就是进程对文件的访问模式. 也就是说操作系统在实现文件系统的时候, 它需要了解用户进程是如何访问文件的.

那么在这里面有这样三种方式 :

• 顺序访问 : 按字节依次读取
  • 大多数的文件访问都是顺序访问

第一种是顺序访问, 按文件的字节序列这个顺序依次进行读写操作, 我们现在用到的大多数文件访问都是顺序访问.

• 随机访问 : 从中间读写
  • 不常用, 但仍然重要
  • 例如, 虚拟内存中把内存页存储在文件

而第二种是随机访问, 我访问的位置并不是顺序的, 从中间读. 这种做法呢, 在实际的进程访问当中并不常用, 但仍然很重要. 比如说这里虚拟存储当中, 把内存页存储到对换文件当中, 这时候它的访问就是随机的, 它对系统的性能影响很大.

• 索引访问 : 依据数据特征索引
  • 通常操作系统不完整提供索引访问
  • 数据库是建立在索引内容的磁盘访问上

第三种是索引访问, 依据数据特征来找文件当中的相应位置的数据.

这种做法通常情况下, 操作系统里并不完整地提供索引访问机制. 一种做法是在上面建立数据库, 数据库提供完善的索引访问方式, 实际上从某种角度来讲, 我们可以认为操作系统里的文件系统是一个小型的数据库.

索引文件示例

这是索引访问文件的一个示例, 说我要找文件里的某一个记录, 这时我怎么找呢.

我需要先找到这个记录对应的位置在哪, 这时候形成一个索引. 一种是我整个把它读出来, 然后再挑我想要的这个, 这时候它的效率会比较低. 所以在这基于索引的访问的话, 就是我在这里加了一个索引, 事先把相应的内容做了一种抽象, 然后我再来访问的时候, 我先访问索引文件里的内容, 找到它相应的位置, 这时候再去读它相应记录的内容, 这样的话就可以提高它的读写效率.

文件内部结构

对于文件的内部呢, 我们说从操作系统的角度来讲, 它并不关心它的结构, 在实际的系统当中, 我们可以把它视为这样几种结构 :

• 无结构
  • 单词, 字节序列

一种是无结构的, 它就是一个单词, 或者说字节的序列

• 简单记录结构
  • 分列
  • 固定长度
  • 可变长度

第二种是简单的记录结构, 我们把它分成若干列, 每一列是其中的一个内容, 这种列的大小或者记录的大小可以有固定长度的, 也可以是可变长度的

• 复杂结构
  • 格式化的文档 (如, MS word, PDF)
  • 可执行文件
  • .....

再有一种就是复杂结构, 我在这里定义复杂的结构. 通常情况下这些复杂的结构都是由你应用程序来识别, 而从操作系统层面来讲, 这些结构并不是很关心, 但是为什么我们这里会来讨论它的内部结构呢 ?

就是你到底是可执行文件还是文本文件, 在操作系统接口这一层面上, 它提供某种程度的支持和识别

文件共享和访问控制

• 多用户系统中的文件共享是很必要的

比如说系统里的很多文件, 你不能每个用户都保存一份, 这样硬盘空间不一定放得下. 所以我们通过共享来解决这个问题.

但是共享之后又带来一个问题, 我的访问如何来控制.

• 访问控制
  • 每个用户能够获得哪些文件的哪些访问权限
  • 访问模式 : 读, 写, 执行, 删除, 列表等

以什么样的方式来访问, 这是访问权限

在我们现在的系统里, 通常情况下的访问权限有这样几种 : 读, 写, 执行, 删除和看到它的列表.

• 文件访问控制列表 (ACL)
  • <文件实体, 权限>

这些基本的权限, 对应到每一个用户, 这就是我们的文件访问控制列表

• Unix 模式
  • <用户|组|所有人, 读|写,可执行>
  • 用户标识 ID
  • 识别用户, 表面每个用户所允许的权限及保护模式
  • 组标识 ID
  • 允许用户组成组, 并指定了组访问权限

对于每一个用户每一个文件, 在 unix 系统里面它的做法是这样的, 用户分成当前的用户, 用户所在的组合系统里的所有人, 也就是分成三个范围. 然后每一个文件的访问权限, 分成读写执行这三种权限

在这种情况下, 你要想把所有的文件权限全部列清除, 这时候就构成了一个访问矩阵了. 三种类型的用户, 然后它有三种权限组合到一起, 每一个文件有一个自己的选择, 那这样我给出整个系统当中的每一个文件的访问权限.

为了让这个事情做起来方便, 我们需要识别用户, 看用户是谁, 这样才能决定它有什么样的访问权限. 然后为了让这件事情做起来效率更高, 我们可以把用户分组, 提供组标识.

那这样的话, 我可以给一组人设相同的权限, 我只需要判断这个用户是否在这个组里就行了.

关于访问权限, 我们就只讨论这么多, 深入的讨论在不同的操作系统当中都有很多的内容.

语义一致性

• 规定多进程如何同时访问共享文件
  • 与同步算法相似
  • 因磁盘 I/O 和网络延迟而设计简单

当多个进程同时访问共享文件的时候, 它们如何来协调, 这里的协调同前面的同步算法很相似, 我需要协调我写到里面的内容, 你读的内容大家是不是一致的.

由于磁盘和网络延迟的缘故, 我们在文件系统里, 对这个问题是弱化处理的, 也就是说它设计很简单.

• Unix 文件系统 (UFS) 语义
  • 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
  • 共享文件指针允许多用户同时读取与写入文件

在 unix 系统里简单到什么程度呢 ? 对于文件的读写, 一个用户写进去的时候, 其他用户立即可见; 然后共享文件呢, 允许多个用户同时读写.

基本上这里它没用协调的这些控制, 这样一来的话, 你的内容读写是不是完整, 就需要应用程序自己来把握. 那也就相当于我把这个一致性的问题甩给应用程序进程自己去处理了.

• 绘画语义
  • 写入内容只有当文件关闭时可见

还有两种做法

一个是会话语义, 写入的内容只有当文件被关闭的时候, 其它用户才可见. 这样一来, 你相当于改的内容必须写完整了, 其他的进程才能看得到. 这样一来它们之间要协调的事情就会变得简单一些, 但是它的效率也会低一些.

• 读写锁
  • 一些操作系统和文件系统提供该功能

操作系统在这里提供几种基本的互斥访问锁, 由应用程序自己来选择, 我需要什么样的同步互斥来保证我内容的一致性

目录, 文件别名和文件系统种类

分层文件系统

• 文件以目录的方式组织起来

文件多到一定数目以后, 我们要想对它进行有效的管理, 这时候我们就必须引入分层的结构, 也就是说把若干个文件以目录的形式组织起来.

比如说在这里头, 给出的是文件系统里的一种组织方式. 圆圈表示我们基本的普通的文件, 在这里方块就是目录.

• 目录是一类特殊的文件
  • 目录的内容是文件索引表 <文件名, 指向文件的指针>

目录是一种特殊的文件, 这个特殊的文件里存的内容是用来表示其它文件的信息, 所以它是特殊的.

这个特殊的文件, 文件内容是文件的索引表, 一条索引就是文件名和指向文件的指针. 有了这个之后, 我们就可以把所有的文件组织成一个树状结构.

这时候我们如何来标识一个特定的文件呢 ? 每一个文件, 在我们这里对应过来, 从根目录开始的一条路径, 第一级根目录, 然后找到它的下一级目录的名字, 这是我们第一级根目录里的目录项. 到第二级目录的时候, 它又有它的目录项, 根据你这个文件的路径, 一直找到最后文件的内容.

有了这种方式之后, 我们就可以用路径的形式来标识每一个文件, 这样的话方便用户的访问. 这里的方便是指, 方便用户的记忆和分类.

目录操作

用这种方式组织之后, 我们在目录上的操作, 就跟其它的文件有一些不一样的地方.

• 典型目录操作

  • 搜索文件
  • 创建文件
  • 删除文件
  • 列目录
  • 重命名文件
  • 遍历路径

• 操作系统应该只允许内核修改目录

  • 确保映射的完整性
  • 应用程序通过系统调用访问目录

这些操作, 对于操作系统来说, 它都是封装到内核里面的, 只能由内核来对目录进行修改. 这样的话就可以保证这种目录的映射的完整性. 用户进行这个操作是他需要通过系统调用来完成.

目录实现

• 文件名的线性列表, 包含了指向数据块的指针
  • 编程简单
  • 执行耗时

目录的实现呢, 是描述我目录里的这些文件的列表我怎么来组织. 最简单的做法是把它组织成一个线性的表. 这时候的问题是说如果这个表很大, 那这时候检索或者说增删查改这些操作的时间会很长. 但是它的好处是编程简单.

• 哈希表 --- 哈希数据结构的线性表
  • 减少目录搜索时间
  • 冲突 --- 两个文件名的哈希值相同
  • 固定大小

然后另一种做法是, 我是把目录里这些文件组织成一个哈希表. 先做哈希, 然后再进行后续的操作, 这种做法由于哈希的缘故, 它可以减少搜索的时间. 不过也会有另外一个问题, 就是两个文件名, 它做哈希之后, 可能哈希结果是一致的, 这时候会产生冲突, 那么冲突呢, 我需要在哈希表里解决这个问题.

这样做之后, 我目录表里面的每一项, 长度是固定的.

文件别名

• 两个或多个文件名关联同一个文件

接下来我们说文件别名, 也就是说我有一个文件, 我想给它起两个或者多个名字的时候, 我怎么办.

首先我们在这看一个例子

在这里面我有一个文件. 这有它的路径 /dict/count /spell/count. 这两个最后指向的是同一个实体.

我们这么做的原因是为了方便共享, 减少存储空间.

在文件系统中我们怎么表示它, 这里是另外一个例子 /dict/w/list /dict/all /spell/words/list, 这三个实际上最后都是同一个文件.

它的实现办法我们这有两种

• 硬链接 : 多个文件项指向同一个文件

一种叫硬链接, 也就是说多个文件的目录项最后都指向同一个文件. 比如说在这里面, 我们上面例子里面的两个文件.

• 软链接 : 以 "快捷方式" 指向其他文件
  • 通过存储真实文件的逻辑名称来实现

另一种做法是软链接. 它的做法是以快捷方式来指向其它文件. 它的文件描述出来仍然是各自独立的. 只是说链接文件里面, 存的是另一个文件的完整的路径. 它以这种方式来实现文件别名.

第一种方式就会涉及到一个问题, 就是我要来一个删除操作, 我需要把所有的指向它的这些路径删掉, 才能完完全全实实在在地把这个文件删掉.

而第二种做法, 软链接呢, 我删除的时候, 我删除别名和删除其它的文件是一样的, 我把别名删除了, 实际上源文件本身是不受任何影响的, 删除源文件之后, 你原来的别名所指向的文件就不存在了.

文件目录中的循环

还有一个问题是文件目录中的循环

我可以指向下一级子目录, 那我的子目录可不可以指回到它的父目录呢 ?

这时候如果你这样做的话, 就会构成循环. 比如说这里, 你要找某一个文件, 它的子目录的子目录, 我把它指向一个循环之后, 这条路径就可以无限制循环下去了 /avi/book/avi/book/avi/book/avi/book/avi/book/avi/book/avi/book/avi/book......

这种情况怎么处理呢, 我们的处理办法有这么几种.

• 如何保证没用循环 ?
  • 只允许到文件的链接, 不允许在子目录的链接
  • 增加链接时, 用循环检测算法确定是否合理

一种是我加链接的时候, 我只能是文件, 不允许目录的链接;

还有一种做法是, 我在这里吗加链接的时候, 我用检测算法来检测, 这跟我们死锁检测差不太多, 我可以用银行家算法. 但这个时候你的检测开销会比较大

• 更多实践
  • 限制路径可遍历文件目录的数量

所以实际的做法, 通常情况下, 我限制你可以检索下去的长度, 超过这个长度, 我就不再给你往下检索了. 这样的话也就减少了这种由于循环带来的问题.

名字解析 (路径遍历)

• 名字解析 : 把逻辑名字转换成物理资源 (如文件)
  • 依据路径名, 在文件系统里找到实际文件位置
  • 遍历文件目录直到找到目标文件

我们接下来看我如何找一个文件, 也就是我们这里的名字解析.

在很多地方有名字解析的问题, 这里说名字解析是把一个逻辑的名字转换成它的物理资源. 比如说我们这里的文件.

对于文件系统里的名字解析, 就是我给你一个路径, 然后你告诉我这个路径所对应的文件存在哪, 把它的内容读出来.

它的实际做法就是遍历文件目录, 从根目录开始, 一直找到你要找的那个文件为止, 这是文件名的解析

• 举例, 解析 "/bin/ls"
  • 读取根目录的文件头 (在磁盘固定位置)
  • 读取根目录的数据块, 搜索 "bin" 项
  • 读取 bin 的文件头
  • 读取 bin 的数据块, 搜索 "ls" 块

这有个例子, 我有个路径, 最后文件名是 "ls", 我怎么来找呢.

首先我找这个文件分区的根目录, 根目录里头的位置在文件系统当中是固定的;

然后我从这里读出根目录的数据块, 里面每一个子目录和它的根目录里的文件对应着一项, 我在这里要找到 "bin" 这一项, 这一项会指向下一级目录的数据块;

我再去找着这个 "bin" 目录所对应的文件头, 然后在这里读取它的数据块, 也就是在 bin 这个目录里所有文件和子目录的列表中去找有没有 "ls" 这一项;

找到 ls 之后, 我再就可以读取到 ls 这个文件的内容了.

• 当前工作目录 (PWD)
  • 每个进程都会指向一个文件目录用于解析文件名
  • 允许用户指定相对路径来代替绝对路径, 比如用 PWD= "/bin" 能够解析 "ls"

那为了方便这种查找呢, 我们就提出一种概念, 叫作当前工作目录. 它指每一个进程给它设定一个缺省的目录, 它的名字解析就从这个目录开始往下解析.

这样做的好处在于, 如果说我这个进程, 经常就在这一个目录里进行操作的话, 它就没有必要每次都从根目录往下找. 只有在你要切换当前目录的时候, 才会从根目录里找一遍, 这样就会提高效率

这时候路径就有一种相对路径, 也就是说基于当前目录所进行的查找

文件系统挂载

• 文件系统需要先挂载才能被访问

在我们计算机系统起来之后, 它有个根文件系统, 通常我们访问这些数据, 所在的文件系统必须挂接到系统当中才能被访问

比如说在这里是一个未挂载的文件系统, 系统起来的时候它有一个根文件系统, 未被挂载的文件系统需要挂载到这个根文件系统中, 然后才能进行访问

• 未挂载的文件系统被挂载到挂载点上

所谓的挂载就是, 我把这个文件系统, 它根目录对应到根文件系统里的某一个目录.

比如说我这里 user 这个地方就是它的挂载点

挂载上去之后, 我再去找这个文件系统里的某一个文件, 它的路径什么, 从整个系统的根开始, 沿着这找, 找到你的挂载点之下, 在找到你这个文件系统的根; 从这个地方再往下找, 就可以找到当前这个已挂载文件系统当中的任何一个文件了.

文件系统的种类

• 磁盘文件系统
  • 文件存储在数据存储设备上, 如磁盘
  • 例如 FAT, NTFS, ext2/3, ISO9660 等

接下来说文件系统的种类

我们最常用的一种文件系统叫磁盘文件系统, 它是用磁盘作为存储介质在上面存数据.

这上面我们定义了各种各样的文件系统, 这时候有个问题, 为啥要定义这么多种文件系统, 我有一种是不是就够用了 ?

当然不是, 不同的文件系统, 由于存的数据不同, 它会做不同的优化, 它使用场景的不同也会做各种不同的优化. 比如我们的光盘, 它的文件系统是一次性写入, 多次读出; 而正常磁盘文件系统是多次写入多次读出的, 会有修改. 这样的话它的优化角度是会不一样的.

然后不同的文件系统, 它的安全要求不同, 安全要求等级越高, 它的访问效率也会相对下降. 对于我要求安全级别不高的文件系统, 我可能就会把安全机制减弱, 甚至于取消, 这样我们就构成了多种不同文件系统.

• 数据库文件系统
  • 文件特征是可被寻址 (辨识) 的
  • 例如 WinFS

再有一类是数据库文件系统, 它可以基于文件特征来被寻址或者被检索. 一个例子是 WinFS

• 日志文件系统
  • 记录文件系统的修改/事件

再有一个是日志文件系统, 也就说我们对文件系统的修改, 这些我必须以原子的形式来进行, 因为我的数据很关键. 比如我银行里的这些记录的修改.

这时候我们构成日志文件系统, 它是指文件系统上所有修改, 它都会做相应的记录, 以避免我这个操作执行到半截导致我文件系统损坏, 由此导致数据丢失.

• 网络分布式文件系统
  • 例如 : NFS, SMB, AFS, GFS

这时候实际上相当于, 我们看到的是把文件存到远端的机器上, 这时候不同的网络访问方式构成了我们这里不同的文件系统

• 特殊/虚拟文件系统

再有一个是特殊文件系统, 比如像我们前面讲道德进程间通讯中用到的管道, 就是一类特殊的文件系统

网络/分布式文件系统

• 文件可以通过网络被共享
  • 文件位于远程服务器
  • 客户端远程挂载服务器文件系统
  • 标准系统文件访问被转换成远程访问
  • 标准文件共享协议, NFS for linux, CIFS for windows

前面的文件共享是在一个系统里多个进程之间进行共享; 分布式文件系统呢, 它是想通过网络来进行文件共享, 文件被存放在远端的服务器上

对于这种情况, 我们用户在访问远端文件系统的时候, 要通过挂载远端服务器上的文件, 这时候就会有网络通讯, 我们正常的标准的文件操作就会被转换成网络上远程访问

这样我们在这里存在多种分布式文件系统的共享协议, NFS, CIFS, 这是 unix 和 windows 常用的两种网络文件系统

• 分布式文件系统的挑战
  • 客户端和客户端上的用户辨别起来很复杂
  • 一致性问题
  • 错误处理模式

对于分布式文件系统, 我们会面临比原来更大的麻烦. 比如说在本地我只需要标识这个用户是谁, 我能标识清楚, 这个安全的管理就可以实施了.

而在网络环境上, 你想识别一个用户, 这时候它会更加复杂. 所以在这种情况下, 我们用到的 NFS 实际上它是存在某些安全隐患的.

再有一个问题就是一致性问题. 加了网络之后, 我读写的时候这个一致性就更难把握了

出了错误之后, 我的错误处理也会比原来更复杂, 这都是网络上的分布式文件系统所面临的挑战

虚拟文件系统

虚拟文件系统的提出是为了面对我们有多种不同的文件系统, 而操作系统当中它又希望对手提供一个统一的接口.

文件系统的实现

这个问题就涉及到了文件系统的实现

• 分层结构
  • 虚拟 (逻辑) 文件系统 (VFS, Virtual File System)
  • 特定文件系统模块

文件系统采用了一种分层的结构, 这中间为了把上边抹平, 弄成一致的, 在这里加了一个虚拟文件系统

它使得文件系统对上层应用提供统一的文件访问和文件系统控制的系统调用接口; 然后中间维护各种文件系统所共同的一些数据结构和常用的操作算法; 然后下面来对各种不同的实际的文件系统提供相应的访问接口, 这就是我们所说的虚拟文件系统

虚拟文件系统 (VFS)

• 目的
  • 对所有不同文件系统的抽象

那么在虚拟文件系统里面, 它的目标是要针对所有的不同的文件系统给出一个抽象. 在这里面具体要提供的功能有这样几个 :

• 功能
  • 提供相同的文件和文件系统接口
  • 管理所有文件和文件系统关联的数据结构
  • 高效查询例程, 遍历文件系统
  • 与特定文件系统模块的交互

一个是, 对上提供相同的文件和文件系统访问接口; 然后它在内部维护所有文件和文件系统相关的数据结构, 这是各种文件系统统一的; 然后在这里有一组高效的查询例程来完成对文件系统的遍历; 再往下是对特定的文件系统模块提供相应的交互接口.

这是对下的, 有了这些之后, 我们就希望能够把各种各样的文件系统统一到一起, 然后对上层用户提供统一的接口

文件系统基本数据结构

具体说起来, 在文件系统里有三个基本的树状结构

• 文件卷控制块 (Unix : "superblock")
  • 每个文件系统一个
  • 文件系统详细信息
  • 块、块大小、空余块、计数/指针等

一个是文件卷控制块, 就是我们通常所说的超级块. 它里面是每个文件系统对应着有一个文件卷控制块, 里面描述了这个文件系统的详细信息. 详细信息比如说它的数据块有多大, 有多少数据块已经分出去了, 还有多少是空闲的, 相应的共享等等这些引用的计数.

• 文件控制块 (Unix : "vnode" or "inode")
  • 每个文件一个
  • 文件详细信息
  • 访问权限、拥有者、大小、数据块位置等

第二个是文件控制块, 通常也是我们所说的索引节点, 或者叫 inode, 说的都是它.

每一个文件有一个文件控制块; 在里面描述了这个文件的详细信息; 比如说这个文件的访问权限, 拥有者, 大小和数据块所在的位置等等这样一些信息.

• 目录项 (Linux : "dentry")
  • 每个目录项一个 (目录和文件)
  • 将目录项数据结构及树型布局编码成树型数据结构
  • 指向文件控制块、父目录、子目录等

再有一个是目录项, 目录里面是由目录项组成的, 每个目录项对应着一个子目录, 或者说一个文件; 然后所有这些目录项的数据结构和树状的分层结构, 形成了文件系统的数据结构; 然后这里主要维护的是每一个目录项所对应的文件控制块在哪, 它的父目录子目录分别在哪, 这样的话就形成了我们这里的树状的数据结构了.

文件系统的组织视图

有了这些基本的数据结构之后, 我们就可以看到这样一张文件系统组织结构

文件卷控制块到每一个目录项; 这些目录项组织成一个树状结构; 树状结构里再往下一层是每一个文件, 它的文件控制块; 文件控制块知道它实际的, 文件里面的数据块

这是构成了文件系统里的组织视图.

在这种视图的情况下, 我们就要去来讨论它的存储

文件系统的存储结构

• 文件系统数据结构

  • 卷控制块 (每个文件系统一个)
  • 文件控制块 (每个文件一个)
  • 目录节点 (每个目录项一个)

• 持久存储在外存中

  • 存储设备的数据块中

上面那些东西都是要存到你的磁盘上的数据块当中

• 当需要时加载进内存
  • 卷控制模块 : 当文件系统挂载时进入内存
  • 文件控制块 : 当文件被访问时进入内存
  • 目录节点 : 在遍历一个文件路径时进入内存

有了这个之后, 当你需要加载的时候, 我们把相应的内容加载到内存里面

它分别在什么时候加载的呢.

卷控制块, 它的内容是在文件系统挂载的时候, 把它加载到内存

而文件控制块, 是在访问相应文件的时候加载到内存. 因为你需要访问文件, 就必须知道它都在哪些位置, 那这时候就把这些内容加载进内存

而目录项呢, 它没有一个统一的时间. 你在遍历, 要找某一个文件的时候, 它会遍历从根目录到相应文件的路径. 遍历的时候, 遇着的, 就把这些目录项都加载到内存中

有了这样一个过程之后, 我们就可以看到文件系统的存储结构

文件系统的存储视图

首先我们看到下面我们的磁盘, 磁盘上面都是一个个基本的数据块单位

然后 vol 是卷控制块, 卷控制块在磁盘的位置是固定的.

卷控制块下边是每一个目录的目录项, 就构成磁盘图片上中间这一段.

目录项里面对应的可能是下一级目录, 或者说是文件. 对应到文件的话, 那么这就是文件控制块

文件控制块里说明了每一个文件所在的位置, 那这就是再往下的一层

这就是我们整个磁盘的存储视图, 有了这个视图之后我们就能知道虚拟文件系统里面, 需要保存的各个文件系统公共的一些信息是什么, 从而也就通过虚拟文件系统把各种实际的文件系统和应用之间的间距给弥补上了, 从而我们可以通过一个统一的接口, 访问各种各样实际的文件系统

文件缓存和打开文件

文件缓存是指我们从磁盘上读数据到内存, 甚至于到 CPU 使用, 中间有多种缓存.

多种磁盘缓存位置

我们先看看这在哪些地方都有可能有缓存

首先我们是在磁盘上有数据; 然后通过磁盘控制器, 来完成对磁盘上扇区的读写, 在这个磁盘控制器上头就有扇区的缓存; 基于这个再往上就是内存, 内存里面我们有数据块的缓存, 同时还有一类虚拟磁盘, 内存虚拟盘, 它用内存来虚拟一个逻辑的磁盘, 然后这个上我们维护了一个每一个打开文件的打开文件表, 打开文件表里面的每一项对应着我这里的一个文件; 最后是到 CPU.

在这里面我们看到内存, 磁盘控制器上面都有缓存. 在我们操作系统里讨论的缓存呢, 是在内存当中的数据块缓存.

数据块缓存

• 数据块按需读入内存
  • 提供 read() 操作
  • 预读 : 预先读取后面的数据块

我们从磁盘上读数据块到内存, 这地方的读呢, 通常情况下是按需进行的.

我有一个 read, 在执行 read 的操作的时候, 会把相应的一整块读到内存里来, 选择我需要的, 给相应的进程拿去使用.

而在读的过程中, 我也可以采取一定的预读机制, 我可以多读几块.

• 数据块使用后被缓存
  • 假设数据将会再次用到
  • 写操作可能被缓存和延迟写入

那么这时候我们认为, 数据块在使用之后会被缓存, 这种缓存的意思在于日后我们这一块可能还会再用到, 如果出现这种情况那我就不用再去磁盘上读了.

在写的时候呢, 也有可能这种写会被延迟到以后, 也就相当于, 我先把它写到内存的缓存里头, 然后后续再有修改的时候而我事先没有写, 这样我就可以把两个写合并到一起, 来往下写.

当然你这种合并之后写有一种风险, 就是可能你前一个写没用进行, 第二个写也没进行的时候, 系统出故障了, 那么你头一个本来认为它已经正常写进去的, 也可能会被丢掉.

• 两种数据块缓存方式
  • 数据块缓存
  • 页缓存 : 统一缓存数据块和内存页

现在我们看这个缓存我们怎么来控制, 这里有两种缓存机制.

一种是数据块缓存, 我读磁盘上的东西, 我放内存里, 我标记这一块内存的东西是磁盘的缓存, 以后你要去读磁盘我先查这个地方.

还有一种机制是页缓存. 从刚才我们的这种讨论, 在虚拟存储里面, 我们会把物理内存不够用的地方放到外存里面.

实际上数据块的缓存, 你可以理解为是我把磁盘上的东西, 在内存里做一个反向的缓存. 从这个角度来讲, 这两者之间有很强的的关联性和相似性, 所以我们可以把这两种机制统一到一起.

---

具体我们来看一下这两种机制

首先是磁盘块缓存, 它和虚拟存储之间是相互隔开的. 你可能会有虚拟页的对换, 也可能会有进程对文件的读写.

在虚拟页对换这个地方的时候, 我看看是否有相应的缓存. 因为我们前面讲的页面置换算法里面, 有一种情况是我会往外写, 或者说, 从磁盘上读的时候, 我有一部分内容在内存里面还是有备份的, 对于这种情况我可以直接从页缓存里拿到相应的结果使用.

---

而对于读写文件, 我可能在内存里有磁盘块的缓存, 我也可以从这里拿出来.

---

这样一来对于这两种情况, 它们在这个磁盘块的数据块的缓存这个地方, 就可以合并到一起. 但是前面虚拟页对换这里多了一级页缓存. 然后数据块缓存再往下就到磁盘上的文件系统

页缓存

而另一种机制是把它俩统一起来

• 虚拟页式存储
  • 在虚拟地址空间中虚拟页面可映射到本地外存文件中

这就是我们这里说的, 逻辑地址空间里面的页面, 经过内核的虚拟存储管理机构, 把它映射到物理内存, 或者说把它映射到外存. 这两者之间都是可以存数据的, 所以它可以利用这种方式来扩展进程可用的逻辑地址空间.

这时候说我们除了把它放在对换区里面, 你也可以认为它是一个文件. 我们还可以对一些可执行文件直接映射到你的可执行文件里面去.

• 文件数据块的页缓存
  • 在虚拟内存中文件数据块被映射成页
  • 文件的读/写操作被转换成对内存的访问
  • 可能导致缺页和/或设置为脏页
  • 问题 : 页置换算法需要协调虚拟存储和页缓存之间的页面数

这种机制实际上和我们这里文件数据块的页缓存机制是一样的. 那么这时候我可以把这个页面缓存到别的文件里面, 也就是我们这里一种情况, 有了这种做法之后, 我们就可能反过来提供一种机制, 就是把文件缓存到内存中, 把你的文件读写转换成对内存的访问. 这样就可以把这两者统一起来.

在这种情况下, 你在文件访问的时候, 就会导致缺页和相应的页面状态的变化, 这是它运用页面缓存的好处.

但是它也会有一个问题, 就是页面置换算法, 我们有一个是给每一个进程分配多少物理页面, 如果是全局置换算法的话, 给整个系统有多少物理页面. 如果说你再把页缓存和磁盘缓存放在一起的话, 这中间的页面数到底分配多少.

实际上这里又多了一个需要动态调节的部分, 这时候你需要在虚拟存储之间和页缓存之间去协调各自物理内存分配情况.

---

有了这种机制之后, 我们可以看到进程的内存访问和文件读写, 会被转换成我这里的页缓存.

如果说有, 直接在内存里面就行了, 如果没有就再转换下面, 去到文件系统里读写. 这是我们说有了文件系统之后, 我缓存的做法.

当然你想要维护这一套做法, 那你所有打开的文件在操作系统里, 都必须维护相关的数据结构, 来记录这些缓存的状态.

我们接下来就看看打开文件的数据结构

文件系统中打开文件的数据结构

• 文件描述符
  • 每个被打开的文件都有一个文件描述符
  • 文件状态信息
  • 目录项、当前文件指针、文件操作设置等

这里面重要的一个内容就是文件描述符. 打开文件表里的每一项就是一个文件描述符所对应的信息. 每一个打开的文件, 都有一个文件描述符.

文件描述符里面包含的信息有相关的文件指针, 文件操作的设置, 以及对应的目录项的缓存.

• 打开文件表
  • 每个进程一个进程打开文件表
  • 一个系统级的打开文件表
  • 有文件被打开时, 文件卷就不能被卸载

这些信息对应过来是每个进程, 有一个进程的打开文件表; 而整个系统有一个系统的打开文件表; 并且在这种情况下, 如果说你某一个文件卷已经有文件被打开, 那么这时候有打开文件的文件卷就不能被卸载, 这就是有些情况下我把系统里的某个文件卷卸载不成功的原因.

打开文件表

有了这个之后我们来看前面说到的, 文件系统组织视图跟我们打开文件怎么对应起来呢.

在这里面你打开某一个文件, 就对应这相应的目录项, 文件控制块和文件的内容需要在内存当中有缓存. 这一信息在内存当中的记录就构成了我们这里的系统打开文件表.

系统打开文件表里有一些内容, 各个进程是不一样的, 那这些不一样的部分就构成了我们进程的打开文件表; 而进程的打开文件表里呢, 共同的部分会映射到系统的打开文件表里面, 这样的话两个进程共用的部分, 它就在打开文件表里面. 这就是我们说到的进程打开文件表和系统打开文件表.

打开文件锁

• 一些文件系统提供文件锁, 用于协调多进程的文件访问
  • 强制 - 根据锁保持情况和访问需求确定是否拒绝访问
  • 劝告 - 进程可以查找锁的状态来决定怎么做

接下来我们看打开文件锁, 也就说有多个进程共享同一个文件的时候, 那么这时候对于它们的访问就需要协调. 操作系统能够提供一种机制, 就是文件锁. 这种机制分成两种实现策略.

一种是强制, 你在访问一个文件的时候, 它根据锁的保持状态和你的访问请求, 来判断是否允许你进行相应的访问, 或者是拒绝你的访问.

还有一种做法是劝告. 实际上在这里, 它是在操作系统提供相应的一些机制, 使得进程可以查询文件打开和锁定的状态, 然后进程就可以想一想自己是应该怎么做.

进程的一种做法是我不管你怎么样, 我直接访问, 因为我对它的中心状态不关心, 或者说这个中心状态对我没用影响; 如果有影响, 那你就可以跟我说, 我延迟一会之后, 等相应操作完成了, 我再来进行相应操作完成我的事情. 这样的话就把打开文件的访问机制变成是应用进程自己来协调. 这是关于数据块缓存和打开文件维护的讨论.

文件分配

文件分配是指我们把哪些块分配给一个文件来存它的数据. 在具体讨论分配方法之前呢, 我们有必要分析一下文件的大小, 也就是说我分配的方法跟文件的大小是有直接关系的.

文件大小

• 大多数文件都很小
  • 需要对小文件提供很好的支持
  • 块空间不能太大

在我们实际数据的统计当中, 我们可以发现, 大多数的文件都是很小的, 所以在我们的分配方法里面, 那个数据块的大小不能太大. 因为如果说你的大部分数据放到一块里有很大的剩余的话, 这个时候的存储效率是比较低的. 所以我们在这需要对小文件提供很好的支持.

当然这个文件小也是相对的. 比如我们用计算机的早期时候, 我的数据, 比如邮件通常情况下是几百字节, 当然也有几千字节的, 不过很少见; 现在的邮件实际上我们上面有一个图片签名, 这下子就是多少 k 出去了, 所以这个大小也是一种相对的.

• 一些文件非常大
  • 必须支持大文件 (64 位文件偏移)
  • 大文件访问需要高效

与此同时我们还有一些非常大的文件, 所以我们分配方法里面必须考虑到如何能支持这些大的文件. 比如说我要描述分配给一个文件的数据块有多少个, 那这时候你有一个标识, 这个标识比如说是个整数, 整数有多少位, 就跟你这里能表示的最大个的文件的大小是直接相关的. 如果说你不足以表示实际用到的最大文件的大小, 那么你这个文件系统就没法来使用了, 所以我们需要对大文件有很好的支持, 要考虑到这个文件可能会比较大.

_文件分配

针对这种文件大小的分布, 我们来看如何进行文件分配

• 如何表示分配给一个文件数据块的位置和顺序

分配指的是我把哪些数据块给一个文件, 但实际上这种分配本质实际上是用什么样的方式来表示一个文件数据块的位置和顺序. 因为这个位置和顺序的表示方法, 直接决定着你如何来分配.

我们看看有怎么样的分配方法.

• 分配方式
  • 连续分配
  • 链式分配
  • 索引分配

---

• 连续分配

我分配一个起点, 然后连续的若干个数据块用来存这个文件

---

• 链式分配

我告诉你在第一块里记第二块的位置, 一直到最后一块

---

• 索引分配

我专门分配一块, 拿来存序号, 说我这里都有哪些块存了数据, 这些块的顺序是什么样子

---

• 指标
  • 存储效率 : 外部碎片等
  • 读写性能 : 访问速度

这几种办法, 我们在选择的时候, 考虑的因素一个是存储效率, 一个是读写性能.

存储效率是说, 我每次分配的最小单位是一块, 所以内碎片我们就没办法进行处理了, 我们在这里能处理的是你在选择数据块大小的时候多考虑一下.

假定这个问题我们忽略, 我们来看外碎片, 也就相当于如果我是连续分配, 中间块数不够的时候, 你想表示大文件就是不行的, 所以在这里你的选择算法有存储效率的问题, 当然我们说后两种算法它就没有外碎片, 但是它有读写性能的问题.

如果我是顺序分配, 那我知道起点然后我就按照序号往下算我就能知道我要访问的任何一个位置在哪, 这样的话我的随机读取的速度就会很快; 但是如果说你是链式分配的话, 那么这时候我要想找中间某一块, 我必须从头往后去找, 去遍历这个链表, 那这时候它的读写性能就会比较差.

这些都是我们在这里讨论文件分配的时候必须考虑的指标.

连续分配

那我们对三种分配办法做一个简要的描述.

• 文件头指定起始块和长度

首先是连续分配. 连续分配是在文件头也就是我们所说的文件控制块里面, 记录起始第一块的位置和长度. 因为我是连续的, 所以我知道第一块和长度之后就能说清楚每一块这个文件分配的块都在什么位置.

• 分配策略
  • 最先匹配, 最佳匹配...

那在这里面我们怎么去找这个连续的这块区域呢 ? 最先匹配, 最佳匹配这些我们在前面的内存分配里面有类似的讨论, 我们就不在这里说了.

• 优点
  • 文件读取表现好
  • 高效的顺序和随机访问

这些做法的特点是文件的读取性能表现非常好, 也可以有很好的顺序和随机读取的性能.

• 缺点
  • 碎片 !
  • 文件增长问题
  • 预分配 ?
  • 按需分配 ?

但是它的麻烦很明显, 就是碎片. 我想分配十块结果现在就剩五块了, 那这五块就没法用了. 如果说我在这里面碎片很多, 这时候它的分配效率会比较差的.

还有一个问题, 这是我们前面内存分配里面很少遇到的或者说不是很重要的问题, 就是文件长度的变化. 我减少长度, 还好说; 增加长度, 如果说正好是分配到一块, 然后后面的块被其它文件占用了, 这个时候怎么办.

因为我们是持久数据保存, 这个保存完之后, 这个数据的长度会增加是极有可能的. 这个问题我们不能忽视, 我可以在后面预留几块, 还是说我分配的时候再把它整个搬运. 从这个角度来讲, 这个长度增加对于它来说是一个比较棘手的事情.

这是第一种做法, 连续分配.

链式分配

接下来我们讨论第二种做法, 链式分配

• 文件以数据块链表方式存储

• 文件头包含了到第一块和最后一块的指针

链式分配就是说我用一个数据块的链表来表示, 在文件头里面有指向第一块的指针, 然后第一块有指向第二块的指针, 按照这个顺序走下去, 同时第一个开头里面再加上一个指向最后一块的指针. 这样一来我们就可以表示清楚一个文件占用的数据块第一块是哪里, 然后都占用了哪些数据块, 数据块的顺序是什么样子.

• 优点
  • 创建、增大、缩小很容易
  • 没用碎片

这个做法的优点是我在这里面增删占用的数据块就很方便. 我任何的数据块都可以插到里面来, 所以它没有外碎片.

• 缺点
  • 无法实现真正的随机访问
  • 可靠性差
  • 破坏一个链, 后面的数据块就丢了

但是它没有办法很方便地实现随机访问. 我想找第一块最后一块, 那这我可以直接从文件控制块里面找到. 但是如果我想找中间一块, 我只能从第一块开始, 按照顺序向后遍历, 我才能找到后面这一块.

实际上这也是链表数据结构的问题, 增删容易查改困难.

再有一条就是它的可靠性. 我们在这里存到磁盘上, 数据放一段时间之后, 或者说多次读写之后, 里面数据可能会出错. 如果说我这里面指向下一块的指针出了错, 那么从这个指针往后面的数据你就丢了, 所以从这个角度讲它的可靠性是比较差的.

这是第二种做法, 链式分配.

索引分配

• 为每个文件创建一个索引数据块
  • 指向文件数据块的指针列表

索引数据块里面存着信息, 告诉你哪些数据块存了数据.

索引数据块的内容是指向所以数据块的指针的列表.

• 文件头包含了索引数据块指针

然后你文件头里面有一个指向索引数据块的指针, 这样的话从文件头就可以知道这个索引块在哪里, 然后从索引块里面我能知道每一块的位置和它们的顺序.

我在文件头里面指向索引块, 索引块里面有每一块的序号和它们的顺序.

• 优点

  • 创建、增大、缩小很容易
  • 没有碎片
  • 支持直接访问

• 缺点

  • 当文件很小时, 存储索引的开销
  • 如何处理大文件 ?

缺点是, 如果我的文件很小, 它一块就能存得下, 但是还得需要分配一个索引块, 那么这时候我又得要两块, 所以这时候它的存储开销是很大的.

如果文件比较大, 大到我索引块里面存的这些序号, 它用一块都放不下了, 这时候我这地方就得再加一个索引块. 如果你这里面不支持加索引块的话, 这样对大文件的支持也会有麻烦.

这三种分配方法各有各的优点和缺点, 我们在实际使用中会把这几种方法组合起来使用.

大文件的索引分配

• 链式索引块 (IB+IB+...)

这时候对于大个的索引文件, 我们又可以在这里组合新的方式, 链式索引块.

总体上来说它是索引分配方法. 我索引块之间用一个链式.

• 多级索引块 (IB*IB*...)

或者索引块之间再做一个索引, 这样就变成了多级索引块.

这是对大文件的表示方法.

UFS 多级索引分配

我们来看一个实际的索引分配方法, 看看它怎么把我们前面所说的各种方法的优点集中在一起, 把缺点去掉.

UFS 是指 Unix File System, unix 文件系统.

它的做法是在这个文件控制块里面, 我前面 10 个是直接索引, 直接 10 块的位置都标在这里. 如果说你的数据比较少, 只有 10 块以内, 我就索引直接到文件对应的数据块.

如果说大于 10 块, 我这时候第 11 个指针, 写的是一个一级间接索引, 在这里指向一个索引块, 这个索引块里面再指向实际的数据块, 这是一个间接索引. 这时候我在间接索引块里能放多少个序号呢, 假定说能放 N 个, 根据你每一个序号所占用的空间不同, 和你块的大小, 这个地方是不一样的.

如果一级索引, 再加上前面的 10 块加在一起仍然不够用, 这里不是再给加一个一级索引, 这里加的是一个二级索引. 这是索引块的索引, 二级索引. 那么只要你大到一定程度之后, 我就不再采用一级索引了, 我采用二级索引.

那二级索引仍然不够用怎么办呢, 那就再加一级, 三级索引.

IB 就是索引块的意思

这时候我们可以看到, 越到后面, 你要想访问到实际的数据块, 它前面是有大量要查询的, 这是我们多级索引面临的麻烦.

• 例子

  • 文件头包含 13 个指针
  • 10 个指针指向数据块
  • 第 11 个指针指向索引块
  • 第 12 个指针指向二级索引块
  • 第 13 个指针指向三级索引块

• 效果

  • 提高了文件大小的限制阈值
  • 动态分配数据块, 文件扩展很容易
  • 小文件开销小
  • 只为大文件分配间接数据块, 大文件在访问数据块时需要大量查询

空闲空间管理

• 跟踪记录文件卷中未分配的数据块
  • 采用什么样的数据结构表示空闲空间列表 ?

有了前面的文件分区, 空闲空间管理相对来说变得更容易了. 原因在于, 这里我们不需要记录它的顺序, 只需要记录和跟踪文件卷中未分配的数据块的分布情况.

当然在这里面它也会有和前面文件分配不一样的地方. 那就是这里面, 随着文件的创建和删除, 空闲状态是随时发生变化的, 我们在这里有什么样的办法来说这个事情呢. 我们要考虑的问题是我用什么样的数据结构来表示空闲空间的这个列表.

空闲空间组织 : 位图

• 用位图代表空闲数据块列表
  • 1111111111111111100011111100
  • Di = 0 表明数据块 i 是空闲, 否则, 表示已分配

首先看到第一种是位图. 每一个块占一位, 然后所有的块对应所有位放到一起, 就构成一个空闲数据块的列表, 在这个列表里面 0 表示对应的数据块 i 是空闲的, 否则表示这一块已经被分配出去了.

• 使用简单但是可能会是一个很大的向量表
  • 160GB 磁盘 -> 40M 数据块 -> 5MB 位图
  • 假定空闲空间在磁盘中均匀分布, 则找到 "0" 之前要扫描 n/r
  • n = 磁盘上数据块的总数
  • r = 空闲块的数目

用这种办法之后, 如果你的文件分区很大的话, 这时候这个向量表占的空间也是很大的.

这地方给出一个例子, 我 160GB 磁盘, 一个数据块 4K, 这样 2^30 * 160, 然后我 4K 就是 2^12 位一块, 这样一个除法, 我就有 4MB 个数据块. 如果说我一个 8 位能表示 8 个数据块, 那就是 5MByte 的位图所占用的空间, 这个空间你需要频繁进行修改, 这时候它的修改量也是很大的.

与此同时我们想要去找到磁盘上一个空闲块, 我要去查这个表, 假设空闲块的分布是均匀的, 那我查表的范围, 查表的时间基本上是磁盘块的总数和空闲块数目之间的一个比. 你占的比例越高, 它就越容易找到, 这是位图表示空闲空间的一种方法.

其他空闲空间组织方式

• 链表

我们前面说到的链表法仍然可以用来表示空闲空间. 每一个空闲块里面有一个指针指向下一块.

这样我就很方便地把我的空闲块找到并组织起来. 当然这种办法它的开销会比较大.

我们也可以把它和其它办法组合到一起, 这就是下面的链式索引

• 链式索引

链式索引, 我最底下一层是用索引, 然后上面用链表. 这样既节省空间又节约时间.

实际上系统里也是这几种方法组合起来用的.

冗余磁盘阵列 RAID

冗余磁盘阵列 raid 实际上是一种提高文件系统可靠性和读写性能的一组技术.

磁盘分区

• 通常磁盘通过分区来最大限度减小寻道时间
  • 分区是一组柱面的集合

通常情况下, 我们在访问磁盘的时候, 由于磁盘上有磁头的移动, 这是一种机械运动, 所以它的性能是相对比较慢的.

通常情况下我们会通过磁盘分区来限制这个寻道的时间, 从而提高它的性能.

分区是一种柱面的集合.

比如说我把一个磁盘上分成了 A B 两个分区. 那每一个分区, 我们在逻辑上都可以视为独立的一个磁盘. 但实际上它是没办法完全独立的.

比如说这里面, 我要是只在 A 分区上进行文件读写, 那么它的性能是会提高的, 但如果说你把这一个磁盘分成了 A B 两个分区, 你的操作系统同时在两个分区上进行切换, 它的性能是很差的.

一个典型的磁盘文件系统组织

• 文件卷 : 一个拥有完整文件系统实例的外存空间, 通常常驻在磁盘的单个分区上

这里有一个典型的文件系统分区的做法, 首先我们说一下文件卷和磁盘分区的关系.

比如说我们把一号磁盘分成 A B 两个分区, 每一个分区有一套自己完整的文件系统实例, 它有目录和文件, 通常前面还有文件卷控制块. 我们还可以把多个磁盘合在一起, 变成一个逻辑的分区, 这样可以扩大你的分区容量, 以便于你在一个分区能够存更多的数据.

这些都没有办法提高我们的读写性能和可靠性.

多磁盘管理

• 使用多磁盘可以改善
  • 吞吐率 (通过并行)
  • 可靠性和可用性 (通过冗余)

多分区管理实际上就想利用多个独立的磁盘同时使用来提高它的性能, 也就是通过并行提高它的吞吐量, 然后来提高它的可靠性. 也就是通过冗余, 比如说数据存多份, 来提高它的可靠性和可用性.

• 冗余磁盘阵列 (RAID, Redundant Array of Indexpensive Disks)
  • 多种磁盘管理技术
  • RAID 分类
  • 如 RAID-0, RAID-1, RAID-5

具体说起来, 冗余磁盘阵列, 实际上 raid 是一组磁盘管理的技术. 它通过条带化、映像和带校验的条带化来实现对磁盘可靠性性能的提升.

• 冗余磁盘阵列的实现
  • 软件 : 操作系统内核的文件卷管理
  • 硬件 : RAID 硬件控制器 (I/O)

这组技术的实现方法有两种. 一种我们可以做到操作系统文件系统里面, 通过文件系统的卷管理来实现上面说到的这些冗余磁盘阵列的技术.

也可以用硬件来实现, 用硬件的 RAID 控制器. 用这种控制器, 实际上在你的操作系统中, 感觉不到它的存在, 就像是用一个分区一样的.

下面我们来看这几种冗余磁盘阵列技术, 它所能带来的好处和它的具体做法.

RAID-0 : 磁盘条带化

• 把数据块分成多个子块, 存储在独立的磁盘中
  • 通过独立磁盘上并行数据块访问提供更大的磁盘带宽

第一种 RAID-0 是一种磁盘条带化技术, 它通过把数据块分成若干个子块, 然后把这些子块存在独立的磁盘上, 注意这里一定是要独立. 我在一个硬盘上把它分成多个逻辑分区是不起作用的.

通过这些独立硬盘上的并行数据来提高磁盘的带宽.

我们看一下具体的做法.

假定我这里有三个磁盘, 然后在操作系统层面上, 看到一个数据块是这样的, 那我在存储的时候呢, 我把它分成三个子块, 这里一行是一块.

然后我把它存到这三个磁盘上, 这样的话我如果说是写数据, 那么我是三个磁盘同时写, 它的速度应该会提高近三倍; 如果是读数据, 我可以从三个磁盘一起来读, 这时候它的速度也会提升三倍.

但如果说你读取的数据量小, 这时候你读三个, 但是我只要第一个里的数据, 这时候它的速度是没有提升的.

这是第一种做法, RAID-0.

RAID-1 : 磁盘镜像

• 向两个磁盘写入, 从任何一个读取
  • 可靠性成倍增长
  • 读取性能线性增加

第二种做法是 RAID-1, 磁盘镜像. 它通过同时向两个磁盘写入相同的数据, 来提高它的可靠性. 当然你读取的时候, 可以从任何一个来读取. 如果你读取的数据可以同时从两个里面读的话, 它的性能会提高一倍.

它的具体做法是, 这里有两个物理的硬盘, 我们把它划成分区, 然后我把数据同时存在这两个上面, 这时候写的性能是跟原来一样的, 然后如果你读取很多数据的话, 读的性能是会提高的.

这是磁盘镜像, 它的主要特征是提高可靠性.

RAID-4 : 带校验的磁盘条带化

• 数据块级的磁盘条带化加专用奇偶校验磁盘
  • 允许从任意一个故障磁盘中恢复

它的做法是把数据块做条带化, 并且加了一个校验磁盘, 专门用来存校验和, 这时候你的存储容量是没有条带化那么高的, 但是它的可靠性提高了. 也就是说 N 个磁盘, 其中有一个错误的时候, 是可以恢复过来的. 它允许任意一个磁盘出现故障, 然后从里面把数据完整恢复出来.

假定我这有 5 个磁盘, 那我用来存数据采用条带化是前面 4 个, 最后一个用来存它的校验和. 在存校验和的时候, 我需要根据前面四个数据去算这个校验和.

我读数据的时候, 需要把它们全部一起算出来, 然后去判断它是否正确. 任何一个出错我都可以从这里把它恢复回来. 这样的话就提高了它的可靠性, 也提高了它的读写性能. 当然这里的可靠性是不如有我们刚才这个镜像那么高.

那我这边 N 个磁盘里, 1/N 的可能性它会坏掉, 那我是能恢复的, 如果更多的话那就不行了.

RAID-5 : 带分布式校验的磁盘条带化

这种做法和 RAID-4 相比, 它就是把校验和的存放位置做了一个分布, 不是把校验和固定存在校验磁盘上.

这样的做法可以把校验磁盘的访问瓶颈分摊开来, 从而提高它的性能.

我们具体来看它如何实现的.

我们把每一个数据块分散到这 5 个磁盘上. 第一个 X, 它的校验和假定我们说是在 5 号磁盘上, 最后一个磁盘. 然后下一个存的时候, 它的校验和就不是存放在这个 5 号磁盘上了, 而是存放在 1 号上. 第三个的时候, 我再放到 2 号磁盘. 第四个我再放到 3 号磁盘上.

这样的话, 我们在每次读写的时候, 这个校验和的这种依赖也就变得分散开了. 这样就可以减少它对校验和所在的那个磁盘的读写压力.

基于位和基于块的磁盘条带化

这些技术都是用来提高它的读写性能和它的可靠性的, 它们都是基于数据块的.

• 条带化和奇偶校验按 "字节" 或者 "位"
  • RAID-0/4/5 : 基于数据块
  • RAID-3 : 基于位

实际上它也可以基于字节或者基于比特位.

这种做法实际上相当于我们这里 RAID-0 4 5, RAID -3 是基于位的

这种做法实际上区别在于哪里呢

假定我有三个磁盘, 它做校验怎么办. 这是基于每一块里的, 每一位组合到一起来使用的. 当然现在我们在实际系统里, 用得最多的还是基于数据块的.

可纠正多个磁盘错误的冗余磁盘阵列

• RAID-5 : 每组条带块有一个奇偶校验块

  • 允许一个磁盘错误

• RAID-6 : 每组条带块有两个冗余块

  • 允许两个磁盘错误

我们还可以进一步扩展, RAID-5 可以恢复一个磁盘的错误. 那如果有多个呢 ? 实际上我们在这里有 RAID-6, 它增加了两个冗余块, 那这样的话我可以允许有两个磁盘出错的时候, 它也是可以恢复的, 这样就进一步提高它的可靠性.

当然这种可靠性到底提高了多少, 要根据你数据重要性和你对可靠性的要求.

RAID 嵌套

与此同时我们这些技术也允许把它嵌套在一起来使用.

比如我们说 RAID-0 是提高它的性能, 而 RAID-1 可以提高它的可靠性, 那这时候我是不是可以在提高性能的同时提高它的可靠性呢 ?

• RAID 0+1

这时候就把这两个组合起来, 成为 RAID 0+1.

首先是两个磁盘之间做条带化, 这时候你往里面读写的时候它的性能会提高. 然后在这基础上我再做一个镜像. 那么可靠性就提高了.

当然我们这里的办法来提高性能和可靠性, 成本也是大幅度提高的.

这上面两个 RAID-0 组合到一起变成 RAID-1, 就是 RAID 嵌套

• RAID 1+0

这个嵌套也可以反过来, 底下是 RAID-1 先做镜像, 然后上面套一层 RAID-0. 我往两个里面写, 也是起到类似的效果.