Lab Lock

前置知识

一、哈希表(略)，双链表(略)

二、 buffer cache的LRU实现

buffer cache是一个双链表。每次新加入一个块，就会把它插到头指针后面，每次需要替换掉一个块，就选择一个头指针前面(也就是最后一个元素)进行替换。每一个块都有一个引用数，代表当前是否有进程在使用它。

Task: Memory allocator

这个task要求我们给每个cpu都分配一个freelist，来减少多个cpu对一个freelist修改的阻塞问题，还是比较简单的。

我们需要把整个freelist分给所有的cpu。

// kalloc.c
struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

kfree中，释放的时当前cpu的freepage。注意中断的开闭。

...
  r = (struct run*)pa;
  push_off();

  int cpunum = cpuid();
  acquire(&kmem[cpunum].lock);
  r->next = kmem[cpunum].freelist;
  kmem[cpunum].freelist = r;
  release(&kmem[cpunum].lock);

  pop_off();
...

在kalloc中，我们需要在当前cpu的freelist中来分配。如果当前freelist用光了，那么就需要去别的cpu偷取。

void *
kalloc(void)
{
  struct run *r;
  push_off();
  int cpunum = cpuid();
  acquire(&kmem[cpunum].lock);
  r = kmem[cpunum].freelist;
  if(r)
    kmem[cpunum].freelist = r->next;
  release(&kmem[cpunum].lock);

  if (!r) {
    r = ksteal(cpunum); // steal page
  }
  pop_off();
  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

偷取我封装成了一个函数。具体实现便是循环所有的cpu，如果找到可用的freelist那就返回它。

struct run* ksteal(int cpunum)
{
  struct run* r;
  for (int i = 1; i < NCPU; i++)
  {
    //if (i == cpunum) continue;
    int crcpu = (cpunum + i) % NCPU;

    acquire(&kmem[crcpu].lock);
    r = kmem[crcpu].freelist;
    if (r) kmem[crcpu].freelist = r->next; // if succeed
    release(&kmem[crcpu].lock);

    if (r) break;
  }
  return r;
}

Task Buffer cache

这个task就很难了。它需要我们像上一个task一样优化cache，但是不是根据cpu，而是实现一个hash。思路不复杂，但有非常多的地方容易出bug。在这个task里，有两个可行的方法来实现LRU(least-recently-used)算法，分别是时间戳和头插法。我都进行了实现并通过了make grade，但因为时间戳比较简单，所以只在最后给出核心代码供参考，这里主要是实现了头插法。(因为按理说头插法跑得要稍微快一点点)

首先定义并声明一个bcache对象。注意，这里面有一个大锁和一些小锁。至于为何需要大锁，在后面会有说明。

struct hashbuf {
  struct buf head;
  struct spinlock lock;
};

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.
  struct hashbuf buckets[NBUCKET]; // 需要去param.h把这个常量定义为13，当然也可以是什么别的质数
  //struct buf head;
  struct spinlock hashlock;
} bcache;

把锁和所有双链表初始化一下。同时，将所有的cache在一开始都挂载到0号链表上。

void
binit(void)
{
  struct buf *b;
  char lockname[16];

  //initlock(&bcache.lock, "bcache");
  initlock(&bcache.hashlock, "hashlock");
  for (int i = 0; i < NBUCKET; i++)
  {
    snprintf(lockname, sizeof(lockname), "bcache-%d", i);
    initlock(&bcache.buckets[i].lock, lockname);
    // Create linked list of buffers
    bcache.buckets[i].head.prev = &bcache.buckets[i].head;
    bcache.buckets[i].head.next = &bcache.buckets[i].head;
  }

  //bcache.head.prev = &bcache.head;
  //bcache.head.next = &bcache.head;
  for(b = bcache.buf; b < bcache.buf + NBUF; b++){
    b->next = bcache.buckets[0].head.next;
    b->prev = &bcache.buckets[0].head;
    initsleeplock(&b->lock, "buffer"); // doubly linked list init
    bcache.buckets[0].head.next->prev = b;
    bcache.buckets[0].head.next = b;
  }
  //printf("binit ok\n");
}

写一个小辅助函数，并修改一下bpin和bunpin。

int hash(int x)
{
  return x % NBUCKET;
}
...
void
bpin(struct buf *b) {
  int bid = hash(b->blockno);
  acquire(&bcache.buckets[bid].lock);
  b->refcnt++;
  release(&bcache.buckets[bid].lock);
}

void
bunpin(struct buf *b) {
  int bid = hash(b->blockno);
  acquire(&bcache.buckets[bid].lock);
  b->refcnt--;
  release(&bcache.buckets[bid].lock);
}

