CMU15-445 Project #1 Buffer Pool
Lab内容
Lab的總體目标是建構一個buffer pool manager 用于管理page寫入寫出buffer pool。本質上就是實作slides中的下圖，維護一個page_id到frame_id的映射，并且根據不同狀态執行不同的操作。
分為兩個部分，LRU REPLACEMENT POLICY以及BUFFER POOL MANAGER，LRU REPLACEMENT POLICY是為 BUFFER POOL MANAGER服務的
TASK #1 - LRU REPLACEMENT POLICY
這部分就是實作LRU算法,經典面試題，實作一下Leetcode 146. LRU 緩存機制，與Leetcode不同的是，Leetcode實作的是一個KV，而Lab中所給出的接口略有不同
為了實作LRU功能新增了如下資料結構
std::list<frame_id_t> cache
用于存儲是以可被換出的frame_id，也就是unpined狀态下的frame_id集合，同時維護了frame的最後通路時間順序，從頭到尾通路時間從近到遠，是以需要找到page換出時會從尾部取，而插入從頭部插入
std::map<frame_id_t, std::list<frame_id_t>::iterator> frameid2node;
維護了frame_id到std::list<frame_id_t>::iterator的映射，用于O(log(n))找到對應frame_id在cache中的位址(用unordered_map可以O(1))
int maxframes;
cache大小上限，也就是buffer pool 的大小
std::mutex lru_lock;
鎖，用于互斥通路
需要實作如下接口：
bool LRUReplacer::Victim(frame_id_t *frame_id)
該函數找到一個頁換出，并且将換出的frame_id存在參數*frame_id中，需要滿足優先換出最遠通路的page
void Pin(frame_id_t frame_id) override;
用于将frame_id鎖定，轉換成pinned狀态，該狀态的frame不會被換出，在本實作中也就是從cache中删除，這裡注意不要重複删除
void Unpin(frame_id_t frame_id) override;
用于将frame_id解除鎖定，轉換成unpinned狀态，該狀态的frame有可能被換出，本實作就是插入cache中，注意不要重複unpinned
TASK #2 - BUFFER POOL MANAGER
該部分是配合上一個task的lru_replacer實作一個buffer pool manager，主要實作以下接口。
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id)
該接口實作的是将參數page_id換入buffer pool中，需要注意的點有如下幾個：
1.如果page_id在page_table_裡，需要pin_count++，因為此時可能還有其他線程使用該page_id
2.如果page_id在page_table_裡，需要replacer_->Pin(frame_id)，確定該page_id對應的frame_id處于pinned狀态
bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty)
該接口實作的是将對應page_id 從Buffer pool 中Unpin，并且給page賦is_dirty，需要注意的有如下幾點:
1.page_table_中找不到page_id，需要return true，雖然接口說明寫清楚了true otherwise，但是一般第一次寫都會return false吧。。。
2.unpined的時候需要判斷pin_count 每次調用UnpinPageImpl,--pin_count,隻有pin_count調用前等于1，也就是--pin_count=0的時候才調用replacer_->Unpin(page_table_[page_id])
3.設定is_dirty需要Pageptr->is_dirty_ = Pageptr->is_dirty_ || is_dirty;防止本來page是dirty的，用is_dirty=false刷成false，導緻出錯
bool BufferPoolManager::FlushPageImpl(page_id_t page_id)
該接口實作的是将page_id的内容刷入disk中，實作比較簡單但是有個坑，這個函數要加鎖，因為測試的時候會調用這個函數，如果不加鎖，當作一個函數在需要重新整理的地方調用，那麼測試的時候會導緻多個線程寫同一個page造成錯誤，是以我發現了這個問題時在原本調用無鎖FlushPageImpl的地方改成了FlushPageImplWithoutLock。
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id)
該接口實作的是建立一個page，這裡有一個坑點，就是建立page 不能将dirty設定成true等換出的時候flush,因為有測試是類似check(0,newpage->data())，需要将初始化的内容馬上刷進disk，不然就過不了測試
bool BufferPoolManager::DeletePageImpl(page_id_t page_id)
該接口實作的是将page_id從buffer_pool删除，加入free_list_中，這裡有個坑點是删除的時候需要Pin(page_id)，如果不調用，假設該page_id原先是unpinned的，在replacer中，那麼就會導緻該page_id同時出replacer和free_list_中。
void BufferPoolManager::FlushAllPagesImpl()
把所有page_id刷盤，這個沒什麼好說的。。
換出政策
以上所有實作涉及到需要換出舊page，換入新page的時候，首先是需要從free_list_中，如果free_list_沒有空閑，再從replacer中找，因為從free_list_中可以直接得到空閑的frame，不涉及換出，而從replacer中需要換出unppined的frame,即使使用了lazy write機制，還是從free_List_中擷取frame通路disk和記憶體的次數小。是否将淘汰頁刷入disk則需要通過Page的dirty标記判斷。
結果
