CMU 15445 Buffer Pool
写在前面
直接去写 task 1，发现如果知道上面 BFM 是如何被访问，以及访问页命中和不命中时具体做的事情，那么就好写多了
所以需要考虑下面这些事情
- 读取一个页
- 在 buffer 里面
- 不在 buffer 里面
- 写一个页
- 在 buffer 里面
- 不在 buffer 里面
task 1 实现 LRU-k
Evivt, 从缓冲里淘汰掉一个页- 当缓冲满的时候
RecordAcess, 记录下这个访问的页的页 id 以及时间戳- 当一个页被访问时，需要进行
pin，一般这个操作位于pin之后
- 当一个页被访问时，需要进行
Remove, 清空一个页的历史访问记录- 当一个页被从 BFM 中删除时才调用
SetEvictable, 设置一个页的状态为可以被删除或者不可以被删除，显然当pin的计数为0时，可以调用设置为可以被删除。Size, 返回当前的可淘汰的页的数量，
- 淘汰的策略, 翻译过来就是
- 所有的页都被访问了超过 k 次，那么选一个页，它的往前数 k 个访问记录（倒数第 k 次访问）的时间戳最早，淘汰掉这个页。
- 如果有页没有被访问超过 k 次，那么在这些访问次数小于 k 的页里面优先选一个淘汰，选其中的具有最早的时间戳的页进行淘汰（就是 FIFO）
- 所以网上有些关于 LRU-K 解释说是要有两个队列。
Backward k-distance is computed as the difference in time between current timestamp and the timestamp of kth previous access.A frame with fewer than k historical accesses is given +inf as its backward k-distance. When multiple frames have +inf backward k-distance, the replacer evicts the frame with the earliest overall timestamp (i.e., the frame whose least-recent recorded access is the overall least recent access, overall, out of all frames).