主要参考自 《给操作系统捋条线》，加上了自己的笔记。

锁大家都很熟悉了，就是用来进程互斥、实现同步。本文首先介绍锁的实现，然后是 xv6 中锁的使用，xv6 基于锁实现了互斥和同步。

索引：

这里介绍下与锁相关的基本概念

竞争条件比如说多进程要并行读写同一段地址空间，这样很可能会破坏读写原子性，譬如读取到其他写操作的中间状态。显然竞争条件并不是我们想要的，虽然一些竞争条件出现的概率很小，但根据墨菲定律，会出错的总会出错，加之计算机的运行频率，就算出错的概率再小，在某天某时某刻那也是有可能发生的。

所以对于进入临界区访问公共资源我们要避免竞争条件，保证公共资源的互斥排他性，一般有两种大的解决方案来实现互斥

xv6 就根据上面两种方案，分别实现了两个类型的锁，在后面会看到

这里介绍下 sleep、exit、wakeup 三个函数的基本作用，更深层次的，在这些函数中使用的互斥并发，将在介绍了锁后讨论。

这里的 sleep 不是那个系统调用，而是 xv6 的内核函数。chan 表示进程因为什么对象而沉睡？lk 表示管理这个对象的锁。

sleep 大概就干了上面的事：

调用 sched 之后是不会返回的，而是去执行其他进程了，这就是休眠的好处，提高 cpu 的利用率。

wakeup 的作用就是唤醒所有因 chan 而沉睡的进程，具体就是遍历一遍 pcb 数组，然后判断 sleeping && p->chan == chan。wakeup1 是没有加锁版本的 wakeup，一般是获取了锁然后调用这个函数。

这里来看看 exit 函数。在进程的 main 函数执行完后将会系统调用 exit 函数，让子进程回收一部分资源，标记为僵尸态等到父进程回收剩下的资源。

父进程调用 wait 就是用来负责回收子进程，流程为：

简单介绍了几个函数和基本概念，接下来就是锁是怎么实现的了！前面说过，锁分为自旋锁和睡眠锁。首先介绍最简单的自旋锁

有关自旋锁的结构定义如上，最重要的就是 locked 元素，用来表示该锁是否已被某 cpu 取得，1表示该锁已某 cpu 取走，0 表示该锁空闲。其他三个元素用作为 debug 调试信息。

因为锁不属于信号量，所以 locked 最多只能为1，这应该很清楚了。

这部分就是初始化锁的名字、设置为空闲、没有 CPU 持有该锁

开关中断这两个函数在请求锁、释放锁的时候会被用到。这里看下函数原理：pushcli 和 popcli 为 cli 和 sti 的封装函数，只是增加了计数，每个 popcli 与 pushcli 匹配，有多少次 pushcli 就要有多少次 popcli，只有第一次 pushcli、最后一次 popcli 才会开关中断。

在持有锁的过程中，进程将不会处理中断，因此后面本文的讨论中，只要拥有一个锁，此时是不会因时间片到期放弃 CPU 进入调度的。

为什么使用 pushcli() 和 popcli() 而不是使用 cli() sti() 后面详细说明。

holding 函数是在关中断下检查锁是否被某 CPU 取走，仔细看检查是否持有锁的条件为两个：一是锁是否被取走，二锁是否由当前 CPU 取走。

由于不一定持有锁，所以为了保证获取信息这个操作的原子性，需要关中断下执行，避免被调度。

关中断下进行取锁的操作，以避免死锁，原因见后面 FAQ

acquire 检查当前 CPU 是否已经持有锁，如果已持有，则 panic()，也就是说 xv6 不允许同一个 CPU 对同一个锁重复上锁。

