禅茶一味

明天再说的自留地

0%

CMU15-445 lab01

发表于 更新于 分类于 Valine：
本文字数： 11k 阅读时长 ≈ 10 分钟

Task1 LRU REPLACEMENT POLICY

任务描述

这个任务要求我们实现在课堂上所描述的LRU算法。

你需要实现下面这些函数。请确保他们都是线程安全的。

  • Victim(T*) : Remove the object that was accessed the least recently compared to all the elements being tracked by the Replacer, store its contents in the output parameter and return True. If the Replacer is empty return False.

  • Pin(T) :This method should be called after a page is pinned to a frame in the BufferPoolManager. It should remove the frame containing the pinned page from the LRUReplacer.

  • Unpin(T) : This method should be called when the pin_count of a page becomes 0. This method should add the frame containing the unpinned page to the LRUReplacer.

  • Size() : This method returns the number of frames that are currently in the LRUReplacer.

LRU实现

基本数据结构

LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
  • 考虑到线程安全及并发错误， 需要在函数中加入latch锁。
  • capacity表示replacer的容量。
  • lru_list为双向链表，记录replacer的frame。
  • 使用lruMap哈希表+双链表的结构，哈希表存储frame id以及指向lru_list内frame的begin指针，让插入和删除复杂度均为O(1)。
1
2
3
4
5
private:
  std::mutex latch;  // thread safety
  size_t capacity;   // max number of pages LRUReplacer can handle
  std::list<frame_id_t> lru_list;
  std::unordered_map<frame_id_t, std::list<frame_id_t>::iterator> lruMap;

Victim 函数实现

注意这里必须要加锁，以防止并发错误。
  • 使用std::scoped_lockc++17中的scope锁，它能够避免死锁发生，其构造函数能够自动进行上锁操作，析构函数会对互斥量进行解锁操作，保证线程安全。
  • 如果replacer为空，意味着找不到牺牲页，返回false。
  • 如果replacer非空，删除最久未使用的页面。
1
2
3
4
5
6
7
8
9
10
11
12
bool LRUReplacer::Victim(frame_id_t *frame_id) {
  std::scoped_lock lock{latch};
  // If empty, it means that no victim can be found.
  if (lruMap.empty()) {
    return false;
  }
  // Find the last frame and remove it.
  *frame_id = lru_list.back();
  lruMap.erase(*frame_id);
  lru_list.pop_back();
  return true;
}

pin 函数实现

注意这里必须要加锁，以防止并发错误。
  • pin的作用是标记该页（如正在使用），防止并发错误。
  • 如果找到该frame, 将其从replacer中删除。
1
2
3
4
5
6
7
8
9
void LRUReplacer::Pin(frame_id_t frame_id) {
  std::scoped_lock lock{latch};
  // Find the frame and pin it.
  auto it = lruMap.find(frame_id);
  if (it != lruMap.end()) {
    lru_list.erase(lruMap[frame_id]);
    lruMap.erase(frame_id);
  }
}

unpin 函数实现

注意这里必须要加锁，以防止并发错误。
  • unpin的作用是取消标记，将该页加入replacer中。
  • 如果在replacer中找不到该frame，且replacer不满，加入该frame。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void LRUReplacer::Unpin(frame_id_t frame_id) {
  std::scoped_lock lock{latch};
  // If exist, do nothing.
  auto it = lruMap.find(frame_id);
  if (it != lruMap.end()) {
    return;
  }
  // if list size >= capacity, do nothing
  if (Size() >= capacity) {
    return;
  }
  // insert
  lru_list.push_front(frame_id);
  lruMap.emplace(frame_id, lru_list.begin());
}

Test

  • 检测语法及格式
1
2
3
4
5
$ cd build
$ make format
$ make check-lint
$ make check-clang-tidy
$ make lru_replacer_test
  • 测试
1
2
3
4
5
6
7
8
9
10
11
12
$ ./test/lru_replacer_test
Running main() from gmock_main.cc
[==========] Running 1 test from 1 test suite.
[----------] Global test environment set-up.
[----------] 1 test from LRUReplacerTest
[ RUN      ] LRUReplacerTest.SampleTest
[       OK ] LRUReplacerTest.SampleTest (0 ms)
[----------] 1 test from LRUReplacerTest (0 ms total)

[----------] Global test environment tear-down
[==========] 1 test from 1 test suite ran. (0 ms total)
[  PASSED  ] 1 test.

Task2 BUFFER POOL MANAGER

任务描述

接下来，您需要在系统中实现缓冲池管理器(BufferPoolManager)。BufferPoolManager负责从DiskManager获取数据库页面并将它们存储在内存中。BufferPoolManage还可以在有要求它这样做时，或者当它需要驱逐一个页以便为新页腾出空间时，将脏页写入磁盘。为了确保您的实现能够正确地与系统的其余部分一起工作，我们将为您提供一些已经填写好的功能。您也不需要实现实际读写数据到磁盘的代码(在我们的实现中称为DiskManager)。我们将为您提供这一功能。

