MIT 6.S081 Lecture 10: Multiprocessors and locking

5 Sep 2022

The world never lacks criticism and advice, but reason and thinking.

6.S081第十课，课程教授多处理器与锁地知识，阅读课本第六章。

Why we need lock?

What is Concurrency?

大多数内核(包括xv6)交错执行多个进程。交错的一个来源是多处理器硬件:具有多个独立执行的cpu的计算机，多个cpu共享物理RAM，而xv6利用共享来维护所有cpu读写的数据结构。这种共享可能导致一个CPU读取一个数据结构，而另一个CPU正在更新它，甚至多个CPU同时更新相同的数据;如果没有仔细的设计，这种并行访问可能会产生不正确的结果或损坏的数据结构。即使在单处理器上，内核也可能在多个线程之间切换CPU，导致它们的执行交错进行。最后，如果中断发生在错误的时间，与某些可中断代码修改相同数据的设备中断处理程序可能会破坏数据。并发这个词指的是由于多处理器并行、线程切换或中断而导致多个指令流交错的情况。

Concurrency control

内核中充满了并发访问的数据。内核设计人员喜欢允许大量并发性，因为它可以通过并行性和响应性来提高性能。然而，尽管有这样的并发性，内核设计者还是花费了大量的精力证明正确性。有许多方法可以设计正确的代码，有些方法比其他方法更容易推理。这些旨在实现并发下正确性的策略，以及支持它们的抽象，被称为并发控制技术。

根据具体情况，Xv6使用了许多并发控制技术;现实OS还有更多。锁是一种广泛使用的技术:锁。锁提供互斥，确保一次只有一个CPU可以持有锁。如果程序员为每个共享数据单元关联一个锁，并且代码在使用这个共享数据单元时总是持有关联的锁，那么该单元一次只能被一个CPU使用。在这种情况下，我们说锁定数据项。尽管锁是一种易于理解的并发控制机制，但锁的缺点是它们会降低性能，因为它们会序列化并发操作。

Race conditions

竞争条件（race conditions）是指并发访问某个内存位置，且至少有一次访问是写操作。竞争通常是错误的标志，

丢失了更新(如果访问是写的);
读取了未完全更新的数据结构。

竞争的结果取决于所涉及的两个cpu的确切时间，以及内存系统如何对它们的内存操作进行排序，这可能使竞争引起的错误难以重现和调试。

critical section

锁的互斥效果可以避免数据竞争，在获取/释放锁之间的代码也被称为临界区（critical section）。以下为使用一个锁的示例。

struct element *list = 0;
struct lock listlock;

void
push(int data)
{
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;


  acquire(&listlock);
  l->next = list;
  list = l;
  release(&listlock);
}

当我们说锁保护数据时，是指锁可以保护一些适用于数据的不变性（invariant）集合。不变性是跨操作维护的数据结构的属性。通常，操作的正确行为取决于操作开始与结束时的不变性。该操作可能会暂时违反不变性，但必须在完成后又保持了不变性。

我的理解是这是数据的一致性（consistency），一些操作需要原子（atomically）地改变数据结构，中间不可打断。所以用锁来实现原子性。

当然也可以将锁操作看作是序列化并发的临界段，以便它们一次运行一个临界段，从而保持不变性(假设隔离的临界段是正确的)。还可以将由同一个锁保护的关键部分视为彼此之间的原子性，因此每个关键部分只能看到以前关键部分的完整更改，而永远看不到部分完成的更新（这个部分完成就可理解为 inconsistent）。

lock limits performance

如果多个进程同时需要同一个锁，或者锁发生争用(一个进程也有可能多次用同一个锁)，这就是冲突。内核设计中的一个主要挑战是避免锁冲突。这也是锁机制性能不友好的原因之一。Xv6在这方面做得很少，但是复杂的内核专门组织数据结构和算法，以避免锁争用。

以 free list 维护的堆为例，内核可以为每个CPU维护一个 free list 与其相关的锁。只有在某个CPU的 free list 用尽且必须从另一个CPU获取内存时，内核才会接触另一个CPU的 free list 并申请锁。

Using locks

basic principles

使用锁的难点在于决定使用多少锁，以及每个锁应该保护哪些数据和不变性。有一些基本原则。

当一个CPU可以写入一个变量，而另一个CPU可以读取或写入它时，应该使用一个锁来防止两个操作重叠。这是使用锁的场景。
其次，记住锁保护不变量：如果一个不变量涉及多个内存位置，通常需要使用一个锁来保护所有这些位置，以确保维护不变量。

We need less lock.

