本文记录了 Lab: Locks 的实验过程

Lab: locks

git fetch
git checkout lock
make clean

---

Memory allocator (moderate)

任务

在 kernel/kalloc.c 文件中重新设计物理内存分配器，减少多个 CPU 同时争用一把锁的情况。提示：为每个 CPU 维护一个 freelists，那么当某个 CPU 需要物理内存时，它只会获得自己维护的 freelists 的锁；只有当 CPU 的 freelists 为空时，它才会查看其它 CPU 的 freelists，借用它们的空闲物理页。

实验思路

维护一个 kmem[NCPU] 数组，初始化其中的锁， kfree() 中只需要修改获取释放锁的代码。kalloc() 除了修改锁相关代码外，还需要补充当 CPU 的 freelists 为空时，去其他的 CPU 的 freelists 获取空闲物理页这个情况。注意获取当前 CPU 的 id 时需要关中断，之后再开中断。

---

Buffer cache (hard)

任务

在 kernel/bio.c 中重新设计 buffer cache 的分配方式，减少锁的争用（原始文件中 buffer cache 只有一把锁，当多个进程频繁进行文件读写时会严重降低系统性能）。一个可行的方法是使用一个哈希表维护这些 buffer cache，然后对哈希表中的每个 bucket 进行加锁来确保 invariant。

实验思路

1. 维护一个哈希表

#define NBUCKET 13
struct {
  struct spinlock lock;
  struct buf head;
} buckets[NBUCKET];

2. 去掉 kernel/buf.h 中的 prev 指针，改成 uint timestamp，来实现 LRU 算法
3. 在 binit() 中初始化哈希表，即初始化每个 bucket 的锁， 然后将 NBUF 个 buffer cache 添加到哈希表中（头插法）。
4. 修改函数 brelse(), bpin(), bunpin() 中的相关代码
5. 修改函数 bget()，首先我们会用 blockno 来确定 bucket 的位置，然后在这个 bucket 中查找某个 block 是否已经被缓存。如果有，则返回这个被缓存的 block；否则在这个桶查找是否有可用的 buf（refcnt == 0），有的话标记并返回这个 block；没有的话在需要在其他 bucket 中（此时需要获得其他 bucket 的锁）查找是否有可用的 buf。

---

测试

make qemu
kalloctest
usertests sbrkmuch
bcachetest
usertests

make grade

Diff

diff --git a/kernel/bio.c b/kernel/bio.c
index 60d91a6..18f298f 100644
--- a/kernel/bio.c
+++ b/kernel/bio.c
@@ -23,6 +23,7 @@
 #include "fs.h"
 #include "buf.h"
 
