代码：https://github.com/JasenChao/xv6-labs.git
内存分配器
单个空闲内存列表可能引起多个CPU的频繁锁争用，题目要求设计内存分配器，让每个CPU维护一个空闲内存列表，不同CPU的分配和释放可以并行执行，但如果一个CPU可用列表为空，而其他CPU可用列表不为空，则这个CPU必须窃取其他CPU的空闲内存，从而引入了锁争用。
在kernel/kalloc.c中实现每个CPU的空闲列表，以及相应的内存分配和释放函数。
首先把kmem改为每个CPU维护一个：
struct {
struct spinlock lock;
struct run *freelist;
} kmem[NCPU];
kinit()时将每个锁都初始化：
void
kinit()
{
for (int i = 0; i < NCPU; ++i)
initlock(&kmem[i].lock, "kmem");
freerange(end, (void*)PHYSTOP);
}
kalloc()函数修改为单个CPU并行，空闲列表不足时获取其他CPU的内存锁以偷窃内存：
void *
kalloc(void)
{
struct run *r;
push_off(); // 关中断
int id = cpuid();
acquire(&kmem[id].lock); // 获取当前CPU的内存锁
r = kmem[id].freelist;
if(r){ // 如果当前CPU有空闲内存
kmem[id].freelist = r->next; // 让出r，释放锁
}
else{ // 当前CPU没有空闲内存了
for(int i = 0; i < NCPU; ++i){ // 从其他CPU找
if(i != id){
acquire(&kmem[i].lock); // 获取其他CPU的锁
if(kmem[i].freelist){ // 如果这个CPU有空闲内存，那就抢走
r = kmem[i].freelist;
kmem[i].freelist = r->next;
release(&kmem[i].lock);
break;
}
release(&kmem[i].lock);
}
}
}
release(&kmem[id].lock);
pop_off(); // 开中断
if(r)
memset((char*)r, 5, PGSIZE); // fill with junk
return (void*)r;
}
kfree()函数只需要把当前的内存清空并插入当前CPU的空闲列表即可：
void
kfree(void *pa)
{
struct run *r;
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;
push_off();
int id = cpuid();
acquire(&kmem[id].lock);
r->next = kmem[id].freelist;
kmem[id].freelist = r;
release(&kmem[id].lock);
pop_off();
}
Cache缓冲区
类似于上一个问题，多个进程在读写磁盘时都会用到Cache，重复读取不同的文件会引发bcache.lock争用，题目要求降低获取bcache锁的迭代次数（小于500）。
在buf.h中根据提示，用质数（如13）个存储桶来减少哈希冲突的可能性，同时在buf中加入时间戳，选取空白缓存时选择refcnt==0且时间最小的：
#define NBUCKET 13
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;
uchar data[BSIZE];
uint time;
};
在bio.c中根据提示，删除缓冲区列表，将bcache改为哈希存储桶的个数：
struct {
struct spinlock lock;
struct buf buf[NBUF];
// Linked list of all buffers, through prev/next.
// Sorted by how recently the buffer was used.
// head.next is most recent, head.prev is least.
} bcache[NBUCKET];
在binit函数中，将所有bcache和其包含的buf中的锁都初始化：
void
binit(void)
{
struct buf *b;
for(int i = 0; i < NBUCKET; ++i){
for(b = bcache[i].buf; b < bcache[i].buf + NBUF; b++){
initsleeplock(&b->lock, "buffer");
}
initlock(&bcache[i].lock, "bcache");
}
}
此时可能会出现一个问题就是锁的数量不够用了，这里会导致系统里面需要初始化的锁太多了，将spinlock.c中锁的数量改大，比如改到800：
#define NLOCK 800
bget函数的逻辑需要修改，先取到对应的哈希存储桶，遍历其中的buf，如果找到了dev和blockno一致的缓存，引用+1后直接返回，如果没有就取refcnt==0并且时间最早的缓冲区：
static struct buf*
bget(uint dev, uint blockno)
{
struct buf *b = 0;
struct buf *min_b = 0;
int i = blockno % NBUCKET;
uint min_time = -1;
acquire(&bcache[i].lock);
// Is the block already cached?
for(b = bcache[i].buf; b < bcache[i].buf + NBUF; b++){
if(b->dev == dev && b->blockno == blockno){
b->refcnt++;
release(&bcache[i].lock);
acquiresleep(&b->lock);
return b;
}
if(b->refcnt == 0 && b->time < min_time)
{
min_time = b->time;
min_b = b;
}
}
b = min_b;
if(b!=0)
{
b->dev = dev;
b->blockno = blockno;
b->valid = 0;
b->refcnt = 1;
release(&bcache[i].lock);
acquiresleep(&b->lock);
return b;
}
panic("bget: no buffers");
}
在brelse函数中，只要获取对应的哈希存储桶，并且引用数-1即可释放，当引用数为0时将最新一次被使用的时间戳更新上去，方便下次bget：
void
brelse(struct buf *b)
{
if(!holdingsleep(&b->lock))
panic("brelse");
releasesleep(&b->lock);
int i = b->blockno % NBUCKET;
acquire(&bcache[i].lock);
b->refcnt--;
if (b->refcnt == 0) {
// no one is waiting for it.
b->time = ticks;
}
release(&bcache[i].lock);
}
bpin和bunpin函数只需要将原来获取bcache的代码改为获取对应的哈希存储桶：
void
bpin(struct buf *b) {
int i = b->blockno % NBUCKET;
acquire(&bcache[i].lock);
b->refcnt++;
release(&bcache[i].lock);
}
void
bunpin(struct buf *b) {
int i = b->blockno % NBUCKET;
acquire(&bcache[i].lock);
b->refcnt--;
release(&bcache[i].lock);
}
测试结果
使用make grade测试，结果如下：
== Test running kalloctest ==
$ make qemu-gdb
(51.8s)
== Test kalloctest: test1 ==
kalloctest: test1: OK
== Test kalloctest: test2 ==
kalloctest: test2: OK
== Test kalloctest: test3 ==
kalloctest: test3: OK
== Test kalloctest: sbrkmuch ==
$ make qemu-gdb
kalloctest: sbrkmuch: OK (5.4s)
== Test running bcachetest ==
$ make qemu-gdb
(7.2s)
== Test bcachetest: test0 ==
bcachetest: test0: OK
== Test bcachetest: test1 ==
bcachetest: test1: OK
== Test usertests ==
$ make qemu-gdb
usertests: OK (41.3s)