Buffer Pool Manager

实现 BusTub 的 Buffer Pool Manager。

使用课程的框架代码，实现函数。

Task 1 - Adaptive Replacement Cache (ARC) Replacement Policy

Size(): 按照要求直接返回可访问的 frames 数量。

SetEvictable(frame_id_t frame_id, bool set_evictable): 这个函数是用来设置 frame 要不要被淘汰的，这个函数是在 Page 的 Pin Count 设置为 0 或设置为非 0 时调用的。 这个函数的作用是，设置 frame 进出淘汰的备选列表。

RecordAccess(frame_id_t frame_id, page_id_t page_id): 这个函数在下面老师会有详细讲解，只需要按照老师的讲解一步步做就可以了。 老师提了一个问题 Try considering why in case 4(a) and 4(b), there must be items in the ghost lists.

a. 如果 mru_.size() == replacer_size_ && mru_ghost_.size() == 0 ，那么会触发 evict() ，就会 mru_ghost 会有数据 b. 如果 mur_.size() + mfu_.size() + mru_ghost_.size() == 2 * replacer_size_ && mfu_.size() == 0 ，联系 a ，可以推理出 mru_size() + mru_ghost_.size() < replacer_size && mfu_.size() > replacer_size ， 这里就出现了矛盾，当 mfu_size() == replacer_size 的时候，就会触发 evict()

Evict() -> std::optional<frame_id_t> : 这个函数是当需要添加 frame 时，alive_map_ 满了，需要淘汰掉 frame 才有位置放入。需要注意移除 frame 时，要加入到 ghost 列表中，还是比较简单的。

Remove(frame_id_t frame_id) : 这个函数是对外开放的，和刚刚的 Evict() 不同，这个是让别人主动移除，和刚刚的 Evict() 类似，但是不需要加入 ghost 列表中。

Task 2 - Disk Scheduler

需要先读懂题目， Disk Scheduler 是和 Disk Manager 沟通的一个类，类似于运输带，它只负责将请求运输到 Disk Manager ，具体执行是由 Disk Manager 执行，而 Arc Replacer 只是一个执行规则。 当 Buffer Pool Manager 要做某些事情的时候，会先通过 Arc Replacer 做一个计划，然后把计划给 Disk Scheduler ， Disk Scheduler 会将计划送到 Disk Manager 这里，最后由 Disk Manager 执行。

DiskScheduler(): 这个函数就是要将参数里面的所有数据存入 channel 中，需要注意一下语法问题。

StartWorkerThread(): 这是整个 Disk Scheduler 的核心，按照老师的提示一步步做进行了，简单说就是取出 channel 中的数据，然后发送请求，执行回调函数。

这个任务还是十分简单的，难点在于理解各个模块的工作流程。

Task 3 - Buffer Pool Manager

难点在于理解各个模块的工作流程以及理解题目的意思。

ReadPageGuard::ReadPageGuard()
ReadPageGuard::ReadPageGuard(ReadPageGuard &&that)
ReadPageGuard::operator=(ReadPageGuard &&that) -> ReadPageGuard &
ReadPageGuard::Flush()
ReadPageGuard::Drop()
WritePageGuard::WritePageGuard()
WritePageGuard::WritePageGuard(WritePageGuard &&that)
WritePageGuard::operator=(WritePageGuard &&that) -> WritePageGuard &
WritePageGuard::Flush()
WritePageGuard::Drop()

这里的函数主要是需要熟悉 cpp 的语法，跟 proj 0 类似。需要注意的是，这里的 replacer_size_ 是 1-x ，并不是 0-(x - 1) ，debug 了十分久。

NewPage() -> page_id_t
DeletePage(page_id_t page_id) -> bool
CheckedWritePage(page_id_t page_id) -> std::optional<WritePageGuard>
CheckedReadPage(page_id_t page_id) -> std::optional<ReadPageGuard>
FlushPageUnsafe(page_id_t page_id) -> bool
FlushPage(page_id_t page_id) -> bool
FlushAllPagesUnsafe()
FlushAllPages()
GetPinCount(page_id_t page_id)

这里的函数主要是需要理解各个模块的工作流程以及理解题目的意思，然后调用各个模块的函数就可以了。

Gemini + 修改

Gemini 有错误

数据库缓冲池 (Buffer Pool) 设计模式：图书馆比喻

为了理解数据库缓冲池（Buffer Pool）的工作原理，我们可以将其比作一个现代化、管理严格的大型图书馆。这个比喻有助于清晰地描绘出项目中各个核心模块的职责与协作关系。

图书馆的角色 (项目模块)

