posts/s081-lab8-locks/ #18
Replies: 12 comments 9 replies
-
这里freelist部分 kalloc 如果当前cpu空闲链表空了,持有本cpu锁去其它cpu偷(申请其它cpu的锁) |
Beta Was this translation helpful? Give feedback.
-
@sprayerH 感谢指正! 释放自己的锁可能会导致短时间内多个kalloc为同一个cpu重复偷页(因为没拿任何锁的时候,cpu是可中断的,可能被调度其他进程)。当然这个设计是比较简单,真实发生的话影响也不是特别大,确实可能是比较合适的折中。 |
Beta Was this translation helpful? Give feedback.
-
偷过来页记录在候补空闲链表指针上,所以kalloc放弃自己的锁去偷页前需要查看是否已经偷过了(候补空闲链表指针不为0)当然这里的查看需要用锁保护 |
Beta Was this translation helpful? Give feedback.
-
@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后再次检查是否满足驱逐条件的方式防止两锁交接中途被见缝插针。有兴趣可以略读一下后面的总结😃 |
Beta Was this translation helpful? Give feedback.
-
谢谢你的回复。对于这种需要互相持有对方锁得场景我页不清楚怎么解决。一般来说死锁避免有两种方式,一种是按顺序加锁(这种适合内核,对于很多场景 顺序并不好定义)。还有一种是用大锁。 我觉的你这里的思路很巧妙,额外定义了一个大锁,同时又使用了一个固定的加锁顺序。代价是在取得驱逐锁后需要再次检查是否满足驱逐条件。 |
Beta Was this translation helpful? Give feedback.
-
大佬,想问下是否可以把 eviction_lock 改成每个桶各一个来减少锁的粒度并且提升性能呢。或者说把 eviction_lock 从保护整个哈希表的结构改成保护单个桶的结构。 因为不加 eviction_lock 时,会造成同一个块有两个缓存只会发生在下面这种情况: 从进程 a 放弃了自己的锁,然后开始找可驱逐的缓存,到进程 a 找到了可驱逐的缓存,然后尝试拿回自己的桶锁。这段时间进程 b 拿到了锁,b 又进入了找可驱逐缓存的状态。 那这里的前提是两个进程的 |
Beta Was this translation helpful? Give feedback.
-
或者是否可以在找到可驱逐的缓存,并且拿到自己的桶锁后,再检察一遍自己的桶里是否已经有了对应 blockno 的缓存。 找到可驱逐的缓存并没有真正的改变自己桶的结构。拿到自己桶锁后再进行添加缓存的操作确保了对于某个桶,任何一个时刻只有一个线程在进行驱逐后的添加操作。 那么拿到桶锁后再检查一遍相应的缓存是否已经添加了,应该能确保不会重复添加缓存吧。 PS:刚刚这些其实我都不太确定,所以问下,说错了大佬别喷我。 |
Beta Was this translation helpful? Give feedback.
-
仔细一想,还是不行。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的拆解可行,能得到的性能提升也大概率不值得额外的工程复杂度。 |
Beta Was this translation helpful? Give feedback.
-
@Miigon 感谢回复,我觉得根据 bcachetest 的数据,确实可以发现 cache miss 的概率较低,然后 eviction_lock 的竞争程度低,所以没有修改的必要。但还是对你举的例子有些疑问:
我记得你代码里的偷(及把空闲缓存从桶中删除)和添加是分开的,添加时会取回桶锁,如下。我们为了防止环路死锁只是在找空闲缓存的过程中释放桶锁,找到空闲缓存后,会一直拿着源桶(空闲 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桶里移出一个空闲块“,即两个进程同时操作一个桶的情况出现。 出现冲突应该是在发现桶内没有需要的缓存,然后释放桶锁准备偷缓存后,找到可偷的缓存,然后拿回锁准备添加前。 在这段时间内,可能有另一个进程调用 那么在没有任何保护的时候,会造成同一 blockno 的缓存被添加两次。 那假设有 C, D 两个进程就刚好同时调用了同一 blockno 的 假如我们在添加这一步之前,拿到自身桶锁之后,再检查一遍桶中是否有 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 又没有足够的强度(毕竟没有任何保护的时候还是测不出来),所以还请大佬帮忙看下问题,谢谢。 |
Beta Was this translation helpful? Give feedback.
-
这一点你是对的。从源桶里面偷取和插入到目标桶里面是两步,并且的确各自都是原子的。eviction_lock只需保护「同一个桶内」不同时进行两个并行偷buf即可,本质是保护同一个blockno不被并行重复偷buf分配。 我自己也快一年没看这个代码了,一些小细节忽略了,现在可能你比我还熟悉我的代码 🤣 后面的部分,我假设你是在尝试完全去除eviction_lock并将重复检查后移到移除之后添加之前?blockno=0并不能表示空闲,0号盘块是存在的,这么做会和0号盘块实际的buf互相干扰。可以给buf加一个trash标记表示该buf的dev和blockno是否有效,偷buf后若发现blockno重复,则将偷来的buf设置为 我在原来的代码基础上尝试实现了这个机制: 这样一来确实节约了驱逐锁的使用,允许同个桶内多个blockno同时进行缺buf驱逐。原本检查是否重复分配的开销依然存在,而重复偷buf的开销变大(不仅多了一个插入开销,还无辜驱逐了一个其他桶的buf)。复杂度稍微上升(因为每个桶中都多了trash buffers需要考虑)。 这个相比每个桶分配一个专有eviction_lock的方案,如果是我个人的话可能并不会选,因为一般bget()之后是紧跟着磁盘读取的,而磁盘读取的时间比bget()的耗时要高很多个数量级,大多数时间是花在disk io上,而两个bget()同时同刻进行缺buffer驱逐的概率极小(即使是所有桶一起看)。获取一个自旋锁的开销本身也很小,只要没有竞争。相比之下,稍微增加的设计复杂度和(极稀有状态下)误杀导致的重读开销,可能并不划算,不过能想到这一个方案还是很厉害的,good thinking! 附:每个桶分配一个专有eviction_lock的方案,跑完usertests之后bcachetest打印出来的各个锁统计数据,eviction锁上的竞争几乎微不足道,大多数都是0次。
|
Beta Was this translation helpful? Give feedback.
-
@Miigon 哈哈谢谢大佬看我那个评论,不用 eviction_lock 那个方案确实大大增加了复杂度,而且可能造成过多的缓存块无缘无的被驱逐,然后加入到一个桶中(当然,小概率事件) 我个人也觉得加入 eviction_lock 的方案比较好,主要是易于理解而且实现相对简单。 另外感谢博主的这些文章,对我做 xv6 的实验有很大的帮助,既可以在遇到困难的时候帮助定位问题,也可以做完了之后学习新的思路。 |
Beta Was this translation helpful? Give feedback.
-
一个应该不需要eviction_lock的思路(脑测好像没问题),方便表达直接改你源码:
|
Beta Was this translation helpful? Give feedback.
-
[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/
Beta Was this translation helpful? Give feedback.
All reactions