MIT_6.s081_Lab8:Xv6 and Lock

于2022年3月7日2022年3月7日由Sukuna发布

Lab8_1 Memory Access.

在这个部分的测试中,三个进程频繁地调度kalloc和kfree.

对于每个锁，acquire 维护对该锁的调用计数，以及获取中的循环尝试但未能设置锁的次数。 kalloctest 调用一个系统调用，使内核打印 kmem 和 bcache 锁（这是本实验的重点）和 5 个最争用次数最多锁的计数。如果存在锁争用，获取循环迭代的次数将会很大。系统调用返回 kmem 和 bcache 锁的循环迭代次数的总和。

对于本实验，您必须使用具有多核的专用机器。如果您使用一台正在做其他事情的机器，那么 kalloctest 打印的计数将是无稽之谈。

kalloctest 中锁争用的根本原因是 kalloc() 有一个空闲列表，由一个锁保护。要消除锁争用，您必须重新设计内存分配器以不使用一个锁和列表。基本思想是为每个 CPU 维护一个空闲列表，每个列表都有自己的锁。不同 CPU 上的分配和释放可以并行运行，因为每个 CPU 将在不同的列表上运行。主要挑战将是处理一个 CPU 的空闲列表为空，但另一个 CPU 的列表有空闲内存的情况；在这种情况下，一个 CPU 必须“窃取”另一个 CPU 的空闲列表的一部分。窃取可能会引入锁争用，但希望这种情况很少见。(这个叫“负载均衡”)

你的工作是实现每个 CPU 的空闲列表(就是对于每个CPU的核维护一个空闲列表,这个列表就是kmem)，并在 CPU 的空闲列表为空时进行读取。 您必须为所有以“kmem”开头的锁命名。 也就是说，您应该为每个锁调用 initlock，并传递一个以“kmem”开头的名称。 运行 kalloctest 以查看您的实现是否减少了锁争用。 要检查它是否仍然可以分配所有内存，请运行 usertests sbrkmuch。 您的输出将类似于下图所示，kmem 锁的争用总量大大减少，尽管具体数字会有所不同。 确保 usertests 中的所有测试都通过。 make Grade 应该说 kalloctests 通过了。

1) 按照提示,更改内存块的结构.不是所有内存块都共享一个锁,是每个CPU都有一个独立的锁.

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

2) 改为初始化所有锁.

void
kinit()
{
  for (int i = 0; i < NCPU; i++)
    initlock(&kmem[i].lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

3) 获取CPU的id,在这个地方获取id的时候要关中断,防止因为中断分配给其他CPU来进行处理了.

push_off();
int id = cpuid();
pop_off();

4) 对于kalloc和kfree的锁获取和进入改成对于CPU为id的那个锁

acquire(&kmem.lock)->acquire(&kmem[id].lock)

5) 在if(r)的后面添加else,代表如果寻找失败,就到其他的核中获取.

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