MIT 6.S081 Lab 8: Locks
6.S081课程的第八个Lab,为 xv6 的堆与buf缓冲区提供细粒度锁机制,减少 lock contention 以提高性能。
Memory allocator
在 xv6 原本设计中,内核用一个 freelist
负责堆资源的管理。试想多个进程频繁地增长收缩其地址空间,导致并发调用 kalloc
与 kfree
。由于 kmem.lock
保护 freelist
,同一时间只有一个执行流拥有这个锁,这会导致大量 acquire
中的循环在竞争这个锁。这也是所谓的 lock contention
现象。衡量 lock contention
的指标就是 acquire
中的循环迭代次数 loop iterations
。p.s. 因为是自旋锁。 kalloctest
程序在衡量 xv6 中 kmem/bcache
的锁争用。我们的任务在于将 kmem 与 bcache 中共享数据切割成更小的粒度,用细粒度的锁提高并发性。
在 Linux 系统中可以用 perf-lock
相关命令分析统计不同的锁行为,其中包括锁争用的统计。具体见perf-lock mannual
per-CPU freelists
设计上,可以将 freelist
分成每个 CPU 负责单独一个。在某个CPU上执行流只会向其负责的 freelist
申请与归还内存。
//kernel/kalloc.c
struct {
struct spinlock lock;
struct run *freelist;
char lockName[8];
} kmem[NCPU];
void
kinit()
{
int i;
for(i = 0; i < NCPU; ++i) {
snprintf(kmem[i].lockName, 8, "kmem_%d", i);
initlock(&kmem[i].lock, kmem[i].lockName);
}
freerange(end, (void*)PHYSTOP);
}
源文件 kernel/proc.c
中的函数 cpuid
可以返回当前的 CPU 核心编号。但需要小心,只有在 push_off()
与 pop_off()
关闭/开启中断的 scope 中,才能保证返回的 CPU ID 是不变的。否则,一个执行流在调用 cpuid
后,又被调度到其他 CPU 上执行,原来返回的 CPU 核心编号就是错的。
修改后的 kfree
函数如下。可以看到,使用 cpu_id
的代码必须关闭中断。
// Free the page of physical memory pointed at by v,
// which normally should have been returned by a
// call to kalloc(). (The exception is when
// initializing the allocator; see kinit above.)
void
kfree(void *pa)
{
struct run *r;
int cpu_id;
if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
panic("kfree");
// Fill with junk to catch dangling refs.
memset(pa, 1, PGSIZE);
r = (struct run*)pa;
// get current cpu id
push_off();
cpu_id = cpuid();
acquire(&kmem[cpu_id].lock);
r->next = kmem[cpu_id].freelist;
kmem[cpu_id].freelist = r;
release(&kmem[cpu_id].lock);
pop_off();
}
stealing
将原来唯一的资源切成小粒度时,有个问题需要注意,如果某个 CPU 的 freelist
被使用完,但仍有 kalloc
申请资源,其实仍有机会为其分配。因为其他的 freelist
可能仍有空闲页面。这时就需要实现从其他资源富裕的 freelist
窃取资源。 stealing
的思想是简单的,但是实现上需要注意死锁与资源泄漏的情况。
所有 freelist
的锁都是平级的。试想,如果 CPU A 的 freelist
用尽,在持有锁 A 的情况下,申请 CPU B 的锁,但 B 也有可能正在申请 A 的锁,造成循环等待,产生死锁。为了避免这个问题,就是在设计上,执行流不能在同时持有一个以上的平级的锁。
以下两个工具函数,steal_page
与 add2tail
。前者通过快慢指针,从其他freelist
夺取一半的空闲页面;后者将 content
添加到 head
指示的 freelist
的末尾。
static struct run*
steal_page(int cpu_id) {
struct run *slow, *fast, *ret;
int i;
for (i = 0; i < NCPU; ++i) {
if (cpu_id == i)
continue;
acquire(&kmem[i].lock);
if (kmem[i].freelist) {
slow = fast = kmem[i].freelist;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
ret = kmem[i].freelist;
kmem[i].freelist = slow->next;
slow->next = 0;
release(&kmem[i].lock);
return ret;
}
release(&kmem[i].lock);
}
return 0;
}
static void
add2tail(struct run* head, struct run* content) {
while (head->next)
head = head->next;
head->next = content;
}
修改的 kalloc
代码看上去很冗余,但是必要的。比如在调用 steal_page
后,又再次检查当前的 freelist
是否为空,并做不同处理。这个是必须的。因为在 stealing
阶段,没有持有当前 CPU freelist 的锁,之前检查得出的结论是失效的。p.s. 在这里其实没有失效,因为当前 CPU 的执行流关闭了中断,没有其他执行流能让这个空 freelist
获取空闲页面。但这个检查的模式在多线程模型中是必要的,因为关中断不是在所有设计中都是一致的,其他线程可能会修改之前的数据。
// Allocate one 4096-byte page of physical memory.
// Returns a pointer that the kernel can use.
// Returns 0 if the memory cannot be allocated.
void *
kalloc(void)
{
struct run *r;
int cpu_id;
// get current cpu id
push_off();
cpu_id = cpuid();
acquire(&kmem[cpu_id].lock);
r = kmem[cpu_id].freelist;
if(r)
kmem[cpu_id].freelist = r->next;
release(&kmem[cpu_id].lock);
// steal page for empty free-list
if (r == 0) {
r = steal_page(cpu_id);
if(r) {
acquire(&kmem[cpu_id].lock);
if (kmem[cpu_id].freelist == 0)
kmem[cpu_id].freelist = r->next;
else {
// special case: current freelist become not empty
add2tail(kmem[cpu_id].freelist, r);
r = kmem[cpu_id].freelist;
kmem[cpu_id].freelist = r->next;
}
release(&kmem[cpu_id].lock);
}
}
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
pop_off();
return (void*)r;
}
bcache
如果多个进程密集地使用文件系统,它们很可能竞争使用 bcache.loc
这个保护磁盘 block cache 的锁。这一部分实验的任务是修改 block cache 使得在 bcachetest
程序测试下,竞争 bcache
中的锁的次数尽可能小。修改 bget
与 brelse
函数使得查询和释放 bcache
中不同的 block 时减少用锁的冲突。p.s 就是不需要全部等待 bcache.lock
。同时,必须保证每个 block 最多只被缓存一次(为了这点需要保留bcache级别的锁,和前一个实验不同)。
hash bucket
减少 block cache
中的争用比 kalloc
更棘手,因为 bcache cache
是真正在进程(以及cpu)之间共享的。对于 kalloc
,可以通过为每个CPU分配自己的 allocator
来消除大部分争用;这对块缓存不起作用。我们可以使用哈希表,每个哈希桶 bucket
有一个锁,以此来查找缓存中的 block 。可以使用固定数量的 bucket
,而不动态地调整哈希表的大小。使用素数桶(例如13)来减少散列冲突的可能性。
#define NBUCKET 13
#define BIO_HASH(x) (x % NBUCKET)
struct {
struct spinlock lock;
struct buf buf[NBUF];
// Linked lists of each bucket buffers, through prev/next.
// Sorted by how recently the buffer was used.
// head.next is most recent, head.prev is least.
struct buf buc_head[NBUCKET];
struct spinlock buc_locks[NBUCKET];
} bcache;
实验建议使用时间戳来指示上一次使用,即使用 kernel/trap.c
中的 ticks
变量。如此,brelse
函数不需要获取 bcache lock
而 bget
通过时间戳来选择 LRU empty block
以完成驱逐与重新缓存。向结构体 buf
添加时间戳字段记录上次 access 情况。
// in kernel/buf.h
struct buf {
int valid; // has data been read from disk?
int disk; // does disk "own" buf?
uint dev;
uint blockno;
struct sleeplock lock;
uint refcnt;
struct buf *prev; // LRU cache list
struct buf *next;
uint64 lasttick; // last access
uchar data[BSIZE];
};
修改的 brelse
就只用持有 bucket
级别的锁,且不用像之前的 LRU 双链表结构一样将引用计数为 0
的 buf 进行移动。p.s. 我为了后续的 stealing
方便,还是保留了双链表的结构。
// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
int id;
if(!holdingsleep(&b->lock))
panic("brelse");
releasesleep(&b->lock);
id = BIO_HASH(b->blockno);
acquire(&bcache.buc_locks[id]);
b->refcnt--;
if (b->refcnt == 0) {
// no one is waiting for it.
b->lasttick = ticks;
}
release(&bcache.buc_locks[id]);
}
eviction
在修改 bget
时必须考虑到,如果一个目标 block
未缓存,需要将 unused buf
拿来使用。这个过程伴随将其 bucket
满了,可能需要从其他 bucket
取 unused buf
。类似 kmem
里的窃取流程,为避免死锁不能同时持有两个 bucket
锁。除此之外,还需注意”必须保证每个 block 最多只被缓存一次”。试想,两个执行流并发地为同一个 block 进行 evicition
,如果没有一个全局的锁控制,之后会有两个 blockno 相同的 buf
存在。这比 kmem
的情况要复杂一些。因为 kmem
的 freelist
并不在乎空闲页面的数据存在相等的可能(无必要)。
封装了双链表的删除与插入操作,以便窃取。
static void
removeFrom(struct buf* b) {
b->next->prev = b->prev;
b->prev->next = b->next;
}
static void
insertTo(struct buf* b, int bucketID) {
b->next = bcache.buc_head[bucketID].next;
b->prev = &bcache.buc_head[bucketID];
bcache.buc_head[bucketID].next->prev = b;
bcache.buc_head[bucketID].next = b;
}
修改后的 bget
代码如下,
// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
int i, id, oldInd;
uint lastvisit;
struct buf *b;
struct buf *pick;
id = BIO_HASH(blockno);
acquire(&bcache.buc_locks[id]);
// Is the block already cached?
for(b = bcache.buc_head[id].next; b != &bcache.buc_head[id]; b = b->next){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache.buc_locks[id]);
acquiresleep(&b->lock);
return b;
}
}
release(&bcache.buc_locks[id]);
// eviction
acquire(&bcache.lock);
acquire(&bcache.buc_locks[id]);
// must search again. There might be an eviction after last search.
for(b = bcache.buc_head[id].next; b != &bcache.buc_head[id]; b = b->next){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache.buc_locks[id]);
release(&bcache.lock);
acquiresleep(&b->lock);
return b;
}
}
release(&bcache.buc_locks[id]);
lastvisit = 0xffffffff;
pick = 0;
oldInd = -1;
// Not cached.
// Recycle the least recently used (LRU) unused buffer by time stamp
for (i = 0; i < NBUCKET; i++) {
acquire(&bcache.buc_locks[i]);
// find lru unused buf in this bucket
struct buf* curPick = 0;
for (b = bcache.buc_head[i].next; b != &bcache.buc_head[i]; b = b->next) {
if (b->refcnt == 0 && b->lasttick <= lastvisit) {
lastvisit = b->lasttick;
curPick = b;
}
}
if(curPick) {
if (pick) {
removeFrom(curPick);
release(&bcache.buc_locks[i]);
// ensure most two locks acquired
// restore
acquire(&bcache.buc_locks[oldInd]);
insertTo(pick, oldInd);
release(&bcache.buc_locks[oldInd]);
pick = curPick;
oldInd = i;
} else {
removeFrom(curPick);
release(&bcache.buc_locks[i]);
pick = curPick;
oldInd = i;
}
} else {
release(&bcache.buc_locks[i]);
}
}
if (pick) {
pick->dev = dev;
pick->blockno = blockno;
pick->valid = 0;
pick->refcnt = 1;
// insert to
acquire(&bcache.buc_locks[id]);
insertTo(pick, id);
release(&bcache.buc_locks[id]);
release(&bcache.lock);
acquiresleep(&pick->lock);
return pick;
}
release(&bcache.lock);
panic("bget: no buffers");
}
其主要流程为,
- 持有当前哈希桶的锁情况下,搜索桶内是否有缓存。
- 持有全局锁
bcache.lock
情况下,- 持有当前哈希桶的锁,再次搜索桶内。这一步必要,因为其他线程可能完成一次
eviction
- 持有不同哈希桶的锁,在各个桶内搜索
LRU empty buf
,并将选中的buf
从原桶中删除。 - 如果更换
pick buf
则需要将之前选中的buf
还原到原桶中。我用oldInd
记录原哈希桶。 - 如果有符合条件的
pick buf
,改写其元信息,将其插入blockno
的哈希桶内。
- 持有当前哈希桶的锁,再次搜索桶内。这一步必要,因为其他线程可能完成一次
这样的设计保证多进程在
- 使用同一个
blockno
buf 时 - 因为没有命中缓存,执行
eviction
代码,寻找 unused block 以代替时, - 使用同一个哈希桶时,
的并发正确性。
Conclusion
细粒度的锁可以减少锁的争用,提高性能。但实现需要小心避免死锁与资源泄漏。在本次实验的场景下,我通过保证加锁顺序,破坏循环等待条件,任何执行流不可能同时持有一个以上的同一级的细粒度锁,因此内核代码可以避免死锁。
但除了死锁以外,资源泄漏(还有其他资源被浪费的现象)也是可能发生的。在多线程的模型下,
- 如果持有锁 L2 ,之前在同一级锁 L1 的临界区内得出的结论,此时并不一定成立。因为机器可能在此线程出 L1 临界区后,调度其他线程又进入锁 L1 的临界区。这也是为什么在
kalloc
与bget
代码中有重复检查的代码。 - 如果有窃取流程,被窃取的资源在离开锁 L1 保护的数据结构后,未加入锁 L2 保护的数据结构前。其”保护者” 并不存在。这个
剥夺-插入
的流程一定要符合数据结构的invariant
,以避免资源泄漏。是否要在细粒度锁之上加一个高级别的eviction lock
则要视情况而定。如果eviction
不允许多个执行流同时执行,例如多个进程为同一个blockno
并行eviction
会导致多个buf的blockno
相同(这是资源浪费,也可看作某种泄漏),那么就需要一个eviction lock
原子化eviction
流程。
正如第十课讨论的,
死锁的危险通常限制了锁的粒度,因为细粒度锁带来更复杂的代码,更多死锁与资源泄漏的危险。锁的粒度决策需要由性能度量和复杂性考虑来驱动。everything is trade-off.