Lec10 Locking

自旋锁、睡眠锁、竞争和锁定序。

Published

2024-04-04

Modified

2024-10-23

1 课前准备

Read “Locking” with kernel/spinlock.h and kernel/spinlock.c .

1.1 竞争

当一个内存位置被并发访问并至少有一次访问写入了数据时，就发生了竞争 (race)。通常的解决办法是使用锁，锁保证了互斥 (mutual exclusion)，因此每次只有一个 CPU 会访问被保护的部分，这个部分称为临界区段 (critical section)。

当我们说锁保护了数据时，我们真正想说的是锁保护了适用于数据的不变量集合。在临界区段中对数据的修改临时破坏了数据的不变量，此时竞争就会发生。

也可认为锁序列化了并发的临界区段以使它们一次一个地执行；或者临界区段被锁保护使其原子化，因此其他部分每次只能看到完整的更改，而非部分更改。

虽然锁可以修正问题，但它导致了效率的低下。如果多个处理器同时想拥有相同的锁，便导致了冲突 (conflict)，或者说这个锁被争用 (contention)。现代内核都会有复杂的组织结构和算法来避免锁争用，但 xv6 做得不多。

1.2 Code：Locks

xv6 有两种锁：自旋锁 (spinlock) 和睡眠锁 (sleep-lock)。先介绍自旋锁。核心是在 struct spinlock 中的 locked 变量，它为 0 时表示空闲，非零时表示被持有。于是获取一个锁可以这么写：

void acquire(struct spinlock *lk) // dose not work!
{
    for(;;) {
        if(lk->locked == 0) {
            lk->locked = 1;
            break;
        }
    }
}

但是第 4 和第 5 行并不是原子的：有可能多个处理器同时访问了第 4 行，并都执行了第 5 行，此时两个处理器都获得了锁。我们希望将这一步变为原子操作，即不可再分的¹。

¹ 你说得对，但是原子现在是可分的了，可以改名叫夸克操作了。

多核处理器一般都提供了上述所需的原子指令。RISC-V 有 amoswap r, a.amoswap，它从内存地址 a 读取值，将寄存器 r 的值写到这个地址，然后将读取的值写入 r。即，它交换了寄存器和地址上的值。它在硬件上保证了操作是原子的。

xv6 在 acquire 中使用的 __sync_lock_test_and_set 最终就是由 amoswap 实现的。它会不断地向 lk->locked 交换 1，并查看交换出来的值：如果交换出来的值是 0，代表锁是空闲的并且 1 被写入，CPU 成功持有了这个锁；否则锁仍被占用。我们持续不断地重试这个步骤，直到成功，这就是为什么被称为自旋。同时，lk-cpu 记录了哪个 CPU 持有了锁，方便调试。

与 acquire 相对的 release 也是同样的策略。从概念上讲，释放锁只需要将 lk->locked 置为零即可，但 C 编译器有可能将赋值转为多条 store 指令，因此它有可能不是原子的。所以我们使用 __sync_lock_release 来进行原子赋值，它的底层仍然是 amoswap。

1.3 Code：Using Locks

对锁粒度的设计是在性能和编码复杂度之间的平衡。xv6 同时有粗粒度（比如 kalloc 对单独的链表设置一个单独的锁）和细粒度（比如对每个文件分别加锁）的锁。一个简单的内核可能会只设置一个线程然后完全不关心锁，将这个单核处理器上的系统移植到多核处理器上只需为整个内核设置一个锁，通常称为大内核锁 (big kernel lock)。

1.4 死锁 (deadlock) 和锁定序 (lock ordering)

如果一条代码路径需要同时持有不同的锁，那么所有代码路径都应该以相同的顺序获取这些锁，否则可能会导致死锁。比如两条代码路径需要锁 A 和 B，第一条先获取 A 再获取 B，第二条相反。那么在第一条获取 A 时，第二条获取了 B。此时第一条需要获取 B，但 B 已经被第二条持有；第二条想获取 A 但已被第一条持有。双方僵持不下，系统永久阻塞。全局锁获取顺序的必要性意味着锁实际上是每个函数规范的一部分：调用者必须以一种使得锁按照约定的顺序被获取的方式来调用函数。

