MIT6.s081 Lab8：locks
这个lab主要就是实现“一个锁变成多个锁”，对于一个相同的数据类型，分成多份，然后分别加锁。这个真的是做的最快的实现，所有测试一把过。
代码
1. Memory allocator
内核中的页表都是由一个链表维护的，每次需要申请或者释放内存的时候，我们需要链表的锁，防止出现对数据的重复操作之类的，引起一些意料之外的错误，因此分开链表，每个CPU维护一个能减少获取锁的次数，也是这个实验的关键。在写博客的过程中，发现了一点中断不合理的地方，代码已经进行修改。
-
增加页表“维护者”，设为
CPU的个数。struct {struct spinlock lock;struct run *freelist; } kmem[NCPU]; -
对每个链表初始化，这个锁的名称命名可能有点奇怪。
void kinit() {int i;char kmem_name[6] = {'k', 'm', 'e', 'm', '0', '\0'};for(i = 0; i < NCPU; i++) {kmem_name[4] = (char)(i + (int)'0');initlock(&kmem[i].lock, kmem_name);}freerange(end, (void*)PHYSTOP); } -
修改
kfree，每次释放的锁由CPU的 id 决定，这里需要关闭中断，以防出现下面这种情况。在进行分配的时候，本来是在
cpu0上执行，中断发生，结果分配到CPU1上了，这样会出现CPU1操作CPU0的链表，这是不合理的。kfree(void *pa) {struct run *r;push_off();int cpu_id = cpuid();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;acquire(&kmem[cpu_id].lock);r->next = kmem[cpu_id].freelist;kmem[cpu_id].freelist = r;release(&kmem[cpu_id].lock);pop_off(); } -
修改
kalloc。同样的，要防止中断的发生；然后可能稍微复杂一点的地方在于‘窃取’页面，如果CPU自己没有空闲的，要去别的CPU看看，跳过自己，然后如果有，就偷一个‘头’，在分配给自己。kalloc(void) {struct run *r;push_off();int cpu_id = cpuid();acquire(&kmem[cpu_id].lock);r = kmem[cpu_id].freelist;if(r)kmem.freelist = r->next;release(&kmem.lock);kmem[cpu_id].freelist = r->next;else {for(int i = 0; i < NCPU; i++) {if(r)break;if(i == cpu_id)continue;acquire(&kmem[i].lock);struct run *oc;oc = kmem[i].freelist;if(oc) {kmem[i].freelist = oc->next;oc->next = r;r = oc;}release(&kmem[i].lock);}}release(&kmem[cpu_id].lock);pop_off();if(r)memset((char*)r, 5, PGSIZE); // fill with junkreturn (void*)r; }
2. Buffer cache
虽然是hard，但是仔细分析之后，做起来也不是很难，思路总体上来看和上一个差不多，还是分锁，上一个根据CPU分，这个用质数个HASH桶，也就是质数个锁。
-
修改
bcache，使用桶，同时减少buf的个数，这里有上限(使用30个的话，initlock会出问题)，因此要减少buf的数量，其实也可以限制为最大30个，怎么方便怎么来吧。#define BUCKETS 13 #define NEWNBUF (MAXOPBLOCKS) //上面两个我放在param.h中的 struct {struct spinlock lock;struct buf buf[NEWNBUF];struct buf head; } bcache[BUCKETS]; -
修改初始化，修改了结构，肯定要修改初始化，代码如下。只能说太像了
void binit(void) {int i;char bcache_name[8] = {'b', 'c', 'a', 'c', 'h', 'e', '0', '\0'};char buffer_name[8] = {'b', 'u', 'f', 'f', 'e', 'r', '0', '\0'};for(i = 0; i < BUCKETS; i++) {bcache_name[6] = (char)(i + '0');initlock(&bcache[i].lock, bcache_name);for(int j = 0; j < NEWNBUF; j++) {buffer_name[6] = (char)(j + '0');initsleeplock(&(bcache[i].buf+j)->lock, buffer_name);}} } -
在
buf中增加一个时间戳，方便找到最久未使用的，以减少锁的使用。struct buf { ……uint timestamp; }; -
修改
brelse，因为加了时间戳，这里更新一下时间戳即可，不需要遍历链表放到最后了，减少锁的使用。void brelse(struct buf *b) {if(!holdingsleep(&b->lock))panic("brelse");releasesleep(&b->lock);b->refcnt--;b->timestamp = ticks; } -
因为使用了桶，每个
blockno要寻找自己对应的桶，方便对锁进行分散，用blockno % BUCKETS来获取需要使用用哪个锁，这里先修改bpin和bunpin，比较简单void bpin(struct buf *b) {int buckets_no = b->blockno % BUCKETS;acquire(&bcache[buckets_no].lock);b->refcnt++;release(&bcache[buckets_no].lock); }void bunpin(struct buf *b) {int buckets_no = b->blockno % BUCKETS;acquire(&bcache[buckets_no].lock);b->refcnt--;release(&bcache[buckets_no].lock); } -
修改
bget，最难的一部分，差别最大就是，当没有buf存放找的blockno时，要找一个最久没使用的给他，但是也是从当前的桶里找，也是容易的，如果很久没有使用，并且引用为0，就可以将这个buf给这个blockno了。bget(uint dev, uint blockno) {struct buf *b;int i;int buckets_no = blockno % BUCKETS;acquire(&bcache[buckets_no].lock);// Is the block already cached?for(i = 0; i < NEWNBUF; i++) {b = bcache[buckets_no].buf+i;if(b->dev == dev && b->blockno == blockno){b->refcnt++;release(&bcache[buckets_no].lock);acquiresleep(&b->lock);return b;}}int minstamp = 0xfffffff;int lruindex = -1;// Not cached.// Recycle the least recently used (LRU) unused buffer.for(i = 0; i < NEWNBUF; i++) {b = bcache[buckets_no].buf+i;if(b->timestamp < minstamp && b->refcnt == 0){minstamp = b->timestamp;lruindex = i;}}if(lruindex >= 0) {b = bcache[buckets_no].buf + lruindex;b->dev = dev;b->blockno = blockno;b->valid = 0;b->refcnt = 1;release(&bcache[buckets_no].lock);acquiresleep(&b->lock);return b;}panic("bget: no buffers"); }