概述

CMU 15-445 是 CMU 的一个操作系统课程，Youtube 上有整个课程的视频，视频早在过年的时候已经看完了，然而实验却迟迟没有动。去年给自己定了个任务是要自己完成一个数据库，2020 年也只剩下半年了，是要开始完成这个任务了。

第一个实验，就是要实现磁盘页和内存页的管理。数据库系统将磁盘读入到内存中，并维护一个内存池，如果某个查询需要查询磁盘的某一页，会先去维护的内存池中获取，如果没有则从磁盘获取，并写入内存池，然后这里就涉及到一些换入换出的策略，比如 FIFO、LRU、Clock 等。实际上和操作系统的文件系统管理基本是一样的，也有很多数据库管理系统就是直接用的操作系统的文件系统缓存来做 Buffer Pool。

这个实验主要是要完成两个任务，一个是页面置换算法，CLOCK 算法的实现，另一个就是实现 Buffer Pool 的管理，例如分配一个页，获取某个页，将某一页刷回磁盘这样的功能。

TASK #1 - CLOCK REPLACEMENT POLICY

Clock 算法

image

Victim 方法实现

这个就是采用 clcok 算法置换页的方法。clock 算法的实现我采用的是 unordered_map 加 vector 的实现，用 unordered_map 来记录当前页是不是在 clocker_replacer 里面，用 vector 来记录页的位置以及 ref_bit，实现时钟扫描。具体算法的逻辑是，clock_hand 初始值为 0，然后依次往后查找，如果当前页在 map 里，就看他的 ref_bit 是不是为 0，如果是 0 就是找到了要替换的页，就把这一页替换出去，返回 true, 如果是 1 则要将 ref_bit 置为 0。初始是默认所有的页都不在 clock_replacer 里面所以 map 初始时是空的，但是所有的页都必须要在 clocker_replacer 里有一个位置，所以初始化时 vector 的大小应该和 buffer pool 的大小一样。

构造函数的实现：

image

要注意的是必须保证线程安全。

Victim 具体实现：

image

Pin, Unpin 方法实现

Pin 代表当前页正在被使用，不应该被置换，所以要把这页从 clock replacer 里移除出去。

Unpin 的化好 pin 相反，说明当前页没有被使用，所以要把这页加到 clock replacer 里，由于这页是刚被使用过的，所以 ref_bit 要置为 1。

具体实现：

image

TASK #2 - BUFFER POOL MANAGER

FetchPageImpl 方法实现

这个方法是从 Buffer Pool 里取一页。具体逻辑是通过传入的 page_id 在页表中查找，如果页表中有说明这页在 Buffer Pool 里面，直接从 Buffer Pool 取出这一页返回。如果页表中没有就要通过 page_id 到磁盘中去把这页读到 Buffer Pool 中，可以读到 Buffer Pool 中的空间一个是空闲的 free_list, 如果 free_list 中已经没有可用的空间了，那么就会从 replacer 中找出一页来替换。如果从 free_list 或者是 replacer 里取出来的页是脏页（这页被修改过），那么还要把这页先刷回磁盘。最后就是修改页表映射关系，然后把磁盘里的数据读到 Bool Pool 里来。

具体实现：

image

NewPageImpl 方法实现

这个方法和之前的 FetchPageImpl 实现类似，不同点在于这个方法是在 Buffer Pool 中新建一个页，不会先从 Buffer Pool 中取，而是直接去磁盘中取。

具体实现：

image

UnpinPageImpl 方法实现

这个方法是将 Buffer Pool 中的某一页标志为没有被使用，如果 pin_count <= 0 那么说明这页之前就是没有被使用过的，所以不需要做任何操作，直接返回 false, 如果 pin_count > 0 则返回 true。需要注意的是如果这一页被 unpin 了那么就需要把它加到 repacer 中。

具体实现：

image

FlushPageImpl 方法实现

这个方法是将指定页写回磁盘，比较简单。

具体实现：

image

DeletePageImpl 方法实现

这个方法是将指定页从 Buffer Pool 删除，如果指定页不在 Buffer Pool 直接返回 false, 如果指定页正在被使用那么不能直接删除，直接返回 false。否则的话就可以被删除。

具体实现：

image

FlushAllPagesImpl 方法实现

这个方法也比较简单，直接便利页表，调用 FlushPageImpl 就可以了。

具体实现：

image

测试

image

实验上说代码里给的单元测试不全，可能需要自己补充。所以通过测试并不代表实现是正确的，这个还是看看之后能不能发现问题吧。