xv6 有许多 lock ordering 的实例。比如 consoleintr，作为处理输入字符的中断例程，需要在一行接收到时唤醒所有等待控制台输入的进程，所以它按顺序持有了 cons.lock 和进程的锁。另一个例子是文件系统，它按顺序持有了每个目录、每个文件的 inode、每个硬盘块缓冲区、硬盘驱动的 vdisk_lock 和每个进程的锁。

对避免全局死锁的 lock ordering 的遵循可能会出乎意料地困难。同时，死锁的危险通常是对 locking scheme 粒度的一个限制，因为更多的锁通常意味着更多的死锁机会。避免死锁的需求通常是内核实现中的一个重要因素。

1.5 可重入 (Re-entrant) 锁

如果一个进程尝试获取它已经得到的锁，内核允许这样做而不是引发 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() 只能被执行一次，要么被 f 要么被 g。但是引入了可重入锁后，如果 h 调用了 g 的话，实际上被执行了两次。由于可重入锁增加了定位问题的困难，xv6 没有使用。

1.6 锁和中断处理

在 xv6 中，有一些自旋锁用于保护同时被线程和中断处理程序使用的数据。例如，tickslock 自旋锁用于保护系统中的时钟滴答数 ticks，该数据既可能被定时器中断处理程序 clockintr 访问（用于增加时钟滴答数），也可能被内核线程在 sys_sleep 中读取（用于等待一段时间）。如果一个内核线程（例如 sys_sleep）持有了 tickslock 自旋锁，并且在此期间被定时器中断触发，那么定时器中断处理程序 clockintr 也会尝试获取 tickslock 自旋锁。然而，由于自旋锁是被线程持有的，clockintr 会发现自旋锁已经被持有，并等待自旋锁被释放。但是，由于线程持有自旋锁的同时又被中断，线程无法继续执行并释放自旋锁，这就导致了死锁。为了避免这种情况，如果一个中断处理程序持有了自旋锁，CPU 上的中断必须被禁用。xv6 做得更加保守：当一个 CPU 获取任何自旋锁时，xv6 会在该 CPU 上禁用中断。这样，中断处理程序在获取自旋锁时会等待线程释放锁，但不会在同一个 CPU 上出现死锁情况。

1.7 指令和内存定序

在当下的编译器和处理器下，指令并不一定按源代码写就的顺序执行。为了性能，指令的处理可能会被拆分和打乱，这有可能导致并发程序出错。为此，编译器和 CPU 通过遵循一系列规则，称为内存模型 (memory model) 来帮助程序员控制指令定序。

xv6 在 acquire 和 release 中使用 __sync_synchronze() 来告诉硬件和编译器不要重新定序。__sync_synchronze() 是一个内存屏障 (memory barrier)，它告诉编译器和 CPU 不要将 load 和 store 定序到超过屏障的位置。

1.8 睡眠锁

在一些操作中，比如文件系统的文件读写操作，需要在磁盘上读取或写入数据，这可能需要花费数十毫秒的时间。在这种情况下，持有自旋锁会导致资源的浪费，因为如果另一个进程想要获取这个锁，那么获取过程中会一直占用 CPU。自旋锁的另一个缺点是，持有锁的进程无法在持有锁的同时让出 CPU。我们希望能够在持有锁的同时让出 CPU，以便其他进程可以使用 CPU，而持有锁的进程可以等待磁盘等操作完成。然而，如果一个线程在持有自旋锁的时候让出 CPU，而另一个线程试图获取这个锁，由于自旋锁的获取过程不会让出 CPU，因此第二个线程会一直在自旋等待，可能会阻止第一个线程重新获得 CPU 资源并继续执行释放锁的操作。因此，我们希望有一种新的锁类型，它在等待获取锁的过程中可以让出 CPU，同时在持有锁的时候也可以让出 CPU（允许中断）。

