CMU15445 Project1记录

CMU15445 Project1记录
W3nYuiTask1 ARC算法实现
这里需要实现五个函数:
Size() -> size_t:返回当前可被淘汰的 frame 数量。SetEvictable(frame_id_t frame_id, bool set_evictable):设置某个 frame 是否可淘汰,并同步维护替换器大小。通常当某页的 pin count 变为 0 时,对应 frame 应标记为可淘汰。RecordAccess(frame_id_t frame_id, page_id_t page_id):记录某个 page 在某个 frame 中被访问。Buffer Pool Manager 在页面被 pin 到 frame 后应调用它。Evict() -> std::optional<frame_id_t>:按 ARC 规则选择一个 frame 淘汰。如果没有可淘汰 frame,返回std::nullopt。Remove(frame_id_t frame_id):如果 frame 存在且可淘汰,则从替换器中移除。Buffer Pool Manager 删除页面时会用到。
其中最难以理解的是:RecordAccess、SetEvictable、Evict这三个函数。
项目将ARC的算法拆分:RecordAccess:负责在修改页面时进行缓存命中,若是命中失败就加入LRU,若是命中成功就实现晋升策略/LFU内部提升策略。若是命中Ghost缓存,就要将其加入LFU缓存中,并根据命中类型,调整p值。如果都没有名字,就需要加入到LRU缓存中,并判断大小,对ghost进行裁剪。- 调用
RecordAccess(frame_id, page_id)时,正好会发生以下四种情况之一:- page 已经在 MRU 或 MFU 中:这是真正的缓存命中。把 page 移到 MFU 的前端。
- page 在 MRU ghost 中:这是实际缓存未命中,但 ghost list 命中。需要把它视为伪命中,并增大 MRU 目标大小,然后把 page 移到 MFU 前端。增大幅度取决于 MRU ghost 和 MFU ghost 的大小关系,且不能超过替换器容量。
- page 在 MFU ghost 中:类似上一种情况,但这说明如果 MFU 更大一些可能命中。需要减小 MRU 目标大小,然后把 page 移到 MFU 前端。目标大小不能小于 0。
- page 不在替换器中:既没有实际缓存命中,也没有 ghost 命中。此时把 page 加入 MRU 前端,并在必要时裁剪 ghost list,保证四个列表总大小不超过约束。
- 调用
Evict:真正找一个evictable的alive frame,把它从 T1/T2 移到ghost,且由于我的项目定义list是新->旧,因此倒序查找。核心规则是:
1
2
3
4如果 |mru_| >= mru_target_size_:
优先从 mru_ 淘汰
否则:
优先从 mfu_ 淘汰BusTub 注释里有两个特殊点:
mru_.size() == mru_target_size_时,也从 mru_ 淘汰。- 如果优先侧全是
pinned / non-evictable,就尝试另一侧。
综上,简单来说就是根据 mru_.size() 和 mru_target_size_ 决定优先淘汰侧,如果找不到就找对方,都没有返回nullopt
如果你要完成arc_replacer_performance_test这个test,最好实现一个迭代器指针,用于O(1)的删除list内的节点。如果想进一步学习RAII,也可以用shared_ptr + weak_ptr + 手写双向链表来实现O(1)删除。总之这个O(1)的删除有很多方法,因为项目允许在FrameStatus这个结构体里动刀子,我就直接在里面塞了两个迭代器指针。
以下是我让GPT给出的BMI的ARC算法流程:
核心结构
ARC 维护 4 个链表:- T1:真实缓存,表示“最近只访问过一次”的页,近似 LRU。
- T2:真实缓存,表示“访问过至少两次”的页,近似 LFU / frequent。
- B1:幽灵缓存,只保存从 T1 淘汰出去的 page id,不保存 frame。
- B2:幽灵缓存,只保存从 T2 淘汰出去的 page id,不保存 frame。
真实缓存容量是 c:
1
|T1| + |T2| <= c
幽灵缓存不占 frame,只占元数据。通常限制:
1
2|B1| + |B2| <= c
|T1| + |T2| + |B1| + |B2| <= 2cARC 还有一个自适应参数:
1
p = T1 的目标大小
含义:
- p 越大,ARC 越偏向 LRU / recent。
- p 越小,ARC 越偏向 LFU / frequent。
ARC_ACCESS(x):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45ARC_ACCESS(x):
如果 x 在 T1 中:
从 T1 删除 x
将 x 插入 T2 的 MRU
返回 HIT
如果 x 在 T2 中:
从 T2 删除 x
将 x 插入 T2 的 MRU
返回 HIT
如果 x 在 B1 中:
p = min(c, p + max(1, |B2| / |B1|))
REPLACE(x)
从 B1 删除 x
从磁盘读取 x 到新的 frame
将 x 插入 T2 的 MRU
返回 MISS_GHOST_B1
如果 x 在 B2 中:
p = max(0, p - max(1, |B1| / |B2|))
REPLACE(x)
从 B2 删除 x
从磁盘读取 x 到新的 frame
将 x 插入 T2 的 MRU
返回 MISS_GHOST_B2
# x 不在 T1 / T2 / B1 / B2,完全未命中
如果 |T1| + |B1| == c:
如果 |T1| < c:
删除 B1 的 LRU ghost
REPLACE(x)
否则:
victim = T1 的 LRU
从 T1 删除 victim
释放 victim 的 frame
否则如果 |T1| + |B1| < c:
如果 |T1| + |T2| + |B1| + |B2| >= c:
如果 |T1| + |T2| + |B1| + |B2| == 2c:
删除 B2 的 LRU ghost
REPLACE(x)
从磁盘读取 x 到新的 frame
将 x 插入 T1 的 MRU
返回 MISS_NEWREPLACE 逻辑
REPLACE(x) 是 ARC 的核心淘汰函数。它决定从 T1 还是 T2 淘汰真实 frame。
伪代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16REPLACE(x):
if |T1| > 0 and (
|T1| > p
or (x 在 B2 且 |T1| == p)
):
victim = T1 的 LRU
从 T1 删除 victim
将 victim.page_id 插入 B1 的 MRU
释放 victim 的 frame
else:
victim = T2 的 LRU
从 T2 删除 victim
将 victim.page_id 插入 B2 的 MRU
释放 victim 的 frame含义:
- 如果 T1 比目标 p 大,说明 recent 区太大,淘汰 T1。
- 否则淘汰 T2,给 frequent/recent 新页腾空间。
- 如果当前访问的是 B2 命中,并且 |T1| == p,也倾向淘汰 T1,因为 B2 命中说明 frequent 区应该更重要。
Task2 Disk Scheduler
理解这个任务花了很长一段事件,在理解明白后代码就很顺畅了。
Disk Scheduler穿件一个工作线程则负责处理排队的请求,同时实现一个Schedule函数把传进来的DiskRequest加入到channel:request_queue_内。
官方提供了一个线程安全的容器,便于实现Disk Scheduler的功能:加入待处理的内容->实现需要处理的内容
同时再这个Task学到了一个新的并发函数:std::promise<bool> 与 std::future<bool>,他的作用是实现线程阻塞,我个人感觉上与std::condition_variable差不多,前者是一次性值传递机制,后者是通用条件同步原语,可以利用notifiy_***实现多次唤醒。
因为我们知道了promise是用于线程安全,所有最后需要将promise利用set_value去置true。
Task3 BufferPoolManager
现在才是实现最重要的缓存池,BufferPoolManager是一个封装了 ARC(对内存物理页帧)与Disk Scheduler的管理者,同时还要完成一个友元函数:Guard函数,用于线程安全的刷盘。
BufferPoolManager整体上是实现一个线程安全的、利用整体锁+页锁的管理类,他主要面对三种情况,这三者情况又根据读写可以进一步划分:
页正在被使用,不需要IO读取到帧中(缓存命中)
页没有被刷入到帧中,但是有空闲帧,可以直接输入
页没有被刷入到帧中,但是缓冲池满了,没有空闲帧,就需要利用
ARC进行清除,如果是脏页就需要刷入磁盘重新获取。
整体写下来最麻烦的感觉就是页锁与池锁的关系,池锁(bpm_latch_)锁住的是缓存池内部的映射表、空闲队列,而页锁(page、frame)则是保护read与write关系的一环。
按照项目的提示,我以RAII的语义,在Guard实例的同时需要获取所有资源,但是资源的得到顺序又与外部不对应:构建时:需要利用池锁来构建新的映射,得到
Guard->Guard内获取页锁,选择读写类型析构时:如果只是先析构外部表的映射,再利用自身释放页锁,就会造成
ABBA的死锁现象,循环获取。所以我先手动释放页锁,再申请表锁。
缝缝补补的,感觉写的不是很理想,事后就是细化锁粒度,不把他和IO事件关联造成阻塞与死锁现象。
同时我自己在写完提交时发现没有做好pin与unpin的管理,导致很多奇葩错误。在返回各种Guard的时候,要手动做好frame的pin,不然pin永远计数有误。
整体看下来,Project1还是比较有难度的,写后面的task就会回头完善前面的task,同时也学会了std::promise<bool>的用法,不只是局限于条件变量或者信号量了。
由于我不是一把大锁锁到底,结果是需要对page也有一个锁,避免T1读取P1,而T2也读取P1,我觉得可以采用信号量机制来实现并发。
感觉自己写的越来与麻烦,但是基础测试通过了,但是没有对SCAN做优化,所以QPS偏低,实在写不动了= =。






