cmu15445源码解析2

发表于 | 分类于 | 次

Bustub重点解析

buffer pool manger

Lru-k-replacer

RecordAccess

一、核心设计思想

  1. 两阶段存储
1
2
lru_premature_  // 存储访问次数 < k 的帧
lru_mature_     // 存储访问次数 >= k 的帧
  1. 状态转换
1
2
3
4
访问次数 < k-1  →  premature（未成熟）
访问次数 = k-1  →  即将转换
访问次数 = k    →  mature（成熟）  
访问次数 > k    →  mature（成熟）
  1. 先删后改再插
1
旧状态 → 从集合移除 → 修改访问记录 → 插入到新集合

二、代码执行流程图

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
开始 RecordAccess(frame_id)
    ↓
获取锁
    ↓
帧记录是否存在？
    ├─ 否 → 分配新记录
    └─ 是 → 继续
    ↓
获取当前状态（快照）
├─ is_premature = AccessSize() < k
└─ is_evictable = IsEvictable()
    ↓
    ├─ 情况1：可驱逐 + 未成熟 + (访问次数 == k-1)
    │   └─ 从 premature 集合移除
    │
    └─ 情况2：可驱逐 + 成熟
        └─ 从 mature 集合移除
    ↓
更新访问：Access(CurrTime())
    ↓
    ├─ 情况3：可驱逐 + 未成熟 + (访问次数 == k)
    │   └─ 插入到 mature 集合（转换）
    │
    └─ 情况4：可驱逐 + 成熟
        └─ 插入到 mature 集合（更新位置）
    ↓
结束

SetEvictable

场景A：不可驱逐 → 可驱逐（开始保护 → 允许驱逐）

1
2
3
4
5
6
7
8
9
if (set_evictable && !frames_[frame_id]->IsEvictable()) {
  // transit from not evictable to evictable
  replacer_size_++;
  if (is_premature) {
    lru_premature_.insert(frames_[frame_id]);
  } else {
    lru_mature_.insert(frames_[frame_id]);
  }
}

条件分解：

  1. set_evictable == true：目标状态是可驱逐
  2. !frames_[frame_id]->IsEvictable()：当前状态是不可驱逐

执行流程：

1
2
3
4
5
6
7
8
当前状态：不可驱逐（不在任何集合中）
目标状态：可驱逐（需要插入到集合）
   ↓
replacer_size_++  // 增加可驱逐帧计数
   ↓
根据is_premature插入到对应集合
├─ true  → lru_premature_.insert()
└─ false → lru_mature_.insert()

示例：

1
2
3
4
5
6
7
8
9
// 初始：帧被钉住（正在使用）
replacer.SetEvictable(5, false);

// 访问记录：访问次数达到mature
replacer.RecordAccess(5);  // count=2, mature

// 现在允许驱逐
replacer.SetEvictable(5, true);
// → 插入到 lru_mature_（因为访问次数≥k）

场景B：可驱逐 → 不可驱逐（允许驱逐 → 开始保护）

1
2
3
4
5
6
7
8
9
if (!set_evictable && frames_[frame_id]->IsEvictable()) {
  // transit from evictable to non evictable
  replacer_size_--;
  if (is_premature) {
    lru_premature_.erase(frames_[frame_id]);
  } else {
    lru_mature_.erase(frames_[frame_id]);
  }
}

条件分解：

  1. !set_evictable == true：目标状态是不可驱逐
  2. frames_[frame_id]->IsEvictable()：当前状态是可驱逐

执行流程：

1
2
3
4
5
6
7
8
当前状态：可驱逐（在某个集合中）
目标状态：不可驱逐（需要从集合中移除）
   ↓
replacer_size_--  // 减少可驱逐帧计数
   ↓
根据is_premature从对应集合移除
├─ true  → lru_premature_.erase()
└─ false → lru_mature_.erase()

示例：

1
2
3
4
5
6
// 初始：帧可以被驱逐
replacer.SetEvictable(5, true);  // 插入到集合

// 帧正在被使用，需要保护
replacer.SetEvictable(5, false);
// → 从集合中移除，不会被Evict()选中

完整状态转换图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
┌─────────────────────────────────────────────────────────────┐
│                    帧状态转换图                             │
├─────────────────────────────────────────────────────────────┤
│                                                             │
│   ┌──────────────────┐         ┌──────────────────┐       │
│   │   不可驱逐状态    │         │   可驱逐状态     │       │
│   │ (Not Evictable)  │ ──────> │ (Evictable)     │       │
│   │                  │ 允许驱逐 │                 │       │
│   │ 不在任何集合中   │ <────── │ 在premature或   │       │
│   │                  │ 开始保护 │ mature集合中    │       │
│   └──────────────────┘         └──────────────────┘       │
│           │                            │                   │
│           │                            │                   │
│           ▼                            ▼                   │
│   ┌──────────────────┐         ┌──────────────────┐       │
│   │  RecordAccess()  │         │  RecordAccess()  │       │
│   │  更新访问次数    │         │  更新访问次数和   │       │
│   │  但不改变集合    │         │  集合中位置      │       │
│   └──────────────────┘         └──────────────────┘       │
│                                                             │
└─────────────────────────────────────────────────────────────┘

Evict

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
开始 Evict(frame_id*)
    ↓
加锁（获取互斥锁）
    ↓
检查两个LRU集合
    ↓
    ├─ 都为空 → return false（无帧可驱逐）
    └─ 至少一个非空
        ↓
    检查 premature 集合
        ↓
        ├─ 非空 → has_premature = true
        └─ 为空 → has_premature = false
        ↓
    选择淘汰目标
        ↓
        ├─ has_premature = true
        │   └─ first_iter = lru_premature_.begin()
        │       （访问次数最少的帧）
        │
        └─ has_premature = false
            └─ first_iter = lru_mature_.begin()
                （第K次访问最早的帧）
        ↓
    获取帧ID
        *frame_id = (*first_iter)->GetFrameId()
        ↓
    删除帧记录
        DeallocateFrameRecord(first_iter, has_premature)
        ↓
    return true（成功淘汰）