修改breles，运用头插法将新使用过的块插到最前面。

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  int bid = hash(b->blockno);

  releasesleep(&b->lock);

  acquire(&bcache.buckets[bid].lock);
  //acquire(&bcache.lock);
  b->refcnt--;

  //acquire(&tickslock); 
  //b->tstamp = ticks; 
  //release(&tickslock); 

  if (b->refcnt == 0) { 
    // no one is waiting for it.
    b->next->prev = b->prev;
    b->prev->next = b->next;
    b->next = bcache.buckets[bid].head.next;
    b->prev = &bcache.buckets[bid].head;
    bcache.buckets[bid].head.next->prev = b;
    bcache.buckets[bid].head.next = b;
  }
  
  release(&bcache.buckets[bid].lock);
}

修改bget，重点注意not cashed的时候，需要去其他桶里面偷取。同样，steal封装成了函数。因为我们用头插法实现，所以寻找是否cashed的时候只需要从后往前找。

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

  acquire(&bcache.buckets[bid].lock);

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

  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  for (int j = 0; j < NBUCKET; j++)
  {
    int i = (bid + j) % NBUCKET;
    // 一号位置
    for(b = bcache.buckets[i].head.prev; b != &bcache.buckets[i].head; b = b->prev){
      if(b->refcnt == 0) {
        if (i != bid)
          bsteal(b, i, bid);

        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;
        release(&bcache.buckets[bid].lock);
        acquiresleep(&b->lock);
        return b;
      }
    }
  }
  panic("bget: no buffers");
}
...
void bsteal(struct buf *b, int i, int bid) // 把它放到bget前面
{
  acquire(&bcache.hashlock);
  b->next->prev = b->prev;
  b->prev->next = b->next;
  release(&bcache.hashlock);
  //printf("buckets %d released p6\n", i);  
  //release(&bcache.buckets[i].lock);

  b->next = bcache.buckets[bid].head.next;
  b->prev = &bcache.buckets[bid].head;
  bcache.buckets[bid].head.next->prev = b;
  bcache.buckets[bid].head.next = b;
  return;
  //printf("bsteal ok\n");
}

首先，解释一下为何需要大锁。若一个cpu持有当前桶的锁，想要steal的时候，它必须申请steal桶的锁，假如此时恰好另一个cpu持有steal桶的锁，想要到当前桶来steal，那就会造成deadlock。所以我们如果想要steal，必须拿到大锁和小锁后才能执行。一开始，我只实现了小锁，并学习了网友的特殊做法来避免死锁，通过了所有test，但是这种方法有较大的风险。比如，当你从想要偷取的时候设置的是从0号桶开始寻找，就非常容易出问题。代码如下，供大家思考：

// 这段程序放置在1号位置
    if (i != bid) {
      if (!holding(&bcache.buckets[i].lock)) {
        acquire(&bcache.buckets[i].lock);
        //printf("buckets %d acquired p3\n", i);
        //printf("%d\n", bid);
      }
      else
        continue; // avoid deadlock, but little bug
    }

其次，关于如果没有cashed，为何偷取时从bid + 1开始寻找而不是0开始寻找。这是一个尚未解决的问题。我发现当从0开始寻找的时候，单独跑bcachetest会过，但是make grade时bcachetest会爆test1。怀疑有两点，一点是一开始的挂载问题，第二点是从固定桶开始寻找可能出现分配问题。希望有高人能够解决这个问题。

最后，挂上时间戳实现的核心代码。

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

  acquire(&bcache.buckets[bid].lock);
  //printf("buckets %d acquired p1\n", bid);

  // Is the block already cached?
  for(b = bcache.buckets[bid].head.next; b != &bcache.buckets[bid].head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){ // cashed
      b->refcnt++;

      acquire(&tickslock); 
      b->tstamp = ticks; 
      release(&tickslock); 

      //printf("buckets %d released p2\n", bid);        
      release(&bcache.buckets[bid].lock);
   
      acquiresleep(&b->lock);
      return b;
    }
  }

  b = 0;
  struct buf* temp;
  // Not cached.
  // Recycle the least recently used (LRU) unused buffer.
  for (int j = 0; j < NBUCKET; j++)
  {
    int i = (bid + j) % NBUCKET;

    uint mx = 0xffffffff;
    for(temp = bcache.buckets[i].head.prev; temp != &bcache.buckets[i].head; temp = temp->prev)
    {
      if (temp->refcnt == 0 && temp->tstamp < mx) {
        b = temp;
        mx = temp->tstamp;
      }
    }
    if(b) {
        if (i != bid)
          bsteal(b, i, bid); // steal

        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;

        acquire(&tickslock); 
        b->tstamp = ticks; 
        release(&tickslock); 

        //printf("buckets %d released p4 \n", bid);        
        release(&bcache.buckets[bid].lock);
        acquiresleep(&b->lock);
        //printf("i go s1 %d\n", i);
        return b;
      }
  }
  panic("bget: no buffers");
}

后记

其实在实现第二个task时，如果在cache中找到了需要找的数据，那被找到的这个块也应该移到链表的头部，但是当时没有想到这个问题，后来在研究LRU的时候才发现。虽然这样会大量移动指针，但一定会再次提高效率。