图书馆角色	计算机科学概念	职责简述
你 (读者)	应用线程 (Application Thread)	最终用户，需要读取或修改数据。
总服务台/馆长办公室	缓冲池管理器 (Buffer Pool Manager - BPM)	核心大脑，负责协调所有资源，响应读者请求。
电子查询系统	页表 (Page Table)	一张高速哈希表，记录“书在哪张桌上”。
阅览区	缓冲池 (Buffer Pool)	速度快的内存区域，容量有限。
阅览桌	帧 (Frame)	缓冲池中的一个固定大小的槽位，用于存放一本书。
书籍	页 (Page)	磁盘上存储数据的基本单位，对应书库里的书。
门禁卡/座位卡	页面卫士 (Page Guards)	RAII对象，自动化管理访问权限和资源释放。
地下密集书库	磁盘 (Disk)	容量巨大但速度慢的持久化存储。
库管员	磁盘管理器 (Disk Manager)	负责在物理层面执行从书库取书/还书的操作。
智能任务调度系统	磁盘调度器 (Disk Scheduler)	异步任务队列，优化与书库的交互，避免馆长干等。
数据分析顾问	替换策略器 (Replacer, 如 ARC)	决策专家，在阅览桌不够时，建议哪本书该被移走。

---

工作流程场景分析

场景一：借阅一本热门书 (缓存命中)

当你需要一本热门书时，它很可能已经被其他读者借出并放在阅览区了。

1. 提出请求: 你（读者）向总服务台 (BPM) 申请查阅《数据库系统概念》（page_id=101）。
2. 快速查询: 馆长首先锁上办公室门（获取 bpm_latch_），然后在电子查询系统 (Page Table) 中查找。系统显示：“在阅览区 5 号桌”。
3. 更新状态:
   • 馆长走到 5 号桌，将桌上的“使用人数”计数器加一（增加 pin_count）。
   • 他通过对讲机告知数据分析顾问 (Replacer)：“5 号桌刚被访问，更新记录，并且暂时不能把它移走！” (RecordAccess, SetEvictable(false))。
   • 释放 bpm_latch_ （打开大门），否则会发生死锁。（如果你在座位上才释放锁，这时别人来申请阅览区，会锁上大门，同时等待你释放座位卡，但是你需要等待大门打开）。
4. 授予权限: 馆长递给你一张智能座位卡 (Page Guard)。
   • 只读: 若你只看书，会得到一张“绿色阅览卡”(ReadPageGuard)，它会在桌上亮起绿灯（读锁），允许多人同时阅读。
   • 读写: 若你要做笔记，会得到“红色研究卡”(WritePageGuard)，它会亮起红灯（写锁），禁止任何其他人靠近。
5. 开始阅读: 你拿着卡片找到座位，开始使用书籍。。
6. 自动归还: 当你离开时，将卡片扔进回收箱（Guard 离开作用域）。卡片会自动：
   • 熄灭桌上的灯（解锁 Guard）。
   • 向总服务台发送信号，将“使用人数”减一（Unpin）。
   • 如果人数归零，总服务台会通知顾问：“5 号桌没人了，可以考虑把它移走了。” (SetEvictable(true))。

场景二：借阅一本冷门古籍 (缓存未命中)

当你需要一本冷门书时，它大概率还在地下书库里。

1. 提出请求: 你向总服务台 (BPM) 申请查阅《炼金术图鉴》（page_id=205）。
2. 查询失败: 馆长锁门后查询电子系统，发现“无记录”。他看了一眼阅览区，所有桌子都满了。
3. 决策咨询: 馆长向数据分析顾问 (Replacer) 求助：“阅览区满了，哪本书最该被送回书库？” 顾问根据数据建议：“3 号桌的《五年高考三年模拟》。” (Evict())。
4. 处理旧书 (驱逐):
   • 馆长检查 3 号桌的书，发现上面有笔记（页面是脏的 is_dirty）。
   • 他不能直接丢弃笔记。他创建一张“还书入库”请求，发给智能任务调度系统 (Disk Scheduler)，让后台的库管员 (Disk Manager) 去处理。
5. 调度取书:
   • 3 号桌空出后，馆长立刻创建一张“取书上架”请求，让库管员去地下书库 (Disk) 找《炼金术图鉴》并送到 3 号桌。
   • 这个请求也发给了任务调度系统。
6. 阻塞等待: 这次取书是必须的，馆长必须等待书被送到。他会盯着调度系统的状态屏幕（future.get()），直到显示“已送达”。
7. 更新状态: 书送到后，馆长立刻：
   • 更新电子查询系统：“《炼金术图鉴》在 3 号桌”。
   • 设置 3 号桌的“使用人数”为 1 (pin_count=1)。
   • 通知顾问：“3 号桌刚上了新书，有人用，不准清理！”
8. 授予权限: 后续流程与“缓存命中”场景的第 4 步完全相同。

---