CMU15-445 Project1

CMU15-445 Project1

Part I LRU Replacement Policy

类的设计

Replacer作为基类，LRU_Replacer作为继承类，实现基本功能：

Victim、Pin、Unpin、Size。

链表+Hash table来实现。Hash table存frame_id到链表上元素指针的映射。这里通过存指针来实现直接定位链表上的元素。链表的实现可以是作用域中的另外一个struct。一开始要有两个sentinel指针head和tail。

函数及其功能

Victim(frame_id_t *)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
auto LRUReplacer::Victim(frame_id_t *frame_id) -> bool {
  mtx_.lock();
  if (size_ == 0) {
    mtx_.unlock();
    return false;
  }
  ListNode *tail_node = head_->next_;
  *frame_id = tail_node->frame_id_;
  tail_node->Remove();
  delete tail_node;
  --size_;
  hash_map_.erase(*frame_id);
  mtx_.unlock();
  return true;
}

这个函数就是直接把链表首元素返回，同时在hash table中删除即可。

犯了一个错：如果要对指针指向的值进行修改，一定要先对指针进行解引用，如果对指针本身指向的地址更改，可以不用解引用，如果要对指针本身指向的值进行更改，并且要让这个更改传递下去，需要定义为指针的引用

Pin(frame_id_t frame_id)

1
2
3
4
5
6
7
8
9
10
11
void LRUReplacer::Pin(frame_id_t frame_id) {
  mtx_.lock();
  if (hash_map_.find(frame_id) != hash_map_.end()) {
    ListNode *object_node = hash_map_[frame_id];
    object_node->Remove();
    hash_map_.erase(frame_id);
    delete object_node;
    --size_;
  }
  mtx_.unlock();
}

就是直接从LRU队列中将这个元素给删掉。

Unpin(frame_id_t frame_id)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void LRUReplacer::Unpin(frame_id_t frame_id) {
  mtx_.lock();
  if (hash_map_.find(frame_id) == hash_map_.end()) {
    while (size_ >= capacity_) {
      ListNode *object_node = head_->next_;
      object_node->Remove();
      hash_map_.erase(object_node->frame_id_);
      delete object_node;
      --size_;
    }
    auto *new_node = new ListNode(frame_id);
    AddTail(new_node);
    hash_map_[frame_id] = new_node;
    ++size_;
  }
  mtx_.unlock();
}

一开始要判断LRU队列是不是满的，如果是满的，就要把队首的给删了。

设计要点

1.类中动态分配了内存，所以析构函数一定要考虑到类中所有的成员变量！对应着delete。这里要遍历链表进行delete：

1
2
3
4
5
6
7
8
9
10
LRUReplacer::~LRUReplacer() {
  //释放整个链表的内存
  ListNode *temp;
  for (auto it = head_ -> next_; it != tail_; it = temp) {
    temp = it -> next_;
    delete it;
  }
  delete head_;
  delete tail_;
}

2.Latch需要在每个外部函数中加上。在加锁之前先分析清楚代码层次结构，如果外部加了锁内部就不要再继续加锁了。

3.对Pin和Unpin表示的意义：单看LRU这一部分不能理解的很清楚，先查阅整个项目整体的设计，需要设计哪些函数，每个函数用来干什么。

Part II BufferPoolManager

设计逻辑

这一部分和LRU这一部分联系起来。先要详细阅读任务书中的要实现的函数的定义、作用，记一下类中的成员变量的作用。做成一个文档列出来方便查阅，不急着写。

1.BufferPool上存储page的位置叫做frame。一开始所有的frame都是空的，空的frame_id都存在free_list中。从外层操作BufferPool的逻辑是，如果我们要分配一个新的page，那么就先看free_list上有没有空的frame，如果有就直接把page放到对应的frame上，否则从LRU中找。

2.LRU和BufferPool交互的逻辑：LRU队列上存的都是已经有page的frame，并且这些frame现在并没有被任何线程操作。也就是说，一开始LRU队列是空的，每当我们在BufferPool中对一个frame上的page操作完后，我们就在LRU层次上对他Unpin，那么就说明这个frame是可以被替换的。如果一个线程对这个frame要进行操作了，我们就在LRU层次上对这个frame Pin，那么这个frame就不能被替换了。

3.BufferPool上的成员操作的都是frame，因此需要有一个map将给定的page_id映射到frame_id上。

4.设计每一个函数的逻辑应该是这个函数的操作步骤–>LRU应该做什么。即上层应该考虑到下层应该做什么操作，想清楚再写。

5.不仅仅是LRU，对磁盘的读写操作也是一个下层。什么时候应该写回磁盘，需要在写每个函数前弄清楚。

函数及其功能

