一、Lock


xv6 可以运行在多核处理器上,每个核(以下笼统称为CPU)都能执行独立的指令序列。看下面这段代码:

struct list {
  int data; 
  struct list *next;
}; 
struct list *list = 0;
void insert(int data) 
{
  struct list *l;
  l = malloc(sizeof *l);
  l->data = data;
  l->next = list;
  list = l;
}

这是一段内核代码。如果只有一个 CPU,这段代码的执行没有问题。

现在假设有两个进程,独立的运行在不同的 CPU 上。对于进程来说 list 这个结构体是共享的(因为所有进程的内核映射都是相同的)。同时执行 insert() 函数,当执行到 list = l 时,会出现 Race Condition:

+---------+
|data|next| :local var l in CPU1
+------+--+
       |            +--+list
       |            |
       +------> +---v-----+    +---------+    +---------+
                |data|next+--->+data|next+--->+data|next|
       +------> +---------+    +---------+    +---------+
       |
       |
+------+--+
|data|next| :local var l in CPU2
+---------+

两个 CPU 执行 list = l 的先后顺序不同,会造成链表的数据不同,其中一个数据会被覆盖掉。这就是 Race Condition 的出现造成的后果。下面是 xv6-book 中对 Race Condition 的定义:

A race condition is a situation in which a memory location is accessed concurrently, and at least one access is a write.

为了解决这个问题,我们先确定一个范围。在这个范围内,一次只能有一个 CPU 执行。这个范围称为 Critical Section(关键区域)。

xv6 中提到过一个术语: Invariant(不变量)。对于上面这个例子,不变量指 list 永远指向链表第一个节点。 l->next = list 修改了不变量,list = l 修复了不变量。在这期间不允许其他 CPU 对这个不变量进行任何操作。这样就能保证正确。

也就是当一个 CPU 开始执行 l->next = list 后,它就通过某种方式告诉其它 CPU: 等我把这两句执行完了你们再执行。等执行完 list = l 后,以某种方式通知其他 CPU。

这种通知与被告知,可以通过一个内核全局变量(所有进程共享)来实现,这个全局变量形象的称为锁。在 xv6 中,spinlock 以及其对应的函数,就具备这种性质。

struct spinlock {
  uint locked;
  char *name;       
  struct cpu *cpu;  
  uint pcs[10];     
};

void acquire(struct spinlock *lk)
{
  pushcli();
  if(holding(lk))
    panic("acquire");
  while(xchg(&lk->locked, 1) != 0)
    ;
  __sync_synchronize();
  lk->cpu = mycpu();
  getcallerpcs(&lk, lk->pcs);
}

void release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");
  lk->pcs[0] = 0;
  lk->cpu = 0;
  __sync_synchronize();
  asm volatile("movl $0, %0" : "+m" (lk->locked) : );
  popcli();
}

这里似乎有点矛盾,spinlock 也是一个共享的数据,要是 CPU 们对它的读写又造成了 Race Condition 怎么办呢?xv6 中使用一个汇编原子指令 xchgl,巧妙的解决了这个问题:

static inline uint xchg(volatile uint *addr, uint newval)
{
  uint result;
  asm volatile("lock; xchgl %0, %1" :
               "+m" (*addr), "=a" (result) :
               "1" (newval) :
               "cc");
  return result;
}

这个函数返回的是第一个参数的指,只要 lk->locked 还为 1,就一直循环。一旦 lk->locked 为 0 ,就跳出循环,获得锁。

如果对前面的例子加锁:

struct list *list = 0; 
struct spinlock listlock; 
void insert(int data) 
{ 
  struct list *l;
  l = malloc(sizeof *l);
  l->data = data;
  acquire(&listlock);
  l->next = list;
  list = l; 
  release(&listlock);
}

这就完美的解决了共享的问题。使用一个原子的汇编指令,实现了多条 C 语句的原子操作。

可以看到如果一个 CPU1 需要长时间持有锁 lockA,而另一个 CPU2 执行了 acquire(lockA) 就会进入 while 循环。这造成了 CPU2 的空转,是一种系统资源的浪费。为了解决这个问题,xv6 实现了 sleeplock:

struct sleeplock {
  uint locked;       
  struct spinlock lk;
  char *name;        
  int pid;           
};

void acquiresleep(struct sleeplock *lk)
{
  acquire(&lk->lk);
  while (lk->locked) {
    sleep(lk, &lk->lk);
  }
  lk->locked = 1;
  lk->pid = myproc()->pid;
  release(&lk->lk);
}

void releasesleep(struct sleeplock *lk)
{
  acquire(&lk->lk);
  lk->locked = 0;
  lk->pid = 0;
  wakeup(lk);
  release(&lk->lk);
}

睡眠锁用到了 xv6 中调度的知识,下面介绍 xv6 中的进程调度,回过头来看就豁然开朗了。

 

二、Schedule


虚拟地址空间的实现,让进程认为自己占用了整个物理内存。而进程调度的实现,则让进程认为自己独占了处理器。

调度就是让 CPU 在多个进程中来回的切换执行。在 xv6 中进程调度中就是:

struct context {
  uint edi;
  uint esi;
  uint ebx;
  uint ebp;
  uint eip;
};

上下文切换过程由下面这段汇编实现:

在 xv6 中只有两个地方调用了 swtch() 函数:

void scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  c->proc = 0;
  for(;;){
    sti();
    acquire(&ptable.lock);
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
      if(p->state != RUNNABLE)
        continue;
      c->proc = p;
      switchuvm(p);
      p->state = RUNNING;
      swtch(&(c->scheduler), p->context); 
      switchkvm();
      c->proc = 0;
    }
    release(&ptable.lock);
  }
}
void sched(void)
{
  int intena;
  struct proc *p = myproc();
  ...
  intena = mycpu()->intena;
  swtch(&p->context, mycpu()->scheduler);
  mycpu()->intena = intena;
}

The procedures in which this stylized switching between two threads happens are sometimes referred to as coroutines(协程); in this example, sched and scheduler are co-routines of each other.

上图模拟了进程 A 向进程 B 调度(执行swtch中popl %edi前)时三个内核栈的布局。结合这图和 swtch.S 就能大致理解 xv6 中进程切换的原理了。