上面的规则说了什么时候需要锁，但是没有说什么时候不需要锁。其实为了提高效率，锁不要太多（本质是共享不用太多），因为锁会减少并行性。如果并行性不重要，那么可以只安排一个线程，而不用担心锁。一个简单的内核可以在多处理器上做到这一点，方法是使用一个锁，这个锁必须在进入内核时获得，在退出内核时释放(但管道读取或 wait 等系统调用会带来问题)。

许多单处理器操作系统已经使用这种方法(有时称为”big kernel lock”)转换为在多处理器上运行，但是这种方法牺牲了并行性:一次只能在内核中执行一个CPU。如果内核要进行繁重的计算，那么使用一组更大的细粒度锁会更有效率，这样内核就可以同时在多个cpu上执行。

coarse-grained or fine-grained

究竟应当使用粗粒度，还是细粒度的锁，这就需要软件设计者结合实际场景考虑。如 xv6 内核只有一个 free list 锁，如果不同cpu上的多个进程试图同时分配页，每个进程都必须通过自旋（spin）请求来等待。自旋会降低性能，因为它不是有用的工作。如果争用锁浪费了大量CPU时间，那么可以通过更改设计，内核维护多个 free list，每个 free list 都有自己的锁，从而允许真正的并行分配，从而提高性能.

而Xv6对每个文件都有一个单独的锁，因此操作不同文件的进程通常可以并行，而不需要等待其他文件的锁。如果想要允许进程同时写入同一个文件的不同区域，那么文件锁的设计需要更细粒度。最终，锁的粒度决策需要由性能度量和复杂性考虑来驱动。everything is trade-off.

Deadlock and lock ordering

死锁众所周知，其四个必要条件：

互斥
请求并保持
不可剥夺
循环等待

为了避免死锁，需要破坏必要条件。锁与其保护的资源天然互斥，这个条件不用改，

破坏”请求与保持”：两个思路，静态分配，每个进程在开始执行时就申请他所需要的全部资源；动态分配，每个进程在申请所需要的资源时他本身不占用系统资源。
破坏”不可剥夺”：一个进程不能获得所需要的全部资源时便处于等待状态，等待期间他占有的资源将被隐式的释放重新加入到系统的资源列表中，可以被其他的进程使用，而等待的进程只有重新获得自己原有的资源以及新申请的资源才可以重新启动执行。
破坏”循环等待”：采用资源有序分配。其基本思想是将系统中的所有资源顺序编号，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行，一个进程只有获得较小编号的进程才能申请较大编号的进程。

书中的所谓 lock ordering 就是为了防止循环等待。所有进程采取相同的锁顺序。有相同顺序意味着锁是每个函数规范的组成部分:调用方caller其调用函数的方式必须使锁顺序。

constraint

如此会导致锁的顺序与有时与逻辑程序结构冲突，例如，代码模块M1调用模块M2，但是锁的顺序要求M2的锁必须在M1的锁之前获得。

有时，锁的标识不能提前知道，这可能是因为必须持有一个锁才能发现下一个要获取的锁的标识。这种情况会在文件系统中出现，因为它在一个路径中查找连续的单元；在 wait 和 exit 系统调用代码中出现，因为它们需要在进程表中查找子进程。

死锁的危险通常限制了锁的细粒度，因为更多的锁通常意味着死锁的机会更多。在内核实现中，避免死锁的通常是一个主要因素。

Re-entrant locks

通过使用可重入锁(也称为递归锁 recursive locks)来避免一些死锁和锁排序问题。其思想是，如果锁被某个进程持有，并且该进程试图再次获得锁，那么内核可允许这样做(因为该进程已经拥有锁)，而不是像xv6内核那样调用panic。

但可重入锁使得对并发性的推理变得更加困难，其打破了锁导致临界部分相对于其他临界部分是原子的这种直觉。例如下面的伪代码，

struct spinlock lock;
int data = 0; // protected by lock

f() {
  acquire(&lock);
  if(data == 0){
    call_once();
    h();
    data = 1;
  }
  release(&lock);
}
g() {
  aquire(&lock);
  if(data == 0){
    call_once();
    data = 1;
  }
  release(&lock);
}

函数 call_once 在同一个锁的不同临界区，直觉上只能被执行一次（注意锁保护的变量 data 指示执行次数）。但如果锁重入是可能的，且函数 h 调用了 g 函数，那么 call_once 会被执行两次。

如果不允许重入锁，那么 h 调用 g 会导致死锁，这也不是很好。但假设调用一次会是一个严重的错误，那么最好的选择是死锁。内核开发人员将观察死锁(内核恐慌)，并可以修复代码以避免死锁，而两次调用call可能会无声地导致难以跟踪的错误。

所以 xv6 使用更简单的方法，即不可重入锁。然而，只要程序员了解锁的规则，两种方法都可以工作。如果xv6要使用可重入锁，则必须修改acquire才能注意到锁当前由调用线程持有。我们还必须在结构自旋锁中添加一个嵌套的acquire计数重入，其样式与后面讨论的 push_off 类似。

