2019-06-20发表2023-12-15更新《操作系统》笔记30 分钟读完 (大约4446个字)0次访问

11 文件系统 | 《操作系统》笔记

这一系列是操作系统 (清华大学向勇、陈渝)视频课的课堂笔记，主要是课堂 PPT 和部分讲授内容的文字版，仅供参考。

基本概念

文件系统：种用于持久性存储的系统抽象
- 分配文件磁盘空间
  - 管理文件块（哪一块属于哪一个文件)
  - 管理空闲空间（哪一块是空闲的）
  - 分配算法（策略）
- 管理文件集合
  - 定位文件及其内容
  - 命名：通过名字找到文件的接口
  - 最常见：分层文件系统
  - 文件系统类型（组织文件的不同方式）
- 提供的便利及特征
  - 保护：分层来保护数据安全
  - 可靠性/持久性：保持文件的持久即使发生崩溃、媒体错误、攻击等
文件：文件系统中一个单元的相关数据在操作系统中的抽象
- 文件属性
  - 名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、……
- 文件头
  - 在存储元数据中保存了每个文件的信息
  - 保存文件的属性
  - 跟踪哪一块存储块属于逻辑上文件结构的哪个偏移
文件描述符
- 文件使用模式
  - 使用程序必须在使用前先“打开”文件
  - 内核跟踪每个进程打开的文件
    - 操作系统为每个进程维护一个打开文件表
    - 一个打开文件描述符是这个表中的索引
- 需要元数据数据来管理打开文件
  - 文件指针：指向最近的一次读写位置，每个打开了这个文件的进程都这个指针
  - 文件打开计数：记录文件打开的次数，当最后一个进程关闭了文件时，允许将其从打开文件表中移除
  - 文件磁盘位置：缓存数据访问信息
  - 访问权限：每个程序访问模式信息
- 视角
  - 用户视角
    - 持久的数据结构
  - 系统访问接口
    - 字节的集合（UNIX）
    - 系统不会关心你想存储在磁盘上的任何的数据结构
  - 操作系统内部视角
    - 块的集合（块是逻辑转换单元，而扇区是物理转换单元）
- 用户怎么访问文件：在系统层面需要知道用户的访问模式
  - 顺序访问：按字节依次读取
    - 几乎所有的访问都是这种方式
  - 随机访问：从中间读写
    - 不常用，但是仍然重要。例如，虚拟內存支持文件：内存页存储在文件中
    - 更加快速：不希望获取文件中间的内容的时候也必须先获取块内所有字节
  - 基于内容访问：通过特征
    - 许多系统不提供此种访问方式，相反，数据库是建立在索引内容的磁盘访问上（需要高效的随机访问）
- 文件结构
  - 无结构
    - 单词、比特的队列
    - 简单记录结构
    - 固定长度
    - 可变长度
  - 复杂结构
    - 格式化的文档（如 Word、PDF）
    - 可执行文件
- 多用户系统
  - 访问控制
    - 谁能够获得哪些文件的哪些访问权限
    - 访问模式：读、写、执行、删除、列举等
  - 文件访问控制列表（ACL）
    - <文件实体,权限>
  - Unix 模式
    - <用户|组|所有人,读|写|可执行>
    - 用户 ID 识别用户，表明每个用户所允许的权限及保护模式
    - 组 ID 允许用户组成组，并指定了组访问权限
  - 指定多用户/客户如何同时访问共享文件
    - 和过程同步算法相似
    - 因磁盘 I/0 和网络延迟而设计简单
  - Unix 文件系统（UFS）语义
    - 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
    - 共享文件指针允许多用户同时读取和写入文件
  - 会话语义
    - 写入内容只有当文件关闭时可见
  - 锁
    - 一些操作系统和文件系统提供该功能
目录
- 文件以目录的方式组织起来
- 目录是一类特殊的文件
  - 每个目录都包含了一张表 <name, pointer to file header>
- 目录和文件的树型结构
  - 早期的文件系统是扁平的（只有一层目录）
- 典型操作
  - 搜索文件
    - 文件名的线性列表，包涵了指向数据块的指针
      - 编程简单
      - 执行耗时
    - Hash 表
      - 减少目录搜索时间
      - 碰撞：两个文件名的 hash 值相同
      - 固定大小
  - 创建文件
  - 删除文件
  - 枚举目录
  - 重命名文件
  - 在文件系统中遍历一个路径
    - 名字解析：逻辑名字转换成物理资源（如文件）的过程
      - 在文件系统中：到实际文件的文件名（路径）
      - 遍历文件目录直到找到目标文件
    - 举例:解析“/bin/ls”
      - 读取 root 的文件头（在磁盘固定位置）
      - 读取 root 的数据块；搜索“bin”项
      - 读取 bin 的文件头
      - 读取 bin 的数据块；搜索“ls”项
      - 读取 1s 的文件头
    - 当前工作目录（做了缓存）
      - 每个进程都会指向一个文件目录用于解析文件名
      - 允许用户指定相对路径来代替绝对路径
- 操作系统应该只允许内核模式修改目录
  - 确保映射的完整性
  - 应用程序能够读目录（如 ls）
