文件系统和磁盘调度(上)：https://developer.aliyun.com/article/1459601
虚拟文件系统
- 分层结构
上层：虚拟(逻辑)文件系统
底层：特定文件系统模块
- 目的
对所有的不同文件系统的抽象
- 功能
提供相同的文件和文件系统接口
管理所有的文件和文件系统关联的数据结构
高效的查询例程，遍历文件系认
与特定的文件系统模块的交互
需要包含那些内容：
- 卷控制块
每个文件系统一个
文件系统详细信息
块，块大小，空余块、计数指针等
- 文件控制块
每个文件一个
文件详细信息
许可、拥有者、大小、数据库位置等
- 目录节点
每个目录项一个
将目录项数据结构和树形布局编码成树形数据结构
指向文件控制块，父节点和项目列表
数据块缓存
数据块需要按需读入内存
- 提供read操作
- 预读：预选读取后面的数据块
数据块使用后被缓存
- 假设数据将会被使用
- 写操作可能被缓存和延时写入
两种数据块的缓存方式
- 普通缓冲区缓存
- 页缓存：统一缓存数据块和内存页
分页要求：
当需要一个页的时候才将其载入内存
支持存储
一个页可以被映射到一个本地文件中
打开文件
- 打开文件描述
每个被打开的文件一个
文件状态信息
目录项，当前文件指针、文件操作设置等
- 打开文件表
一个进程一个
一个系统级的
每个卷控制块也会保存一个列表
所以如果有文件被打开将不能被卸载
锁的保护机制：
- 一些操作系统和文件系统提供该功能
- 调节对文件的访问
- 强制和劝告：
强制：根据锁保持情况和需求拒绝访问
劝告：进程可以查找锁的状态来决定怎么做
文件分配
- 大多数文件都很小
需要对小文件提供强力的支持
块空间不能太大
- 一些文件非常大
必须支持大文件(64-bit文件偏移)
大文件访问需要相当高效
如何为一个文件分配数据块？
- 分配方式
连续分配
文件头指定起始块和长度
位置/分配策略
最先匹配，最佳匹配
优势：文件读取表现好； 高效的顺序和随机访问
劣势：碎片！； 文件增加问题：预分配？按需分配？
链式分配
文件以数据块链表方式存储
文件头包含了到第一块和最后一块的指针
优点：创建、增大、缩小很容易；没有碎片
缺点：不可能进行真正的随机访问；可靠性不强：破坏一个链然后…
索引分配
为每个文件创建一个名为索引数据块的非数据数据块
文件头包含了索引数据块
优点：创建增大缩小很容易；没有碎片；支持直接访问
缺点：当文件很小时，存储索引的开销，如何处理大文件？链式索引快，多级索引块
- 指标
高效：如存储利用率
表现：如访问速度
空闲空间管理
跟踪在存储中所有未分配的数据块
空闲空间列表存储在哪里？空闲空间列表的最佳数据结构是什么样的？
- 用位图代表空闲数据块列表：
使用简单但是可能会是一个big vector
需要保护
执行空闲列表的指针
位图
必须保存在磁盘上
在内存和磁盘拷贝可能有所不同
不允许block在内存中的状态为bit而在磁盘中bit
解决
在磁盘上设置bit[i]为1
分配block[j]
在内存中设置bit[i] = 1
- 链式列表
- 分组列表
RAID多磁盘管理
- 通常磁盘通过分区来最大限度减小寻道时间
一个分区是一个柱面的集合
每个分区都是逻辑上独立的磁盘
- 分区：硬件磁盘的一种适合操作系统指定格式的划分
- 卷：一个拥有一个文件系统实例的可访问的存储空间
- 使用多个并行磁盘来增加
吞吐量
可靠性和可用性
- RAID - 冗余磁盘阵列
各种磁盘管理技术
RAID levels:不同RAID分类
- 实现
在操作系统内核：存储、卷管理
RAID硬件控制器
RAID0
- 数据块分成多个子块，存储在独立的磁盘中
和内存交叉相似
- 通过更大的有效块大小来看提供更大的磁盘带宽
RAID1
- 可靠性城北增长
- 读取性线性增加
向两个磁盘写入，从任何一个读取
RAID3
- 存储Bit-string 作奇偶校验
RAID4
- 数据块级磁带配有专用奇偶校验磁盘
允许从任意一个故障磁盘中恢复
RAID5
- 每个条带块有一个奇偶校验块
允许一个磁盘出错
RAID6
- 两个冗余块
有一种特殊的编码方式
允许两块磁盘错误
组合方式
- RAID01
- RAID10
其他
磁盘调度
- 读取或者写入时，磁头必须被定为在期望的磁道，并从所期望的扇区开始
- 寻道时间：定为到期望磁道所花费的时间
- 旋转延迟：从扇区的开始处到达目的处花费的时间
- 平均班旋转延时时间：磁盘旋转一周时间的一半
调度手段：
- 先进先出：
按顺序处理请求
公平对待所有进程
在很多进程的情况下，接近随机调度性能
- 最短服务优先：
选择从磁臂当前位置需要移动最少的I/O请求
总选择最低端的寻道时间
- SCAN方式
磁臂在一个方向上个移动，满足所有未完成的请求，知道磁臂到达该方向上的最后的磁道
调换方向
有时被称为 elevator algorithm
- C-SCAN
限制了仅在一个方向上的扫描
当最后一个磁道也被访问过之后，磁臂返回到磁盘的另外一端再进行扫描
- C-LOOK
C-SCAN的改进版本
磁臂先到达该方向上最后一个请求处，然后立即反转
- N-step-SCAN
在SSTF/SCAN和CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况，例如进程反复请求对某一个磁道的IO操作。我们把这一现象称为磁臂粘着
N-step-SCAN算法是将磁盘请求队列分为若干个长度为N的字队列，磁盘调度将按照FCFS算法依次处理这些子队列。而每处理一个队列时优势按照SCAN算法，对每一个队列处理完成之后再处理其他队列
当正在处理某个子队列时，如果出现新的磁盘I/O请求，便将新的请求进程放入其他队列，这样就可以避免出现粘着现象
- FSCAN
FSCAN算法实质上是N步SCAN算法的简化，即FSCAN只将磁盘请求队列分成两个子队列
一个是由于当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按照SCAN算法仅此呢个处理。在处理某个队列期间，将新出现的所有请求磁盘I/O的进程，放入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理
