Cmu15445_2021fall

 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
40

 Matrix(int rows, int cols) : rows_(rows), cols_(cols), linear_{new T[rows * cols]} {}

  RowMatrix(int rows, int cols) : Matrix<T>(rows, cols) {
    data_ = new T *[rows];
    for (int i = 0; i < rows; i++) {
      data_[i] = this->linear_ + i * cols;
    }
  }

  void FillFrom(const std::vector<T> &source) override {
    // throw NotImplementedException{"RowMatrix::FillFrom() not implemented."};
    bool flag = source.size() == static_cast<size_t>(this->rows_ * this->cols_);
    if (!flag) {
      throw Exception{ExceptionType::OUT_OF_RANGE, "out_of_range"};
    }
    memcpy(this->linear_, &source[0], source.size() * sizeof(T));
  }

    static std::unique_ptr<RowMatrix<T>> Multiply(const RowMatrix<T> *matrixA, const RowMatrix<T> *matrixB) {
    // TODO(P0): Add implementation
    int k{};
    bool flag = ((k = matrixB->GetRowCount()) == matrixA->GetColumnCount());
    if (!flag) {
      return std::unique_ptr<RowMatrix<T>>(nullptr);
    }

    int a{matrixA->GetRowCount()};
    int b{matrixB->GetColumnCount()};
    auto matrixC{std::make_unique<RowMatrix<T>>(a, b)};
    for (int i = 0; i < a; i++) {
      for (int j = 0; j < b; j++) {
        T sum{};
        for (int t = 0; t < k; t++) {
          sum += matrixA->GetElement(i, t) * matrixB->GetElement(t, j);
        }
        matrixC->SetElement(i, j, sum);
      }
    }
    return matrixC;
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

Victim(frame_id_t*)
// 从LRUReplacer去除最近最少访问的frame。将物理页移除内存。
// 因此当容量不为空时，去除最后一个frame.

Pin(frame_id_t)//
Unpin(frame_id_t)//
// pin是将page固定到BufferPoolManager后调用的方法，使得LRUReplacer中相应的frame移除。
// unpin会在page pagecount为0时调用,将unpinned page添加到replacer中。
//
// 这里注意一下，如果该页面已经在replacer时需要直接返回，这样跟测试匹配。（我在这里其实认为应当更新下顺序,即放到头前） 否则插入 LRUReplacer。
// 说白了,pinned page表示有thread 正在占用该frame.
// 注意当Size达到容量时，就不做处理了，因为这代表在replacer中管理的闲置frame达到上限。
// 同时由于Size()也上锁了，所以这里判断Size需要判断底层容器的size，否则调用Size()会死锁。解决死锁还可以scoped_lock里绑定个可重入的锁，但这样增加了锁的开销。


Size()// frame nums in LRUReplacer。
//注意replacer所有成员函数都要加锁。因为存在某个时刻，过程A调用Size(),过程B做一些数据的改动。

// 由于Replacer根据id查找page，因此使用map。但因为lru的特性，使用double-linked list比较方便，同时用hash table记录位置。

//其中 unordered_map使用bucket实现，而非tree，因此init时可以reserve

 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
40
41
42
43

Page *FetchPgImp(page_id)
//  从 buffer pool 维护的页表中根据page_id取出数据。如果freelist没有可用page，且其余页面均pinned，则返回null.

//先从page_table取出page，并且 pinned page。表示当前thread占用该page， replacer 移除该page,pin cnt++.因为存在之前page占用完后，page_table 留存page,且replacer重新收集了frame的情况。
// 找不到，就从freelist头部取frame，因为freelist中frame是初始未使用的情况，因此不需要dirty check，同时我们确保使用过的页面在返回freelist前已经flush过.(当然按照题目给的顺序，可以在取出frame后，统一做一个dirty check)
// 或者从replacer中使用Victim取出尾部空余frame（和pin的区别在于，pin 清除指定frame的replacer数据,victim是进行某种比如lru策略的尾部清除）
// 可能该frame处于dirty state,因此需要写回。并从page_table去除原有的该frame原存储的page_id.
//最终，对该frame位置的page进行初始化，从disk读取page_id的数据到此处，并pinned page.



UnpinPgImp(page_id, is_dirty)
// 从 buffer pool unpin page,要根据dirty bit写回数据。

//放回replacer的操作。从page_table找到该frame，如果pin cnt>=1返回false，因为无法放回replacer.
//否则,pin cnt--,如果此时<=0,则可以返回replacer.


FlushPgImp(page_id)
// 不管pin状态，直接写回磁盘。

// 当page_id有效时，在page_table查找对应frame，然后判断pages数据脏位写回，重置dirty bit.

NewPgImp(page_id)
// 在buffer pool 创建新页。
//简而言之，若所有页都pinned page，则返回Nullptr

//因此我们先从freelist和replacer取出,其中replacer如果dirty则写回。
//拿到新位置frame后，分配page即获得new page id.这时对frame位置上的page数据重置，
// 然后加入page table并返回。


DeletePgImp(page_id)
//从 buffer pool 删除 page。

//调用deallocate后，如果page table不存在，则自然true.
//如果存在，如果pin cnt >0表明有别的thread在占用，表明delete未成功，返回False.
//如果脏，则写回。并对该位置frame初始化，并加入freelist.为确保加入freelist，需要page table清理和调用replacer pin().

FlushAllPagesImpl()
//刷新所有 page。

//将page_table中所有page flushPg.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 多数函数都如此函数一样处理
Page *ParallelBufferPoolManager::FetchPgImp(page_id_t page_id) {
  // Fetch page for page_id from responsible BufferPoolManagerInstance
  return GetBufferPoolManager(page_id)->FetchPage(page_id);
}

Page *ParallelBufferPoolManager::NewPgImp(page_id_t *page_id)
//new page我们需要通过rr 选择下一个instance来处理。原理是通过AllocatePage中调用ValidatePageId，
//来促使不符合modulo分发的退出new page的处理。这也表明第二阶段中new page需要首先调用 allocatpage
//来进行 modulo的检查。
//
//当某个page返回非空时，就可以返回了。注意要维护next_instance_index的数值。