兰斯小窝

Appearance

ch11 文件系统的实现 ​

11.3 文件系统的结构 ​

  • 存在两个设计问题：
    1. 如何定义文件系统对用户的接口？即文件及其属性，所允许的操作，在组织文件的目录结构等，第十章内容
    2. 创建怎样的数据结构和算法将逻辑文件系统映射到物理外存设备上？
  1. 逻辑块与物理块
    1. 逻辑块
      • 文件系统将磁盘视为一个逻辑空间，该空间就像一个大数组，数组的每个元素时文件系统操作的基本单位——逻辑块。比如数据库表里的每行记录就是一个逻辑记录
      • 逻辑块一般从0开始，大小为扇区大小的2n倍
    2. 物理块
      • 物理块时数据在磁盘上的存取单位，也就是每进行一次I/O操作，最小传输的数据大小，一般情况下，一个物理块对应一个扇区（有时对应多个）
      • 为了让整数n次I/O读进来一个逻辑块，所以把逻辑块的大小为设置为扇区大小的2n倍
  2. 文件系统分层设计
    • 为了实现从逻辑地址到物理磁盘地址的转换，采用分层设计，上层（逻辑文件系统）负责管理文件逻辑数据，中间层（文件组织模块）负责将逻辑地址转化为基本闻不见系统的物理块地址，下层（基本文件系统）对底层驱动程序发送物理地址读写指令 alt text
    • 逻辑文件系统（logical file system）：通过文件控制块（FCB）管理文件的所有不包括具体数据（数据块内容）的结构数据，即元数据（metadata），维护文件结构
    • 文件组织模块（file organization module）：通过逻辑文件系统传入的FCB，使用FCB种文件分配类型和文件的位置信息，算出基本文件系统所用的物理块地址

11.4 目录的实现 ​

  1. 目录的本质

    • Unix系统中将目录视为文件，称为目录文件，目录文件的内容时目录表，阿紫打开文件前就将目录文件信息加载进内存，根据查询对应文件名的一行记录找到文件的位置信息
    • 两种常用的目录表
      • DOS等系统采用，如FAT文件系统，实现简单，但不利于文件分享（第二种可以实现共享索引节点号（Unix系统里的FCB）来实现文件的共享，而这种方法不是获得指向FCB的指针而是FCB的具体内容，所以不易共享） alt text
      • Unix采用，将FCB与文件名分开，目录表简单（名号目录项），便于文件分享 alt text

  2. 文件控制块（FCB）

    • 文件控制块（FCB）是一种数据结构，它包含了一个文件的所有结构信息，通过目录表里的叶节点种文件名和FCB号的一一映射，我们可以根据文件名获取该文件的FCB，我们后期所有对单一文件的操作所需要的信息本质上都来源于FCB
    • 一般FCB的结构，注意FCB种包含对该文件数据块物理地址的指针 alt text
    • Unix里由incode充当FCB这个角色，它的数据块地址索引的设计上采用了多级索引结构，很适合不同大小的文件灵活使用 alt text

  3. 目录实现的数据结构

    1. 先行列表（Linear List）：将目录文件的每行信息用线性表组织起来，易于编程和查找，创建新文件困难
    2. 哈希表（Hash Table）：根据哈希函数易于查找，但是会出现冲突（collision），出现溢出块（类比数据库的哈希索引）降低效率，但是还是要比线性表全表查找快

