总完成时长 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_
的值,均匀分配给不同的缓冲池实例。