一、操作系统是如何实现锁的？

• 首先要搞清楚一个概念，在硬件层面，CPU 提供了原子操作、关中断、锁内存总线的机制；OS 基于这几个 CPU 硬件机制，就能够实现锁；再基于锁，就能够实现各种各样的同步机制（信号量、消息、Barrier 等）

• 在多线程编程中，为了保证数据操作的一致性，操作系统引入了锁机制，用于保证临界区代码的安全。通过锁机制，能够保证在多核多线程环境中，在某一个时间点上，只能有一个线程进入临界区代码，从而保证临界区中操作数据的一致性。

• 锁机制的一个特点是它的同步原语都是原子操作

• 操作系统之所以能构建锁之类的同步原语，是因为硬件已经为我们提供了一
  些原子操作，例如：
  1. 中断禁止和启用（interrupt enable/disable）
  2. 内存加载和存入（load/store）测试与设置（test and set）指令

• 禁止中断这个操作是一个硬件步骤，中间无法插入别的操作。同样，中断启用，测
  试与设置均为一个硬件步骤的指令。在这些硬件原子操作之上，我们便可以构建软
  件原子操作：锁，睡觉与叫醒，信号量等

二、操作系统使用锁的原语操作

• 可以使用中断禁止，测试与设置两种硬件原语来实现软件的锁原语。这两种方式比较起来，显然测试与设置更加简单，也因此使用的更为普遍。此外，test and set还有一个优点，就是可以在多 CPU 环境下工作，而中断启用和禁止则不能

• 使用中断启用与禁止来实现锁： 要防止一段代码在执行过程中被别的进程插入，就要考虑在一个单处理器上，一个线程在执行途中被切换的途径。我们知道，要切换进程，必须要发生上下文切换，上下文切换只有两种可能：
  1. 一个线程自愿放弃 CPU 而将控制权交给操作系统调度器（通过 yield 之类
  的操作系统调用来实现）；
  2. 一个线程被强制放弃 CPU 而失去控制权（通过中断来实现）
  (1)原语执行过程中，我们不会自动放弃 CPU 控制权，因此要防止进程切换，就要在原语执行过程中不能发生中断。所以采用禁止中断，且不自动调用让出 CPU 的系统调用，就可以防止进程切换，将一组操作变为原子操作。
  (2)中断禁止：就是禁止打断，使用可以将一系列操作变为原子操作
  (3)中断启用：就是从这里开始，可以被打断，允许操作系统进行调度
  (4)缺点：使用中断实现锁，繁忙等待，不可重入

• 使用测试与设置指令来实现锁
  测试与设置（test & set）指令：以不可分割的方式执行如下两个步骤：
  1. 设置操作：将 1 写入指定内存单元；
  2. 读取操作：返回指定内存单元里原来的值（写入 1 之前的值）
  缺点：繁忙等待，不可重入

三、操作系统中的锁机制

• 互斥锁：mutex，用于保证在任何时刻，都只能有一个线程访问该对象。只有取得
  互斥锁的进程才能进入临界区，无论读写，当获取锁操作失败时，线程会进入睡眠，
  等待锁释放时被唤醒

• 读写锁：rwlock，分为读锁和写锁。读写锁要根据进程进入临界区的具体行为（读，写）来决定锁的占用情况。这样锁的状态就有三种了：读加锁、写加锁、无锁。
  1. 无锁。读/写进程都可以进入；
  2. 读锁。读进程可以进入。写进程不可以进入；
  3. 写锁。读/写进程都不可以进入

• 自旋锁：spinlock，自旋锁是指在进程试图取得锁失败的时候选择忙等待而不是阻
  塞自己。
  (1)选择忙等待的优点在于如果该进程在其自身的 CPU 时间片内拿到锁（说明
  锁占用时间都比较短），则相比阻塞少了上下文切换
  (2)注意这里还有一个隐藏条件：多处理器。因为单个处理器的情况下，由于当前自旋进程占用着 CPU，持有锁的进程只有等待自旋进程耗尽 CPU 时间才有机会执行，这样 CPU 就空转了

• RCU：read-copy-update，在修改数据时，首先需要读取数据，然后生成一个副本，对副本进行修改，修改完成后，再将老数据 update 成新的数据。【有点像copy-on-write】
  (1) 使用 RCU 时，读者几乎不需要同步开销，既不需要获得锁，也不使用原子指令，不会导致锁竞争，因此就不用考虑死锁问题了。
  (2) 对于写者的同步开销较大，它需要复制被修改的数据，还必须使用锁机制同步并行其它写者的修改操作。
  (3)在有大量读操作，少量写操作的情况下效率非常高。【读多写少】