美文网首页
Modern OS & OS Concept -文件系统(fil

Modern OS & OS Concept -文件系统(fil

作者: 1哥 | 来源:发表于2021-10-28 00:10 被阅读0次

    Modern OS & OS Concept -文件系统(file system)

    1.背景

    所有应用有存取信息的需求。存取信息的第一个问题是,进程运行的时候,它能存储有限数量的信息于它自己的地址空间中,这个存储的容量受限于虚拟地址空间的大小。但是对于某些应用来说远远不够。
    第二个问题是保存进程地址空间的信息:进程正常运行结束后,保存在进程地址空间的信息会丢失。进程有些信息需要长久保存,甚至由于计算机崩溃而杀死进程,这个信息也不能丢失。
    第三个问题,多个进程能同时访问这个信息。如果信息存在进程的地址空间,只有这个进程能访问。需要解决这个问题让信息本身独立于任何一个进程。
    因此,对于长期信息存储,有三个必不可少的的要求:

    • 必须能存大量的信息;
    • 使用信息的进程终结后,信息还能存活;
    • 多个进程能同时访问信息。

    磁盘

    • 一直以来用于长期存储,近些年SSD日益流行起来。
    • 可以看作是一个线性的块序列,每个块大小固定;
    • 支持两个操作:
      i)读block 号为K 的block;
      ii)写block 号为k的block。

    但这些操作方式在大型的有需要应用程序和需要用户使用的系统中,都极其不方便。几个关键问题:

    • 如何找到信息?
    • 怎么防止一个用户访问另一个用户的信息?
    • 如何知道磁盘的哪些block 是空闲的?

    正如OS 从处理器概念抽象创建进程,从物理内存概念抽象出提供进程虚拟地址空间一样。OS 解决这个问题采用一种新的抽象:文件。进程,地址空间,文件是OS最重要的概念。

    进程创建文件,磁盘上存放大量文件;
    OS(文件系统)负责管理文件;

    • 结构化文件;
    • 命名;
    • 保护文件;
    • 文件系统视角:
      • 用户视角:用户如何命名文件,组织文件
      • 实现视角:文件是如何在磁盘中组织的

    2.用户视角

    2.1 文件命名

    • 所有OS 都用1~8个字母;
    • 用后缀作为名字的一部分;

    2.2 文件结构

    image.png

    字节序列

    • 最灵活,可以放任何内容

    • UNIX和 windows采用这种

    固定长度的记录

    • 一个文件有一系列的记录组成;

    • 每个记录有内部的结构

    • 读操作返回一条记录,写操作则覆盖或追缴一条记录

    • 现代OS 不在使用这种;

    树形结构

    • 文件有一个记录树组成,每个记录不必同样长度;
    • 在记录的固定位置有key;
    • 树按key 排序
    • 可通过key 来查找记录;

    2.3 文件类型

    • 普通文件-包含用户信息
    • 字符特殊的文件
    • 块特殊文件-磁盘

    2.4 文件属性-metadata

    文件除了名字和文件中的数据外,还有相关其他的信息,文件属性。


    image.png

    2.5文件操作

    create,delete,open,close,read,write,oppend,seek,get attributes,set attributes,rename

    2.7 目录

    层级结构

    • 一级目录系统


      image.png
    • 层级目录系统


      image.png

    目录操作

    create. delete, opendir, closedir, readdir, rename, link, unlink

    3.文件系统实现

    用户关心文件命名,可以对文件进行的操作,目录树长什么样及对目录的操作。文件系统的实现则关心文件和目录如何存储,磁盘恐怕如何管理,如何让每件事情工作得高效可靠。

    3.1 文件系统layout

    • 文件系统存储在磁盘上;

    • 磁盘可分成一个或多个分区,每个分区有单独的文件系统;

      • MBR
        1)磁盘 sector 0
        2)用于引导启动计算机
        3)MBR的最后一部分是分区表;
        分区表记录每个分区的起始,结束地址;
        表中的其中一个分区会Mark成active状态;
        引导计算机时,BIOS会读并执行MBR,然后MBR会首先定位active 分区,然后执行该active分区的第一个block ,即boot block,然后执行它;
      • Boot block
        1)负责装载包含在该分区的OS;
        2)每个分区包含一个boot block, 即使它不包含可引导的OS
      • super block
        1)包含文件系统的所有关键参数
        magic number;
        文件系统的block 数量;
        其他关键管理信息
        2)计算机启动或者首次使用文件系统的时候会读进内存中
    • 空闲空间管理
      以bitmap或者链表指针的形式

    • inode 表
      每个文件一个inode, 描述该文件的所有信息

    • 根目录
      包含文件系统树的根部

    • 文件和目录


      image.png

    3.2 文件的实现

    • 连续分配
      优点
      易于实现:只需要记录第一个block号,block 数
      读性能好,只需要一次寻道操作
      缺点
      随着时间前进,磁盘空间会出现碎片化
      文件创建时需要知道文件大小;
      外部碎片化,需要压缩空间,开销大
      image.png
    image.png
    • 链表分配

      1. 每个文件以链表的方式将block联系起来存储
      2. 每个block的第一个dword指向下一个block
      3. 最后一个block的第一个dword指向0;
      4. 没有外部碎片化;
      5. 随机读很慢:定位一个文件的第n个block,需要从0到第n-1 block 逐个读,一次读一个;
      6. 文件的每个block 有几个字节由指向下一个block的地址占用着,读文件数据需要将block直接的有效数据拼接在一起,有拷贝的开销;


        image.png
        image.png
    • 使用内存中的表的链表分配

      1. 链表分配的缺点可通过将每个block的指针放在内存中和放在一个内存的表(FAT)中消除;
      2. 将指针放在内存的表中;
      3. 随机访问会更快;
      4. 不适合大容量的磁盘:整个表必须一直在内存中,但会随着文件系统的容量增加而增大。


        image.png
        image.png
      • i-node
        1. 将指向数据block 的所有指针集合在一个地方,索引block;
        2. 每个文件有自己的索引block,包含一个元素是数据block的地址的数组;
        3. 用一个inode数据结构存放文件属性和block地址;
        4. 与使用内存中的表的链表分配相比,优势是,只有相应打开的文件的inode需要在内存中;
        5. k 个active 文件,每个inode占n(B),需要n*k(B) ;
        6. 支持小文件和大文件的机制:
          • 链式方案:
            i) 正常小文件只需要1个索引block 来存放文件的磁盘block 地址;
            ii) 为支持大文件,将多个索引block 链接在一起。如一个索引block 前面是100个数据block 地址,最后 一个地址为下一个索引block 的指针,对于小文件该值为NULL
          • 多级索引
            i) 大文件需要多个索引block,多级索引;
            ii) 第一级索引block 指向第二级索引block的集合;第二级索引block 指向文件数据block;
            iii) 可以类似有多级索引;
          • 链式索引和多级索引结合的方案:
            i) 基于UNIX 的文件系统采用的方案;
            ii) 文件inode中索引block 有15个指针;
            iii) 前12 个指针指向直接block,也就是数据block地址;(高达48KB 数据可以直接访问)
            ix)后面三个指针指向间接block;
            第一个指向single 间接block;
            第二个指向double间接block;
            第三个指向triple 间接block;


            image.png
    image.png image.png

    3.3 目录的实现

    • 文件读之前,需要打开文件,文件打开OS使用文件名定位在磁盘的目录项;
    • 目录项提供找到磁盘block 的信息;
      可使整个文件的磁盘地址信息(连续分配)
      or 第一个block 的地址号;(链表分配)
      or inode 号;
    • 实现文件名字到定位文件数据的信息的映射;
      文件属性存在目录项里面;
      or 文件属性存在inode 中,目录项存inode号和文件名


      image.png
    • 不同长度文件名处理
      固定文件头+变长文件名
      or 使用堆存放文件名,使用指针指向文件名
      image.png

    3.4 日志结构文件系统(Log-structured FS)

    • 动机
      1)磁盘cache 越来越快,多数读请求可通过文件系统cache;
      2)多数磁盘操作是小块的写,效率低
      3)写一个文件,目录inode,目录block,文件inode, 文件本身都必须写
    • 优化写
      1)将整个磁盘当成一个大log;
      2)收集小size的写请求,定期的作为一个连续的segment写到磁盘log的最后;
      3)一个segment 可能包含inode, 目录block,数据block,所有都混合在一起;
      4)每个segment 的开始是一个segment summary, 对这个segment 内容的总结;
      5)可利用满带宽;
      6)inode 散落在整个log 中。而不是在磁盘的固定位置;
      7)inode map 定位inode
      inode号作为索引,得到的entry 指向inode 文件的inode;
      存在磁盘上;
      在内存中缓存起来用来定位inode;
      8)整理线程-垃圾回收,释放没有使用的空间;
      9)面对故障,很健壮;
      10)不兼容多数文件系统,不怎么使用

    3.5 日志文件系统(Journaling FS)

    在对文件系统的采取每一个动作前先记录一个日志,写到磁盘里,然后再执行这个动作 ,完成这个动作后,清除掉这个日志
    系统崩溃发生在执行之前,可以重启后重新执行日志里的动作

    4.文件系统管理和优化

    4.1 磁盘空间管理

    • 两种策略:分配连续的空间,分配不连续的空间
    • 类似于内存空间管理,分段和分页
    • 几乎所有文件系统将文件切分成多个固定大小的block,block 直接不必连续;
    • 空闲block的管理
      • bitmap
        i)每个block 用1bit 表示
        若空闲,为1;
        若已分配,为0;
        2)CPU 提供位操作指令
        3)block 号计算 = 每个dw,bit的位数 * 为0的dw的个数 + 第一个为1的bit 的偏移
      • 链表
        1)将所有空闲block 链接在一起;
        2)将链表头指针放在文件系统特殊的位置,缓存在内存中;
        3)不容易获取连续的空间;
        4)没有浪费;
      • 分组
        修改链表来让第一个空闲的block,存放后面n-1个空闲block的地址 及下一个包含空闲block 地址的 block 地址;
      • 计数
        1)基于采用连续分配extents,空间经常连续分配,连续释放;
        2)存第一个空闲block 地址和后面空闲block的个数;
        3)空闲空间链表的每个entry包含地址和个数;
      • Trim 未使用的blocks
        1. HDD 能够原地覆盖更新,只需要空闲list
          • 释放block的时候,不需要特殊处理;
          • block上的数据仍然在,但没有文件指针指向它,直到被覆盖;
        2. NVM 设备不允许原地覆盖
          • 写之前需要擦除,擦除是以更大的块,并且很慢;
          • Trim 是一种文件系统通知NVM 设备一个page是空闲的机制
            GC;(free,但未trim)
            or 空闲,block 可以擦出;(free&&trim)

    4.2文件系统效率和性能

    效率依赖

    • 磁盘分配,目录算法;
    • 文件目录项存放数据的类型;
    • metadata 数据结构的预分配,or 按需分配;
    • 固定大小 or 可变大小的数据结构

    性能

    • 数据和metadata 一起靠近存放;
    • buffer cache- 单独的一块内存用于频繁访问的block;
    • 同步写请求
      i) APP 请求或OS需要
      ii) 不buffer和caching- write 必须落盘
    • 异步写,更常见,可cache, 更快
    • 顺序写优化技术
      i) free behind
      一旦请求下一个page,就将该page 从缓存中移除;
      之前的page 不可能再次使用并且浪费缓冲buffer空间;
      ii) read ahead (预读)
      请求页和它后续的页都读上来,并缓冲起来;
      这些后续的页很有可能会有请求要访问;
    • page cache
      使用虚拟内存技术和地址来缓存页,而不是磁盘block;
      文件数据使用page cache;
      使用虚拟内存更高效,
    • buffer cache
      缓存磁盘block,以文件系统block 为单位;
      文件系统IO 使用buffer cache;
    • 统一buffer cache
      使用同样的page cache 缓存文件系统IO和文件数据,避免都double caching


      image.png

    4.3 文件系统恢复

    • 动机:系统崩溃可能导存储的文件系统数据结构之间不一致;
      1) 许多文件系统原地更新数据结构;
      2) 一个操作可能包含对多个数据结构的修改;
      3) 这些改动可能会被系统崩溃打断;
      4) 处于IO性能考虑,会cache更新,若在cache 落盘前系统崩溃;
    • 恢复方法
      • 一致性检查
        1. 先检查,然后尝试修复;
        2. 扫描每个文件系统上所有metadata来确认文件系统是否一致;
        3. 但比较耗时;
        4. 应该每次系统启动时就扫描检查;
          • 可在文件系统metadata中记录状态;
          • 任何metadata 改变,对该状态置位,以指示metadata变动;
          • 所有metadata的更新落盘后,清除该位;
          • 若系统该状态位仍然是置位状态,需要一致性检查;
        5. unix 系统使用fsck 程序
      • 日志结构/日志文件系统
        • 将每个metadata的更新作为一个交易记录到文件系统中;
        • 所有交易写到一个日志里
          1. 一旦交易写到日志中,commit状态
          2. 可以在文件数据结构中回放日志entry里的操作;
        • 日志中的交易是异步更新到文件系统数据结构中的
          一旦完成交易,删除日志中的交易
        • 若系统崩溃,日志中的剩下的交易必须继续执行;
        • 更快从系统崩溃中恢复,消除了metadata 不一致的可能;
      • 文件系统备份
        • 处理两种情况:
          设备故障中恢复;
          误操作;
        • 备份一个设备的数据到另外一个设备中;
        • 然后从备份中恢复数据;
        • 增量备份
          第一次,做完整备份;
          后面每次都基于上一次备份做周期性增量备份;
          恢复需要从完整备份开始然后包含每次增量备份;

    相关文章

      网友评论

          本文标题:Modern OS & OS Concept -文件系统(fil

          本文链接:https://www.haomeiwen.com/subject/moswoltx.html