Wings 的博客
归档 系列 分类 标签 关于 友链 开往
Wings 的博客

MIT 6.S081 Fall 2020 Lab 8

Locks

Wings  收录于  类别 操作系统 和 系列 Learning MIT 6.S081
     约 1787 字  预计阅读 4 分钟    次阅读     条评论  
系列 - Learning MIT 6.S081

学!

每个 CPU 维护一个 kmem 队列, 在 kalloc 和 kfree 时优先自己的队列. 自己队列没有空闲空间时, 去找其他 CPU 维护的队列.

注意操作自己的队列时也需要加锁, 因为其他 CPU 可能会来使用.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

diff --git a/kernel/kalloc.c b/kernel/kalloc.c
index fa6a0ac..7ed4f66 100644
--- a/kernel/kalloc.c
+++ b/kernel/kalloc.c
@@ -21,12 +21,13 @@ struct run {
 struct {
   struct spinlock lock;
   struct run *freelist;
-} kmem;
+} kmem[NPROC];
 
 void
 kinit()
 {
-  initlock(&kmem.lock, "kmem");
+  for (int i = 0; i < NPROC; i++)
+    initlock(&kmem[i].lock, "kmem");
   freerange(end, (void*)PHYSTOP);
 }
 
@@ -34,9 +35,18 @@ void
 freerange(void *pa_start, void *pa_end)
 {
   char *p;
+  int i;
+  struct run *r;
+
   p = (char*)PGROUNDUP((uint64)pa_start);
-  for(; p + PGSIZE <= (char*)pa_end; p += PGSIZE)
-    kfree(p);
+  for(i = 0; p + PGSIZE <= (char*)pa_end; p += PGSIZE, i++) {
+    if (i == NPROC)
+      i = 0;
+    r = (struct run*)p;
+    memset(p, 1, PGSIZE);
+    r->next = kmem[i].freelist;
+    kmem[i].freelist = r;
+  }
 }
 
 // Free the page of physical memory pointed at by v,
@@ -47,6 +57,7 @@ void
 kfree(void *pa)
 {
   struct run *r;
+  int hartid;
 
   if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
     panic("kfree");
@@ -55,11 +66,12 @@ kfree(void *pa)
   memset(pa, 1, PGSIZE);
 
   r = (struct run*)pa;
+  hartid = cpuid();
 
-  acquire(&kmem.lock);
-  r->next = kmem.freelist;
-  kmem.freelist = r;
-  release(&kmem.lock);
+  acquire(&kmem[hartid].lock);
+  r->next = kmem[hartid].freelist;
+  kmem[hartid].freelist = r;
+  release(&kmem[hartid].lock);
 }
 
 // Allocate one 4096-byte page of physical memory.
