3.1.1. 替换策略¶

只要缓冲池中有未使用的缓冲区可用， 就可以按需从磁盘读取新信息。 当应用程序继续从磁盘读取新信息时， 最终缓冲池中的所有缓冲区都会被填满。 一旦发生这种情况，就必须做出决定， 缓冲池中的哪些信息将被牺牲以腾出空间给 新请求的信息。

替换缓冲池中包含的信息时， 目标是选择具有"不必要"信息的缓冲区， 即最不可能再次被请求的信息。 因为缓冲池无法确切知道未来请求的模式， 必须使用基于某种 启发式 或最佳猜测的决策。 有几种方法可以做出这个决策。

一种启发式方法是 first-in, first-out 。该方案 simply 将缓冲区按队列顺序排列。队列前端的缓冲区用于存储新信息，随后被移至队列末尾。这样，被替换的缓冲区是持有信息时间最长的，期望这些信息不再需要。当处理以大致顺序且稳定速度沿文件进行时，这是一个合理的假设。然而，许多程序反复使用某些关键信息片段，而信息的重要性与其首次被访问的时间长短关系不大。通常更重要的是知道信息被访问的次数，或者信息最近一次被访问的时间。

另一种方法叫做 最不经常使用 （LFU）。 LFU 跟踪缓冲池中每个缓冲区的访问次数。 当必须重用一个缓冲区时， 访问次数最少的缓冲区被认为包含"最不重要"的信息， 因此它被下一个使用。 LFU 虽然直觉上合理，但有许多缺点。 首先，需要存储和更新每个缓冲区的访问计数。 其次，过去被频繁引用的内容现在可能已经无关紧要。 因此，通常需要某种时间机制使计数"过期"。 这还避免了缓冲区因恰好被使用足够多次 以避免被替换而慢慢积累大计数的问题。 另一种方法是为所有曾经读取的扇区（而不仅仅是 当前在缓冲池中的扇区）维护计数。 这避免了立即替换刚读取的缓冲区， 因为它还没有时间建立高访问计数。

第三种方法叫做 最近最少使用 （LRU）。 LRU 简单地将缓冲区保存在列表中。 每当缓冲区中的信息被访问时， 该缓冲区被移到列表前面。 当必须读取新信息时，从列表后面 （最近最少使用的）取出缓冲区， 其"旧"信息根据需要被丢弃或写入磁盘。 这是 LFU 的一种易于实现的近似方法， 通常是管理缓冲池的首选方法， 除非有关于应用程序信息访问模式的特殊知识 建议使用专用的缓冲区管理方案。

Settings

Saving...
Server Error
Resubmit

3.1.2. 脏位¶

缓冲池的主要目的是最小化磁盘 I/O。 当块的内容被修改时， 我们可以立即将更新的信息写入磁盘。 但如果该块再次被更改怎么办？ 如果每次更改后都写入块的内容， 这可能是大量可以避免的磁盘写操作。 等待文件关闭或缓冲池中包含该块的缓冲区 内容被刷新时再写入更有效。

当缓冲区的内容要在缓冲池中被替换时， 我们只想在必要时将内容写入磁盘。 只有当内容在块最初从文件读取后发生了更改时， 才需要写入。 确保块在必要时（且仅在必要时）被写入的方法是 维护一个与缓冲区关联的布尔变量 （通常称为 脏位）， 当缓冲区的内容被客户端修改时打开。 当块从缓冲池中刷新时， 当且仅当脏位已打开时才写入磁盘。

Settings

Saving...
Server Error
Resubmit

现代操作系统支持 虚拟内存。 虚拟内存是一种技术，允许程序员编写程序时 仿佛存在比实际更多的更快的主存（如 RAM）。 虚拟内存使用缓冲池来存储 从较慢的辅助存储器（如磁盘驱动器）块中读取的数据。 磁盘存储虚拟内存的完整内容。 根据内存访问的需求，块被读入主存。 当然，使用虚拟内存技术的程序比数据完全存储在 主存中的程序慢。 优势在于减少了程序员的工作量， 因为良好的虚拟内存系统提供了更大的主存外观， 而无需修改程序。

这是一个可视化工具，让你可以尝试 各种缓冲池替换策略。

3.1.3. 实现缓冲池¶

实现缓冲池时，关于缓冲池用户与缓冲池类本身之间的 信息传输，有两种基本方法。 第一种方法是在两者之间传递"消息"。 以下抽象类说明了这种方法：

// ADT for buffer pools using the message-passing style
public interface BufferPoolADT {
  // Copy "sz" bytes from "space" to position "pos" in the buffered storage
  public void insert(byte[] space, int sz, int pos);

  // Copy "sz" bytes from position "pos" of the buffered storage to "space"
  public void getbytes(byte[] space, int sz, int pos);
}

这个简单的类提供了一个具有两个成员函数的接口， insert 和 getbytes。 信息通过 space 参数在缓冲池用户和缓冲池之间传递。 这是缓冲池客户端提供的存储空间， 至少 sz 字节长， 缓冲池可以从中获取信息（insert 函数）或将信息放入 （getbytes 函数）。 参数 pos 指示信息将放置在 缓冲池逻辑存储空间中的哪个位置。 实际上，它将被复制到缓冲池中某个缓冲区的 相应字节位置。 这个 ADT 类似于 Java 中 RandomAccessFile 类的 read 和 write 方法。

另一种接口是让缓冲池向用户提供 指向包含请求信息的缓冲区的直接指针。 这样的接口可能如下所示：

// ADT for buffer pools using the buffer-passing style
public interface BufferPoolADT {
  // Return pointer to the requested block
  public byte[] getblock(int block);

  // Set the dirty bit for the buffer holding "block"
  public void dirtyblock(int block);

