MIT 6.S081---Lab: locks

Memory allocator (moderate)

1. 修改kernel/kalloc.c，修改kmem声明并定义结构体数组：
   
2. 修改kernel/kalloc.c中的kinit函数，对kmemList进行初始化：
   
3. 修改kernel/kalloc.c中的kfree函数，获取当前的cpuid并将释放的内存添加到对应的freelist：
   
4. 修改kernel/kalloc.c中的kalloc函数，当前cpu的list为空时，从其他cpu的freelist获得：
   
   测试结果如下：
   
   

Buffer cache (hard)

1.修改kernel/buf.h，添加时间字段：

2. 修改kernel/bio.c,添加NBUCK宏定义，代表哈希表桶的数量：

3. 修改kernel/bio.c，添加结构体buck并修改binit进行初始化，初始化过程中将当前buffer加入到对应哈希桶的哈希列表中：

4. 修改kernel/bio.c中的struct bcache结构体，删除head（这是因为可以用ticks来判断时间戳大小来释放buffer就不用自己维护lru链表了）：

5. 修改kernel/bio.c中的bget函数（前半段逻辑相同，后半段获取当前最小的ticks并将其加入对应的哈希桶的链表当中）：

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

  uint64 num = blockno % NBUCK;
  acquire(&(hashtable[num].lock));
  // Is the block already cached?
  for(b = hashtable[num].head.next; b != &hashtable[num].head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&(hashtable[num].lock));
      acquiresleep(&b->lock);
      return b;
    }
  }
  release(&(hashtable[num].lock));

  struct buf* min_buf = 0;

  for (b = bcache.buf; b < bcache.buf + NBUF; ++b) {
    if (b->refcnt == 0) {
      if (min_buf == 0) {
        min_buf = b;
      } else {
        if (b->ticks < min_buf->ticks) {
          min_buf = b;
        }
      }
    }
  }

  acquire(&(hashtable[num].lock));
  min_buf->dev = dev;
  min_buf->blockno = blockno;
  min_buf->valid = 0;
  min_buf->refcnt = 1;
  min_buf->ticks = ticks;
  min_buf->next = hashtable[num].head.next;
  min_buf->prev = &hashtable[num].head;
  hashtable[num].head.next->prev = min_buf;
  hashtable[num].head.next = min_buf;

  release(&(hashtable[num].lock));
  acquiresleep(&min_buf->lock);
  return min_buf;

  panic("bget: no buffers");
}

6. 修改kernel/bio.c中的brelse函数（注意将其在对应的桶中的链表中删除掉）：
   

7. 修改kernel/bio.c中的bpin、bunpin函数：
   
   测试结果如下：