总完成时长 11小时。
TASK #1 - LRU REPLACEMENT POLICY
实现 LRU页面替换策略。
思路
如果之前对 LRU 没有怎么接触，推荐可以先去 LeetCode 上做一下这道题：146. LRU 缓存
数据结构选取双向链表 + 哈希表，双向链表有助于我们在移动节点时更方便的找到某个节点的前节点。
同时设置 dummy_tail ，因为在置换时我们总是需要移除最后一个节点。
提示
理清 Pin 和 Unpin 的含义，注意我们需要实现的只是一个 POLICY ，具体的实现是在下一个 TASK，如果直接当 buffer pool 处理很多含义都是相反的。
Pin：代表有线程正在占用这个 frame，所以需要从 cache_ 和 DLinkedNode 中删除，防止被替换。
Unpin：占用结束，重新把 frame 加入 cache_ 和 DLinkedNode ，重复 Unpin 不会影响节点的位置。
另外，如果你和我一样是自己实现的双向链表而不是用 STL 中的 list，一定要记住在 remove(node)后将 node 给 delete（我直接搬运了 leetcode 代码没考虑太多…），我这一节是满分过了，但是 project2 的内存检测后来死活过不了，才意识到问题…
TASK #2 - BUFFER POOL MANAGER INSTANCE
实现缓冲器管理器实例。
思路
首先明确一下 BufferPoolManagerInstance 中几个成员变量的含义：
-
std::list<frame_id_t> free_list_;缓冲池剩余空间的 frames 用
free_list_表示，初始大小为pool_size_的大小，free_list_为空，则说明此时 buffer pool已满，需要用上一个 TASK 完成的 LRU 获取新的 frame 。 -
std::unordered_map<page_id_t, frame_id_t> page_table_frame_id是 缓冲池中的帧序号。page_id是页的标识符。每当把 page 放入缓冲池，相当于在
page_table_对两者做一个映射。
-
Page *pages_;缓冲池 page 的数组，以 frame_id 为索引。
根据 page_table_ 和 pages_ ，如果给定一个 page_id ，我们可以通过 page_table_.find(page_id)，去获取这个page_id 所对应在内存中的 frame_id，再通过 Page* page = pages_[framge_id] 即获取到了这个 page.
注意，在 Page 类中已经把 BufferPoolManagerInstance 设置为友元，所以我们可以直接访问 Page 对象中的私有成员进行修改。
需要实现的方法注释已经非常详细
auto FetchPgImp(page_id_t page_id) -> Page * override;
auto NewPgImp(page_id_t *page_id) -> Page * override;
auto UnpinPgImp(page_id_t page_id, bool is_dirty) -> bool override;
auto FlushPgImp(page_id_t page_id) -> bool override;
auto DeletePgImp(page_id_t page_id) -> bool override;
void FlushAllPgsImp() override;
不过其实很多代码都是可以重用的，比如 NewPgImp 和 FetchPgImp 都会涉及到从free_list 和lru 中获取一个新的frame，我们可以将其包装为auto GetFreeFrame() -> frame_id_t;，还有比如脏页我们需要重新写回磁盘、涉及到对 page 的 Reset ，如果追求代码简约的话都可以封装一下。
坑点
记录一个我犯的挺蠢的错误…
auto iter = page_table_.find(page_id);
if (iter != page_table.end()){
xxxx...
page_table_.erase(page_id);
free_list_.push_back(iter->second);
xxxx...
}
原因在于我把 page_table_.erase(page_id); 写在了前面，而 iterator 只是 STL 中指针的封装，erase 之后这片地址空间发生了改变，再去调用iter->second 就发生了错误。
还有可能是我自作聪明，过多封装了一些方法，导致锁处理有一些麻烦 .. gradescope 上跑出了几个timeout（死锁），如果和我一样写单元测试不太熟练，可以尝试把测试文件输出出来：
std::ifstream file("/autograder/bustub/test/buffer/grading_buffer_pool_manager_instance_test.cpp");
string line;
while (file.good()){
std::getline(file,line);
cout<<line<<endl;
}
把上述代码放在一个会涉及到的方法里即可，不过还是推荐自己写单元测试 debug 。
TASK #3 - PARALLEL BUFFER POOL MANAGER
实现并行缓冲池管理器。
思路
因为缓冲池实例的操作必须上锁，随着缓冲池数据规模的增大锁的开销也增大了。这一个 TASK 就是让我们实现一个缓冲池管理器，其内部维护了一个 vector 容器。
std::vector<BufferPoolManagerInstance *> buffer_pool_manager_;
这样我们可以根据 page_id % num_instances_的值，均匀分配给不同的缓冲池实例。
最后：
