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)计算机启动或者首次使用文件系统的时候会读进内存中
- 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 不一致的可能;
- 文件系统备份
- 处理两种情况:
设备故障中恢复;
误操作; - 备份一个设备的数据到另外一个设备中;
- 然后从备份中恢复数据;
- 增量备份
第一次,做完整备份;
后面每次都基于上一次备份做周期性增量备份;
恢复需要从完整备份开始然后包含每次增量备份;
- 处理两种情况:
- 一致性检查
网友评论