Lab8: locks
原文地址:YSBLOG
参考资料:[mit6.s081] 笔记 Lab8: Locks | 锁优化 | Miigon’s blog
实验目的:重新设计代码以提高并行性性能。
Memory allocator(moderate)
提高内存分配的性能,为每个CPU分配空闲列表,需要分配内存时,若当前CPU空闲列表存在可用内存,则只需要对当前CPU列表进行加锁,不会影响其他CPU的执行,提高并行性能。
具体修改如下啊:
//kalloc.c
struct {
struct spinlock lock;struct run *freelist;
} kmem[NCPU]; // 为每个CPU都分配一个空闲列表,用独立的锁进行保护void
kinit()
{
// 初始化每一个锁for (int i = 0; i < NCPU; ++i) {
initlock(&kmem[i].lock, "kmem");}freerange(end, (void*)PHYSTOP);
}void
kfree(void *pa)
{
... ...r = (struct run*)pa;// 在需要获取CPUID时要关闭中断,避免在使用CPUID的过程中该进程被切换到其他CPU上执行push_off();int cpu = cpuid();// 只获取当前CPU上的锁,将该页面添加到当前CPU的空闲列表中acquire(&kmem[cpu].lock);r->next = kmem[cpu].freelist;kmem[cpu].freelist = r;release(&kmem[cpu].lock);pop_off();
}void *
kalloc(void)
{
struct run *r;push_off();int cpu = cpuid();acquire(&kmem[cpu].lock);if (!kmem[cpu].freelist) {
// 如果当前CPU上没有空闲列表了,需要向其他CPU偷取页面int steal_page_nums = 64; // 定义一次最大偷取的页面数量for (int i = 0; i < NCPU; ++i) {
if (i == cpu) {
// 跳过自身continue;}// 获取待偷取CPU的空闲队列锁acquire(&kmem[i].lock); struct run *other_freelist = kmem[i].freelist;while (other_freelist && steal_page_nums > 0) {
// 其他CPU空闲列表不为空,并且还需要进行偷取// 使用头插法将偷取的空闲列表放入当前CPU的空闲列表中kmem[i].freelist = other_freelist->next;other_freelist->next = kmem[cpu].freelist;kmem[cpu].freelist = other_freelist;// 待偷取数量减一steal_page_nums--;// 重新定位待偷取页面other_freelist = kmem[i].freelist;}release(&kmem[i].lock);if (steal_page_nums <= 0) {
// 数量满足,停止偷取break;}}}r = kmem[cpu].freelist;if(r)kmem[cpu].freelist = r->next;release(&kmem[cpu].lock);// 不再使用CPUID,开启中断pop_off();if(r)memset((char*)r, 5, PGSIZE); // fill with junkreturn (void*)r;
}
Buffer cache(hard)
在原本的XV6中存在一个Buffer Cache,当CPU准备访问磁盘时,会先查询该cache,若cache中存在目标的缓冲,这直接返回给需要的进程,反之这使用LRU挑选一个空闲缓冲块去磁盘中读取后再返回。在这样一个过程中,存在多个CPU同时访问该cache,所以需要用锁对其进行并行控制。
个人觉得这个任务难度较大, 学习Miigon大佬的博客完成实验,下面内容时我对大佬代码的理解。
根据实验提示,我们需要构建一个哈希表,表中每个桶拥有自己的缓冲块链表,当我们需要访问磁盘时,只需要根据访问目标进行计算,根据计算结构到对应的桶中寻找缓冲块即可,这样就不会阻塞其他缓冲块的访问。若当前缓冲块中不存在目标缓冲块,则使用LRU算法寻找空闲缓冲块。
在XV6原本的实现中,缓冲块全部位于一个双向链表上,我们每次释放一个块就会像该链表的头部插入,当需要一个最近最少使用的块时,直接从头节点向前查找即可。
但是由于我们使用了哈希表,缓冲块分散在不同的桶上,我们无法再向原本的XV6的方式来实现,根据提示,我们可以使用ticks
(类似于时间戳)来记录不同缓冲块释放时间,当我们需要缓冲块时,就遍历所有的桶找到一个ticks
最小的可用缓冲块。
下面是我阅读大佬代码后添加的注释
// 哈希表大小
#define NBUFMAP_BUCKET 13
// 哈希函数
#define BUFMAP_HASH(dev, blockno) ((((dev) << 27) | (blockno)) % NBUFMAP_BUCKET)
/*Buffer cache同步对磁盘块的访问,以确保磁盘块在内存中只有一个副本,并且一次只有一个内核线程使用该副本缓存常用块,以便不需要从慢速磁盘重新读取它们。 */
struct {
struct buf buf[NBUF]; // 该buf数组表示全部的buffer空间,用于初始化遍历struct spinlock eviction_lock; // 用于保护buffer的结构,需要修改桶中元素位置时申请该锁// 将buffer分到不同的桶中,降低锁的粒度struct buf bufmap[NBUFMAP_BUCKET]; struct spinlock bufmap_locks[NBUFMAP_BUCKET]; // 分别保护每个桶的引用计数
} bcache;void
binit(void)
{
// 初始化bufmapfor (int i = 0; i < NBUFMAP_BUCKET; ++i) {
initlock(&bcache.bufmap_locks[i], "bcache_bufmap");bcache.bufmap[i].next = 0;}// 初始化每个buffer空间for (int i = 0; i < NBUF; ++i) {
struct buf *b = &bcache.buf[i];initsleeplock(&b->lock, "buffer"); // 初始化每个buf的锁b->lastuse = 0;b->refcnt = 0; // 引用计数设置为0// 初始化时将所有buf空间全部放在第一个桶下面b->next = bcache.bufmap[0].next;bcache.bufmap[0].next = b;}initlock(&bcache.eviction_lock, "bcache_eviction");}// 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)
{
struct buf *b;// 使用dev和blockno计算哈希值uint key = BUFMAP_HASH(dev, blockno);acquire(&bcache.bufmap_locks[key]);// 确认buffer中是否已经存在该磁盘块for (b = bcache.bufmap[key].next; b != (void*)0; b = b->next) {
if (b->dev == dev && b->blockno == blockno) {
// 找到相同的磁盘块,直接返回该缓冲区b->refcnt++;release(&bcache.bufmap_locks[key]);acquiresleep(&b->lock); // 使用睡眠锁确保当前块没有其他进程在使用return b;}}// 尝试在其他桶中窃取可用缓冲块// 首先释放当前缓冲块的锁,避免造成死锁release(&bcache.bufmap_locks[key]);// 需要修改缓冲结构,获取保护结构的锁acquire(&bcache.eviction_lock);// 由于在release与acquire之间可能会被中断,导致有缓冲区被重置// 所以获得锁之后要再次判断 避免在哈希表中同时缓冲了两个相同的磁盘区域 for (b = bcache.bufmap[key].next; b != (void*)0; b = b->next) {
if (b->dev == dev && b->blockno == blockno) {
acquire(&bcache.bufmap_locks[key]);b->refcnt++;release(&bcache.bufmap_locks[key]);release(&bcache.eviction_lock);acquiresleep(&b->lock);return b;}}// 再次确认后依旧没有所需要的缓冲区// 寻找一个最久没有使用过的缓冲区进行替换struct buf *brefore_least = 0;uint holding_bucket = -1;for (int i = 0; i < NBUFMAP_BUCKET; ++i) {
acquire(&bcache.bufmap_locks[i]); // 保护refcntint newfound = 0; // 在当前桶中是否找到的最近最少使用的块for (b = &bcache.bufmap[i]; b->next != (void*)0; b = b->next) {
if (b->next->refcnt == 0&& (brefore_least == (void*)0 // 还没有找过个合适的块|| b->next->lastuse < brefore_least->next->lastuse) // 当前块释放时间更早 ) {
brefore_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 (!brefore_least) {
// 所有桶中都没有找到合适的块panic("bget: no buffers");}b = brefore_least->next; // 合适块的地址if (holding_bucket != key) {
// 需要从其他的桶中拿取块brefore_least->next = b->next; // 将b从原来桶中链表断开release(&bcache.bufmap_locks[holding_bucket]); // 释放原来桶的锁acquire(&bcache.bufmap_locks[key]); // 获取待插入桶的锁// 将合适的块头插到key桶中b->next = bcache.bufmap[key].next;bcache.bufmap[key].next = b;b->dev = dev;b->blockno = blockno;b->refcnt = 1;b->valid = 0;release(&bcache.bufmap_locks[key]);} else {
// 合适的块本身就在key桶中,无需从其他桶迁移// 无需再获得锁,之前已经保持了该桶的锁// acquire(&bcache.bufmap_locks[key]); b->dev = dev;b->blockno = blockno;b->refcnt = 1;b->valid = 0;release(&bcache.bufmap_locks[key]);}release(&bcache.eviction_lock);acquiresleep(&b->lock);return b;
}// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
struct buf *b;b = bget(dev, blockno); // 尝试从缓冲区中读取,读取失败会返回一个新的缓冲区块if(!b->valid) {
virtio_disk_rw(b, 0); // 从磁盘读取数据到新的缓冲区块中b->valid = 1;}return b;
}// Write b's contents to disk. Must be locked.
void
bwrite(struct buf *b)
{
if(!holdingsleep(&b->lock))panic("bwrite");virtio_disk_rw(b, 1);
}// Release a locked buffer.
// Move to the head of the most-recently-used list.
void
brelse(struct buf *b)
{
if(!holdingsleep(&b->lock))panic("brelse");releasesleep(&b->lock);uint key = BUFMAP_HASH(b->dev, b->blockno);acquire(&bcache.bufmap_locks[key]);b->refcnt--;if (b->refcnt == 0) {
b->lastuse = ticks; // 如果当前缓冲块没有被引用,释放该区域时更新上次释放的时间}release(&bcache.bufmap_locks[key]);
}void
bpin(struct buf *b) {
uint key = BUFMAP_HASH(b->dev, b->blockno);acquire(&bcache.bufmap_locks[key]);b->refcnt++;release(&bcache.bufmap_locks[key]);
}void
bunpin(struct buf *b) {
uint key = BUFMAP_HASH(b->dev, b->blockno);acquire(&bcache.bufmap_locks[key]);b->refcnt--;release(&bcache.bufmap_locks[key]);
}