- 挂载
  - 一个文件系统需要先挂载才能被访问
  - 一个未挂载的文件系统被挂载在挂载点上
文件别名：两个或多个文件名关联同一个文件
- 硬链接：多个文件项指向一个文件
  - 硬链接的 inode 值相同
  - 两个文件地位等同：删除任一个文件还在
- 软链接：以“快捷方式”指向其他文件
  - 软链接的 inode 和源文件的不同，其所指向的内容实际上是保存了一个绝对路径
  - 软链接文件和源文件的地位不等同：删除源文件该文件就不在了
- 我们如何保证没有循环呢？
  - 只允许到文件的链接,不允许到子目录的链接
  - 每增加一个新的链接都用循环检测算法确定是否合理
- 更多实践
  - 限制路径可遍历文件目录的数量
文件系统种类
- 磁盘文件系统
  - 文件存储在数据存储设备上，如磁盘
  - 例如：FAT、NTFS、ext2/3/4、IS09660(CDROM)等
- 数据库文件系统
  - 文件根据其特征是可被寻址（辨识）的
  - 例如：WinFS
- 日志文件系统
  - 记录文件系统的修改的文件系统
  - 例如: journaling file system
- 网络/分布式文件系统
  - 例如：NFS、SMB、AFS、GFS
- 特殊/虚拟文件系统
  - 不是为了存储数据，而是以文件的形式展现读写接口来交互或者访问内核中的一些数据
  - 例如：/proc
- 其他问题
  - 文件可以通过网络被共享
    - 文件位于远程服务器
    - 客户端远程挂载服务器文件系统
    - 标准系统文件访问被转换成远程访问
    - 标准文件共享协议：NFS for Unix、CIFS for Windows
  - 分布式文件系统的问题
    - 客户端和客户端上的用户辨别起来很复杂，例如：NFS是不安全的
- - 一致性问题
  - 错误处理模式

虚拟文件系统：是在内存而非硬盘中的一个概念

目的
- 对所有不同文件系统的抽象
功能
- 提供相同的文件和文件系统接口
- 管理所有文件和文件系统关联的数据结构
- 高效查询例程，遍历文件系统
- 与特定文件系统模块的交互
分层结构
- 上层：虚拟（逻辑）文件系统
- 底层：特定文件系统模块
文件系统数据结构
卷控制块（Unix: superblock）
- 每个文件系统一个
- 文件系统详细信息
- 块、块大小、空余块、计数/指针等
目录控制块（Linux: dentry）
- 目录文件就是一系列目录项（dirent）的列表。每个目录项，由两部分组成：所包含文件的文件名，以及该文件名对应的inode号码
文件控制块（Linux：struct inode；BSD：vnode，其中 v 表示 virtual file system）
- 文件数据都储存在”块”中，那么很显然，我们还必须找到一个地方储存文件的元信息，比如文件的创建者、文件的创建日期、文件的大小等等。这种储存文件元信息的区域就叫做 inode，中文译名为”索引节点”
- 每个 inode 都有一个号码，操作系统用 inode 号码来识别不同的文件，Unix/Linux 系统内部不使用文件名，而使用 inode 号码来识别文件。对于系统来说，文件名只是 inode 号码便于识别的别称或者绰号
- 表面上，用户通过文件名，打开文件。实际上，系统内部这个过程分成三步：
  - 首先，系统找到这个文件名对应的 inode 号码
  - 其次，通过 inode 号码，获取 inode 信息
  - 最后，根据 inode 信息，找到文件数据所在的 block，读出数据
数据块
- 操作系统读取硬盘的时候，不会一个扇区一个扇区地读取，这样效率太低，而是一次性连续读取多个扇区，即一次性读取一个”块”（block）。这种由多个扇区组成的”块”，是文件存取的最小单位。”块”的大小，最常见的是4KB，即连续八个 sector组成一个 block
持续存储在磁盘中
- 在分配在存储设备中的数据块中
当需要时加载进内存
- 卷控制模块：当文件系统挂载时进入內存
- 文件控制块：当文件被访问时进入每次
- 目录节点：在遍历一个文件路径时进入内存

数据块缓存/缓冲

数据块按需读入内存
- 提供 read() 操作
- 预读：预选读取后面的数据块
数据块使用后被缓存
- 假设数据将会再次被使用
- 写操作可能被缓存和延迟写入
两种数据块缓存方式
- 普通缓冲区缓存
- 页缓存：统一缓存数据块和内存页
文件数据块的页缓存
- 在虚拟内存中文件数据块被映射成页
- 文件的读/写操作被转换成对内存的访问
- 可能导致缺页和/或设置为脏页

打开文件的数据结构

打开文件描述
- 每个被打开的文件一个
- 文件状态信息
- 目录项、当前文件指针、文件操作设置等
打开文件表
- 一个进程一个
- 系统级的
- 每个卷控制块也会保存一个列表
- 所以如果有文件被打开将不能被卸载
强制和劝告
- 强制：根据锁保持情况和需求拒绝访问
- 劝告：进程可以查找锁的状态来决定怎么做

文件分配