+#define NBUCKET 13
 struct {
   struct spinlock lock;
   struct buf buf[NBUF];
@@ -30,25 +31,40 @@ struct {
   // 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.
-  struct buf head;
 } bcache;
 
+struct {
+  struct spinlock lock;
+  struct buf head;
+} buckets[NBUCKET];
+
 void
 binit(void)
 {
   struct buf *b;
 
+  // init global buffer cache lock
   initlock(&bcache.lock, "bcache");
 
-  // Create linked list of buffers
-  bcache.head.prev = &bcache.head;
-  bcache.head.next = &bcache.head;
-  for(b = bcache.buf; b < bcache.buf+NBUF; b++){
-    b->next = bcache.head.next;
-    b->prev = &bcache.head;
-    initsleeplock(&b->lock, "buffer");
-    bcache.head.next->prev = b;
-    bcache.head.next = b;
+  // init every buffer lock
+  for(int i = 0; i < NBUF; i++){
+    initsleeplock(&bcache.buf[i].lock, "buffer");
+  }
+
+  // init every bucket lock
+  for(int i = 0; i < NBUCKET; i++){
+    initlock(&buckets[i].lock, "bcache.bucket");
+  }
+
+  // total 30 buffer cache, init every bucket
+  for(int i = 0; i < NBUF; i++){
+    b = &bcache.buf[i];
+    int index = i % NBUCKET;
+    b->blockno = index;
+    b->timestamp = 0;
+    b->refcnt = 0;
+    b->next = buckets[index].head.next;
+    buckets[index].head.next = b;
   }
 }
 
@@ -60,30 +76,63 @@ bget(uint dev, uint blockno)
 {
   struct buf *b;
 
-  acquire(&bcache.lock);
+  int index = blockno % NBUCKET;
+  acquire(&buckets[index].lock);
 
   // Is the block already cached?
-  for(b = bcache.head.next; b != &bcache.head; b = b->next){
+  for(b = buckets[index].head.next; b; b = b->next){
     if(b->dev == dev && b->blockno == blockno){
       b->refcnt++;
-      release(&bcache.lock);
+      release(&buckets[index].lock);
       acquiresleep(&b->lock);
       return b;
     }
   }
+  // search in buckets[index] to find whether a available buffer cache
+  // in bucket[index], I use LRU
+  uint lru = 0x7fffffff;
+  for(struct buf *t = buckets[index].head.next; t; t = t->next){
+    if(t->refcnt == 0 && t->timestamp < lru){
+      b = t;
+      lru = t->timestamp;
+    }
+  }
+  if(b){  // find a available buffer cache
+    b->dev = dev;
+    b->blockno = blockno;
+    b->valid = 0;
+    b->refcnt = 1;
+    release(&buckets[index].lock);
+    acquiresleep(&b->lock);
+    return b;
+  }
+  release(&buckets[index].lock);
 
   // Not cached.
-  // Recycle the least recently used (LRU) unused buffer.
-  for(b = bcache.head.prev; b != &bcache.head; b = b->prev){
-    if(b->refcnt == 0) {
+  // here I don't use LRU
+  for(int i = 0; i < NBUCKET; i++){
+    acquire(&buckets[i].lock);
+    struct buf *t = &buckets[i].head;
+    while(t->next && t->next->refcnt != 0)
+      t = t->next;
+    if(t->next){
+      b = t->next;
+      t->next = t->next->next;
+      release(&buckets[i].lock);
+
       b->dev = dev;
       b->blockno = blockno;
       b->valid = 0;
       b->refcnt = 1;
-      release(&bcache.lock);
+
+      acquire(&buckets[index].lock);
+      b->next = buckets[index].head.next;
+      buckets[index].head.next = b;
+      release(&buckets[index].lock);
       acquiresleep(&b->lock);
       return b;
     }
+    release(&buckets[i].lock);
   }
   panic("bget: no buffers");
 }
@@ -121,33 +170,30 @@ brelse(struct buf *b)
 
   releasesleep(&b->lock);
 
-  acquire(&bcache.lock);
+  int index = b->blockno % NBUCKET;
+  acquire(&buckets[index].lock);
   b->refcnt--;
   if (b->refcnt == 0) {
-    // no one is waiting for it.
-    b->next->prev = b->prev;
-    b->prev->next = b->next;
-    b->next = bcache.head.next;
-    b->prev = &bcache.head;
-    bcache.head.next->prev = b;
-    bcache.head.next = b;
+    b->timestamp = ticks; // update LRU
   }
   
-  release(&bcache.lock);
+  release(&buckets[index].lock);
 }
 
 void
 bpin(struct buf *b) {
-  acquire(&bcache.lock);
+  int index = b->blockno % NBUCKET;
+  acquire(&buckets[index].lock);
   b->refcnt++;
-  release(&bcache.lock);
+  release(&buckets[index].lock);
 }
 
 void
 bunpin(struct buf *b) {
-  acquire(&bcache.lock);
+  int index = b->blockno % NBUCKET;
+  acquire(&buckets[index].lock);
   b->refcnt--;
-  release(&bcache.lock);
+  release(&buckets[index].lock);
 }
 
 
diff --git a/kernel/buf.h b/kernel/buf.h
index 4616e9e..a9255e7 100644
--- a/kernel/buf.h
+++ b/kernel/buf.h
@@ -5,7 +5,7 @@ struct buf {
   uint blockno;
   struct sleeplock lock;
   uint refcnt;
-  struct buf *prev; // LRU cache list
+  uint timestamp; // use time-stamp achieve LRU
   struct buf *next;
   uchar data[BSIZE];
 };
diff --git a/kernel/kalloc.c b/kernel/kalloc.c
index fa6a0ac..b984486 100644
--- a/kernel/kalloc.c
+++ b/kernel/kalloc.c
@@ -21,12 +21,23 @@ struct run {
 struct {
   struct spinlock lock;
   struct run *freelist;
-} kmem;
+} kmem[NCPU];
+// get current core number
+int
+getcpu()
+{
+  push_off();
+  int cpu = cpuid();
+  pop_off();
+  return cpu;
+}
 
 void
 kinit()
 {
-  initlock(&kmem.lock, "kmem");
+  for(int i = 0; i < NCPU; i++){
+    initlock(&kmem[i].lock, "kmem");
+  }
   freerange(end, (void*)PHYSTOP);
 }
 
@@ -56,10 +67,11 @@ kfree(void *pa)
 
   r = (struct run*)pa;
 
-  acquire(&kmem.lock);
-  r->next = kmem.freelist;
-  kmem.freelist = r;
-  release(&kmem.lock);
+  int i = getcpu();
+  acquire(&kmem[i].lock);
+  r->next = kmem[i].freelist;
+  kmem[i].freelist = r;
+  release(&kmem[i].lock);
 }
 
 // Allocate one 4096-byte page of physical memory.
@@ -70,11 +82,29 @@ kalloc(void)
 {
   struct run *r;
 
-  acquire(&kmem.lock);
-  r = kmem.freelist;
-  if(r)
-    kmem.freelist = r->next;
-  release(&kmem.lock);
+  int i = getcpu();
+  acquire(&kmem[i].lock);
+  r = kmem[i].freelist;
+  if(r){
+    kmem[i].freelist = r->next;
+  }
+  release(&kmem[i].lock);
+
+  // if current core did't have free number, find in other core
+  if(!r){
+    int idx = (i + 1) % NCPU;
+    while(idx != i){
+      acquire(&kmem[idx].lock);
+      r = kmem[idx].freelist;
+      if(r){  // find a free page in other core
+        kmem[idx].freelist = r->next;
+        release(&kmem[idx].lock);
+        break;
+      }
+      release(&kmem[idx].lock);
+      idx = (idx + 1) % NCPU; // look for next core
+    }
+  }
 
   if(r)
     memset((char*)r, 5, PGSIZE); // fill with junk