文件系统管理类和优化

Disk space management　磁盘空间管理

  • 文件通常存放在磁盘上
  • 存储 n 字节文件的策略
    • 分配n个连续字节的磁盘空间
      • 如果文件增长，则必须将其移动到磁盘上，这是一项昂贵的操作并会导致外部碎片化。
    • 分配 [n/k] 个大小为 k 字节的块
      • 块不需要相邻。

block size 块大小

  • 当块大小增加时，磁盘空间利用率降低
    • 内部碎片化，空间效率降低
    • 这意味着每个文件，甚至一个1字节的文件，都要占用一整个柱面，小的文件浪费了大量的磁盘空间
  • 当块大小减小时，数据传输速率降低
    • 时间效率降低
    • 大文件会跨越多个块，需要多次寻道与旋转延迟才能读出它们
    • 通常大小 k = 512 字节、1k (UNIX) 或 2k

Keeping Track of Free Blocks 记录空闲块

使用位图 bit-map

  • Free blocks ->1, Allocated blocks -> 0
  • 具有 (n) 个块的磁盘需要具有 (n) 位的位图
    • 空闲块由 1 表示
    • 已分配块由 0 表示
    • 16GB 磁盘有 \(2^{24}\)个 1-KB 并且需要 \(2^{24}\) 位 → 2048 个块
    • 使用链表 =\(2^{24}\)/255 = 65793 个块

使用磁盘块的链表

  • 具有 1 KB 块和 32 位磁盘块号。
  • 每个块保存尽可能多的空闲磁盘块号。
    • → 1024 * 8/32 = 256 个磁盘块编号
    • → 255 个空闲块（和）1 个下一个块指针.

File System Backup 文件系统备份
  • 备份是为了处理：从灾难或愚蠢中恢复。
  • 备份的注意事项
    • 整个或部分文件系统
    • Incremental dumps 增量转储：仅转储已更改的文件
    • 压缩 Compression
    • 备份活动文件系统
    • 安全

转储磁盘的两种策略：

  • Physical dump 物理转储：
    • 从块 0 开始到最后一个磁盘块，按序输出到磁带上
    • 优点：简单快捷
    • 缺点：备份一切
  • Logical dump 逻辑转储：
    • 从一个或多个指定目录开始，并递归转储自某个给定基准日期以来已更改的所有文件和目录

File System Consistency 文件系统一致性
  • 大多数操作系统都有一个实用程序，称为文件系统检查器，用于测试文件系统的一致性。
    • 例如，UNIX 中的 fsck，Windows 中的 sfc
  • 可以进行两种类型的一致性检查：
    • 块的一致性检查
    • 文件的一致性检查

块一致性检查

  • 构建两个表，每张表中为每个块设立一个计数器，都初始化为 0
    • 第一个表中的计数器跟踪每个块在文件中出现的次数。
    • 第二个表的计数器记录在空闲表或空闲位图中的出现次数，
  • 然后，程序读取所有 i 节点并使用 i 节点构建文件中使用的所有块的列表（在读取每个块时在其文件计数器+1）。
  • 检查空闲列表或位图以查找所有未使用的块（为空闲列表中的每个块在其空闲列表计数器+1）

文件系统状态

  • 一致
    • 每一块在第一个表计数器中为1，或者在第二个表计数器中为1
  • 块丢失
    • 将丢失的块添加到空闲列表
  • 空闲列表中的重复块
    • 磁盘块4在空闲块中出现了两次，重新建立空闲表
  • 重复数据块
    • 将数据块复制到空闲块

  • 检查目录
    • 使用一张计数器表，一个文件对应于一个计数器，从根目录开始检验，递归检查每个目录，对每个目录的每个文件，将文件使用计数器加1。完成后，会得到一张由i节点号索引的表，说明每个文件被多少个目录包围。
    • 从根目录开始保留每个文件的计数器列表，递归检查每个目录。
    • 对于每个文件，增加文件 i-node 的计数器
  • 将计算值与存储在每个 i 节点中的链接计数进行比较。
    • i-node 链接计数 > 计算值 = 目录条目数。
    • 即使删除所有文件，i-node 链接计数 > 0。因此不会删除 i-node。
    • 解决方案：设置 i-node 链接计数 = 计算值
    • i-node 链接计数 < 计算值
    • 目录将指向未使用的 i-node
    • 解决方案：设置 inode 链接计数 = 计算值

问题

Check Points

  • Please describe the two methods for keeping tracks of free blocks.
    • freelist bitmap
  • Please describe the two strategies for dumping a disk.
    • physical logical
  • Please describe the two types of consistency checks .
    • block file