Code: Locks

关于锁的实现，xv6有 spin lock 自旋锁与 sleep lock 睡眠锁两种。这里直接贴 spin lock 的结构与 acquire/release 代码。详细说明，

// in kernel/spinlock.h
// Mutual exclusion lock.
struct spinlock {
  uint locked;       // Is the lock held?

  // For debugging:
  char *name;        // Name of lock.
  struct cpu *cpu;   // The cpu holding the lock.
};

// in kernel/spinlock.c
// 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();
}

// 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();
}

这里仅解释 acquire 的过程， release 完全是相反操作，

关闭中断
检查重入
spin 获取锁
通过 fence 指令使临界区指令不可重排
记录 cpu 信息方便 debug

这里 2 与 5 就不赘述了。重点从另外三个角度讲 spin lock 的细节。

Locks and interrupt handlers

一些 XV6 spin locks保护线程和中断处理程序使用的数据。例如，clockintr 计时器中断处理程序会增加 tick，同一时间sys_sleep（kernel/sysproc.c：64） 读取 ticks 。锁 tickslock 序列化两个访问。

锁和中断的相互作用会引起潜在的危险。假设 sys_sleep 持有tickslock，其CPU被计时器中断打断。clockintr会尝试获取tickslock，看到它被持有，并等待它被释放。在这种情况下，tickslock 将永远不会释放：因为只有 sys_sleep 可释放它，但是在clockintr返回之前，sys_sleep 不会继续运行。因此，CPU将死锁。

这也是一个 xv6 禁止锁重入的潜在效果。

为了避免这种情况，如果一个自旋锁被一个中断处理程序使用，CPU绝对不能在启用中断的情况下持有该锁。xv6用更为保守的策略：当一个CPU获得任何锁时，Xv6总是禁用该CPU上的中断。中断仍然可能发生在其他CPU上，因此中断可以等待线程释放自旋锁;只是不在同一个CPU上。

当CPU没有自旋锁时，v6重新启用中断;它必须做一些记录来处理嵌套的关键部分。这里 push_off 与 pop_off 的代码很值得学习。当嵌套归零时，pop_off 才真正重启原来的的中断。

acquire 代码中写 lk->locked 之前就严格地调用 push_off 很重要。如果两者被逆转，则获取锁并启用中断间会有一个短窗口期。定时中断会使系统陷入死锁。同样，仅在释放锁后，调用 pop_off 。

这是 xv6 禁止锁重入的情况，必须关闭中断。如果允许重入锁，就如前文所提示的，需要类似 push_off 的嵌套写法。只不过这次不是嵌套记录是否关中断，而是嵌套记录重入次数，还需要一个锁（锁中锁）保护这个计数。

如果xv6要使用可重入锁，则必须修改acquire才能注意到锁当前由调用线程持有。我们还必须在结构自旋锁中添加一个嵌套的acquire计数重入，其样式与后面讨论的 push_off 类似。

Atomic Instructions

为了保证获取锁的过程是原子的，请求锁时必须用原子指令。想想，假如是先读后写的指令，又会带来数据竞争问题。

C代码里用的 portable C library 的 __sync_lock_test_and_set 将被编译为 amoswap 指令。RISC-V 提供了 AMO* 系列指令，支持 SWAP, ADD, AND, OR, XOR, MAX, MIN 。用在 acquire 这里的是 amoswap.w.aq 指令，原子性地交换内存与寄存器的内容。其他指令集类似的原子 swap 与 CAS (compare and swap) 指令。

risc-v 指令描述 spin 过程如下，

li t0, 1 # Initialize swap value.
again:
amoswap.w.aq t0, t0, (a0) # Attempt to acquire lock.
bnez t0, again # Retry if held.
# ...
# Critical section.
# ...
amoswap.w.rl x0, x0, (a0) # Release lock by storing 0.

Instruction and memory ordering

指令重排是常用的优化手段。编译器和cpu在重新排序指令时遵循规则，以确保不会改变正确编写的串行代码的结果。然而，规则允许重新排序改变并发代码的结果。这很容易导致多处理器上的错误行为。CPU的排序规则被称为 memory model 内存模型。

l = malloc(sizeof *l);
l->data = data;
acquire(&listlock);
l->next = list;
list = l;
release(&listlock);

如上代码，行 4 与行 6 重排，必然引发并发错误。xv6使用 __sync_synchronize 指示 memory barrier 内存屏障，防止屏障前后的代码重排，这可以确定绝大部分情况的指令顺序（有些例外在下一章节教授）。对应的 RISC-V 指令是 fence 。

以上就是实现 spin lock 的三大问题：

嵌套的中断屏蔽/重入计数
原子指令读写
内存模型的指令重排

