posts/s081-lab8-locks/

[utterances-bot]

[mit6.s081] 笔记 Lab8: Locks | 锁优化 | Miigon's blog

这是我自学 MIT6.S081 操作系统课程的 lab 代码笔记第八篇：Locks。此 lab 大致耗时：14小时。 课程地址：https://pdos.csail.mit.edu/6.S081/2020/schedule.html Lab 地址：https://pdos.csail.mit.edu/6.S081/2020/labs/lock.html 我的代码地址：https://github.com/Miigon/my-xv6-labs-2020/tree/lock Commits: https://github.com/Miigon/my-xv6-labs-2020/commits/lock 本文中代码

https://blog.miigon.net/posts/s081-lab8-locks/

[sprayerH]

这里freelist部分 kalloc 如果当前cpu空闲链表空了，持有本cpu锁去其它cpu偷（申请其它cpu的锁）
是存在死锁的可能性的，cpu A和B互相都想偷对面的页。
一种方式是释放自己的锁再去偷页，把偷的页头指针保存起来，再申请本cpu的锁来更新空闲链表

[Miigon]

@sprayerH 感谢指正！ 释放自己的锁可能会导致短时间内多个kalloc为同一个cpu重复偷页（因为没拿任何锁的时候，cpu是可中断的，可能被调度其他进程）。当然这个设计是比较简单，真实发生的话影响也不是特别大，确实可能是比较合适的折中。

[sprayerH]

偷过来页记录在候补空闲链表指针上，所以kalloc放弃自己的锁去偷页前需要查看是否已经偷过了（候补空闲链表指针不为0）当然这里的查看需要用锁保护
这样就不存在重复偷页问题了

[Miigon]

@sprayerH 如果为每一个核心都设置一个候补链，确实这样是可行的。不过这样的设计，由于查看和修改候补链本身要求原子，也就是要加锁。其实不需判断候选链是否已经偷过了，直接给每个核心设置一个stealing锁就行了，steal之前先拿steal锁再放弃自己的freelist锁。steal完成后先拿回自己的freelist锁，再放弃steal锁：

acquire(&kmem[cpu].lock)
if no free page left:
    acquire(&kmem[cpu].stealing_lock)
    release(&kmem[cpu].lock)

    // ... steal free pages from other cpus.

    acquire(&kmem[cpu].lock)
    release(&kmem[cpu].stealing_lock)
    
    // put newly stolen free pages into this cpu's freelist

这里虽然看起来好像可能出现lock和stealing_lock的环路等待导致死锁，但是（在xv6的当前设计下）一个进程只要还拿着至少一个锁，就不会被从当前cpu上调度走，而stealing_lock又是该cpu独享的。所以实际上只要某个stealing_lock被一个进程拿着，就不会有第二个进程能够去尝试拿这个stealing_lock，从而不会出现环路。

其实这个和你提到的方案是一样的，只是指出一点不需要去检查候补表来判断是否已经偷过了，只需「拿着这个额外的锁」这件事情本身就足够了。这个锁甚至不会出现任何竞争和等待，唯一的目的其实是关闭当前核心的硬件中断（当然直接push_off也可以）。

再者，另一个纰漏是通过检查候选链实际上也不能保证不会出现重复偷页。可能存在一个进程即将开始偷，但还一个页都没偷到的时候，另一个进程检查了一下候选链发现是空的，也开始偷。这样就还是出现了重复的偷页。如果把“检查候选链”变成“检查一个‘正在偷页’的标记”的话，那这个标记也需要加锁保护，而且这个锁还必须在放弃自身freelist锁之前拿。那这么做，其实就是上面的方案了，标记检查其实也可以干脆去掉，理由已经说过了。

这个问题其实也是为了解决环路死锁，在操作前放弃掉自身的锁。然后又为了防止放弃自身锁之后导致重复操作，添加了额外的锁，所出现的自身锁和额外的锁两个锁交接的问题。这个具体场景里面的特殊之处在于只要拿着这个额外的锁，重复操作和死锁问题就自动消失了，因为stealing_lock和lock都是和cpu绑定的，只要拿着这个额外的锁，线程直接就不会被从这个cpu调度走了，从根本上消除了死锁的可能性。

而且这个问题的另一个特殊之处在于重复操作其实也是可接受的，并不会出现灾难性的后果。

blog中后面一题bcache里遇到的问题也是类似的问题：拿着自己的锁去从别的桶拿buffer（需要拿别人的锁）的话，会造成环路等待。但是放弃自己的锁的话，又可能出现重复请求。