上锁的语句为 xchg(&lk->locked, 1)，xchg 函数可以看作一个原子赋值函数(本是交换，与 1 交换就相当于赋值）

因取锁可能需要一直循环等待，所以名为自旋锁。

__sync_synchronize() 是发出一个 full barrier，简单来说就是不允许将这条语句之前的内存读写指令放在这条之后，也不允许将这条语句之后的内存读写指令放在这条指令之前。

由于编译器翻译成汇编代码是乱序的，在 xchg 获得锁之前，后面关于 debug 的语句可能提前执行，这条指令就能保证需要等到获取锁之后，才会执行 debug 相关的汇编指令。

释放锁主要就是将 lk->locked 设置为 0，其他进程被调度到时如果检测到锁为空闲，将会重新上锁，访问互斥资源。

Ⅰ xv6 内核 scheduler 的开中断

在 proc.c 中可以看到

执行 scheduler 的时候是开中断的，内核中只有 scheduler 函数会短暂的开中断的，其他时候都是关中断的。而如果做过 jos 就知道，jos 在内核态下是全程关中断的。

造成两者区别的原因是：

因此，xv6 的 scheduler 要定时开中断，如果 scheduler 一直无限运行下去，就不能执行中断处理程序。

Ⅱ xv6 加锁为什么要使用 xchg()

我们知道 xchg 是硬件提供的原子指令，xchg(&lk->locked, 1) 具体执行了下面两件事：

假如这个语句不是原子的，那么同时可能有多个 cpu 标记为 lk->locked = 1，然后返回。最后，有多个 cpu 访问互斥资源，显然是错误的。

Ⅲ acquire() 加锁函数的关中断

为什么要关中断呢？由于 scheduler 在 acquire 之前临时开中断，所以现在内核态下，是可以收到中断然后运行中断处理程序的。假设加锁时没有没有关中断，这里划分为几个时间点下产生中断：

逐一分析。假设在 xchg 指令前发生中断，中断处理程序中可能会获取到和 acquire 相同的锁，因为此时内核代码还没有获取锁，所以不会发生死锁；假设在 xchg 指令后发生中断，中断处理程序中可能会请求和 acquire 相同的锁，由于先前该 CPU 的 scheduler 已经获取了锁，中断处理程序将自旋或者沉睡，发生死锁；假设在 release 函数前发生中断，和上面同理，将会发生死锁；

因此，我们需要在 xchg 前关中断，可以回答下面几个问题：

release() 函数先原子赋值释放锁再开中断，也就同理了，如果两者交换先开中断，那么在释放锁之前可能发生中断，而中断处理程序刚好需要该锁，那么发生死锁。

Ⅳ xv6 的竞争条件有哪些？

可能的情况如下，下面逐一分析：

xv6 是个支持多处理器的系统，各个 CPU 之间可以并行执行，所以可能会出现同时访问公共资源的情况，是一个竞争条件。

在单个 CPU 上，内核态下，scheduler 是开中断的，所以内核代码可能会和中断处理其程序并发执行，并发的进入临界区。前面提到过，取锁时关中断，内核代码就不会切换到 scheduler，所以不是竞争条件。

xv6 不支持线程，而各个进程之间内存是不共享的，加之内核进入临界区访问公共资源的时候是关了中断的，关了中断除了自己休眠是不会让出 CPU 的，所以运行在单个处理器上的各个进程之间的并发其实并不会产生竞争条件。

Ⅴ 关中断开中断为什么要使用 pushcli() 和 popcli() 而不直接使用 cli() 和 sti()?

为什么要使用 pushcli() 和 popcli()，其实也简单，那是因为某个函数中可能要取多个锁，比如先后取了锁 1 锁 2，那么释放锁 2 之后能开中断吗？显然不能，必须等锁 1 也释放的时候才能开中断。所以使用增加了计数功能的 pushcli() 和 popcli() 来实现最后一个锁释放的时候才开中断。

Ⅵ 内存乱序问题

现今的指令的执行都有流水线的技术，其实还有乱序执行。乱序执行指的是在 CPU 运行中的指令不按照代码既定的顺序执行，而是按照一定的策略打乱后顺序执行，以此来提高性能。

在一些时候，我们不希望指令顺序被打乱，为避免这种情况，我们设置了屏障，禁止这个屏障前后的指令顺序打乱

xv6 里面还提供了另一种锁，休眠锁，它在自旋锁的基础之上实现，定义如下：

休眠锁配了一把自旋锁来保护，原因见后。休眠锁的意思是某个进程为了取这个休眠锁不得而休眠，所以有个 pid 来记录进程号。

休眠锁的初始化，检验是否持有锁等都类似，就不赘述了，再这里主要看看取锁和解锁的区别：

睡眠锁需要保证 检测锁状态、上锁操作、休眠操作 这几个操作是原子的，在自旋锁中由于只需要保证前两个操作，所以使用 xchg 指令就可以实现。

原子性即代表当前 CPU 不发生调度、其他 CPU 执行 acquiresleep 需要互斥。因此睡眠锁使用 xchg 很难保证原子性，这里 xv6 使用自旋锁，就能很好的保证睡眠锁的原子性。

这里使用自旋锁的 acquire、release 就保证了原子性。在获取自旋锁后，如果此时休眠锁上锁，将会调用 sleep 函数放弃自旋锁并陷入沉睡。如果此时休眠锁空闲，将设置 lk->locked 表示上锁，并且记录进程的 pid。

解锁操作基本上就是上锁的逆操作，注意一点，可能有其他进程休眠在休眠锁上，所以当前进程解锁后需要唤醒休眠在休眠锁上的进程，wakeup 将会请求表锁，查找因为休眠锁沉睡的进程。

锁同步的问题一直是操作系统里面最为复杂的问题之一，，xv6 的锁设计本身不难，难得是锁的使用，这里就根据进程这一块使用锁的地方来简单聊一聊，进程中与锁的有关地方主要有休眠，唤醒，等待，退出，调度，切换。

休眠是休眠在某个对象上，唤醒是唤醒休眠在某个对象上的进程，所以想当然的可以这样来声明 sleep 和 wakeup：

那这样声明对不对呢？来看个用户态下，简单的变种生产者消费者的例子

乍一看感觉没什么问题，但是由于我们不能保证进程被调度到的顺序。如果 wakeup 发生在 sleep 之前就会引起死锁:

比如上面这种在单处理器上并发的情况，指令执行顺序如下：

综上，由于 sleep 发生在 wakeup 之前，陷入死锁。就算不是中断，因为是多处理器，两者运行的时间是不确定的，完全也可能出现上述的情况。

避免这种前后感知的信息不一致的办法就是加锁，来看第二个版本：

第二种版本做了一个修改，保证生产者和消费者操作的原子性，生产者、消费者读取对象、使用对象、唤醒、沉睡是一个原子操作，在解锁前不会被调度和抢占。

回到上面的问题，此时不会再出现消费者在 sleep 前被调度，lost wakeup 的情况。recv 在准备 sleep 之前获得了 obj_lock，send 没有 obj_lock，是不可能 wakeup 的，所以休眠就不会错过唤醒。

这个问题倒是解决了，又有一个新问题，如果进程带着 obj_lock 休眠不释放的话，同样死锁。

因此将 sleep 的接口定义为：

这个锁作为 sleep 的参数，在进程进入休眠状态时释放该锁，在进程返回时重新获取该锁。

也就是说，在 sleep 函数中，修改进程状态前要先释放锁，然后才修改为 SLEEPING，让出 CPU。为了保证在释放锁后，不会出现 sleep 错过 wakeup 的情况，修改进程状态和释放锁需要是一个原子操作。

由于涉及到了进程状态的修改，所以 xv6 选择用 ptable.lock 来保证上面操作的原子性。

在放弃 CPU 前：

sched 将会交出 CPU，等到该进程被 wakeup，重新获取 CPU。在重新拥有 CPU 后：

进程变为 SLEEPING 之后将不会被调度到，因此 sleeplock 减少了 CPU 的负担，不会再让一个CPU忙等，而是合理放弃 CPU。

特殊情况在于，如果 lk = 表锁，那么放弃 cpu 前不请求表锁，拥有 cpu 后不放弃表锁。休眠对象是一个进程，在 xv6 中，这种情况只发生在 wait 函数中，父进程等待子进程退出，这个时候它休眠在自己身上。

然后是 wakeup 函数，分为两个部分：不加锁的 wakeup1 和加锁版本的 wakeup。这么划分是因为，在有些情况下已经获取了表锁，直接调用 wakeup 会死锁，详见下面的 wait 函数。

这里来看看 exit 函数

首先第一个进程是不能退出的，如果退出直接报错。他需要用来回收子进程和孤儿进程的资源

子进程会自己回收掉一部分资源。比如打开文件描述符表，这一部分关闭所有文件，如果减到 0，再释放该文件的 inode，如果文件的链接数和引用数都为 0 了，就删除该文件。

和前文对应，由于 exit 函数已经拥有了表锁，为了避免死锁，使用不加锁版本的 wakeup1。

然后是要唤醒父进程，通知父进程来回收自己。这里还会抛弃当前进程的所有子进程，子进程成为孤儿进程，将孤儿进程的父进程修改为 init 进程，让 init 进程负责回收资源。最后将自己的状态设置为 zombie，父进程将在 wait 调用中回收 zombie 的子进程。

因为这个操作会修改进程状态，所以执行前要获取表锁。提一嘴，虽然这里是获得了锁，sched 函数需要当前进程持有锁，后面会看到设计的原因。

为什么要父进程负责回收呢？私以为，因为子进程在内核中运行时还要使用到页表、内核栈、进程结构体，如果直接回收，执行下一条内核代码将会报错，影响系统执行，所以这些资源等到父进程回收为好。

父进程调用 wait 就是用来负责回收子进程，流程为：

exit 和 wait 如何保证原子性和防止死锁（没有 lost wakeup）？因为他们使用表锁进行互斥，正好符合上面所说的生产者消费者模型

切换进程的流程是：进程 A --> scheduler --> 进程 B。进程 A 切换到调度进程是使用 sched 函数，sched 函数是 swtch 函数的封装。当切换回 scheduler 时，除了返回对应的切换上下文外，此时 scheduler 还需要保证关中断和拥有 ptable.lock。

在 swtch 和 scheduler 执行的过程中，必须要持有表锁。要知道执行 swtch 是会切换进程的，因为这个锁在一个进程中获取，在另一个进程中释放。这样使用锁很不常见，但这里是必须的。

也就是说，sched 是进程 A 取锁，进程 B 放锁。即使是 sched 之后的语句一般会来个放锁操作，新进程也是如此。

因此在进入 sched 前一定要获取 ptable.lock，进入调度有多种情况，我们逐一分析及验证：

在 trap.c 中，当进程因为时间中断进入中断处理时，将会 yield 放弃 CPU。

yield 对应于前文，首先要获取 ptable.lock 这把锁，更改状态为 RUNNABLE。

如果在 swtch 没有持有表锁会怎么样？例如：CPU 0 调用 yield 放弃进程A，然后 yield 中设置进程状态为 RUNNABLE。CPU0 在执行 sched 之前另一个 CPU1 会调度进程 A，在这短暂的时间内，这样的话一个进程运行在两个 CPU 上，内核栈将会发生错误。

sched 函数首先执行了一些检查：

intena 这里表示 pushcli 之前 CPU 允许中断的情况。这个值保存下来等待进程被调度到时，用来恢复 CPU 的中断情况，保证在同一个进程里中断允许情况一致。比如说在进程 A 放弃CPU之前是开中断，进程 A 恢复执行后，在 yield 中将会 popcli 恢复开中断。

在 scheduler 中仍然还是关中断，等到调度到进程 B 后。

进程 B 在这里恢复 CPU 的中断情况

跳转回到 yield 函数，释放表锁，成功对应上文：进程A上锁，进程B解锁。从 yield 返回后就是跑到 trapret 恢复进程执行了，这里就不再多说。

假如是调度到一个新进程，新进程的第一条指令（不是用户指令啊！）是 forkret，在这里将会释放表锁，完成”进程B解锁“。

sleep 前面也看过了

在 sched 函数前会获取表锁，sched 函数后释放表锁，也就保证了前面说的。进程 A 上锁，进程B解锁。进入 sched 的状态不是 RUNNING!!

sleep 什么时候被使用到呢？

exit 也是在 sched 前获取锁，然后设置为僵尸态。