MIT 6.S081 - Lab Lock - Buffer cache (1) 分析原始设计

Cache 结构

CPU - Disk 中的缓存,使用 DRAM 的一部分作为其物理载体。

阅读 kernel/bio.c 发现,该缓存的工作方式是只缓存读,而没有缓存写。

即上层文件系统调用 bread(),内部调用 bget() 并检查 valid,如果为 0 即未命中,然后去磁盘读取 virtio_disk_rw(b, 0);上层文件系统调用 bwrite(),内部(几乎是直接)直接调用 virtio_disk_rw(b, 1)

之前学过的 CPU - DRAM 的 Cache 是缓存读也缓存写的。

Cache 数据结构以及使用

赏析一下这个双向循环链表的设计。

学过的数据结构的知识狠狠的用上!难得有如此实际的场景,我们就来一部分一部分解读吧。

kernel/bio.c:binit()

首先是一个熟悉的双向循环链表的头节点初始化。

// init
(bcache.head).prev = &bcache.head;
(bcache.head).next = &bcache.head;

双向循环链表的头节点初始化

之后进行了把数组的元素全部插入链表上的操作,插入的方法是头插法。

for (b = bcache.buf; b < bcache.buf + NBUF; b++)
{
  // add b between bcache.head and bcache.head.next
  b->next = (bcache.head).next;
  b->prev = &bcache.head;
  initsleeplock(&b->lock, "buffer");
  (bcache.head.next)->prev = b;
  (bcache.head).next = b;
}

一共需要修改四处(最后修改 (bcache.head).next,不然链表后面的元素就失踪了)。

双向循环链表的头节点初始化

kernel/bio.c:bget()

在数据结构方面,我们需要注意的地方就是 for 循环的开头的部分:

// Is the block already cached?
// from bcache.head.next to bcache.head
for (b = (bcache.head).next; b != &bcache.head; b = b->next)
// Not cached.
// **Recycle** the least recently used (LRU) unused buffer.
// diff from the former
for (b = (bcache.head).prev; b != &bcache.head; b = b->prev)

前一个是从 (bcache.head).next 开始(也就是 most recent used 端),到 bcache.head 结束,用 b = b->next 转移到下一个元素;

后一个是从 (bcache.head).prev 开始(也就是 least recently used 端),到 bcache.head 结束,用 b = b->prev 转移到上一个元素。

kernel/bio.c:brelse()

if (b->refcnt == 0)
{
   // no one is waiting for it.
   // remove b between b->next and b->prev
   (b->next)->prev = b->prev;
   (b->prev)->next = b->next;
   // deal with b itself
   // add b between bcache.head and bcache.head.next
   b->next = (bcache.head).next;
   b->prev = &bcache.head;
   (bcache.head.next)->prev = b;
   (bcache.head).next = b;
}

refcnt = 0 的缓存块,我们先将其从表中取出,然后移动到 head.next 处(most recent used 端)。

头插之前画过了,那画个取出 buf b 的图好了。

取出bufb

为什么要用链表

原本的设计用的是双向循环链表。我们知道各种链表比较下,双向循环链表的查找性能,或者说实现 LRU 算法的性能最好。

其实还有个问题:为什么要用链表呢?就单纯使用数组不行吗?不也可以实现 LRU 算法吗?——比如在 bget 查找 LRU 的时候,只要访问数组的开头或者末尾就可以了。

好吧不卖关子了。问题其实并不出在 bget 上——你只比较 bget 的话其实两者区别不大,因为查找性能都很优秀。实际的问题出在 brelse 上。

上层文件系统调用 brelse 释放了不用的缓存块,这个时候先把 refcnt - 1,然后检查 refcnt,如果为 0,那么就是不再访问的缓存块。将其从表中取出并移动到 head.next (most recent used 端)处。

整个 NBUF 长度的链表就是被 brelse 这个行为驱动起来的。我们也可以发现 kernel/fs.c(也就是上层文件系统)频繁的调用它,那么你可以想象这个链表就在很快的变动着。

每当一个内核线程使用完一个缓存块后,应该对那个缓存块调用 brelse。

我们想一下 “从表中取出,移动到 most recent used 端” 的这个操作,也就是对表的插入和删除操作。很明显数组(或者说顺序表)在这方面的性能是不如链表的。

关于优化

只有一把自旋锁 bcache.lock 用于保护整个 bcache,这么粗粒度的处理是不好的。需要减小锁粒度。

指导书给出了两种优化方案:(可以两个方案一起使用,也可以单独分开用)

  • 使用 哈希表 ,将各块块号 blockno 的某种散列值作为 key 对块进行分组,并为每个哈希桶分配一个专用的锁。通过哈希桶来代替链表,当要获取和释放缓存块时,只需要对某个哈希桶进行加锁,桶之间的操作就可以并行进行,提供并行性能。
  • 移除空闲缓存块列表(bcache.head)。使用 时间戳 作为判断缓存块最一次被访问的顺序的依据。

之后的文章将会去实现这两个优化方案。

最后修改:2022 年 11 月 13 日
如果觉得我的文章对你有用,请随意赞赏