xv6 引入了睡眠锁。它在等待获取锁的过程中可以让出 CPU，从而允许其他线程执行。acquiresleep 函数负责获取睡眠锁，它在等待期间可以让出 CPU。睡眠锁由两个部分组成：一个是 locked 字段，它用于表示锁的状态；另一个是一个用于保护 locked 字段的自旋锁。当一个线程调用 acquiresleep 函数时，它会尝试获取自旋锁，如果获取成功，它会原子地释放自旋锁并让出 CPU。这样其他线程就有机会执行了。由于睡眠锁允许中断，因此不能在中断处理程序中使用。此外，由于 acquiresleep 可能会让出 CPU，因此不能在自旋锁的临界区内使用睡眠锁。

1.9 Real World

多数操作系统支持 POSIX 线程 (Pthreads)，它提供了用户级锁、屏障等功能，并且允许程序员选择锁是否可重入。在操作系统层面支持 Pthreads 需要相应的支持。例如，当一个线程阻塞在系统调用时，同一进程的另一个线程应该能够在同一个 CPU 上运行。

如果多个 CPU 尝试同时获取同一个锁，那么锁可能会变得非常昂贵。这是因为锁的更新可能涉及缓存行的迁移和失效，从而导致额外的开销。为了避免锁带来的开销，许多操作系统使用无锁数据结构和算法。无锁编程更为复杂，因为需要考虑指令和内存重排序等问题，但可以减少锁带来的开销。xv6 避免了无锁编程的额外复杂性，而是使用了传统的锁机制，尽管在某些情况下可能会导致性能下降。

2 Lecture

没有讲什么新东西。课上讲了 UART 中的锁的一个例子，这里不重复了。

