526互联

chapter 12: 块设备 I/O 和缓冲区管理

发布时间 2023-11-13 14:30:22作者: 20211108俞振阳

学习笔记

摘要

本章深入研究了区块设备 I/O 和缓冲管理，重点介绍了原则、I/O 缓冲的优势以及 Unix 缓冲管理算法的不足之处。提出使用信号量设计更高效的缓冲管理算法，介绍了 PV 算法作为示例。还提供了一个编程项目，用于比较 Unix 的缓冲管理算法和 PV 算法，有助于理解文件系统的 I/O 操作。

12.1 区块设备 I/O 缓冲

  • 磁盘 I/O 比内存访问慢，促使使用 I/O 缓冲以减少物理 I/O 操作。
  • I/O 缓冲涉及使用缓冲器作为块设备的缓存内存。
  • 进程通过缓冲器缓存读写磁盘块，避免频繁的磁盘访问。
  • I/O 缓冲提高文件 I/O 效率和系统吞吐量。

12.1.1 I/O 缓冲的基本原理

  1. 读操作：
    • 在缓冲缓存中查找 (dev, blk)。
    • 如果找到，则从缓冲器读取；否则，分配一个缓冲器，从磁盘读取数据，并将缓冲器保留在缓冲缓存中。
  2. 写操作：
    • 获取缓冲器，写入数据，标记为延迟写入，释放到缓冲缓存。
    • 仅当将脏缓冲器重新分配到不同块时，才将脏缓冲器写入磁盘。

12.1.2 缓冲管理术语

  • BUFFER 结构： 用于缓冲器的类型，动态从缓冲缓存中分配。
  • 函数：
    • bread(dev, blk): 返回带有有效数据的缓冲器。
    • bwrite(bp): 同步写入；等待完成。
    • dwrite(bp): 延迟写入；标记缓冲器为脏，以供后续使用。
    • awrite(bp): 异步写入；开始 I/O 但不等待完成。

12.1.3 物理块设备 I/O

  • 每个设备都有一个包含待处理 I/O 缓冲器的 I/O 队列。
  • start_io(bp): 将缓冲器输入设备 I/O 队列，并在队列非空时发出 I/O 命令。
  • 中断处理程序完成当前缓冲器上的 I/O 操作，并在队列非空时启动下一个缓冲器的 I/O。

12.1.4 缓冲器释放

  • brelse(bp): 释放缓冲器；在同步写入后使用。
  • InterruptHandler(): 从 I/O 队列出列，如果是异步的，则释放缓冲器，解除进程阻塞，并在队列非空时发出下一个缓冲器的 I/O 命令。

注意： 延迟写入策略通过仅在必要时将脏缓冲器写入磁盘，减少物理磁盘 I/O 并提高缓冲效率。

12.2 Unix I/O 缓冲管理算法学习笔记

12.2.0 简介

Unix I/O 缓冲管理算法首次出现在 V6 Unix（Ritchie 和 Thompson，1978；Lion，1996）中，详细讨论在 Bach 的第三章中（Bach，1990）。Unix 缓冲管理子系统包括以下组件。

12.2.1 I/O 缓冲

  • NBUF 个内核中的缓冲器作为缓冲缓存，每个缓冲器由结构体表示。
typedef struct buf {
    struct buf *next_free; // 空闲列表指针
    struct buf *next_dev; // 设备列表指针
    int dev, blk; // 分配的磁盘块
    int opcode; // READ|WRITE
    int dirty; // 缓冲器数据已修改
    int async; // ASYNC 写标志
    int valid; // 缓冲器数据有效
    int busy; // 缓冲器正在使用
    int wanted; // 有进程需要这个缓冲器
    struct semaphore lock = 1; // 缓冲器锁定信号量；值为 1
    struct semaphore iodone = 0; // 用于等待 I/O 完成的进程
    char buf[BLKSIZE]; // 数据块区域
} BUFFER;
BUFFER buf[NBUF], *freelist; // NBUF 个缓冲器和空闲缓冲器列表

12.2.2 设备表

  • 每个块设备由设备表结构表示。
struct devtab {
    u16 dev; // 主设备号
    BUFFER *dev_list; // 设备缓冲器列表
    BUFFER *io_queue; // 设备 I/O 队列
} devtab[NDEV];
  • 每个 devtab 包含一个 dev_list，其中包含当前分配给设备的 I/O 缓冲器，以及一个 io_queue，其中包含设备上待处理 I/O 操作的缓冲器。

12.2.3 缓冲初始化

  • 系统启动时，所有 I/O 缓冲器在空闲列表中，所有设备列表和 I/O 队列为空。

12.2.4 缓冲列表

  • 当缓冲器分配给 (dev, blk) 时，将其插入 devtab 的 dev_list 中。如果缓冲器当前正在使用，则标记为 BUSY 并从空闲列表中移除。BUSY 缓冲器可能也在 devtab 的 I/O 队列中。释放缓冲器时，它会被放回空闲列表，但仍保留在 dev_list 中以供可能的重用。

12.2.5 Unix getblk/brelse 算法

/* getblk: 为独占使用返回一个缓冲器=(dev,blk) */
BUFFER *getblk(dev, blk) {
    while (1) {
        (1). 在 dev_list 中搜索 bp=(dev, blk);
        (2). 如果 (bp 在 dev_list) {
            if (bp BUSY) {
                设置 bp WANTED 标志;
                等待(bp); // 等待 bp 被释放
                继续; // 重试算法
            }
            /* bp 不忙 */
            从空闲列表中移出 bp;
            标记 bp 为 BUSY;
            返回 bp;
        }
        (3). /* bp 不在缓存中；尝试从空闲列表获取一个空闲缓冲器 */
        if (空闲列表为空) {
            设置空闲列表 WANTED 标志;
            等待(空闲列表); // 等待任何空闲缓冲器
            继续; // 重试算法
        }
        (4). /* 空闲列表非空 */
        bp =从空闲列表中取出的第一个 bp;
        标记 bp 为 BUSY;
        if (bp DIRTY) { // bp 用于延迟写入
            awrite(bp); // 异步写入 bp;
            继续; // 从 (1) 继续，但不重试
        }
        (5). 重新分配 bp 到 (dev,blk); // 设置 bp 数据无效，等等
        返回 bp;
    }
}