不同之处是bcache的场景下重复请求是灾难性的，会导致一个块有两个cache，造成数据不一致。而且这里的锁不是和cpu绑定的，前面单纯多拿一个锁的方法是无法解决问题的。

blog中我选择的解决方案是用一个全局eviction_lock使得驱逐过程只能单线程，然后自己桶的锁和eviction_lock的锁交接部分是用先放弃，再拿取，拿取eviction_lock后再次检查是否满足驱逐条件的方式防止两锁交接中途被见缝插针。有兴趣可以略读一下后面的总结😃

[sprayerH]

谢谢你的回复。对于这种需要互相持有对方锁得场景我页不清楚怎么解决。一般来说死锁避免有两种方式，一种是按顺序加锁（这种适合内核，对于很多场景 顺序并不好定义）。还有一种是用大锁。 我觉的你这里的思路很巧妙，额外定义了一个大锁，同时又使用了一个固定的加锁顺序。代价是在取得驱逐锁后需要再次检查是否满足驱逐条件。
不知道这种场景是否有一个通用的解决方案。

[ttzytt]

大佬，想问下是否可以把 eviction_lock 改成每个桶各一个来减少锁的粒度并且提升性能呢。或者说把 eviction_lock 从保护整个哈希表的结构改成保护单个桶的结构。

因为不加 eviction_lock 时，会造成同一个块有两个缓存只会发生在下面这种情况：

从进程 a 放弃了自己的锁，然后开始找可驱逐的缓存，到进程 a 找到了可驱逐的缓存，然后尝试拿回自己的桶锁。这段时间进程 b 拿到了锁，b 又进入了找可驱逐缓存的状态。

那这里的前提是两个进程的 bget() 尝试取得的缓存都是同一个 blockno 的。或者说我们只要保证了同一个桶在一个时刻只有一个进程在进行驱逐和添加操作，就不会有冲突。不一定是整个哈希表在某一时刻只能有一个进程进行驱逐操作。

[ttzytt]

或者是否可以在找到可驱逐的缓存，并且拿到自己的桶锁后，再检察一遍自己的桶里是否已经有了对应 blockno 的缓存。

找到可驱逐的缓存并没有真正的改变自己桶的结构。拿到自己桶锁后再进行添加缓存的操作确保了对于某个桶，任何一个时刻只有一个线程在进行驱逐后的添加操作。

那么拿到桶锁后再检查一遍相应的缓存是否已经添加了，应该能确保不会重复添加缓存吧。

PS：刚刚这些其实我都不太确定，所以问下，说错了大佬别喷我。

[Miigon]

@ttzytt

那这里的前提是两个进程的 bget() 尝试取得的缓存都是同一个 blockno 的。或者说我们只要保证了同一个桶在一个时刻只有一个进程在进行驱逐和添加操作，就不会有冲突。不一定是整个哈希表在某一时刻只能有一个进程进行驱逐操作。

good point. 确实，为两个不同的桶查找可驱逐块的过程是可并行互不干扰的，eviction_lock的最终目的只是为了保证同一个桶同时只能有一个进程在为其寻找新空闲块（并添加到其中）。所以将eviction_lock拆分为每个桶各自独立拥有一个的方法是可行并且应该是有正向效果的。

我会确保在下一次这篇博文更新的时候提及这一点，最近在重新思考这一个实验，可能会有补充或更新。

仔细一想，还是不行。eviction_lock原本的作用是，当拿着eviction_lock的时候，所有桶的链表结构都不会改变（即不会增加或减少节点，其实最终是隐含了一个可以安全遍历的意思）。

而驱逐过程是包含两步的：从源桶里移除，再加入到新桶。这两步都会修改桶的链表结构，共有两个桶被修改，前者修改源桶（空闲buf所属桶），后者修改目标桶（blockno所属桶）。假设只拿目标桶的eviction_lock[key]，并不能保证从源桶移除空闲块的过程是安全的。可能出现：A桶从别的桶偷了一个块并在尝试将其加入A桶的同时，B桶也正尝试从A桶里移出一个空闲块（记住我们为了防止环路，A桶偷别人的块的时候是不拿着自己的桶锁的，所以B桶可以这么做），导致两个进程同时修改A桶的链表结构。

那如果B桶尝试从A桶里移出空闲块的时候，不仅去拿A的桶锁，还尝试去拿A桶的驱逐锁呢？也不行，因为这么做，如果出现A偷B，B偷A的话，就会导致A、B的驱逐锁形成一对死锁（实际上就和一开始桶锁的方案一模一样了，就是多叠了一层锁而已，又回到了原来的问题）。

