CMU15445 (Spring 2023) Project #1 - Buffer Pool

发布网友发布时间：2024-10-07 18:08

共1个回答

热心网友时间：2024-12-04 04:14

2023-05-04 五四青年节hh

近期专注于算法学习，今日抽空完成 Project1 的第一部分，即 LRU-K 置换策略。虽然整体并不复杂，但在执行过程中仍遇到了一些挑战，颇感费解。

2023-05-06 全部完成，但遇到一个难以解决的 bug，耗费了一整天的时间。导致最后一个测试无法通过，原因在于写回页面与 pincount 协调不当。因此，最后两部分的正确性无法保证。面试在即，为避免影响备考，暂且搁置后续工作，待有空闲时再进行调试。

2023-05-12 华为笔试通过、综合测评完成，希望结果能满意。今日成功定位 bug。

2023-07-21 补充 task2 部分答案

你可能需要知道的

论文无需阅读，LeetCode 提供相关练习。

三个 Task

Task #1 - LRU-K 替换策略

关键在于理解题意与临界情况的应对。LRU-K 用于记录、更新与删除页面，其历史链表长度代表页面出现次数。当历史链表长度小于等于 K 时，表示最多记录最后 K 次出现。若超过 K 次，则删除链表头部，并将新时间戳加入尾部。历史链表应由小到大排列时间戳。

K-Distance 计算方法：若页面出现次数小于 K，则 K-Distance 无穷大；若出现次数大于等于 K，则 K-Distance 对应历史链表头部的时间戳。

相比 LRU，LRU-K 能更有效地抵抗数据洪流，通过统计出现次数，避免低效。

驱逐策略：优先驱逐 K-Distance 无穷大的页面；若无，考虑 K-Distance 有限的页面，驱逐 K-Distance 最小者。若多个页面 K-Distance 均为无穷大，采用 FIFO（先进先出）策略进行驱逐。

官方文档建议：多个 K-Distance 无穷大的页面，采用 FIFO 进行驱逐，但在代码实现中使用 LRU。实际测试表明，应用 FIFO 进行驱逐更合适。

性能与实现

预期插入、删除等操作快速，但 LRU-K 的复杂度不如 LRU。网上做法使用两个链表维护页面，时间复杂度为 [公式]。我的实现使用链表与红黑树，实现 [公式] 的插入与删除。对 set 的更新，最初尝试通过取地址更新，但发现 set 的排序不随更新变化，更正为删除后更新与插入。

小根堆时间复杂度为 [公式]，但遍历次数大于等于 K 的页面不适用于小根堆。

实现细节：课程未公开代码，提供数据结构帮助理解。推荐使用 std::list 而非 std::list。使用 frame_id_t 时避免使用红黑树，以免涉及权限问题。使用 std::scoped_lock 或 std::lock_guard 保证线程安全。

Task #2 - 缓存管理器

缓存管理器实质为数据库内存部分，其结构与实现相对简单。注意 pages_ 维护页面，使用 frame_id 作为索引。理解 pin_count 表示页面使用者数量，为 0 时可驱逐页面。is_dirty 标记页面是否已修改，需要考虑何时更新。在 unpinpage 时，不修改脏位状态。确保完成 pin_count、is_dirty 的更新与页面写入至 replacer_。

Task #3 - 页管理器

实现 RAII 管理页面，代码量不多，但存在潜在错误。确保移动赋值时处理自赋值与旧值处理、移动后对象完全失效、drop 后析构函数无作用等问题。

总结：虽然遇到了 bug，但 LRU-K 算法的高效性能使得排名较高，21/117。后续有机会将进一步优化。