/** brelse: 将缓冲器释放为 FREE 到空闲列表 **/
brelse(BUFFER *bp) {
    if (bp WANTED)
        唤醒(bp); // 唤醒所有等待 bp 的进程
    if (空闲列表 WANTED)
        唤醒(空闲列表); // 唤醒所有等待空闲列表的进程
    清除 bp 和空闲列表 WANTED 标志;
    将 bp 插入 (空闲列表的尾部);
}

12.2.7 Unix 算法的特点

  1. 数据一致性： 为了确保数据一致性，getblk 绝不会分配超过一个缓冲器给相同的 (dev, blk)。这通过在从睡眠中唤醒后重新执行“重试循环”来实现。脏缓冲器在重新分配之前被写出，确保了数据一致性。

  2. 缓存效果： 通过以下方式实现缓存效果。释放的缓冲器仍保留在设备列表中，以供可能的重用。标记为延迟写的缓冲器不会立即进行 I/O，可供重用。缓冲器被释放到空闲列表的尾部，但从空闲列表的前部分配。这基于 LRU（最近最少使用）原则，有助于延长分配的缓冲器的寿命，从而增加其缓存效果。

  3. 临界区域： 设备中断处理程序可能操纵缓冲器列表，例如从 devtab 的 I/O 队列中删除

bp，更改其状态并调用 brelse(bp)。因此，在 getblk 和 brelse 中，设备中断在这些关键区域被屏蔽。这是暗示但未在算法中显示的。

12.2.8 Unix 算法的缺点

  1. 效率低下： 该算法依赖于重试循环。例如，释放一个缓冲器可能唤醒两组进程：那些需要已释放缓冲器的进程，以及那些只需要一个空闲缓冲器的进程。由于只有一个进程可以获取已释放的缓冲器，所有其他被唤醒的进程必须再次进入睡眠状态。从睡眠中唤醒后，每个被唤醒的进程必须从头开始重新执行算法，因为所需的缓冲器可能已经存在。这可能导致过多的进程切换。

  2. 缓存效果不可预测： 在 Unix 算法中，每个释放的缓冲器都可供使用。如果获取缓冲器的进程需要一个空闲缓冲器，则该缓冲器将被重新分配，即使可能仍然有需要该缓冲器的进程。

  3. 可能的饥饿： Unix 算法基于“自由经济”的原则，即每个进程都有机会尝试但不能保证成功。因此，可能发生进程饥饿。

  4. 算法使用 sleep/wakeup，仅适用于单处理器系统。

12.3 新的 I/O 缓冲管理算法

在本节中，我们将展示一种新的 I/O 缓冲管理算法。我们将使用 P/V 操作在信号量上进行进程同步，而不是使用 sleep/wakeup。信号量相对于 sleep/wakeup 的主要优势有：

  1. 计数信号量可用于表示可用资源的数量，例如空闲缓冲器的数量。
  2. 当许多进程等待资源时，对信号量的 V 操作仅解除一个等待的进程，因为它已经获得资源，无需重试。

这些信号量属性可用于设计更高效的缓冲管理算法。形式上，我们将问题规定如下。

12.3.1 使用信号量的缓冲管理算法

假设是单处理器内核（一次只运行一个进程）。使用计数信号量上的 P/V 操作设计新的缓冲管理算法，满足以下要求：

  1. 保证数据一致性。
  2. 具有良好的缓存效果。
  3. 高效率：无重试循环，没有不必要的进程“唤醒”。
  4. 免于死锁和饥饿。

值得注意的是，仅仅将 Unix 算法中的 sleep/wakeup 替换为信号量上的 P/V 操作并不是一个可接受的解决方案，因为这样做会保留所有的重试循环。我们必须重新设计算法以满足所有上述要求，并证明新算法确实优于 Unix 算法。首先，我们定义以下信号量。

BUFFER buf[NBUF]; // NBUF 个 I/O 缓冲器
SEMAPHORE free = NBUF; // 计数信号量，表示 FREE 缓冲器的数量
SEMAPHORE buf[i].sem = 1; // 每个缓冲器都有一个锁定信号量 sem=1

为简化符号，我们将通过缓冲器本身来引用每个缓冲器的信号量。与 Unix 算法一样，最初所有缓冲器都在空闲列表中，所有设备列表和 I/O 队列为空。

12.8 总结

本章涵盖了块设备 I/O 和缓冲管理。主要内容包括块设备 I/O 的原理和 I/O 缓冲的优势。讨论了 Unix 的缓冲管理算法及其缺点。接着使用信号量设计了一种新的缓冲管理算法，以提高 I/O 缓冲缓存的效率和性能。PV 算法的简单实现展示了其易于实施、具有良好的缓存效果，并且不会发生死锁和饥饿的特点。为了帮助读者更好地理解文件系统中的 I/O 操作和中断处理，提出了一个编程项目，要求读者在模拟系统中实现并比较缓冲管理算法的性能。这个项目有助于读者深入了解文件系统中的 I/O 操作和中断处理。

苏格拉底挑战

点击查看代码 Linux Block I/O Basics