@@ -68,13 +80,21 @@ kfree(void *pa)
 void *
 kalloc(void)
 {
-  struct run *r;
+  struct run *r = 0;
+  int hartid, i, from;
 
-  acquire(&kmem.lock);
-  r = kmem.freelist;
-  if(r)
-    kmem.freelist = r->next;
-  release(&kmem.lock);
+  hartid = cpuid();
+
+  // find a non-empty list
+  for (i = 0, from = hartid; i < NPROC && !r; i++, from++) {
+    if (from == NPROC)
+      from = 0;
+    acquire(&kmem[from].lock);
+    r = kmem[from].freelist;
+    if (r)
+      kmem[from].freelist = r->next;
+    release(&kmem[from].lock);
+  }
 
   if(r)
     memset((char*)r, 5, PGSIZE); // fill with junk

读了好久的题, 边乱写着才知道我要干什么…

这题和上一题异曲同工, 是给 bcache 大锁化小锁, 只不过由于多个进程可能访问同一个 block (即多个 CPU 同时访问同一个 block), 所以不能按 CPU 分配 buffer.

这里的方案是对每个 block 哈希, 哈希值一样的放在一个链表里. 之前的大锁可以看作保护链表结构以及链表中的 block cache 结构, 那对于我们分的多个链表, 也用锁来保护其结构, 以及 该链表中的 block cache.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

struct {
  struct buf buf[NBUF];

  // Linked list of buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  // Hash talbe with open hashing
  struct buf head[BHSIZE];
  // locks for hash bucket
  struct spinlock locks[BHSIZE];
} bcache;

哈希函数可以直接用 block 的 blockno 取模:

1
2

#define BHSIZE    17  // bcache hash table size
#define BHASH(x)  (x % BHSIZE)

初始化修改为对每个链表以及锁, 将可用的缓存块均匀分布在每个链表中.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void
binit(void)
{
  struct buf *b;
  int i;

  for (i = 0; i < BHSIZE; i++) {
    initlock(&bcache.locks[i], "bcache");
    bcache.head[i].prev = &bcache.head[i];
    bcache.head[i].next = &bcache.head[i];
  }

  // Create linked list of buffers
  for(i = 0, b = bcache.buf; b < bcache.buf+NBUF; b++, i++){
    if (i == BHSIZE)
      i = 0;
    b->next = bcache.head[i].next;
    b->prev = &bcache.head[i];
    initsleeplock(&b->lock, "buffer");
    bcache.head[i].next->prev = b;
    bcache.head[i].next = b;
  }
}

bget 的逻辑应该是:

  1. 检查对应链表中有没有 cache, 有的话找到;
  2. 没有的话, 先看自己的链表中有无可换出的, 有的话换出, 维护 LRU;
  3. 没有的话, 再看其他链表中有无可换出的, 有的话换出, 链到自己的链表上 (链表中的 blockno 哈希值要一致, 所以要拿过来).

这里还有一个问题是, 原来只用一个链表, 可以直接实现 LRU, 这里用了多个链表, 每个链表里实现 LRU, 但是全局 LRU 没有维护. 个人认为全局 LRU 没有太大必要 (如果不用一整个链表维护还挺麻烦的).

我的做法是找一个有可以换出的链表, 把他的最久未使用给换出. 所以这里是一个近似的 LRU.

这里注意一下锁的操作. 第二步中之所以先找自己的, 是因为在找其他的时候需要获取其他对应的锁, 而自己的必须释放, 否则会死锁. 所以先把自己的给处理完毕再说.

第三步中在其他链表中找到了可换出的 cache, 先修改一下缓存对应的 block, 然后在链表中 unlink 掉这个元素, 就可以把对应锁给释放了, 因为这个锁是用来维护链表及其内部的 cache 的. 当元素不在链表里, 其他进程遍历链表就一定不会获取到它, 所以可以把锁释放.

释放了之后才可以获取当前链表的锁, 因为我们要链进去. 这里也不能同时持有两把锁, 否则可能死锁.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  int hash, i;

  hash = BHASH(blockno);

  acquire(&bcache.locks[hash]);

  // Is the block already cached?
  for(b = bcache.head[hash].next; b != &bcache.head[hash]; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&bcache.locks[hash]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer in this bucket.
  for(b = bcache.head[hash].prev; b != &bcache.head[hash]; b = b->prev){
    if(b->refcnt == 0) {
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;
      release(&bcache.locks[hash]);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // No available buffer in this bucket
  // Try other buckets with their own LRU scheme
  // So it's not a turly LRU
  release(&bcache.locks[hash]);
  for (i = hash + 1; i != hash; i++) {
    if (i == BHSIZE)
      i = 0;
    acquire(&bcache.locks[i]);
    for (b = bcache.head[i].prev; b != &bcache.head[i]; b = b->prev) {
      if (b->refcnt == 0) {
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;
        // remove from origin list
        b->next->prev = b->prev;
        b->prev->next = b->next;
        // b is removed form the list, now we do not need the lock
        release(&bcache.locks[i]);
        // add to this bucket
        acquire(&bcache.locks[hash]);
        b->next = bcache.head[hash].next;
        b->prev = &bcache.head[hash];
        bcache.head[hash].next->prev = b;
        bcache.head[hash].next = b;
        release(&bcache.locks[hash]);
        acquiresleep(&b->lock);
        return b;
      }
    }
    release(&bcache.locks[i]);
  }
  panic("bget: no buffers");
}

最后修改一下 brelse, bpin, bunpin 的锁即可.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void
brelse(struct buf *b)
{
  int hash = BHASH(b->blockno);

  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&bcache.locks[hash]);
  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[hash].next;
    b->prev = &bcache.head[hash];
    bcache.head[hash].next->prev = b;
    bcache.head[hash].next = b;
  }
  
  release(&bcache.locks[hash]);
}

void
bpin(struct buf *b) {
  int hash = BHASH(b->blockno);

  acquire(&bcache.locks[hash]);
  b->refcnt++;
  release(&bcache.locks[hash]);
}

void
bunpin(struct buf *b) {
  int hash = BHASH(b->blockno);

  acquire(&bcache.locks[hash]);
  b->refcnt--;
  release(&bcache.locks[hash]);
}

不会 C 语言, 爬了

更新于 2022-12-30
 MIT 6.S081
返回 | 主页