系统中的所有内存页面均由Page对象表示。BufferPoolManager不需要了解这些页面的内容。 但是，作为系统开发人员，重要的是要了解Page对象只是缓冲池中用于存储内存的容器，因此并不特定于唯一页面。 也就是说，每个Page对象都包含一块内存，DiskManager会将其用作复制从磁盘读取的物理页面内容的位置。 BufferPoolManager将在将其来回移动到磁盘时重用相同的Page对象来存储数据。 这意味着在系统的整个生命周期中，相同的Page对象可能包含不同的物理页面。Page对象的标识符（page_id）跟踪其包含的物理页面。 如果Page对象不包含物理页面，则必须将其page_id设置为INVALID_PAGE_ID。

每个Page对象还维护一个计数器，以显示“固定”该页面的线程数。BufferPoolManager不允许释放固定的页面。每个Page对象还跟踪它的脏标记。您的工作是判断页面在解绑定之前是否已经被修改（修改则把脏标记置为1）。BufferPoolManager必须将脏页的内容写回磁盘，然后才能重用该对象。

BufferPoolManager实现将使用在此分配的前面步骤中创建的LRUReplacer类。它将使用LRUReplacer来跟踪何时访问页对象，以便在必须释放一个帧以为从磁盘复制新的物理页腾出空间时，它可以决定取消哪个页对象

你需要实现在(src/buffer/buffer_pool_manager.cpp):的以下函数

  • FetchPageImpl(page_id)
  • NewPageImpl(page_id)
  • UnpinPageImpl(page_id, is_dirty)
  • FlushPageImpl(page_id)
  • DeletePageImpl(page_id)
  • FlushAllPagesImpl()

BufferPool实现

基本数据结构

  • pool_size_表示缓冲池的最大容量。
  • *pages_指向缓冲池中page数组，用pages_ = new Page[pool_size_]来初始化。
  • page_table_是页表，page_id标识磁盘页，页表记录了该page在磁盘中的page_id和对应缓冲池中的frame_id。
  • free_list里面存的是frame_id，具体来说就是还没有被分配的缓冲池的数组项
1
2
3
4
5
6
7
8
/** Number of pages in the buffer pool. */
size_t pool_size_;
/** Array of buffer pool pages. */
Page *pages_;
/** Page table for keeping track of buffer pool pages. */
std::unordered_map<page_id_t, frame_id_t> page_table_;
/** List of free pages. */
std::list<frame_id_t> free_list_;

UpdatePage函数实现

  • 这是一个辅助函数，目的是更新页表中的数据。
  • 如果是脏页，需要先将数据写回磁盘。
  • 如果不是脏页，更新页表中的id。
  • 最后清空该页，更新id。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void BufferPoolManager::UpdatePage(Page *page, page_id_t new_page_id, frame_id_t new_frame_id) {
  if (page->IsDirty()) {
    disk_manager_->WritePage(page->page_id_, page->data_);
    page->is_dirty_ = false;
  }

  // Put the new page in page table.
  page_table_.erase(page->page_id_);
  if (new_page_id != INVALID_PAGE_ID) {
    page_table_.emplace(new_page_id, new_frame_id);
  }

  // Make the page data empty.
  page->ResetMemory();
  page->page_id_ = new_page_id;
}

FindVictimPage函数实现

  • 这是一个辅助函数，目的是找到牺牲页。
  • 如果free_list_不满，意味着buffer pool还有空位，找到frame_id。
  • 如果缓冲池已满，调用LRU算法找牺牲页。
1
2
3
4
5
6
7
8
9
10
bool BufferPoolManager::FindVictimPage(frame_id_t *frame_id) {
  // Buffer pool is not full. Get the frame id from free_list.
  if (!free_list_.empty()) {
    *frame_id = free_list_.front();
    free_list_.pop_front();
    return true;
  }
  // Buffer pool is full. Use LRU algorithm.
  return replacer_->Victim(frame_id);
}

FetchPageImpl函数实现

注意这里必须要加锁，以防止并发错误。
  • 如果能在page_table_页表中找到该页，调用replacer将其pin出。
  • 如果找不到，说明该page不在缓冲池中，而在磁盘中，调用FindVictimPage在缓冲池中找到frame。
  • 通过frame_id找到相应的page，更新数据，别忘了pin住该页。
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
Page *BufferPoolManager::FetchPageImpl(page_id_t page_id) {
  // 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.
  std::scoped_lock lock{latch_};

  auto iter = page_table_.find(page_id);
  if (iter != page_table_.end()) {
    // Find the frame id through page table.
    frame_id_t frame_id = iter->second;
    Page *page = &pages_[frame_id];
    // Pin it and and record it in pin count.
    replacer_->Pin(frame_id);
    page->pin_count_++;
    return page;
  }

  // Cannot find. It means that this page is in the disk.
  frame_id_t frame_id = -1;
  // Find the victim page and insert the disk page instead.
  if (!FindVictimPage(&frame_id)) {
    return nullptr;
  }

  // Find the page and get the frame id.
  Page *page = &pages_[frame_id];
  UpdatePage(page, page_id, frame_id);
  disk_manager_->ReadPage(page_id, page->data_);
  // pin it
  replacer_->Pin(frame_id);
  page->pin_count_ = 1;

  return page;
}

