前言

​ 这次的lab/project分为三个步骤：实现extendible hash table, 实现LRU k replacer，实现buffer pool manager instance。值得注意的是在第三个实现会调用前两个实现，因此如果使用autograder，最好先让前两个满分（56），然后再测评第三个。

​ 对我而言，在实现时画类图蛮有效的（毕竟无法过目不忘），因此实验完成之后整理了大类关系图。接下来也会部分截图辅助说明思路。

​ 本次试验并没有用到gdb调试，而是print直接把数据结构给画了出来（个人觉得非并发下调试直接画图对于小例子测试实现逻辑bug来讲更快）。当然并发就无法解决这个问题，因此我直接一个全局lock，希望不会超时（1: ok, 2: ok, 3:ok ）。

Task #1 - Extendible Hash Table

UML图

实现逻辑

除了insert的逻辑基本都封装在bucket里，insert逻辑相对复杂一点，具体如下：

• //插入那个图

其中遇到的问题主要是bucket分裂时逻辑弄错了

bucket spilit的逻辑如下：

开两个新桶，对索引hash，得到的结果分为两类，放进两个桶里（一开始以为会开多个桶，后来发现测试例子不会，就优化掉了）

Task #2 - LRU-K Replacement Policy

UML图

实现逻辑

这里我主要使用了双向链表std::list和std::unordered_map来实现，如果不知道LRU可以先做146.LRU缓存

​ LRU-K是LRU的变种。这种算法认为设置一个K可以有效减少页面的抖动（刚换入又换出），通常K设置为2，再大虽然会增加效率，但是需要大量的数据访问作为前提，否则近似FIFO

​ 和LRU最大的区别在于，新增维护一个history队列，在这个队列中访问次数到达k，则移入cache队列。而替换页面时history队列实行FIFO，而cache队列实行LRU

Task #3 - Buffer Pool Manager Instance

UML图

给出所需要的UML图

• BufferPoolManagerInstance
• Page
• DiskManager

实现逻辑

一开始以为replacer应该是替换page的，后来想想替换frame也可以

这里因为并发编程学的不是很好，先用一把大锁保平安，等下一个实验再做做

跑分结果