NewPgImp(page_id_t *page_id) -> Page *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
auto BufferPoolManagerInstance::NewPgImp(page_id_t *page_id) -> Page * {
  // 0.   Make sure you call AllocatePage!
  // 1.   If all the pages in the buffer pool are pinned, return nullptr.
  // 2.   Pick a victim page P from either the free list or the replacer. Always pick from the free list first.
  // 3.   Update P's metadata, zero out memory and add P to the page table.
  // 4.   Set the page ID output parameter. Return a pointer to P.
  latch_.lock();
  bool flag = true;
  for (int i = 0; i < static_cast<int>(pool_size_); ++i) {
    if (pages_[i].pin_count_ == 0) {
      flag = false;
      break;
    }
  }
  if (flag) {
    latch_.unlock();
    return nullptr;
  }
  frame_id_t stored_frame;
  if (!findFrame(&stored_frame)) {
    latch_.unlock();
    return nullptr;
  }
  page_id_t new_page_id = AllocatePage();
  Page *new_page = &pages_[stored_frame];
  new_page -> page_id_ = new_page_id;
  new_page -> pin_count_++;
  replacer_ -> Pin(stored_frame);
  page_table_[new_page_id] = stored_frame;
  reverse_page_table_[stored_frame] = new_page_id;
  new_page -> is_dirty_ = false;
  disk_manager_ ->WritePage(new_page -> GetPageId(),new_page -> GetData());
  *page_id = new_page_id;
  latch_.unlock();

  return new_page;
}

1.如果所有的frame都在被其他线程使用，无法分配也无法替换，失败。

2.如果能找到一个frame存新分配的page，就分配/替换。

3.修改新分配的page的元数据，确保所有的元数据都要修改到，即使本身不需要修改。这里新分配的page是默认被占用的，因此要在LRU上Pin住。

bool findFrame(frame_id_t *frame_id)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool BufferPoolManagerInstance::findFrame(frame_id_t *frame_id) {
  if (!free_list_.empty()) {
    *frame_id = free_list_.front();
    free_list_.pop_front();
    return true;
  }
  if (replacer_ ->Victim(frame_id)) {
    //如果要替换的帧在page_table_中，就要改写，这里可以另外用一个map
    if (reverse_page_table_.find(*frame_id) != reverse_page_table_.end()) {
      Page* replaced_page = &pages_[*frame_id];
      if (replaced_page -> is_dirty_) {
        disk_manager_ ->WritePage(replaced_page -> page_id_,replaced_page->data_);
        replaced_page -> pin_count_ = 0;
      }
      page_table_.erase(replaced_page -> page_id_);
      reverse_page_table_.erase(*frame_id);
    }
    return true;
  }
  return false;
}

当我们要把一个page从frame上拿出时（可能是直接扔掉，也可能是要拿到上层进行一些修改操作），要写回磁盘。

FlushPgImp(page_id_t page_id) -> bool

1
2
3
4
5
6
7
auto BufferPoolManagerInstance::FlushPgImp(page_id_t page_id) -> bool {
  if (page_id == INVALID_PAGE_ID || page_table_.find(page_id) == page_table_.end()) {
    return false;
  }
  disk_manager_ ->WritePage(page_id,pages_[page_table_[page_id]].data_);
  return true;
}

特别注意这个函数和上一个函数都不要加锁。因为这两个函数在类中属于低层次，并不会直接被类外的函数直接调用，而一定是被类中的其他函数间接调用，如果加锁就会造成死锁问题。

BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) -> Page *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
auto BufferPoolManagerInstance::FetchPgImp(page_id_t page_id) -> Page * {
  // 1.     Search the page table for the requested page (P).
  // 1.1    If P exists, pin it and return it immediately.
  // 1.2    If P does not exist, find a replacement page (R) from either the free list or the replacer.
  //        Note that pages are always found from the free list first.
  // 2.     If R is dirty, write it back to the disk.
  // 3.     Delete R from the page table and insert P.
  // 4.     Update P's metadata, read in the page content from disk, and then return a pointer to P.
  latch_.lock();
  if (page_table_.find(page_id) != page_table_.end()) {
    frame_id_t frame_id = page_table_[page_id];
    Page* page = &pages_[frame_id];
    page->pin_count_++;
    replacer_ ->Pin(frame_id);
    latch_.unlock();
    return page;
  }
  frame_id_t stored_frame;
  if (!findFrame(&stored_frame)) {
    latch_.unlock();
    return nullptr;
  }
  Page *new_page = &pages_[stored_frame];
  if (new_page -> is_dirty_) {
    disk_manager_ ->WritePage(new_page -> page_id_,new_page -> data_);
  }
  page_table_.erase(new_page -> page_id_);
  new_page -> page_id_ = page_id;
  new_page -> pin_count_++;
  replacer_ -> Pin(stored_frame);
  new_page -> is_dirty_ = false;
  replacer_ ->Pin(stored_frame);
  disk_manager_->ReadPage(page_id,new_page->GetData());
  page_table_[page_id] = stored_frame;
  reverse_page_table_[stored_frame] = page_id;
  latch_.unlock();

  return new_page;
}

要点就是要Pin住和写回磁盘。

BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) -> bool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
auto BufferPoolManagerInstance::DeletePgImp(page_id_t page_id) -> bool {
  // 0.   Make sure you call DeallocatePage!
  // 1.   Search the page table for the requested page (P).
  // 1.   If P does not exist, return true.
  // 2.   If P exists, but has a non-zero pin-count, return false. Someone is using the page.
  // 3.   Otherwise, P can be deleted. Remove P from the page table, reset its metadata and return it to the free list.

  latch_.lock();
  if (page_table_.find(page_id) == page_table_.end()) {
    latch_.unlock();
    return true;
  }
  frame_id_t stored_frame = page_table_[page_id];
  Page *delete_page = &pages_[stored_frame];
  if (delete_page -> pin_count_ > 0) {
    latch_.unlock();
    return false;
  }
  if (delete_page -> is_dirty_) {
    FlushPgImp(page_id);
  }
  DeallocatePage(page_id);
  reverse_page_table_.erase(stored_frame);
  page_table_.erase(page_id);
  free_list_.push_back(stored_frame);
  delete_page -> is_dirty_ = false;
  delete_page -> pin_count_ = 0;
  delete_page -> page_id_ = INVALID_PAGE_ID;

  latch_.unlock();
  return true;
}

如果一个page正在被使用，就不能删除。

UnpinPgImp(page_id_t page_id, bool is_dirty) -> bool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
auto BufferPoolManagerInstance::UnpinPgImp(page_id_t page_id, bool is_dirty) -> bool {
  latch_.lock();
  if (page_table_.find(page_id) == page_table_.end()) {
    latch_.unlock();
    return false;
  }
  frame_id_t stored_frame = page_table_[page_id];
  Page *unpin_page = &pages_[stored_frame];
  //unpin_page -> is_dirty_ = is_dirty;
  if (is_dirty) { //notice
    unpin_page -> is_dirty_ = true;
  }
  if (unpin_page -> pin_count_ == 0) {
    latch_.unlock();
    return false;
  }
  unpin_page -> pin_count_--;
  if (unpin_page -> GetPinCount() == 0) {
    replacer_ ->Unpin(stored_frame);
  }

  latch_.unlock();
  return true;
}

设计要点

1.其实每个函数做的事情就是那么几步，自身怎么做、底层怎么做。

2.加锁的问题，先要搞清楚类中的层次，然后是类的每个成员的定义。

3.难点：Page不支持拷贝构造，因此要么用一个vector的emplace_back，要么用一个指针指向数组中的某个位置，对这个指针进行操作，也就是先默认对象数组中的所有元素都是初始化好了的。

PART III Parallel Buffer Pool Manager

设计逻辑

1.Parallel Buffer Pool Manager和Buffer Pool Manager都是Buffer Manager的子类，这里可以直接调用上一部分写的Buffer Pool中的函数，只需要在当前类中用一个数组存Buffer Pools即可。但是因为两个类是兄弟关系，如果要用到Buffer Pool Manager类中的方法，就需要声明友元。

2.一个不太好的设计：其实这里最好是用一个数组存Buffer Pool Manager的实例，但是受限于任务要求，这里我存了指针的指针数组，因此在操作指针的时候容易出问题：是否需要对指针本身进行修改？是否需要对指针指向的内容进行更改等等。而且一旦这样声明了，就必须遍历整个数组一个个delete对象，然后再来delete整个指针数组。

函数及其功能

NewPgImp(page_id_t *page_id) -> Page *

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
auto ParallelBufferPoolManager::NewPgImp(page_id_t *page_id) -> Page * {
  // 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
  latch_.lock();
  auto x = start_index_;
  Page* result = nullptr;
  do {
    BufferPoolManagerInstance*& buffer_pool = buffer_pools_[x];
    if (!allocated_[x]) {
      allocated_[x] = true;
      buffer_pool = new BufferPoolManagerInstance(pool_size_,disk_manager_,log_manager_);
    }
    result = buffer_pool ->NewPgImp(page_id);
    if (result == nullptr) {
      ++x;
      if (x == num_instances_) {
        x = 0;
      }
    }
    else {
      start_index_++;
      if (start_index_ == num_instances_) {
        start_index_ = 0;
      }
      latch_.unlock();
      return result;
    }
  }while (x != start_index_);
  start_index_++;
  if (start_index_ == num_instances_) {
    start_index_ = 0;
  }
  latch_.unlock();
  return result;
}

1.在Parallel Buffer Pool Manager中维护一个start_index，采用轮询分配的方法，先看start_index的这个Buffer Pool能否分配，如果不行就跳到下一个，直到走完一个圈。每次分配新的page都要让start_index++。

2.一个大坑就是：因为之前存的是指针数组，当我取出这个数组中的一个指针时，我是要对这个数组中的元素进行更改的，也就是要对取出来的这个指针进行更改，因此需要声明为指针的引用。

设计要点

1.对于下层类，用什么数据结构来存。最好是直接存实例。

2.关于锁，下层的函数其实都上锁了，但是这里依然要上锁，因为涉及到对当前类中的成员的修改。

总结

1.先通读整个项目需求，搞清楚不同层次之间的联系、每个函数的定义。

2.从下往上设计，用单独的文档写出每个成员变量和成员函数的API。

3.每个类的析构函数，对着成员变量一个个进行检验。

4.写成员函数的时候，先考虑对本层做什么，再考虑对下层做什么，先想清楚再写。

5.锁最后再来加。

赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家