实际上，eviction_lock在这里解决死锁问题的原理，就在于驱逐过程如果采用桶级粒度的锁（就好像我们一开始尝试做的）是行不通的，几乎一定会造成环路等待，所以引入eviction_lock，将锁的粒度从查询blockno是否存在时的桶级锁，退化为更安全的全局锁（虽然更低效），eviction_lock的作用就是降低驱逐过程锁的粒度来交换安全性。尝试在这个方案之上将eviction_lock细化就等同于直接将eviction_lock删除了。

EDIT: 在bcachetest的例子中，整个测试过程eviction_lock只尝试自旋了83次（体现了较低的访问频次和竞争程度），而同时bufmap_locks各个桶锁尝试自旋次数每个都达到上千，最少2000+最多6000+，这里即使对eviction_lock的拆解可行，能得到的性能提升也大概率不值得额外的工程复杂度。

[ttzytt]

@Miigon 感谢回复，我觉得根据 bcachetest 的数据，确实可以发现 cache miss 的概率较低，然后 eviction_lock 的竞争程度低，所以没有修改的必要。但还是对你举的例子有些疑问：

A桶从别的桶偷了一个块并在尝试将其加入A桶的同时，B桶也正尝试从A桶里移出一个空闲块（记住我们为了防止环路，A桶偷别人的块的时候是不拿着自己的桶锁的，所以B桶可以这么做），导致两个进程同时修改A桶的链表结构。

我记得你代码里的偷（及把空闲缓存从桶中删除）和添加是分开的，添加时会取回桶锁，如下。我们为了防止环路死锁只是在找空闲缓存的过程中释放桶锁，找到空闲缓存后，会一直拿着源桶（空闲 buf 桶）的锁，直到这个空闲 buf 被真正的删除。

随后，会拿到自己的桶锁，然后把偷来的缓存添加到链表中。也就是说”偷“和”放“这两个环节都是原子的，虽然这两个操作会改变不同桶的链表结构，但是我们在操作前都会拿到保护桶结构和 ref_cnt 的桶锁。

……
  struct buf *before_least = 0; 
  uint holding_bucket = -1;
  for(int i = 0; i < NBUFMAP_BUCKET; i++){
    acquire(&bcache.bufmap_locks[i]);
    int newfound = 0;
    for(b = &bcache.bufmap[i]; b->next; b = b->next) {
      if(b->next->refcnt == 0 && (!before_least || b->next->lastuse < before_least->next->lastuse)) {
        before_least = b;
        newfound = 1;
      }
    }
    if(!newfound) {
      release(&bcache.bufmap_locks[i]);
    } else {
      if(holding_bucket != -1) release(&bcache.bufmap_locks[holding_bucket]);
      holding_bucket = i;
    }
  }
  if(!before_least) {
    panic("bget: no buffers");
  }
  b = before_least->next;
  
  if(holding_bucket != key) {
    before_least->next = b->next; // 从源桶删除也是拿到锁了
    release(&bcache.bufmap_locks[holding_bucket]); 
    //-----------------删除和添加的分界线------------------------
    acquire(&bcache.bufmap_locks[key]);  // 这里添加给新桶是拿到锁了
    b->next = bcache.bufmap[key].next;
    bcache.bufmap[key].next = b;
  }
  b->dev = dev;
  b->blockno = blockno;
  b->refcnt = 1;  // 这里把 refcnt 设置上了，所以 a 释放锁之后 b 也不能偷（按照前面的例子）
  b->valid = 0;
  release(&bcache.bufmap_locks[key]);
  release(&bcache.eviction_lock);
  acquiresleep(&b->lock);
  return b;
……

所以应该不太会有”A桶从别的桶偷了一个块并在尝试将其加入A桶的同时，B桶也正尝试从A桶里移出一个空闲块“，即两个进程同时操作一个桶的情况出现。

出现冲突应该是在发现桶内没有需要的缓存，然后释放桶锁准备偷缓存后，找到可偷的缓存，然后拿回锁准备添加前。

在这段时间内，可能有另一个进程调用 bget()，并且 blockno 还相同。这个时候会发现桶内没这个缓存，开始进入偷缓存的过程。

那么在没有任何保护的时候，会造成同一 blockno 的缓存被添加两次。

