CMU-15445 Lab 1笔记

2022-04-20 | 阅读：次

PROJECT#1 BUFFER POOL

TASK#1 LRU REPLACEMENT POLICY

作为本次 Lab 的第一个 task，上来就是要我们实现一个 LRU，还好之前在 LeetCode 上实现过类似的，倒也问题不大，双向链表加哈希一把梭

private:  
  // TODO(student): implement me!  
  struct frameNode {  
    frame_id_t frame_id_{-1};  
    struct frameNode *pre{nullptr};  
    struct frameNode *next{nullptr};  

    explicit frameNode(frame_id_t frame_id) : frame_id_(frame_id){}  
  };  
  frameNode *dummyHead;  
  frameNode *dummyTail;  

  size_t capacity_{0};  
  size_t size_{0};  

  std::mutex lru_latch_;  

  std::unordered_map<frame_id_t, frameNode *> frame_map_;  

 private:  
  // 链表相关操作  
  void RemoveNode(frameNode *frame);  
  void MovetoTail(frameNode *frame);  
  void AppendtoTail(frameNode *frame);

不过和常规 LRU 稍微不一样的是，在这里我们需要实现的功能是 victim pin和 unpin

victim 希望返回一个最近最久未使用的 frame 来做替换。既然我们用双向链表来做的话就很简单了，直接返回表头元素即可

pin 的功能很简单，就是把需要的某个 frame 移出我们的 LRU 池（对应的场景就是此时某个线程正在使用这个 frame，我们当然不希望在使用期间这个 frame 被 LRU 调度给替换掉，所以我们主动把这个 frame 移出 LRU，并增加一个 pin 的标记，这样在使用结束后还能被正常移回到 LRU 池中）

unpin 则反过来，当这个 frame 的 pin 标志位为 0 的时候，此时已经没有线程在使用它了，我们就把它再次交由 LRU 调度

这部分还不算太难，唯二需要注意的是在做相关操作比如增加/删除元素的时候记得链表、哈希表、size需要同步更新，以及在重复 unpin 同一个 frame 的时候不需要做操作（从测试里面发现的，我也觉得很奇怪）

void LRUReplacer::Unpin(frame_id_t frame_id) {  
  std::lock_guard<std::mutex> lock(lru_latch_);  
  // LOG_INFO("unpin frame %d", frame_id);  
  if (!frame_map_.count(frame_id)) {  
    frameNode *unpin_frame = new frameNode(frame_id);  
    frame_map_[frame_id] = unpin_frame;  
    AppendtoTail(unpin_frame);  
    size_++;  
  } else {  
    // just do nothing  
    // MovetoTail(frame_map[frame_id]);  
  }  
}

TASK#2 BUFFER POOL MANAGER INSTANCE

在这个 task，我们需要完成一个 buffer pool manager 实例，这部分需要完成的函数就比较多了。

不过函数体里基本都给了比较详细的步骤提示，按着步骤来应该就大差不差了（测试之前是这么想的），结果写完一跑，连本地测试都过不去。。

随着逐渐 fix 代码里存在的问题，我才发现之前对内容的理解还是不太深入

首先就是 page_id 和 frame_id 之间的关系，借用课件里的图

buffer_pool 作为 manager 里的核心容器，每一格都是一个 frame，frame_id 标识 buffer_pool 里的数组项，我们还有一个 free_list 的数组来表示buffer_pool 里面空闲（也就是还没被分配）的 frame_id ; 而 page 的概念则指的是 disk 上面的内容。manager 里面还有一个 page_table 通过哈希表来表示 page_id 和 frame_id 的对应关系（对应关系指的就是此时这个 frame 被这个 page 所占用。因此对于一个到来的 page_id，我们要先去查 page_table，如果查得到就说明此时这个 page 已经被 buffer_pool 装载，直接通过对应的 frame_id 找就行。

然后还有一些其他边边角角的细节问题（比如说返回值以及标志位），这些才是最折磨人的，因为实现说明里面并没有提到这些，需要自己通过测试加上想象去完善。

在 NewPageImp的时候，取得对应的 frame_id 之后需要先判断一下这个 frame_id 的 is_dirty标志位，如果为真的话得先把脏数据执行一次 WritePage操作才能继续重定向操作。并且，在初始化标志位的时候，pin_count需要置成 1 （其实也很好理解，既然调用了 newpage 那么说明此时肯定是有一个线程需要使用该 page，置成 1 之后返回的 page 才不至于被 LRU 置换掉）
对于UnpinPageImp，如果在 page_table 里查不到这个 page_id，我们此时应该返回的是 true。我能想到的比较合理的解释是：unpin 的目的就是为了提醒 lru_replacer 可以把这个页面置换掉，那如果这个 page 甚至都已经不在 buffer_pool 里面了，是不是在另外一个角度来说也算是 unpin 成功了呢？另外，函数里还带了一个 is_dirty 参数，不能简单地直接赋给 pages_[frame_id].is_dirty_，这个想一下就能知道，如果原来就是脏数据但是参数给的是 false 的话，那最后的标志位应该还是 true 的

TASK#3 PARALLEL BUFFER POOL MANAGER

这个 task 相比上一个更上一级。单实例只有一把锁，多线程来争这一把锁的话效率上太低了。所以我们需要完成一个有多实例的 manager

这个 task 算是最不用动脑子的了，基本只要调用上一个 task 完成的 api 就行了，只有 NewPage 的时候需要注意起始 index 的问题，在完成 page 的创建之后，instance_index需要自增一个，方便下次 new 的话不会又在同一个位置 newpage

Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) {  
  // create new page. We will request page allocation in a round robin manner from the underlying  
  // BufferPoolManagerInstances  
  // 1.   From a starting index of the BPMIs, call NewPageImpl until either 1) success and return 2) looped around to starting index and return nullptr  
  // 2.   Bump the starting index (mod number of instances) to start search at a different BPMI each time this function is called  
  Page *page = nullptr;  
  size_t index = instance_index_;  
  do {  
    page = bufferpool_instance[index]->NewPage(page_id);  
    if (page != nullptr) {  
      break;  
    }  
    index = (index + 1) % num_instances_;  
  } while (index != instance_index_);  
  instance_index_ = (instance_index_ + 1) % num_instances_;  
  return page;  
}

记得在析构函数里把创建的 instance 都销毁了

ParallelBufferPoolManager::~ParallelBufferPoolManager() {  
  for (size_t i = 0; i < num_instances_; i++) {  
    delete bufferpool_instance[i];  
  }  
  delete[] bufferpool_instance;  
}

满分通过