--- title: "Lec10 Locking" order: 11 date: 2024-4-4 date-modified: last-modified description: "自旋锁、睡眠锁、竞争和锁定序。" --- ## 课前准备 > Read "Locking" with `kernel/spinlock.h` and `kernel/spinlock.c` . ### 竞争当一个内存位置被并发访问并至少有一次访问写入了数据时，就发生了**竞争** (race)。通常的解决办法是使用锁，锁保证了**互斥** (mutual exclusion)，因此每次只有一个 CPU 会访问被保护的部分，这个部分称为**临界区段** (critical section)。当我们说锁保护了数据时，我们真正想说的是锁保护了适用于数据的不变量集合。在临界区段中对数据的修改临时破坏了数据的不变量，此时竞争就会发生。也可认为锁**序列化**了并发的临界区段以使它们一次一个地执行；或者临界区段被锁保护使其原子化，因此其他部分每次只能看到完整的更改，而非部分更改。虽然锁可以修正问题，但它导致了效率的低下。如果多个处理器同时想拥有相同的锁，便导致了**冲突** (conflict)，或者说这个锁被**争用** (contention)。现代内核都会有复杂的组织结构和算法来避免锁争用，但 xv6 做得不多。 ### Code：Locks xv6 有两种锁：自旋锁 (spinlock) 和睡眠锁 (sleep-lock)。先介绍自旋锁。核心是在 `struct spinlock` 中的 `locked` 变量，它为 0 时表示空闲，非零时表示被持有。于是获取一个锁可以这么写： ``` {.c code-line-numbers="true"} void acquire(struct spinlock *lk) // dose not work! { for(;;) { if(lk->locked == 0) { lk->locked = 1; break; } } } ``` 但是第 4 和第 5 行并不是原子的：有可能多个处理器同时访问了第 4 行，并都执行了第 5 行，此时两个处理器都获得了锁。我们希望将这一步变为原子操作，即不可再分的[^1]。 [^1]: 你说得对，但是原子现在是可分的了，可以改名叫夸克操作了。多核处理器一般都提供了上述所需的原子指令。RISC-V 有 `amoswap r, a.amoswap`，它从内存地址 `a` 读取值，将寄存器 `r` 的值写到这个地址，然后将读取的值写入 `r`。即，它交换了寄存器和地址上的值。它在硬件上保证了操作是原子的。 xv6 在 `acquire` 中使用的 `__sync_lock_test_and_set` 最终就是由 `amoswap` 实现的。它会不断地向 `lk->locked` 交换 1，并查看交换出来的值：如果交换出来的值是 0，代表锁是空闲的并且 1 被写入，CPU 成功持有了这个锁；否则锁仍被占用。我们持续不断地重试这个步骤，直到成功，这就是为什么被称为自旋。同时，`lk-cpu` 记录了哪个 CPU 持有了锁，方便调试。与 `acquire` 相对的 `release` 也是同样的策略。从概念上讲，释放锁只需要将 `lk->locked` 置为零即可，但 C 编译器有可能将赋值转为多条 store 指令，因此它有可能不是原子的。所以我们使用 `__sync_lock_release` 来进行原子赋值，它的底层仍然是 `amoswap`。 ### Code：Using Locks 对锁粒度的设计是在性能和编码复杂度之间的平衡。xv6 同时有粗粒度（比如 `kalloc` 对单独的链表设置一个单独的锁）和细粒度（比如对每个文件分别加锁）的锁。一个简单的内核可能会只设置一个线程然后完全不关心锁，将这个单核处理器上的系统移植到多核处理器上只需为整个内核设置一个锁，通常称为大内核锁 (big kernel lock)。 ### 死锁 (deadlock) 和锁定序 (lock ordering) 如果一条代码路径需要同时持有不同的锁，那么所有代码路径都应该以相同的顺序获取这些锁，否则可能会导致**死锁**。比如两条代码路径需要锁 A 和 B，第一条先获取 A 再获取 B，第二条相反。那么在第一条获取 A 时，第二条获取了 B。此时第一条需要获取 B，但 B 已经被第二条持有；第二条想获取 A 但已被第一条持有。双方僵持不下，系统永久阻塞。全局锁获取顺序的必要性意味着锁实际上是每个函数规范的一部分：调用者必须以一种使得锁按照约定的顺序被获取的方式来调用函数。 xv6 有许多 lock ordering 的实例。比如 `consoleintr`，作为处理输入字符的中断例程，需要在一行接收到时唤醒所有等待控制台输入的进程，所以它按顺序持有了 `cons.lock` 和进程的锁。另一个例子是文件系统，它按顺序持有了每个目录、每个文件的 `inode`、每个硬盘块缓冲区、硬盘驱动的 `vdisk_lock` 和每个进程的锁。对避免全局死锁的 lock ordering 的遵循可能会出乎意料地困难。同时，死锁的危险通常是对 locking scheme 粒度的一个限制，因为更多的锁通常意味着更多的死锁机会。避免死锁的需求通常是内核实现中的一个重要因素。 ### 可重入 (Re-entrant) 锁如果一个进程尝试获取它已经得到的锁，内核允许这样做而不是引发 panic，那么这种锁就是可重入锁。可重入锁会引入问题，比如： ``` c 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()` 只能被执行一次，要么被 `f` 要么被 `g`。但是引入了可重入锁后，如果 `h` 调用了 `g` 的话，实际上被执行了两次。由于可重入锁增加了定位问题的困难，xv6 没有使用。 ### 锁和中断处理在 xv6 中，有一些自旋锁用于保护同时被线程和中断处理程序使用的数据。例如，`tickslock` 自旋锁用于保护系统中的时钟滴答数 `ticks`，该数据既可能被定时器中断处理程序 `clockintr` 访问（用于增加时钟滴答数），也可能被内核线程在 `sys_sleep` 中读取（用于等待一段时间）。如果一个内核线程（例如 `sys_sleep`）持有了 `tickslock` 自旋锁，并且在此期间被定时器中断触发，那么定时器中断处理程序 `clockintr` 也会尝试获取 `tickslock` 自旋锁。然而，由于自旋锁是被线程持有的，`clockintr` 会发现自旋锁已经被持有，并等待自旋锁被释放。但是，由于线程持有自旋锁的同时又被中断，线程无法继续执行并释放自旋锁，这就导致了死锁。为了避免这种情况，如果一个中断处理程序持有了自旋锁，CPU 上的中断必须被禁用。xv6 做得更加保守：当一个 CPU 获取任何自旋锁时，xv6 会在该 CPU 上禁用中断。这样，中断处理程序在获取自旋锁时会等待线程释放锁，但不会在同一个 CPU 上出现死锁情况。 ### 指令和内存定序在当下的编译器和处理器下，指令并不一定按源代码写就的顺序执行。为了性能，指令的处理可能会被拆分和打乱，这有可能导致并发程序出错。为此，编译器和 CPU 通过遵循一系列规则，称为**内存模型** (memory model) 来帮助程序员控制指令定序。 xv6 在 `acquire` 和 `release` 中使用 `__sync_synchronze()` 来告诉硬件和编译器不要重新定序。`__sync_synchronze()` 是一个**内存屏障** (memory barrier)，它告诉编译器和 CPU 不要将 load 和 store 定序到超过屏障的位置。 ### 睡眠锁在一些操作中，比如文件系统的文件读写操作，需要在磁盘上读取或写入数据，这可能需要花费数十毫秒的时间。在这种情况下，持有自旋锁会导致资源的浪费，因为如果另一个进程想要获取这个锁，那么获取过程中会一直占用 CPU。自旋锁的另一个缺点是，持有锁的进程无法在持有锁的同时让出 CPU。我们希望能够在持有锁的同时让出 CPU，以便其他进程可以使用 CPU，而持有锁的进程可以等待磁盘等操作完成。然而，如果一个线程在持有自旋锁的时候让出 CPU，而另一个线程试图获取这个锁，由于自旋锁的获取过程不会让出 CPU，因此第二个线程会一直在自旋等待，可能会阻止第一个线程重新获得 CPU 资源并继续执行释放锁的操作。因此，我们希望有一种新的锁类型，它在等待获取锁的过程中可以让出 CPU，同时在持有锁的时候也可以让出 CPU（允许中断）。 xv6 引入了睡眠锁。它在等待获取锁的过程中可以让出 CPU，从而允许其他线程执行。`acquiresleep` 函数负责获取睡眠锁，它在等待期间可以让出 CPU。睡眠锁由两个部分组成：一个是 `locked` 字段，它用于表示锁的状态；另一个是一个用于保护 `locked` 字段的自旋锁。当一个线程调用 `acquiresleep` 函数时，它会尝试获取自旋锁，如果获取成功，它会原子地释放自旋锁并让出 CPU。这样其他线程就有机会执行了。由于睡眠锁允许中断，因此不能在中断处理程序中使用。此外，由于 `acquiresleep` 可能会让出 CPU，因此不能在自旋锁的临界区内使用睡眠锁。 ### Real World 多数操作系统支持 POSIX 线程 (Pthreads)，它提供了用户级锁、屏障等功能，并且允许程序员选择锁是否可重入。在操作系统层面支持 Pthreads 需要相应的支持。例如，当一个线程阻塞在系统调用时，同一进程的另一个线程应该能够在同一个 CPU 上运行。如果多个 CPU 尝试同时获取同一个锁，那么锁可能会变得非常昂贵。这是因为锁的更新可能涉及缓存行的迁移和失效，从而导致额外的开销。为了避免锁带来的开销，许多操作系统使用无锁数据结构和算法。无锁编程更为复杂，因为需要考虑指令和内存重排序等问题，但可以减少锁带来的开销。xv6 避免了无锁编程的额外复杂性，而是使用了传统的锁机制，尽管在某些情况下可能会导致性能下降。 ## Lecture 没有讲什么新东西。课上讲了 UART 中的锁的一个例子，这里不重复了。