那假设有 C, D 两个进程就刚好同时调用了同一 blockno 的 bget()，它们在实际把找到的缓存添加到桶之前，都需要取得桶锁。所以对于把偷来的缓存实际添加，是有一个先后顺序的。比如在 C 完成找空闲缓存之前，D 已经添加了这个空闲缓存。又或者 D 先拿到了桶锁，C 就只能等。

假如我们在添加这一步之前，拿到自身桶锁之后，再检查一遍桶中是否有 blockno 的缓存，如果有的话，就把偷来的缓存加到自己这里，但是设置 refcnt 和 blockno 为 0 （不加到源桶是因为又要同时持有两把锁）然后返回找到的对应 blockno 的缓存，是否能避免冲突问题？

对于前面的那个 C 和 D 的例子，C 在找到空闲缓存，然后拿到自己的桶锁之后，就可以再检查一遍自己的缓存，然后可以发现已经有 blockno 的对应缓存了。

当然这个方法有一个问题，就是在缓存资源比较紧张的时候，可能会有多个进程为了一个 blockno 重复的偷缓存，进而造成 panic（实际上这很多个进程中会有一个偷到缓存，但是另外几个发现偷不到后就 panic 了，所以要改变 panic 的位置）。

我想到的伪代码大概是下面这样的（没改 panic 的位置）：

……
  if(!before_least) {
    panic("bget: no buffers");
  }
  b = before_least->next;
  
  if(holding_bucket != key) {
    before_least->next = b->next; // 从源桶删除也是拿到锁了
    release(&bcache.bufmap_locks[holding_bucket]); 
    //-----------------删除和添加的分界线------------------------
    acquire(&bcache.bufmap_locks[key]);  // 这里添加给新桶是拿到锁了
    
    检查一遍 bcache.bufmap[key] 中是否已经有 blockno 的缓存;
    if (已经被同一时刻的其他进程添加){
      b->next = bcache.bufmap[key].next; 
      bcache.bufmap[key].next = b;
      b->dev = dev;
      b->blockno = 0;  // 0 应该可以表示空闲吧
      b->refcnt = 0;  
      b->valid = 0;  
      release(&bcache.bufmap_locks[key]);
      acquiresleep(&对应blockno的缓存->lock);
      return 对应blockno的缓存;
    } 
    b->next = bcache.bufmap[key].next; 
    bcache.bufmap[key].next = b;
  }
  b->dev = dev;
  b->blockno = blockno;
  b->refcnt = 1;  // 这里把 refcnt 设置上了，所以 a 释放锁之后 b 也不能偷（按照前面的例子）
  b->valid = 0;
  release(&bcache.bufmap_locks[key]);
  acquiresleep(&b->lock);
  return b;
……

我自己思考的时候还是感觉这个方案没有什么逻辑问题的，但是感觉还是要跑过测试后才能确定。而课程提供的 bcachetest 又没有足够的强度（毕竟没有任何保护的时候还是测不出来），所以还请大佬帮忙看下问题，谢谢。

[Miigon]

@ttzytt

所以应该不太会有”A桶从别的桶偷了一个块并在尝试将其加入A桶的同时，B桶也正尝试从A桶里移出一个空闲块“，即两个进程同时操作一个桶的情况出现。

这一点你是对的。从源桶里面偷取和插入到目标桶里面是两步，并且的确各自都是原子的。eviction_lock只需保护「同一个桶内」不同时进行两个并行偷buf即可，本质是保护同一个blockno不被并行重复偷buf分配。

我自己也快一年没看这个代码了，一些小细节忽略了，现在可能你比我还熟悉我的代码 🤣

后面的部分，我假设你是在尝试完全去除eviction_lock并将重复检查后移到移除之后添加之前？blockno=0并不能表示空闲，0号盘块是存在的，这么做会和0号盘块实际的buf互相干扰。可以给buf加一个trash标记表示该buf的dev和blockno是否有效，偷buf后若发现blockno重复，则将偷来的buf设置为buf->trash = 1再插入目标桶。

我在原来的代码基础上尝试实现了这个机制：
Miigon/my-xv6-labs-2020@0c7a387

这样一来确实节约了驱逐锁的使用，允许同个桶内多个blockno同时进行缺buf驱逐。原本检查是否重复分配的开销依然存在，而重复偷buf的开销变大（不仅多了一个插入开销，还无辜驱逐了一个其他桶的buf）。复杂度稍微上升（因为每个桶中都多了trash buffers需要考虑）。

