XV6 0x8

lab8

多进程

coordination ——sleep/wake

• pipes
• disk read
• wait

broken sleep：在无锁状态下，中断处理提前调用了 wakeup(void *chan)，当 sleep(void* chan, struct spinlock *lk) 执行时，wakeup(void *chan) 已经执行完毕，导致进程持续睡眠。因此sleep(void* chan, struct spinlock *lk)是原子的，在释放锁的同时将进程睡眠。

进程结束，父进程为什么要wait：

• 因为子进程无法释放自己的堆栈。
• 父进程可以获取子进程的退出码，并根据退出码决定接下来的操作。例如，如果子进程出现错误，父进程可能需要重新启动子进程或执行一些错误处理逻辑。
• 方便进行进程同步

Memory allocator(moderate)

我们将内存分配器的锁分配给每个CPU，同时，初始化锁。

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

void
kinit()
{
  char lockname[10];
  for(int i =0; i < NCPU; i++)
    {
      snprintf(lockname, sizeof(lockname), "kmem_%d", i);
      initlock(&kmem[i].lock, "kmem");
    }
  freerange(end, (void*)PHYSTOP);
}

分配内存，从当前CPU空闲列表查找，若找到空闲内存，则分配给进程。若找不到。则从其他进程空闲列表获取。

void *
kalloc(void)
{
  struct run *r;
  push_off();
  int id = cpuid();
  pop_off();

  acquire(&kmem[id].lock);
  r = kmem[id].freelist;
  if(r)
    kmem[id].freelist = r->next;
   release(&kmem[id].lock);
  if(!r)
  {
    for(int i = 0; i < NCPU; i++)
    {
      acquire(&kmem[i].lock);
      r = kmem[i].freelist;
      if(r) 
      {
        kmem[i].freelist = r->next;
        release(&kmem[i].lock);
        break;
      }
      release(&kmem[i].lock);
    }
  }


  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();
  pop_off();


  acquire(&kmem[id].lock);
  r->next = kmem[id].freelist;
  kmem[id].freelist = r;
  release(&kmem[id].lock);
}

Buffer cache(hard)

这个好难啊Qwq，只能去搬救兵了

首先我们将tick标识添加到buf

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 ticks;
};

定义哈希桶，按照指南设置大小为奇数13可以减少获取锁的冲突。

#define HASH_SIZE 13

//定义散列桶
struct hash_table{
  struct spinlock lock;
  struct buf head;
};


struct hash_table hash_table[HASH_SIZE];


struct {
  struct buf buf[NBUF];
} bcache;

初始化，依旧是相同的配方，我们只为一个桶分配内存，当其他哈希桶没有内存时来此窃取。

void
binit(void)
{
  struct buf *b;

  char lockname[20];
  for(int i =0; i < HASH_SIZE; i++)
    {
      snprintf(lockname, sizeof(lockname), "bcache_%d", i);
      initlock(&hash_table[i].lock, lockname);
      hash_table[i].head.prev = &hash_table[i].head;
      hash_table[i].head.next = &hash_table[i].head;
    }

  for(b = bcache.buf; b < bcache.buf+NBUF; b++){    //头插法
    b->next = hash_table[0].head.next;
    b->prev = &hash_table[0].head;
    initsleeplock(&b->lock, "buffer");		
    hash_table[0].head.next->prev = b;
    hash_table[0].head.next = b;
  }
}

• 首先遍历当前散列桶，若遍历到该元素，则返回该元素地址
• 若没有遍历到，则我们需要为该元素分配空间。遍历整个哈希表，寻找引用计数为0且最后访问时间最早的缓存块。
• 插入缓存块

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

  //acquire(&bcache.lock);
  int hash_blockno = blockno % HASH_SIZE;
  acquire(&hash_table[hash_blockno].lock);
  for(b = hash_table[hash_blockno].head.next; b != &hash_table[hash_blockno].head; b = b->next)
  {
      if(b->dev == dev && b->blockno == blockno){
        b->refcnt++;

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

        release(&hash_table[hash_blockno].lock);
        acquiresleep(&b->lock);
        return b;
      }
  }

    b = 0;
    struct buf* tmp;
    for(int i = hash_blockno, cycle = 0; cycle != HASH_SIZE; i = (i + 1) % HASH_SIZE)
    {
      ++cycle;
      if(i != hash_blockno){
        if(!holding(&hash_table[i].lock))
          acquire(&hash_table[i].lock);
      }
      for(tmp = hash_table[i].head.next; tmp != &hash_table[i].head; tmp = tmp->next)
      {
          if(tmp->refcnt == 0 && (b == 0 || tmp->ticks < b->ticks))
            b = tmp;
      }
    
    if(b){
      if(i != hash_blockno){
           b->next->prev = b->prev;
           b->prev->next = b->next;
           release(&hash_table[i].lock);

           b->next = hash_table[hash_blockno].head.next;
           b->prev = &hash_table[hash_blockno].head;
           hash_table[hash_blockno].head.next->prev = b;
           hash_table[hash_blockno].head.next = b;
      }
    
      b->dev = dev;
      b->blockno = blockno;
      b->valid = 0;
      b->refcnt = 1;

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

      release(&hash_table[hash_blockno].lock);
      acquiresleep(&b->lock);
      return b;
     
    }else {
        if(i != hash_blockno)
        {
            release(&hash_table[i].lock);
        }
    }


    }
  panic("bget: no buffers");
}

修改brelse，将ticks写入buf结构体，用以实现LRU。

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


  
  int hash_blockno = b->blockno % HASH_SIZE;
  releasesleep(&b->lock);
  acquire(&hash_table[hash_blockno].lock);
    b->refcnt--;
    acquire(&tickslock);
    b->ticks = ticks;
    release(&tickslock);
  release(&hash_table[hash_blockno].lock);
  

}

void
bpin(struct buf *b) {
  int hash_blockno = b->blockno % HASH_SIZE;
  acquire(&hash_table[hash_blockno].lock);
    b->refcnt++;
  release(&hash_table[hash_blockno].lock);
}

void
bunpin(struct buf *b) {
  int hash_blockno = b->blockno % HASH_SIZE;
  acquire(&hash_table[hash_blockno].lock);
    b->refcnt--;
  release(&hash_table[hash_blockno].lock);

}