Task1:LRU-K Replacement Policy

LRU-K算法，用于在Replacer中选择该移除的page。其会选择拥有最大的backward k-distance的page。backward k-distance等于第k次访问的时间和当前的时间之差。

LRU-K的核心思想就是将K次打包成一次，从而提高了稳定性。对于访问不到K次的page，直接认为其是最不重要的，不需要将其缓存，权重最低。

在这个task中，需要实现五个函数，分别是Evict、RecordAccess、SetEvictable、Remove与Size。

Evict

这个函数需要移除一个evictable的frame。当然evictable的frame有很多，具体移除哪一个就使用LRU-K算法决定。找到拥有最大的backward k-distance的page将其删除即可，这里我选择直接遍历所有的frame。

特殊情况：多个frame不满足K次访问记录，均拥有无限大的backward k-distance，此时根据哪个frame的第一次访问更加久远，决定删除哪一个。

一旦找到可以被移除的page时，需要更新curr_size_（维护了当前有多少个evictable_frame）。

RecordAccess

这个函数可以往Replacer中添加一个frame。
可以现在哈希表中查找是否已经存在这个frame，如果不存在就需要新建，并且设置LRUK-NODE的相应属性。

新建也需要注意，插入这个新的frame是否会超过Replacer的size，如果超过就不能新建。

最后将当前时间戳更新即可。

SetEvictable

将指定的frame的属性设置为evictable。

需要注意这个frame原先的属性是否与要设置的属性相同，如果不同，需要更新curr_size_。

Remove

直接删除指定的frame。删除时需要判断对应的frame是否存在，如果存在，检测其evictable属性，来更新curr_size_。

Size

直接返回curr_size_即可。

Task2:Buffer Pool Manager

这个Task中，需要配合disk-manager完成缓冲池管理的工作。
一共有六个函数需要实现，分别是FetchPage、UnpinPage、FlushPage、NewPage、DeletePage和FlushAllPage。

首先需要理解Buffer Pool的大致框架。首先在Buffer Pool Manager类里，已经声明了一个连续的内存空间（数组形式）叫做pages。这个数组里面存放的就是frame，frame可以用来装page，可以视作page的容器。加载page，就是从磁盘中把page放到frame中，移除page就是把frame里的page数据清空（视情况写回disk）。

另一个重要的点就是pin_count，可以理解为引用计数，pin_count不为0的page不能释放。

NewPage

这个函数中，需要创建一个新的page，然后装入frame中。

有以下几种情况：

有空闲frame。那么优先拿一个空闲frame出来，调用AllocatePage获得page_id。将frame里的数据清空，然后设置相应的meta-data（page_id、pin_count、is_dirty），最后在Task1中实现的LRU-K Replacer中将page设置为不可移除。然后page_table中建立page_id和frame_id的映射。
有可替换frame。令LRU-K Replacer返回该替换的frame_id。然后将对应的frame中的page清空，如果这个frame里存储的page是dirty page，那么调用disk manager将其写回到disk。然后之后的操作与1相同。但是需要注意，page_table需要移除原frame的映射，然后再建立一个frame_id和新page_id的映射。
既没有空闲frame，也没有可替换frame，那么可以直接返回。这代表无法新建page。

FetchPage

这个函数中，需要从磁盘读一个page放到frame里。

有以下几种情况：

有空闲frame，那么优先读入到空闲frame里。将空闲的frame清空，设置相应的meta-data（page_id、pin_count、is_dirty），然后调用Disk_manager将对应的page读入到frame里。最后利用Replacer设置为不可移除。page_table添加frame_id与page_id的映射。
有可替换frame，检查该frame里的page是否dirty，是的话要写回。然后将frame里的page清空，之后操作与1相同。page_table需要先移除旧的映射，然后添加新的映射。
无空闲frame也无可替换frame，可以直接返回，这代表无法读入新的page。
BufferPool中已经存在这个page，不需要读入，直接令其pin_count加一后返回。

UnpinPage

这个函数，需要在Buffer Pool中找到对应的page，将其pin_count减一。

以下几种情况：

找不到对应的page，那么直接返回。
找到了对应的page，但是它的pin_count已经为0，那么也直接返回。
找到了对应的page，且pin_count不为0，那么将其减一，然后检查pin_count是否为0，如果为0就要再调用Replacer将其设置为可移除。最后还需要设置page的drity标志，如果本身就是dirty，那么无论传入什么，都不能改变它的dirty性质。如果不为dirty，则设置成与入参一致。

FlushPage

这个函数的作用是将某个page强行写回磁盘，从而重置其dirty标志。

这个函数的实现就相对简单了，扫描Buffer Pool，如果找到对应page，那么就调用disk_manager将其数据写回，然后将其的Dirty标志清除。
如果找不到，直接返回false即可。

FlushAllPages

这个函数同FlushPage，只不过对所有的Page都进行Flush。

DeletePage

这个函数扫描Buffer Pool找到对应的page，将其删除，而且disk_manager也不再维护相关信息。

扫描Buffer Pool，找到对应的page，要检测其pin_count为0，如果不为0则不能删除，应该直接返回false。找到后，首先将该frame重新回收到空闲frame中，调用Replacer的Remove方法将其删除，最后还要调用DeallocatePage将其彻底删除。一切做完后，将对应的frame清空即可。