大多数文件都很小
- 需要对小文件提供强力的支持
- 块空间不能太大
一些文件非常大
- 必须支持大文件（64-bit 文件偏移）
- 大文件访问需要相当高效
如何为一个文件分配数据块
- 指标
  - 高效：如存储利用（外部碎片）
  - 表现：如访问速度
- 分配方式
  - 连续分配
    - 文件头指定起始块和长度
    - 位置/分配策略（类似于内存分配）：最先匹配、最佳匹配、……
    - 优势
      - 文件读取表现好
      - 高效的顺序和随机访问
    - 劣势
      - 碎片
      - 文件增长问题：预分配？按需分配？
  - 链式分配
    - 文件以数据块链表方式存储
    - 文件头包含了到第一块和最后一块的指针
    - 优点
      - 创建、增大、缩小\很容易
      - 没有碎片
    - 缺点
      - 不可能进行真正的随机访问（串行访问）
      - 可靠性：破坏一个链整个文件可能就会损坏
  - 索引分配
    - 为每个文件创建一个名为索引数据块的非数据数据块
      - 到文件数据块的指针列表
      - 读取文件时首先将索引放到内存中去
    - 文件头包含了索引数据块
    - 优点
      - 创建、增大、缩小很容易
      - 没有碎片
      - 支持直接访问
    - 缺点
      - 当文件很小时，存储索引的开销相对较大
      - 如何处理大文件：索引块可能不够表示这个大文件
  - 其他方法
    - 链式索引块
      - 会出现和链式分配相同的问题：如果链断了可能造成整个文件损坏
    - 多级索引块
    - 文件头包含 13 个指针
      - 10 个指针指向数据块;
      - 第 11 个指针指向间接数据块
      - 第 12 个指针指向二重间接数据块
      - 第 13 个指针指向三重间接数据块
    - 影响
      - 提高了文件大小限制阀值
      - 动态分配数据块，文件扩展很容易
      - 小文件开销小
      - 只为大文件分配间接数据块，大文件在访问间接数据块是需要大量的查询

空闲空间列表

用位图代表空闲数据块列表
- 111111111111111001110101011101111…
  - 如果 i=0 表明数据块 i 是空闲，反之则己分配
- 使用简单但是可能会是一个 big vector
  - 160GB disk -> 40M blocks -> 5MB worth of bits
  - 如果空闲空间在磁盘中均匀分布，那么在找到“0”之前需要扫描 n/r 位

  * n = 磁盘上数据块的总数
  * r = 空闲块的数目

如何保证一致性
问题
- 必须保存在磁盘上
- 在内存和磁盘拷贝可能有所不同
- 不允许 block[i] 在内存中的状态为 bit[i]=1 而在磁盘中 bit[i]=0：内存中的数据是真实数据，如果此时断电导致内存没有及时写回硬盘，那么下次启动时 block[i] 就会以硬盘数据为准导致认为操作系统认为该数据块为空闲而覆盖数据
  - 解决
    - 对于需要将某一位置 1 时，先在硬盘上设置，再在内存中设置
      - 在磁盘上设置 bit[i]=1
      - 分配 block[i]
      - 在内存中设置 bit[i]=1
其他方法
- 链式列表
- 分组列表

多磁盘管理 - RAID

基本概念
- 分区：硬件磁盘的一种适合操作系统指定格式的划分
- 卷：一个拥有一个文件系统实例的可访问的存储空间，通常常驻在磁盘的单个分区上，可以把多个磁盘当成一个卷来管理
使用多个并行磁盘来增加
- 吞吐率（通过并行）
- 可靠性和可用性（通过冗余）
实现方式
- 软 RAID：在操作系统和磁盘系统之间增加一个 RAID 层，来完成磁盘阵列的管理
- 硬 RAID：实现在芯片中，放在主板上，对于操作系统来说就是一个硬盘
RAID - 冗余磁盘阵列
- 各种磁盘管理技术
- RAID levels：不同 RAID 分类，如 RAID-0、RAID-1、RAID-5
原理
- RAID-0：提升吞吐率
  - 数据块分成多个子块，存储在独立的磁盘中，和内存多通道相似
  - 通过更大的有效块大小来提供更大的磁盘带宽
- RAID-1：提高可靠性
  - 可靠性成倍增长（容错，恢复损坏数据）
  - 读取性能线性增加：向两个磁盘写入，从任何一个读取
- RAID-4：提升吞吐率与可靠性
  - 数据块级配有专用奇偶校验磁盘
    - 允许从任意一个故障磁盘中恢复
    - 例如：存储 8,9,10,11,12,13,14,15,0,1,2,3
  - 但是 Parity Disk 读写会成为瓶颈
- RAID-5：将奇偶校验分在多个盘中而不是集中在一个盘中
  - 但是只能同时纠一个错误
- RAID6：两个冗余块
  - 有一种特殊的编码方式
  - 允许两个磁盘错误
- 其他方法
  - 条带化和奇偶校验按 byte-by-byte 或者 bit-by-bit
    - RAID-0/4/5：block-wise
    - RAID-3：bit-wise
  - 在 RAID-3 系统中存储 bit-string 101
磁盘调度
- 略