Sleep locks

有时xv6需要长时间持有一个锁。例如，文件系统(第8章)在读取和写入磁盘上的内容时将文件锁定，这些磁盘操作可能需要几十毫秒。如果另一个进程想要获取自旋锁，那么长时间持有自旋锁会导致浪费时间片，因为获取自旋锁的进程会在 spin 过程中浪费很长时间的CPU(可重入虽然被切换，还是会消耗时间片；不可重入禁用中断，由于不切上下文更是一直消耗时间片)。

自旋锁的另一个缺点是，进程不能在保留自旋锁的情况下让出CPU;我们希望这样做，以便其他进程可以使用CPU，而带锁的进程等待磁盘。在持有自旋锁时让出CPU是非法的，

因为如果第二个线程试图获取这个自旋锁，导致死锁。第二个线程的 spin 可能会阻止第一个线程运行并释放锁。
在持有锁时让出 CPU 也会违反在持有自旋锁时中断必须关闭的要求(禁止锁重入情形下如此)。

因此，我们需要一种锁，它在等待获取时让出CPU，同时在锁被持时也可以让出CPU(和产生中断)。

lock in lock

具体的 sleep lock 细节在下一章。大体上，一个睡眠锁有一个被自旋锁保护的字段，使得函数 acquiresleep 以原子的方式调用 sleep，从而让出CPU并释放自旋锁。最终，其他线程可以在 acquiresleep 等待时调度执行。

因为 sleep lock 使中断处于启用状态，所以不能在中断处理程序中使用 sleep lock。因为 acquiresleep 可能会让出CPU，所以 sleep lock 不能在 spin lock 临界区内使用(但 spin lock 可以在 sleep lock 临界区内使用)。

自旋锁最适合于较短的临界段，因为等待它们会浪费CPU时间;睡眠锁对长时间操作很有效。

Real World

尽管学术界对并发原语和并行性进行了多年的研究，但使用锁进行编程仍然具有挑战性。通常最好是在 synchronized queues 同步队列等高级结构中隐藏锁。但 xv6 没有这样做。如果使用锁进行编程，那么使用识别 race condition 的工具是明智的，因为很容易错过需要锁的场景。

Pthreads

大多数操作系统都支持POSIX线程(Pthreads)，它允许用户进程在不同的cpu上同时运行多个线程。Pthreads支持用户级锁、屏障等。Pthread还允许程序员有选择地指定锁应该是可重入的。

在用户级别支持 Pthreads 需要操作系统的支持。例如，如果一个pthread阻塞了一个系统调用，那么相同进程的另一个pthread应该能够在该CPU上运行。

另一个例子是，如果一个pthread改变了它的进程的地址空间(例如，映射或取消映射内存)，内核必须安排其他运行相同进程线程的cpu更新它们的硬件页表，以反映地址空间的变化。

Other choice

可以在不使用原子指令的情况下实现锁，但是代价很高，而且大多数操作系统都使用原子指令。

自旋锁也有其他选择，

Don’t share (e.g., per-core data)
Deliberate races
Read-copy-update (later in this class)
Read-write locks
Lock-free algorithms (use atomics)

如果许多cpu试图同时获得相同的锁，那么锁的成本可能会很高。因为如果一个CPU在自己的本地缓存中缓存了一个锁，而另一个CPU也必须获取这个锁，那么更新该锁的原子指令必须将该锁的缓存行从一个CPU的缓存移到另一个CPU的缓存中，并且可能会使该缓存行的其他副本失效。从另一个CPU的缓存中获取数据的代价可能比从本地缓存中获取数据的代价高几个数量级。这需要

Cache coherence
Cache consistency
Link-load, store-conditional

为了避免与锁相关的开销，许多操作系统使用无锁数据结构和算法。例如，在全局链表的读写过程中不需要锁，只需要一条原子指令就可以在链表中插入一个项。但是，无锁编程比编程锁更复杂，必须注意指令和内存的重新排序。使用锁进行编程已经很困难了，所以xv6避免了无锁编程的额外复杂性。

Conclusion

如果仅从开发人员用锁的角度看，

如果不需要共享，尽量就不共享。减少数据竞争可能。
可以从粗粒度锁开始设计。
究竟粒度粗细与 spin/sleep 选择，都需要测量（measure）。Don’t assume, measure!
仅在需要更多并行性时插入细粒度的锁。
使用自动化工具如 race detectors 以寻找锁相关的 bugs

本课还详细教授了自旋锁的实现，主要就是三类重点：

禁止中断/允许锁重入，如何写嵌套禁止/重入计数
spin 使用原子指令
通过 fence 指令使临界区指令不可重排

本质上锁的一切都是为了互斥但不死锁，同时兼顾设计上的粒度与代码的执行效率。

Reference

system-programming