  // Tell the size of a buffer
  public int blocksize();
};

在这种方法中，缓冲池用户意识到 存储空间被分成给定大小的块， 每个块是一个缓冲区的大小。 用户向缓冲池请求特定的块， 返回指向保存请求块的缓冲区的指针。 用户然后可以读取或写入此空间。 如果用户写入此空间，则必须通知缓冲池。 原因是，当要从缓冲池中移除给定块时， 如果该块已被修改， 则该块的内容必须写入后备存储器。 如果块未被修改，则不需要将其写出。

这种方法的一个变体是让 getblock 函数 接受另一个参数来指示信息的"模式"。 如果模式是 READ，则缓冲池假定不会对缓冲区内容进行更改 （因此在重用缓冲区存储另一个块时不需要执行写操作）。 如果模式是 WRITE，则缓冲池假定客户端不会查看缓冲区内容， 因此不需要从文件读取。 如果模式是 READ AND WRITE，则缓冲池将从磁盘读取 块的现有内容，并在重用缓冲区时将缓冲区内容写入磁盘。 使用"模式"方法，可以避免 dirtyblock 方法。

缓冲传递 ADT 的一个问题是 过期指针 的风险。 当缓冲池用户在时间 T1 被给予某个缓冲区空间的指针时， 该指针确实在该时间引用了所需的数据。 随着对缓冲池的进一步请求， 任何给定缓冲区中的数据都可能被移除并替换为新数据。 如果缓冲池用户在以后的时间 T2 引用 在时间 T1 给出的指针所引用的数据， 则数据可能不再有效，因为缓冲区内容在此期间已被替换。 因此，指向缓冲池内存的指针已变得"过期"。 为了保证指针不过期， 如果在介入的缓冲池请求后不应使用它。

我们可以通过引入用户（或可能的多个用户） 获取缓冲区然后在完成后释放缓冲区的概念来解决这个问题。 我们将为此目的添加方法 acquireBuffer 和 releaseBuffer。 方法 acquireBuffer 接受块 ID 作为输入， 返回将用于存储此块的缓冲区指针。 缓冲池将维护当前对此块的活动请求数量。 方法 releaseBuffer 将减少关联块的活动用户计数。 与活动块关联的缓冲区不符合从缓冲池中刷新的条件。 如果客户端在不再需要活动块时忽略释放， 就会导致问题。 如果总活动块数多于缓冲池中的缓冲区， 也会出现问题。 因此，缓冲池应初始化为包含比一次需要活动的缓冲区更多的缓冲区。

目前提出的两种 ADT 的另一个问题是， 当用户打算完全覆盖块的内容， 并且不需要读取磁盘上已有的旧内容时。 然而，缓冲池通常无法知道用户是否希望使用旧内容。 这在消息传递方法中尤其如此， 其中给定消息可能只覆盖块的一部分。 在这种情况下，即使不需要也会将块读入内存， 然后其内容将被覆盖。

通过将块分配给缓冲区与实际读取块的数据分开， 可以避免这种低效（至少在缓冲区传递版本中）。 特别是，以下修订的缓冲区传递 ADT 在 acquireBuffer 方法中不实际读取数据。 希望查看旧内容的用户必须发出 readBlock 请求 将数据从磁盘读入缓冲区。

// Improved ADT for buffer pools using the buffer-passing style.
// Most user functionality is in the buffer class, not the buffer pool itself.

// A single buffer in the buffer pool
public interface BufferADT {
  // Read the associated block from disk (if necessary) and return a
  // pointer to the data
  public byte[] readBlock();

  // Return a pointer to the buffer's data array (without reading from disk)
  public byte[] getDataPointer();

  // Flag buffer's contents as having changed, so that flushing the
  // block will write it back to disk
  public void markDirty();

  // Release the block's access to this buffer. Further accesses to
  // this buffer are illegal
  public void releaseBuffer();
}

public interface BufferPoolADT {

  // Relate a block to a buffer, returning a pointer to a buffer object
  Buffer acquireBuffer(int block);
}

同样，可以向 acquireBuffer 方法添加模式参数， 消除对 readBlock 和 markDirty 方法的需求。

显然，缓冲区传递方法对缓冲池用户施加了更多义务。 这些义务包括知道块的大小、不破坏缓冲池的存储空间， 以及在块被修改后和不再需要时都通知缓冲池。 如此多的义务使这种方法容易出错。 优点是当从用户获取信息到缓冲区时 不需要额外的复制步骤。 如果存储的记录很小，这不是一个重要的考虑因素。 如果记录很大（特别是当记录大小和缓冲区大小相同时， 通常在实现 B-树 时就是这样）， 那么这个效率问题可能变得很重要。 但请注意，内存中的复制时间总是远小于 将缓冲区内容写入磁盘所需的时间。 对于磁盘 I/O 是程序瓶颈的应用程序， 即使在缓冲池用户和缓冲区之间 复制大量信息的时间也可能无关紧要。 缓冲区传递的另一个优点是减少了 对将被覆盖的数据的不必要读操作。

请注意，使用 Java 泛型不适合在缓冲池实现中使用。 在我们的 ADT 中，space 参数和缓冲区指针声明为 byte[]。 当类使用 Java 泛型时，这意味着记录类型是任意的， 但类知道记录类型是什么。 相比之下，使用 byte[] 作为空间意味着 不仅记录类型是任意的， 而且缓冲池甚至不知道用户的记录类型是什么。 事实上，一个给定的缓冲池可能有许多存储多种类型记录的用户。

在缓冲池中，用户决定给定记录存储在哪里， 但无法控制数据传输到后备存储器的精确机制。 这与 内存管理器 形成对比， 在内存管理器中，用户将记录传递给管理器， 但完全无法控制记录存储的位置。