11.5 文件系统的实现 ​

  1. 文件系统的物理结构
    1. 磁盘上
      • 磁盘可以整体用作一个操作系统，也可以将一个磁盘分为几个磁盘分区或片（partition），每个分区创立一个文件系统。这些分区可以组合成卷（volume）的结构，在卷上创立文件系统，也就是卷上的文件系统可以使用多个子文件系统（分区上的文件系统），这就开阔了之前安装（mount）的概念，每个分区都相当于一个“U盘” alt text
      • 磁盘上，文件系统包含以下结构：
        1. 卷的引导控制块（per volumn bootcontrol block）：该卷如果有操作系统，则存放引导信息，没有则为空，Unix又称引导块
          • 占据文件系统的开始，一般是一个扇区
          • 含有被读入机器起引导或初启动OS的引导代码
          • 每个文件系统都有一个引导块（可能是空的）
        2. 卷控制块（per volumn control block）：包括卷的详细信息，包括卷分区的块数，块的大小，空闲块的数量和指针，空闲FCB的数量和指针，Unix里又称超级块（super block）
          • 文件系统的规模（多大空间）
          • 文件系统空闲块的数目
          • 文件系统中可用的空闲块表（链表的表头）
          • 索引节点表的大小（决定改文件系统能创建的文件数）
          • 文件系统中空闲索引节点的数目
          • 文件系统中空闲索引节点表
          • 空闲索引节点中下一个空闲索引节点的下标
          • 空闲索引节点表中下一个空闲索引节点的下标
          • 空闲块表的锁字段和空闲索引节点表锁字段
          • 指明超级块倍修改过的标记
        3. 每个文件系统的目录结构（Directory structure per file system）：就是目录表，一个文件系统一个，卷上的“大”文件系统也需要有一个目录结构，目录就存在这里，在想打开该文件系统的文件时，这一块需要先载入内存。
        4. 每个文件的PCB
        5. 具体文件数据块
    2. 内存中，也就是说操作系统对文件系统的认识，它了解磁盘上的文件系统只能通过以下形式，当一个文件系统安装时装入这些结构，写在时删除这些结构
      1. 安装表（mount table）：包含指向安装设备文件系统超级块的指针
      2. 目录结构缓存（directory-structure cache）：实现目录对文件的查找
      3. 系统范围内的打开文件表（system-wide open file table）：每个打开文件的FCB副本和其他信息
      4. 每个进程的打开文件表（per-process open file table）：一个指向系统范围打开文件表中对应文件条目的指针和其他信息
  2. 打开文件表（open file table）：当一个进程想要提交对某文件的删除操作时，为了保证实现当只有所有对该文件的引用都被撤销时这一文件才从磁盘上删除，必须记录当前文件被引用的数量，这就要求只为相同文件激励一个全局的表，当有进程打开引用该文件时计数就加1，一个进程对该文件关闭时，计数就减1。单独为进程维护一个表，无法实现全局的计数删除
  3. Unix中open()和read()的操作实现
    1. open()操作：用户给open()传入一个文件的逻辑路径名，这是先将该文件系统的目录载入内存，根据文件名，操作系统会首先对下同范围内的打开文件表进行搜索（节省时间），如果这个文件被其他进程打开了，则直接将该进程的打开文件表中的指针指向系统范围打开文件表这一页，同时，系统打开文件表引用计数加上1；如果这个文件在系统范围文件表中不存在，说明该文件第一次打开，则对该文件系统的目录表进行搜索，依次寻找叶节点，叶节点包含了一个该文件控制节点（inode）号，即控制接待你的物理位置指针，将这个指针返回给用户，同时在系统范围打开文件表注册一行这个文件的信息，将该进程的打开文件表中指针指向的这条新信息，open()操作的任务就完成了
    2. read()操作：通过open()操作返回的该文件的索引节点号从进程的打开文件表中的指针找到系统的打开文件表中该文件的inode(FCB)物理位置指针，将该FCB读入内存，通过FCB中文件存储类型和存储地址的信息算出数据块的存储地址，将数据块读入即可完成read()操作 alt text
  4. 磁盘分区
    • 分区分为生分区（raw）和熟分区（cooked）
    1. 生分区：没有文件系统的磁盘分区，可以用作页帧对换区（swap space）；数据库自己建文件系统管理自治一样
    2. 熟分区：装有文件系统的磁盘分区，采取了逻辑格式化Format，逻辑格式化Format可以创建文件系统
    • 逻辑格式化Format做了哪些事：
      1. 划分磁盘块：将一定的扇区组织成磁盘块
      2. 创建文件系统，建立文件系统在磁盘上的布局以及建立文件系统所使用的数据结构，比如引导块，超级块，目录表，FCB表（索引节点表），文件分配表（如FAT），空闲块索引表等
  5. 再看目录的安装
    • 将主文件系统位于内存的目录结构中对应的安装点（mount point）的inode上加一位标记，并将指向新的文件系统的超级块的指针i骄傲入道主文件系统的安装表（mount table）中，当遍历到对应inode节点时去安装表里找指针，遍历加入新的文件系统，实现文件系统里的无缝切换
  6. 虚拟文件系统（Virtual File System，VFS）
    • 虚拟文件系统是一个物理文件系统与文件系统服务之间的一个接口层（VFS Interface），它对每个物理文件系统的所有细节进行抽象，并为这些不同的文件系统提供了一个统一的系统调用接口
    • 严格来说，VFS并不是一种实际的文件系统。它只存在于内存中，不存在于任何外存空间。VFS在系统启动的时候建立，在系统关闭时消亡 alt text

