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 文件结构
字节序列
最灵活，可以放任何内容
UNIX和 windows采用这种
固定长度的记录
一个文件有一系列的记录组成；
每个记录有内部的结构
读操作返回一条记录，写操作则覆盖或追缴一条记录
现代OS 不在使用这种；
树形结构
- 文件有一个记录树组成，每个记录不必同样长度；
- 在记录的固定位置有key；
- 树按key 排序
- 可通过key 来查找记录；
2.3 文件类型
- 普通文件-包含用户信息
- 字符特殊的文件
- 块特殊文件-磁盘
2.4 文件属性-metadata
文件除了名字和文件中的数据外，还有相关其他的信息，文件属性。
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）计算机启动或者首次使用文件系统的时候会读进内存中
- MBR
空闲空间管理
以bitmap或者链表指针的形式inode 表
每个文件一个inode, 描述该文件的所有信息根目录
包含文件系统树的根部-
文件和目录
image.png
3.2 文件的实现
-
连续分配
优点：
易于实现：只需要记录第一个block号,block 数
读性能好，只需要一次寻道操作
缺点：
随着时间前进，磁盘空间会出现碎片化
文件创建时需要知道文件大小；
外部碎片化，需要压缩空间，开销大
image.png
-
链表分配
- 每个文件以链表的方式将block联系起来存储
- 每个block的第一个dword指向下一个block
- 最后一个block的第一个dword指向0；
- 没有外部碎片化；
- 随机读很慢：定位一个文件的第n个block,需要从0到第n-1 block 逐个读，一次读一个;
-
文件的每个block 有几个字节由指向下一个block的地址占用着，读文件数据需要将block直接的有效数据拼接在一起，有拷贝的开销；
image.png
image.png
-
使用内存中的表的链表分配
- 链表分配的缺点可通过将每个block的指针放在内存中和放在一个内存的表（FAT）中消除；
- 将指针放在内存的表中；
- 随机访问会更快；
-
不适合大容量的磁盘：整个表必须一直在内存中，但会随着文件系统的容量增加而增大。
image.png
image.png
-
i-node
- 将指向数据block 的所有指针集合在一个地方，索引block；
- 每个文件有自己的索引block，包含一个元素是数据block的地址的数组;
- 用一个inode数据结构存放文件属性和block地址；
- 与使用内存中的表的链表分配相比，优势是，只有相应打开的文件的inode需要在内存中；
- k 个active 文件，每个inode占n(B),需要n*k(B) ;
- 支持小文件和大文件的机制：
- 链式方案：
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
- 链式方案：
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
- HDD 能够原地覆盖更新，只需要空闲list
- 释放block的时候，不需要特殊处理；
- block上的数据仍然在，但没有文件指针指向它，直到被覆盖；
- NVM 设备不允许原地覆盖
- 写之前需要擦除，擦除是以更大的块，并且很慢；
- Trim 是一种文件系统通知NVM 设备一个page是空闲的机制
GC；（free,但未trim）
or 空闲,block 可以擦出;(free&&trim)
- HDD 能够原地覆盖更新，只需要空闲list
-
bitmap
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 落盘前系统崩溃； - 恢复方法
- 一致性检查
- 先检查，然后尝试修复；
- 扫描每个文件系统上所有metadata来确认文件系统是否一致；
- 但比较耗时；
- 应该每次系统启动时就扫描检查；
- 可在文件系统metadata中记录状态；
- 任何metadata 改变，对该状态置位，以指示metadata变动；
- 所有metadata的更新落盘后，清除该位；
- 若系统该状态位仍然是置位状态，需要一致性检查；
- unix 系统使用fsck 程序
- 日志结构/日志文件系统
- 将每个metadata的更新作为一个交易记录到文件系统中；
- 所有交易写到一个日志里
- 一旦交易写到日志中，commit状态
- 可以在文件数据结构中回放日志entry里的操作；
- 日志中的交易是异步更新到文件系统数据结构中的
一旦完成交易，删除日志中的交易 - 若系统崩溃，日志中的剩下的交易必须继续执行；
- 更快从系统崩溃中恢复，消除了metadata 不一致的可能；
- 文件系统备份
- 处理两种情况：
设备故障中恢复；
误操作； - 备份一个设备的数据到另外一个设备中；
- 然后从备份中恢复数据；
- 增量备份
第一次，做完整备份；
后面每次都基于上一次备份做周期性增量备份；
恢复需要从完整备份开始然后包含每次增量备份；
- 处理两种情况：
- 一致性检查
