xv6 中的锁的实现

    
        标签：
        
            xv6 学习笔记
        
            锁
        
    发布于：2023-02-03 16:57:20
    编辑于：2023-02-03 21:08:37
    浏览量：783

概述

Programmer often needs explicit control over the region of code during which a lock is held in order to hide awkward intermediate states.

对于共享数据的并发读写，有可能因为执行顺序的不同导致不确定的结果，可能会破坏程序的正确性。因为我们需要锁来使对关键区域的共享读写进行串行化。

对于 xv6 内核而言，其用到了两种锁，两种锁在使用方式上都是不可重入的互斥锁。具体到实现原理，其中一种是自旋锁，其底层实现依赖原子操作；另一种是睡眠锁，其依赖内核提供的进程调度机制。

自旋锁

自旋锁是指在等待持有锁的过程中，CPU 执行一个循环不断地尝试获取锁，此即所谓的自旋。

其不断执行的指令是一个 swap 指令，该指令原子地交换给定的寄存器和内存地址的值。其中寄存器的值是 1，而内存地址即我们的锁变量本身的内存地址。

在进程尝试获取自旋锁时，有两种情况：

如果锁尚未被其他进程释放，这意味着目标内存地址中的值是 1，因此该指令把寄存器中的 1 和目标内存地址中的 1 进行交换，之后寄存器中的值还是 1，此时循环继续。
如果锁已经被其他进程释放，这意味着目标内存地址中的值是 0，因此该指令把寄存器中的 1 和目标内存地址中的 0 进行交换，之后寄存器中的值变成了 0，而目标内存地址中的值是 1，此时循环继续条件不再满足，退出循环，我们也得到了该内存位置的自旋锁。

对于 RISC-V CPU，我们可以用 amoswap 指令；对于 x86 CPU，我们可以使用 xchg 指令。这些指令的硬件实现是通过全局地锁住目标地址，从而使其他 CPU 在上述指令执行期间不能访问目标内存地址，从而保证了操作执行的原子性。（It performs this sequence atomically, using special hardware to prevent any other CPU from using the memory address between the read and the write.）

xv6 中获取自旋锁的实现代码：

// Acquire the lock.
// Loops (spins) until the lock is acquired.
void
acquire(struct spinlock *lk)
{
  push_off(); // disable interrupts to avoid deadlock.
  if(holding(lk))
    panic("acquire");

  // On RISC-V, sync_lock_test_and_set turns into an atomic swap:
  //   a5 = 1
  //   s1 = &lk->locked
  //   amoswap.w.aq a5, a5, (s1)
  while(__sync_lock_test_and_set(&lk->locked, 1) != 0)
    ;

  // Tell the C compiler and the processor to not move loads or stores
  // past this point, to ensure that the critical section's memory
  // references happen strictly after the lock is acquired.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Record info about lock acquisition for holding() and debugging.
  lk->cpu = mycpu();
}

对于自旋锁的释放，这里同样使用了一个原子交换操作。这里我还不是很理解，释放时就算不是原子操作又如何呢？

xv6 中释放自旋锁的实现代码：

// Release the lock.
void
release(struct spinlock *lk)
{
  if(!holding(lk))
    panic("release");

  lk->cpu = 0;

  // Tell the C compiler and the CPU to not move loads or stores
  // past this point, to ensure that all the stores in the critical
  // section are visible to other CPUs before the lock is released,
  // and that loads in the critical section occur strictly before
  // the lock is released.
  // On RISC-V, this emits a fence instruction.
  __sync_synchronize();

  // Release the lock, equivalent to lk->locked = 0.
  // This code doesn't use a C assignment, since the C standard
  // implies that an assignment might be implemented with
  // multiple store instructions.
  // On RISC-V, sync_lock_release turns into an atomic swap:
  //   s1 = &lk->locked
  //   amoswap.w zero, zero, (s1)
  __sync_lock_release(&lk->locked);

  pop_off();
}

在上面的实现中，push_off() 和 pop_off() 是为了在持有自旋锁的过程中禁用中断。

为什么要禁用中断？这是为了防止死锁。首先需要明确的是，禁用的是执行该进程的 CPU 的中断。考虑到如果我们在持有自旋锁的情况下本 CPU 发生了中断，且中断的处理代码尝试获取同一个自旋锁，此时就构成了死锁：

持有自旋锁的进程拥有自旋锁，等待 CPU 资源。
中断处理代码拥有 CPU 资源，等待自旋锁。

从上面的描述中也可以看出，如果某个自旋锁不会被中断处理代码使用，那么是不需要禁用中断的。

xv6 中的解决方法就是直接禁止中断的发生，从而避免这种环路等待的情况的发生。

使用 push_off() 和 pop_off()，而非直接调用 intr_off() 和 intr_on() 的原因是，可能在调用自旋锁之前 CPU 的中断就已经被禁用了，因此需要计数 & 记录之前的状态以便在自旋锁释放后将中断状态还原到获取自旋锁之前的状态。

除此之外，在上面的实现中我们还调用了编译器的内置函数 __sync_synchronize() 来设置内存屏障，以防止由于编译器和 CPU 的乱序执行导致对临界资源的访问在我们的锁保护的区域之外。注意顺序：获取锁 -> 设置内存屏障 -> 临界区访问代码 -> 设置内存屏障 -> 释放锁。

睡眠锁

睡眠锁指的是当进程尝试获取锁的过程中，区别于自旋锁会导致 CPU 忙等待，睡眠锁会使进程让出 CPU，从执行中状态转到阻塞状态。

睡眠锁的实现依赖内核的进程调度。

【未完待续】

Links: xv6-locks