UnpinPageImpl函数实现

注意这里必须要加锁，以防止并发错误。
  • 如果我们这个进程已经完成了对该页的操作。我们需要unpin。
  • 如果该page在缓冲池中，将pin_count减一，如果pin_count为0，unpin该页.
  • 标注该页为dirty。
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
bool BufferPoolManager::UnpinPageImpl(page_id_t page_id, bool is_dirty) {
  std::scoped_lock lock{latch_};
  auto iter = page_table_.find(page_id);
  // Cannot find the page in buffer pool.
  if (iter == page_table_.end()) {
    return false;
  }
  // Find the page.
  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  // Check pin count.
  if (page->pin_count_ == 0) {
    return false;
  }
  // Do unpin.
  page->pin_count_--;
  if (page->pin_count_ == 0) {
    replacer_->Unpin(frame_id);
  }

  if (is_dirty) {
    page->is_dirty_ = true;
  }

  return true;
}

FlushPageImpl函数实现

注意这里必须要加锁，以防止并发错误。
  • 这个函数是要把一个page写入磁盘。
  • 在缓冲中找到该页，调用WritePage，并标记该页非脏。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool BufferPoolManager::FlushPageImpl(page_id_t page_id) {
  // Make sure you call DiskManager::WritePage!
  std::scoped_lock lock{latch_};
  auto iter = page_table_.find(page_id);

  if (iter == page_table_.end()) {
    return false;
  }

  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  // Write the dirty page into disk.
  disk_manager_->WritePage(page->page_id_, page->data_);
  page->is_dirty_ = false;
  return true;
}

NewPageImpl函数实现

注意这里必须要加锁，以防止并发错误。
  • 这个函数是要从DiskManager中分配一个新页到缓冲池。
  • 在缓冲中找不到位置，且没有牺牲页，返回空指针。
  • 找到frame_id， 更新数据，pin住该页。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Page *BufferPoolManager::NewPageImpl(page_id_t *page_id) {
  // 0.   Make sure you call DiskManager::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.
  std::scoped_lock lock{latch_};

  frame_id_t frame_id = -1;
  if (!FindVictimPage(&frame_id)) {  // Delete page in free list.
    return nullptr;
  }
  // Get the frame id.
  *page_id = disk_manager_->AllocatePage();
  Page *page = &pages_[frame_id];
  // Update and pin page.
  UpdatePage(page, *page_id, frame_id);
  replacer_->Pin(frame_id);
  page->pin_count_ = 1;

  return page;
}

DeletePageImpl函数实现

注意这里必须要加锁，以防止并发错误。
  • 这里是删除缓冲池中的page。
  • 在缓冲中找不到该page，返回true。
  • 找到frame_id，若不是pin状态，删除该页。
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
bool BufferPoolManager::DeletePageImpl(page_id_t page_id) {
  // 0.   Make sure you call DiskManager::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.
  std::scoped_lock lock{latch_};
  // Cannot find the page.
  auto iter = page_table_.find(page_id);
  if (iter == page_table_.end()) {
    return true;
  }
  // Get the frame id.
  frame_id_t frame_id = iter->second;
  Page *page = &pages_[frame_id];
  // Canot delete pin page.
  if (page->pin_count_ != 0) {
    return false;
  }

  disk_manager_->DeallocatePage(page_id);
  UpdatePage(page, INVALID_PAGE_ID, frame_id);
  free_list_.push_back(frame_id);
  return true;
}

Test

  • 检测语法及格式
1
2
3
4
5
$ cd build
$ make format
$ make check-lint
$ make check-clang-tidy
$ make buffer_pool_manager_test
  • 测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
$ ./test/buffer_pool_manager_test 
Running main() from gmock_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from BufferPoolManagerTest
[ RUN      ] BufferPoolManagerTest.BinaryDataTest
[       OK ] BufferPoolManagerTest.BinaryDataTest (0 ms)
[ RUN      ] BufferPoolManagerTest.SampleTest
[       OK ] BufferPoolManagerTest.SampleTest (0 ms)
[----------] 2 tests from BufferPoolManagerTest (1 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (1 ms total)
[  PASSED  ] 2 tests.
  • gradescope测试