这个相比每个桶分配一个专有eviction_lock的方案，如果是我个人的话可能并不会选，因为一般bget()之后是紧跟着磁盘读取的，而磁盘读取的时间比bget()的耗时要高很多个数量级，大多数时间是花在disk io上，而两个bget()同时同刻进行缺buffer驱逐的概率极小（即使是所有桶一起看）。获取一个自旋锁的开销本身也很小，只要没有竞争。相比之下，稍微增加的设计复杂度和（极稀有状态下）误杀导致的重读开销，可能并不划算，不过能想到这一个方案还是很厉害的，good thinking！

附：每个桶分配一个专有eviction_lock的方案，跑完usertests之后bcachetest打印出来的各个锁统计数据，eviction锁上的竞争几乎微不足道，大多数都是0次。

$ usertests
........
ALL TESTS PASSED
$ bcachetest 
start test0
test0 results:
--- lock kmem/bcache stats
lock: kmem_cpu_0: #fetch-and-add 0 #acquire() 595339
lock: kmem_cpu_1: #fetch-and-add 0 #acquire() 502079
lock: kmem_cpu_2: #fetch-and-add 0 #acquire() 868507
lock: kmem_cpu_3: #fetch-and-add 0 #acquire() 68
lock: kmem_cpu_4: #fetch-and-add 0 #acquire() 68
lock: kmem_cpu_5: #fetch-and-add 0 #acquire() 68
lock: kmem_cpu_6: #fetch-and-add 0 #acquire() 68
lock: kmem_cpu_7: #fetch-and-add 0 #acquire() 68
lock: bcache_eviction: #fetch-and-add 0 #acquire() 1256
lock: bcache_bufmap: #fetch-and-add 5178 #acquire() 343675
lock: bcache_eviction: #fetch-and-add 5054 #acquire() 1607
lock: bcache_bufmap: #fetch-and-add 4317 #acquire() 360909
lock: bcache_eviction: #fetch-and-add 0 #acquire() 1196
lock: bcache_bufmap: #fetch-and-add 1321 #acquire() 317239
lock: bcache_eviction: #fetch-and-add 0 #acquire() 1434
lock: bcache_bufmap: #fetch-and-add 7877 #acquire() 921666
lock: bcache_eviction: #fetch-and-add 0 #acquire() 1110
lock: bcache_bufmap: #fetch-and-add 915 #acquire() 281689
lock: bcache_eviction: #fetch-and-add 149 #acquire() 797
lock: bcache_bufmap: #fetch-and-add 384 #acquire() 69539
lock: bcache_eviction: #fetch-and-add 0 #acquire() 601
lock: bcache_bufmap: #fetch-and-add 0 #acquire() 31061
lock: bcache_eviction: #fetch-and-add 0 #acquire() 533
lock: bcache_bufmap: #fetch-and-add 0 #acquire() 28001
lock: bcache_eviction: #fetch-and-add 0 #acquire() 439
lock: bcache_bufmap: #fetch-and-add 0 #acquire() 25345
lock: bcache_eviction: #fetch-and-add 110 #acquire() 401
lock: bcache_bufmap: #fetch-and-add 0 #acquire() 22702
lock: bcache_eviction: #fetch-and-add 0 #acquire() 518
lock: bcache_bufmap: #fetch-and-add 0 #acquire() 447458
lock: bcache_eviction: #fetch-and-add 0 #acquire() 410
lock: bcache_bufmap: #fetch-and-add 4 #acquire() 377628
lock: bcache_eviction: #fetch-and-add 0 #acquire() 363
lock: bcache_bufmap: #fetch-and-add 14 #acquire() 358883
--- top 5 contended locks:
lock: proc: #fetch-and-add 68188600 #acquire() 6959269
lock: proc: #fetch-and-add 31305099 #acquire() 6959480
lock: virtio_disk: #fetch-and-add 30292226 #acquire() 120035
lock: proc: #fetch-and-add 28603745 #acquire() 6962986
lock: proc: #fetch-and-add 17425432 #acquire() 6954259
tot= 25323
test0: OK
start test1
test1 OK
$ 

[ttzytt]

@Miigon 哈哈谢谢大佬看我那个评论，不用 eviction_lock 那个方案确实大大增加了复杂度，而且可能造成过多的缓存块无缘无的被驱逐，然后加入到一个桶中（当然，小概率事件） 我个人也觉得加入 eviction_lock 的方案比较好，主要是易于理解而且实现相对简单。

另外感谢博主的这些文章，对我做 xv6 的实验有很大的帮助，既可以在遇到困难的时候帮助定位问题，也可以做完了之后学习新的思路。