11.6 文件物理空间的分配方法 ​

  1. 连续分配（contiguous allocation）
    • 每个文件在磁盘上占有一组连续的块，可以用第一块磁盘地址和连续块的数量来定义 alt text
    • 优点：实现简单，随机读取速度快，效率高，适合文件内容不进行变动的情况（swap space）
    • 问题：难以对文件进行扩展，需要提前声明文件大小，产生外碎片
    • 分配方法：best fit，first fit，worst fit；next fit
  2. 链接分配（linked allocation）
    • 每个文件是磁盘表的链表，磁盘块分布在磁盘的任何地方，目录块包含文件第一块和最后一块的指针 alt text
    • 优点：实现简单，只需要首地址，没有外碎片问题，文件可以拓展，无需事先说明文件大小
    • 问题：每个文件块都有指针，占用空间；无法实现随机读取；可靠性差，一个中间数据中指针丢失会导致整个链的断裂
    • 加入文件分配表（File Allocation Table，FAT）的链接分配改进版
      • 每个卷的开始部分用来储存该卷的FAT，每块在该表中都有一项，该表可以通过块号码进行索引，FAT使用和链表类似，目录条目含有文件首块的块号，根据块号索引的FAT条目包含文件的下一块号，这条链一直继续道最后一块，该块对应的FAT条目的值为文件的结束值，该项村一个特殊结尾符号表示文件的结束 alt text
      • 优点：通过以下I/O一次性读入FAT表进入内存，就可实现岁任意文件任意位置的随机访问（链表移动工作放在了内存对FAT表项的移动）
      • 问题：如果不采用（Cache）将FAT表读入内存，会导致每次访问都要先访问FAT表，导致访问时间的浪费
  3. 索引分配（indexed allocation）
    • 把所有指针放到统一的索引块上，上面存放着磁盘块地址的数组，索引块的第i个条目指向了文件的第i块 alt text
    • 优点：随机访问；可扩展，文件不需要提前声明大小；没有外碎片
    • 浪费空间（比如一个文件只有两块大小，才有链接分配只浪费一个指针空间，采用索引分配则浪费1块索引块的空间）
    • 当索引块多余一块的时候，需要提供管理组织索引块的机制，有三种方案
      1. 链接方案：将索引块链接起来，每块流出一个字节来存放下一块索引的指针 alt text
        • Q1：应该访问第几个索引块？
        • Q2：应该访问索引块的第几行上对应的数据块
        • R2：块内偏移量
      2. 多层索引方案：将一个链接块索引指向第二层的索引块，第二层的索引块再指向文件数据块，扩展性极强 alt text
      3. 组合方案 alt text

11.7 空闲空间管理 ​

  1. 位向量（bit vector）：将空闲空间表现为位图（bit map），每块空闲空间用一位表示，如果空闲则为1，已分配则为0
    • 优点：实现相对简单
    • 缺点：如果磁盘块过多，对用的超级块空闲空间分配位图也很大
  2. 链表（linked list）：将所有空闲磁盘块用链表链接起来，并将指向第一个空闲块的头指针保存在磁盘的超级块上，同时也缓存在内存中（类似页式管理的空闲帧列表） alt text
    • 优点：查询时占用内存空间小（读进一块即可，优于位向量法）
    • 问题：不可靠；不易找到大量空闲块，查找费时
  3. 改进措施
    1. 组（grouping）：对于空闲链表而言，可以将n个空闲块的地址存在第一个空闲块中，之后的n-1块确实为空，最后一块包含另外n个空闲块的地址
      • 优点：可以快速找到大量空闲块的地址
    2. 计数（counting）：建立一个类似于分区内训管理里中的分区表；每个表项记录第一块的地址和与第一块连续的空闲块的数量；
      • 优点：容易找到连续的空间；需要额外的空间，但表的总长度会更短，因为连续块的数量往往大于1

11.8 例题 ​