目录

• 内存管理子系统锁

• 原子操作

  • 原子操作原理

  • 内存管理中的原子操作

• SpinLock 自旋锁

  • 自旋锁原理

  • Spinlock 使用

  • 内存管理中的自旋锁

• 信号量

  • 信号量原理

  • 信号量使用

  • 内存管理中的信号量

• 互斥锁

  • 互斥锁原理

  • 互斥锁使用

  • 内存管理中的互斥锁使用场景

• 读写信号量

  • 读写信号量原理

  • 读写信号量使用

  • 内存管理中的读写信号量使用场景

• 读写锁

  • 读写锁原理

  • 读写锁使用

  • 内存管理中的读写锁使用场景

• RCU 锁

  • RCU 锁原理

  • RCU 锁使用

  • 内存管理子系统的 RCU 锁使用场景

• 顺序锁

  • 顺序锁原理

  • 顺序锁使用

  • 内存管理子系统的顺序锁使用场景

🙂🙂🙂🙂 捐赠一下吧 🙂🙂🙂🙂

内存管理子系统锁

在内存管理子系统中存在各种各样的锁，用于多个请求者之间数据同步、代码顺序执行、共享数据共享。本文的目的用于介绍不同种类锁在内存管理子系统的作用和用法，目前收录的锁和同步机制如下:

• 原子操作: 确保不被打断的操作
• Spinlock: 同一时间只运行一个线程进入临界区，其余线程只能在临界区外排队自旋.
• 信号量: 允许同一时刻指定数量的内核线程进入临界区，其余线程睡眠等待
• 互斥锁: 同一时刻只允许一个线程进入临界区，其余线程睡眠等待
• 读写信号量: 读写互斥，同一时刻多个读者进入临界区，其余线程睡眠等待
• 读写锁: 读写互斥，同一时刻多个读者进入临界区，其余线程排队自旋等待
• RCU 锁: 读者写者同时进入临界区，在没有读者的时候进行写者更新
• 顺序锁: 读者写者同时进入临界区，读者确保读到最新的值，只允许一个写者进入.

原子操作原理

在操作系统里用于数据同步的手段很多，本节介绍一种名为 原子操作 的手段. 所谓原子操作就是该操作绝对不能在执行完毕前被任何其他任务和事件打断. 原子操作的一些典型应用场景:

• 计数器: 原子操作通常用于实现线程安全的计数器。例如，你可能有一个被多个线程共享的计数器，每个线程都可能对它进行增加或减少的操作。通过使用原子操作，你可以确保这些操作的正确性，即使在高并发的环境中。
• 位标志: 原子操作也常常用于设置或清除位标志。例如，你可能有一个标志位字段，表示一些布尔条件。多个线程可能需要检查或修改这些标志位。原子操作可以帮助你在这些操作中保持一致性。
• 单例模式: 在某些情况下，原子操作可以用于实现线程安全的单例模式。你可能需要确保一个对象只被创建一次。通过使用原子的比较和交换操作，你可以实现这个目标。
• 锁的实现: 原子操作常用于实现各种类型的锁，如自旋锁，互斥锁等。锁的基本操作(如锁定和解锁)通常需要原子性来保证正确性。
• 数据结构的并发访问: 原子操作常用于实现无锁数据结构，如无锁队列，无锁栈等。这些数据结构的操作(如入队，出队，入栈，出栈)通常需要原子性来保证一致性。

原子操作是一种强大的工具，但也需要谨慎使用。尽管原子操作可以提供高效的并发控制，但它们也更难以正确地使用和理解。在选择使用原子操作时，应该首先考虑更高级别的并发控制机制，如锁或信号量，除非性能或其他特殊需求使得这些机制不适用. 早在单核(UP)年代就需要原子操作，只是到了多核(SMP)年代原子操作变得更复杂. 在单核系统中，如果 CPU 仅仅从内存读取(READ/LOAD)一个变量，或者仅仅往内存里写入(WRITE/STORE)一个变量，这类操作都是不可打断的, 也是不可被分割的. 原子操作需要硬件支持，因此不同的架构实现不同，Linux 提供了一套原子操作的 API:

内核定义了 atomic_t 类型的原子变量，其有一个结构体构成，内部成员 val 使用 volatile 进行修饰，该关键字会告诉 GCC 不要对该数据类型进行优化，对它的访问都是对内存的访问，而不是从寄存器里访问. atomic_read() 和 atomic_set() 函数是对原子变量最基础的读写操作，其底层由 READ_ONCE() 和 WRITE_ONCE() 宏实现，但这些宏明面上也只是直接赋值，没有借助什么特殊的指令，那么系统如何实现原子操作呢?

内存总线只有一条独占的，无论是多核还是单核，同一时间只有一个核能够独占总线，占用总线的可以是 CPU 或者 DMA，那么此时将占用者称为 Bus Master. 当 Bus Master 读内存时就会占用总线，读完之后在解除对总线的占用，占用期间其他非 Bus Master 无法访问总线，Bus Master 在一次读内存的中间时刻不会被抢占，只有 Bus Master 完成读内存之后内存总线才会被其他抢占，因此对内存的读是一次原子操作，同理写内存也是一次原子操作. 如果 CPU 不是简单的读/写一个变量，而是需要修改一个变量的值，那么它首先需要将变量的值从内存读到寄存器中(Read), 然后修改寄存器中变量的值(Modify), 最后将修改后的值写回到该变量所在的内存位置(Write), 这个操作称为 RMW. 但对于典型的 RMW 操作，其涉及两次内存访问，读和写是可以分别占用总线，但不是持续的占用总线，为了实现原子性，需要在执行指令前加上 LOCK 前缀, 因此 RMW 类指令执行过程中不会被抢占打断.

在早期的 Intel 架构(P6 之前)，原子操作会显式的向系统总线发出 LOCK# 信号，从而获得对应的 CACHE Line 独占权。上图是对该过程的描述，当 CPU 试图获得 CACHE Line 的访问权(读/写)，该 CPU 所在的 Core 需要向 Bus 发出一个 LOCK# 信号，BUS 仲裁器将会以 Round Robin(无优先级轮流) 算法选取某个 Core 获取访问权限，每次只允许一个 Core 获取 CACHE Line 的独占权。从现在的角度来看，这种方式的效率是非常低的，首先读写没有进行区分，读的一致性要求弱于写，一个 Core 获得独占权之后，其他 Core 就只能等待，时延高.

Intel P6 之后的架构，原子操作不再发出任何的 LOCK# 信号，一切都由 CACHE 一致性协议完成。上图是典型的多核架构下的 CACHE 缓存结构，L1/L2 CACHE 为 CORE 私有 CACHE，L3 则由同一个 Socket 上的多个 Core 共享的，那么就存在 CACHE Coherent 问题，通过之前的文章可以知道，硬件通过 MESI 机制保证 CACHE Coherent。对于 X86 则使用了增强版 MESIF, F 代表 Forwarding. 引入 F 的原因是对于一个处于 Shared 状态的 CACHE Line，在多个 Core 中都有一份备份，那么有一个新的 Core 需要读取该 CACHE Line 内存中数据，发现多个 Core 都有副本，那么此时由哪个 Core 提供副本呢？ 如果每个 Core 都应答新 Core 会造成冗余数据，所以将 S 状态下的某个 Core 的 CACHE Line 标记为 F，并且只由 F 负责应答，通常最后持有备份的为 F.

在现代计算机体系结构中，都存在 Store Buffer 和 Invalidate Queue 两个硬件，Store Buffer 可以先缓存没有收到 Invalidate 应答的 Store 操作，Invalidate QUEUE 可以对收到的 Invalidate Message 立刻进行应答，并且当 CPU 要发 Invalidate Message 之前需要清空自己的 Invalidate QUEUE. 有了以上两个硬件，在次会看 CACHE 一致性是如何保证 RMW 指令的原子性.

再回到 RMW 指令，当两个 Core 同时要对同一个地址执行原子操作，也就是试图修改每个 Core 自己持有的 CACHE Line，假设两个 Core 都持有相同内存地址的 CACHE Line，且 CACHE Line 状态为 S，如果这个时候想要成功执行 RMW 原子操作，那么首先需要将 CACHE Line 由 S 转换成 E/M, 则需要向其他 Core Invalidate 该内存地址的 CACHE Line，则两个 Core 同时向 RingBus 发出 Invalidate 操作，那么 RingBus 会根据仲裁协议仲裁哪个 Core 能赢得 Invalidate 权利: 胜利者会独占 RingBus，此时只有胜者可以向其他 CORE 发送 Invalidate Message，失败者只能接受胜利者的 Invalidate Message. 那么两者按如下逻辑保持原子性:

• A: CoreA 和 CoreB 同时执行 RWM 原子操作
• B: CoreA 和 CoreB 同时执行 LOAD 操作，此时 CACHE Line 为 Shared
• C: CoreA 和 CoreB 想要修改 Shared 态的 CACHE Line，那么需要先将 CACHE Line 的状态从 S 变为 E/M, 于是 CoreA 和 CoreB 准备向 RingBus 发送 Invalidate Message，其检查自己的 Invalidate QUEUE 里没有 Message，于是继续向 RingBus 发送信息.
• D: RingBus 同时收到 CoreA 和 CoreB 的 Read Invalidate Message，于是进行仲裁，仲裁结果是 CoreA 是胜利者，获得 RingBus 的独占，于是向其他 Core 转发 Invalidate Message, 只有其他核应答 ACK 之后，胜利者才会解除对 RingBus 的独占。
• E: CoreA 收到其他核的 ACK 之后将 CACHE Line 的状态有 S 变成 E/M，接下来直接 CACHE Line 进行写而无需通知其他 Core.
• F: CoreB 向 RingBus 发送 Invalidate Message 时，由于 RingBus 被 CoreA 独占，那么 Invalidate Message 只能存储在 CoreB 的 Invalidate QUEUE 里.
• G: CoreB 接下来准备执行 RMW 里的写操作，发现 CACHE Line Invalidte Message 已经在 Invlidate QUEUE 里面，那么 CoreB 将自己的 CACHE Line 标记为 Invalidate.
• H: 此时 CACHE Line 在 CoreB 里 CACHE Miss，那么 CoreB 向其他核发送 Read Invalidate Message，此时 RingBus 空闲, CoreB 可以向其他核直接发送 Invalidate Message
• I: CoreA 收到 Read Invalidate 信息之后，将自己的 CACHE Line 标记为无效，并将 CACHE Line 的值发送给 CoreB
• J: CoreB 收到应答之后，并且最新的值也放在 CoreB 的 CACHE Line 里，且 CACHE Line 标记为 E/M，那么 CACHE Line 直接对 CACHE Line 执行写操作.

至此，MESIF 协议大大降低了读操作的延时，但没有让写变得更慢，同时保持了 CACHE Coherent. 对于原子操作来说，其实锁没有消失，只是转嫁到了 RingBus 的总线仲裁协议中，而且大量的多核同时对一个地址执行原子操作会引起反复的相互 Invalidate 同一个 CACHE Line，造成 PINGPONG 效应，同样会降低性能。只能说基于 RWM 操作不能滥用，最好还是使用数据地址范围分离模式更好.

自旋锁原理

自旋锁 Spinlock: 并发编程或多线程环境中一种锁机制，其主要用途是防止多个线程同时访问共享资源. 其工作原理是: 当一个线程尝试获取自旋锁并发现它被其他线程持有时，而不是进入睡眠状态，它会进入一个循环(“自旋”)并且不断地检查锁，直到它变成可用. 在预期锁被持有时间很短的情况下，这种机制是有用的，因为它避免了使线程进入睡眠然后唤醒它的开销。然而如果锁被持有的时间长，自旋锁会导致 CPU 周期的浪费，因此在这种情况下，普通锁或其他同步原语更合适. 可以从以下几个角度了解自旋锁:

• 并发编程角度: 自旋锁是并发编程中一种基础的同步原语，用于保护临界区(所谓临界区就是共享资源在不同地方被使用的区域)，防止多线程同时访问共享资源. 在一个线程获得锁并进入临界区时，其他试图获取该锁的线程会处于忙等待(Busy waiting) 或称为自旋状态，直到锁被释放.
• 性能优化角度: 自旋锁的设计初衷用于锁持有时间非常短的情况，在这种情况下，线程等待获取锁的时间可能会比入睡然后唤醒的时间更短，因此使用自旋锁可能会得到性能提升。然而如果临界区的执行时间长，使用自旋锁可能会导致 CPU 资源浪费，因此在等待获取锁的过程中，线程将一直占用 CPU.
• 操作系统角度: 在操作系统内核中，自旋锁经常用于保护数据结构以防止并发访问。在这种情况下，自旋锁是有用的，因此内核代码通常很短并且在中断中运行，而在这种情况下，线程睡眠通常不是一种选择.
• 硬件角度: 自旋锁在多核架构中是必要的，因为在多核架构中，多个处理器可能会并发访问同一块内存区域，自旋锁通常依靠与硬件提供的原子操作来实现.

Spinlock 的实现经历了很多个版本，了解其历史可以帮助理解 Spinlock 需要解决的本质问题。(Spinlock 历史内容来自 《spinlock前世今生 -- smcdef》):

wild spinlock

Spinlock 是互斥原语，用于不可睡眠上下文环境访问共享数据的互斥，同一时间只能有一个线程可以获得锁，其他不能获得 spinlock 的线程原地自旋，直到获取锁，那么可以实现上图一个简单的版本，在单核架构中，上面的实现是可行的，当 locked 成员为 1，那么表示获得锁，反之 locked 为 0 表示未获得锁。但对于多核架构，spin_lock() 判断到 locked 为 0 的时候将 locked 设置为 1 的操作需要原子性，因此可以修改为:

假设 test_and_set() 是一条原子操作，测试一个变量的值，然后置为 1，返回值是变量的就值. 假设系统有 8 个 CPU 同时申请 Spinlock，CPU0 成功持有锁，那么 CPU1-CPU7 在做什么? test_and_set() 返回旧值为 1，然后原子的无条件设置为 1，由于旧值为 1，那么 while 循环无法结束，CPU1-CPU7 一直在原子写变量.

由于 test_and_set() 原子操作是一个典型的 RMW 操作，在多核架构下，其原子性通过 MESI 协议进行保证。那么可以知道 CPU1 想要对 CACHE Line 进行写操作，那么需要 CACHE Line 处于 E/M 状态，因此 CPU1 首先在 CACHE Line 中查找并发现 CACHE Miss，那么向总线发起 Read Invalidate，此时 RingBus 总线没有被占用，那么 CPU1 独占 RingBus，然后将 Read Invalidate 信息发送给其他核，CPU0 收到 Read Invalidate Message 之后马上存储到自己的 Invalidate QUEUE 里，并将 CACHE Line Copy 和 Invalidate ACK 发送到 RingBus，CPU1 从 RingBus 收到 Invalidate ACK 和 CACHE Line Copy 之后解除对 RingBus 的独占，此时 CACHE Line Copy 存储到了 CPU1 的 CACHE Line 里，CPU 从 CACHE Line 获得了 locked 的值为 1，接下来执行 Store 操作将 1 写入到 CACHE Line，并将 CACHE Line 标记为 Modify. 接下来其他 CPU2-CPU7 执行与 CPU1 一样的操作，此时可能出现多个 Read Invalidate 信息到达 RingBus，然后 RingBus 需要进行仲裁，仲裁之后有一个 CPU 会独占 RingBus 一段时间，这样无形中给 RingBus 带来了带宽压力，使性能下降, 变量在 CPU1-CPU7 的 CACHE 中来回颠簸. Spinlock 的这次改动并不完美，需要解决 CACHE 颠簸导致的带宽压力和性能损失. 我门知道 CACHE Line 有一种状态是 Shared，可以在多个 CPU 之间共享，而不用发送 Invalidate 消息，而且 CPU1-CPU7 一致在自旋，修改变量页没有意义，只有 CPU0 unlock 的时候，修改才有意义，所以对 Spinlock 进行改进:

当 CPU0 获得 locked 之后，其将 locked 设置为 1，并在其 CACHE Line 中标记为 Modify。CPU1 此时读取 locked 的值时 CACHE Miss，那么向 RingBus 发起 Read Message，CPU 收到 Read Message 之后，将 CACHE Line 标记为 Shared 状态并将 CACHE Line Copy 发送给 RingBus. CPU 收到 CACHE Line Copy 并存储在自己的 CACHE Line，标记为 Shared 状态，CPU1 从自己的 CACHE Line 里读取值，发现 locked 为 1，那么继续 while 循环自旋. CPU2 此时也需要读取 locked 的值，可以发送 CACHE Miss，于是向总线发起 Read Message，CPU1 收到 Read Message 信息之后，向 RingBus 发送 ACK 和 CACHE Line Copy, CPU2 收到 ACK 之后，CACHE Line Copy 放到自己的 CACHE Line，然后 CPU2 从 CACHE Line 中读取 locked 的值，此时 locked 值为 1，那么 CPU2 继续执行 while 自旋. 这样 CPU1-CPU7 一致保持 Locked 的 Shared 状态，没有 CACHE 颠簸.

好景不长，CPU0 需要执行 spin_unlock() 时会打破 Shared 平衡，例如 CPU1-CPU7 在原地自旋，CPU0 释放锁的时候，CPU1-CPU7 中的一个 CPU 先看到了 locked 的值，就先获得锁，导致 CPU0 一直无法获得 locked, 最终会出现 CPU0 饥饿现象. 为解决这个问题，接下来认识 ticket spinlock。

ticket spinlock

Spinlock 的实现更接近完美，引入了排队机制，以 FIFO 的顺序处理申请者，谁先申请谁就获得锁, 保证公平性. spin_lock() 函数了的 xadd() 也是一条原子操作，原子的将变量加 1，并返回变量的旧值. 在这个 Spinlock 实现版本中，可以确认当 owner 等于 next 时，代表锁是释放的，否则说明锁是持有状态。next 就像是排队拿票机制，每来一个申请者，next 就加一代表票号，还是以 CPU0-CPU7 进行讲解其实现过程:

• 初始化状态 spinlock 的 owner 和 next 成员都为 0，并且不再任何 CPU 的 CACHE
• CPU0 调用 spin_lock 之后，其本地变量 next 通过 xadd 读取 lock->next 的值为 0，此时读取 lock->owner 的值为 0 与 next 的值相同，那么 CPU0 获得锁，此时 lock->owner 和 next 变量均缓存在 CPU0 的 CACHE 里，lock->owner CACHE Line 状态为 E，next 变量的 CACHE Line 状态为 M，lock->next 也在 CPU0 的 CACHE 里，CACHE Line 状态为 M.
• CPU1 调用 spin_lock 之后，调用原子操作 xadd(), 其是典型的 RWM 操作，那么 CPU1 查找自己的 CACHE 是否有 lock->next, 并返回 CACHE Miss，那么向 RingBus 发送 Read Invalidate Message，CPU0 收到 Read Invalidate Message 之后放入到自己的 Invalidate QUEUE 里，然后将 lock->next 的 CACHE Line Copy 和 Invalidate ACK 发送到 RingBus，CPU0 从 RingBus 上收到 Invalidate ACK 并将 CACHE Line Copy 存储到自己的 CACHE 里，然后 CPU 从 CACHE 里读取 lock->next, 此时 next 的值为 1，那么 CPU1 将 1 写入到 next 变量里，此时 next 在 CPU1 的 CACHE 里，且最后 CACHE Line 的状态是 Modify。接下来 CPU0 读取 lock->owner，此时 CPU0 CACHE 里并没有 lock->owner，于是 CACHE Miss, 接着向 RingBus 上发送 Read Message，CPU0 收到 Read Message 之后，将 lock->owner 的 CACHE Line 状态标记为 Shared，并将 CACHE Line Copy 发送到 RingBus，CPU1 收到 CACHE Line Copy 之后存储在自己的 CACHE 里，最后 CPU1 对比 lock->owner 的值和 next 变量的值，两者并不相等，那么接下来进行 while 自旋循环.
• 同理 CPU2-CPU7 执行和 CPU1 一样的逻辑，最终 CPU 都会存在 lock-owner 的 CACHE Line，且状态为 Shared，另外每个 CPU 各自的 next 变量对应的 CACHE Line 依旧为 Modify 状态.
• 当 CPU0 调用 spin_unlock() 函数时，其发现 lock->owner 的状态为 Shared，那么 CPU0 向 RingBus 发起 Invalidate Message，由于此时只有 CPU 发送 Invalidate Message，那么 RingBus 仲裁 CPU0 获得 RingBus 的独占权，接下向其他 CPU 发送 Invalidate Message，其他 CPU 接二连三的收到 Invalidate Message 之后，将其存储在各自的 Invalidate QUEUE 之后立刻发送 Invalidate ACK 到 RingBus，CPU0 收到所有的 Invalidate ACK 之后，将 lock->owner 的值加 1 并写入自己的 CACHE Line，并将 CACHE Line 标记为 Modify.
• 此时 CPU2 对 lock->owner 进行读，有一种可能就是 CPU2 的 Invlidate QUEUE 信息还没有处理，此时 CPU2 看到自己的 CACHE 里还有 lock->owner 且状态为 Shared，那么此时读到的值为 0，与自己的 next 值不同，继续 while 自旋.
• 此时 CPU1 对 lock->owner 进行读操作，此时 CPU1 已经处理完自己的 Invalidate QUEUE 的信息，lock->owner 对应的 CACHE Line 已经标记为 Invalidate. 那么 CPU1 读 lock->owner 是 CACHE Miss 了，那么其向 RingBus 发送 Read Message。CPU0 收到 Read Message 之后，将 lock->owner 对应的 CACHE Line 标记为 Shared，然后将 CACHE Line Copy 和 ACK 发送到 RingBus，CPU1 收到了 ACK 和 CACHE Line Copy 并存储在自己的 CACHE Line 里，并标记为 Shared，此时 CPU 读取 lock->owner 的值为 1，与本地的 next 值相同，那么 CPU 结束 while 自旋操作, 获得锁。
• 其他 CPU 又回到各自的自旋状态，并且各自的 CACHE 里包含了 lock->owner 的 Copy 且状态为 Shared.

ticket spinlock 虽然解决了排队问题，但随着 CPU 数量增多，RingBus 带宽压力很大，而且延迟也会随着 CPU 增加而增加，性能也会逐渐下降. 而且 CPU0 释放锁之后，CPU1-CPU7 也只有一个 CPU 可以获得锁，理论上没有必要影响其他 CPU 的缓存，只需要影响接下来应该获取锁的 CPU。这说明 ticket spinlock 不是 scalable (同样 wild spinlock 也存在这个问题).

MCS lock

如果在 ticket spinlock 的基础上进一步修改，让每个 CPU 不再是等待同一个 spinlock 变量，而是基于各自不同的 PERCPU 的变量进行等待，那么每个 CPU 只需要检查自己对应的这个变量所在的本地 CACHE Line, 仅在这个变量发生变化的时候，才需要读取内存和刷新这条 CACHE Line，这样就解决了上述问题.

由于 spinlock 底层实现定义为 PERCPU 变量，每个 CPU 访问 spinlock 最终会访问到每个 CPU 自己的本地 MCS lock，此时无需上锁 CPU 就可以操作自己的 MCS Lock，即只需访问自己本地的 CACHE Line 即可，无需所有 CPU 都盯着一个变量.

MCS Lock 的定义如上图，每当一个 CPU 试图获取 Spinlock，那么它就会将自己的 MCS LOCK 加入到这个 spinlock 的等待队列，称为该队列的一个节点，加入的方式是由该队列末尾的 MCS Lock 的 next 成员指向这个新的 MCS LOCK。另外当 MCS LOCK 的 locked 成员值为 1 表示该 CPU 是 spinlock 的持有者，为 0 表示没有持有.

上图是 MCS LOCK 上锁逻辑，之前说过加入队列的方式是添加到末尾(Tail), 所以首先需要知道 Tail 在哪里. 函数的第一个参数 “lock” 指向这个末尾的指针，之所以是一个二级指针，是因为它指向的是末尾节点的 next 域，而 netxt 本身是一个指向 struct mcs_spinlock 的一级指针. 第二个参数 “node” 试图加锁的 CPU 对应的 MCS lock 节点. xchg() 函数的作用是获得队列 Tail 值，然后将 Tail 替换成 node。如果此时 prev(Tail) 为空，表示原始 MCS LOCK 队列为空，那么该 CPU 直接持有 Spinlock; 反之 MCS LOCK 队列不空，那么将原先 Tail 的 next 指向 node，接下来调用 arch_mcs_spin_lock_contended() 进行自旋.

arch_mcs_spin_lock_contended() 函数的实现如上，其调用 smp_cond_load_acquire() 函数，该函数会检查自己 struct mcs_spinlock 的 locked 值是否为 1，如果不等于 1 就一直自旋. 从这里看出，每个 CPU 都是通过检查各自 struct mcs_spinlock 的 locked 变量，那么该变量在本地 CPU CACHE 里大部分时间都是 E 状态的，可以直接读无需通知其他 CPU.

MCS LOCK 解锁通过调用 mcs_spin_unlock() 函数实现，其包含两个参数与 mcs_spin_lock() 函数一致，函数首先调用 READ_ONCE() 原子性的获得该 CPU 之后的下一个应该获得锁对应的 MCS LOCK。如果此时 next 为空，那么表示 MCS LOCK 队列是空的，那么直接将 lock 设置为 NULL，直接释放锁; 反之如果 MCS LOCK 不为空，那么调用 arch_mcs_spin_unlock_contended() 函数:

arch_mcs_spin_unlock_contended() 函数实现原理是将即将获得锁的 MCS LOCK 的 locked 置为 1，那么 MCS LOCK 由自旋状态变成了持锁状态，而刚刚释放锁的 MCS LOCK 并没有将自己的 locked 设置为 0，也没有修改其 next 指针，因为这样做没有意义的，因此 MCS LOCK 是排队的.

MCS LOCK 实现保留在 Linux 源码里，但找不到调用的地方，因为相比起 Linux 中只占用 4 字节的 ticket spinlock，MCS lock 多一个指针，要多占用 4 或 8 字节，消耗的存储空间是原来的 2-3 倍. Spinlock 可是操作系统中使用最广泛的数据结构，这多占的存储空间不可小觑，而且 spinlock 常常会被嵌入到结构体中，对于像 “struct page” 这种结果体大小极为敏感，根本不可能直接使用 MCS LOCK。所以 Linux 真正使用的是 qspinlock，其是在 MCS Lock 基础上进行改进的.

qspinlock

MCS lock 可以解决在锁的争用比较激烈的场景下, CACHE Line 无谓刷新的问题，但它内含一个指针，所以更消耗存储空间，但这个指针又是不可或缺的，因为正是依靠这个指针，持有 spinlock 的 CPU 才能找到等待队列中的下一个节点，将 spinlock 传递给它。本文要介绍的 qspinlock，其首要目标就是把原生的 MCS lock 结构体进行改进，塞进4字节的空间里. 具体细节很复杂，但这篇文章讲的很不错，开发者可以自行参考:

Linux中的spinlock机制[三] - qspinlock

Spinlock 使用

Spinlock 的核心是对拿锁时间很短的场景，拿到锁的线程进入临界区运行，拿不到锁的线程不让出 CPU 的自旋，直到获得锁为止. 接下来通过一个实践案例介绍 Semaphore 的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] Spinlock  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-SPINLOCK-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-SPINLOCK-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义两个内核线程，然后使用 Spinlock 加锁进入临界区，没有获得锁的只能自旋等待锁的释放。模块首先在 17 行定义了一个自旋锁 BiscuitOS_spinlock，然后 BiscuitOS_init() 函数里创建 2 个内核线程但不理解启动，其中 tsk1 运行在 CPU1 上，而 tsk2 运行在 CPU2 上，然后先启动内核线程 tsk1，3s 之后在启动内核线程 tsk2. 内核线程都会调用 kthread_fun() 函数，该函数首先调用 spin_lock() 函数上锁，如果上锁成功，那么进行 while 循环，直到收到线程停止运行之后才结束 while 循环，循环结束之后调用 spin_unlock() 函数释放锁. 没有获得锁的 tsk2 只能在 22 行出自旋，直到 tsk1 释放锁之后才能进行临界区. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread1 先运行并获得了 Spinlock 锁，3s 之后 Kthread2 开始运行，但是由于 Kthread1 还在临界区内，所以 kthread2 虽然运行，但一直在自旋等待锁. 当 Kthread1 退出临界区之后，释放了 Spinlock 锁，Kthread2 进入临界区. 至此 Spinlock 实践完成.

信号量原理

信号量: 并发编程中常见的一种同步机制，在需要控制访问资源的线程数量时就会用到信号量. 信号量的概念是计算机科学家 Dijkstra(Dijkstra算法的发明者)提出来的，广泛应用在不同的操作系统中。系统中会给每一个进程一个信号量，代表每个进程当前的状态，未得到控制权的进程，会在特定的地方被迫停下来，等待可以继续进行的信号到来。如果信号量是一个任意的整数，通常被称为计数信号量(Counting semaphore)，或一般信号量(general semaphore); 如果信号量只有二进制的 0 或 1，称为二进制信号量(binary semaphore)。在linux系统中，二进制信号量(binary semaphore) 又称互斥锁(Mutex). 计数信号量具备两种操作动作，称为 V(signal()) 与 P(wait()). V 操作会增加信号量 S 的数值，P 操作会减少它. 其运行方式如下:

• A: 初始化信号量，给它一个非负数的整数值
• B: 运行 P(wait()), 信号量 S 的值将减少. 企图进入临界区的进程，需要先运行 P(wait())。当信号量 S 减少为负值时，进程会被阻塞，不能继续运行; 当信号量 S 不为负值时，进程可以获准进入临界区.
• C: 运行 V(signal()), 信号量 S 的值会被增加. 结束离开临界区的进程，将会运行 V(Signal()). 当信号量 S 不为负值时，先前被阻塞的其他进程，将可获准进入临界区.

信号量(互斥锁)与自旋锁不同之处是: 使用自旋锁的话，获取锁失败的时候，进入忙等待状态，也就是一直在自旋。而使用信号量(互斥锁)的话，如果获取信号量失败，则相应的进程会被挂起，直到资源被释放，相应的进程才会继续运行。因此信号量只能由可以睡眠的程序使用，像中断和可延时函数不能使用. 信号量使用场景如下:

• 资源管理: 信号量可以用于管理有限的资源。例如，如果你有一台只能同时处理 5 个任务的打印机，你可以使用一个初始值为 5 的信号量来管理打印任务。每次打印开始时，减少信号量的值; 每次打印结束时，增加信号量的值。
• 并发控制: 信号量可以用于控制并发访问的数量。例如，如果你有一个对并发访问敏感的系统，你可以使用信号量来限制同时访问系统的线程数量。
• 互斥锁: 二进制信号量（也称为互斥信号量或互斥量）可以用作互斥锁，以保护临界区或共享资源，防止多个线程或进程同时访问。
• 同步和顺序控制: 信号量也可以用于同步多个线程或进程的执行顺序。例如，一个线程可能在完成一项任务后通过增加信号量的值来通知另一个线程开始执行任务。
• 生产者消费者问题: 在生产者和消费者模型中，信号量可以用于同步生产者和消费者的生产和消费速度。一个信号量用于控制可用空间（对生产者开放），另一个用于控制可用项目(对消费者开放)
• 读者-写者问题: 在处理读者-写者问题时，信号量可以用于保护读写访问，以防止写者和读者或多个写者同时访问数据

Semaphore 使用

Semaphore 的核心是运行一定数量的线程进入临界区，并且没有进入临界区的线程就阻塞睡眠，直到有线程从临界区出来之后唤醒睡眠的线程，那么采用新的线程能进入临界区. 接下来通过一个实践案例介绍 Semaphore 的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] Semaphore  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-SEMAPHORE-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-SEMAPHORE-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用 Semaphore 控制同一时刻最多两个内核线程进入临界区。模块首先在 18 行定义了一个 Semaphore，然后 BiscuitOS_init() 函数里创建 3 个内核线程但不立即启动，然后先启动内核线程 tsk1，2s 之后在运行内核线程 tsk2 和 tsk3. 内核线程都会调用 kthread_fun() 函数，函数首先调用 down() 函数获得 sema 信号量，如果获取成功，那么进行 while 循环，直到收到线程停止运行之后才结束 while 循环，循环结束之后调用 up() 函数解除 sema 信号量. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread1 先运行并获得信号量，2s 之后 Kthread2 和 Kthread3 开始运行，但是由于 Kthread1 还在临界区内，所有只能由一个内核线程再进入临界区，可以看到 Kthread3 进入了临界区，Kthread2 只能睡眠等待. 当 Kthread1 退出临界区之后，唤醒了 sema 的等待队列，Kthread2 进入临界区. 至此 Semaphore 实践完成.

互斥锁原理

如果信号量只有二进制的 0 或 1，称为二进制信号量(binary semaphore), 在linux系统中，二进制信号量(binary semaphore) 又称互斥锁(Mutex). 因此互斥锁的特点就是同一时刻只运行一个线程进入代码临界区，并且没有获得互斥锁的线程将进入睡眠并让出 CPU，待持锁线程从临界区出来释放锁，并唤醒等待的线程。内核提供了一系列 API 实现互斥锁的 PV 操作:

mutex_lock() 函数用于获得互斥锁，如果获取失败则会进入睡眠，mutex_unlock() 函数用于释放互斥锁。与自旋锁一样同一时刻只允许持有锁的线程进入临界区，但不同的是互斥锁在获取锁失败之后不会像自旋锁一样一直占着 CPU 进行自旋，而是进入睡眠，待互斥锁释放时被唤醒重新争取锁，其应用场景如下:

• 共享数据的保护: 当多个线程需要访问和修改同一段共享数据时，可以使用互斥锁来保护这段数据，防止数据在被多个线程同时修改时出现不一致的情况.
• 设备的独占访问: 当多个线程需要访问同一设备时（比如打印机），可以使用互斥锁来确保任何时候只有一个线程能够使用该设备.
• 防止死锁: 互斥锁可以用于避免死锁，即两个或多个线程永久地互相等待。通过设计合理的锁获取和释放策略，可以有效避免死锁的发生.
• 保护代码的执行顺序: 在某些情况下，你可能希望一段代码在另一段代码之后执行。这种顺序可以通过互斥锁来强制实现.

值得注意的是，互斥锁也有它的限制和开销。例如，过度使用互斥锁可能导致性能下降或者死锁。在设计并发系统时，应谨慎使用互斥锁，尽量减少锁的粒度和持有时间，同时要注意避免死锁和饥饿问题.

互斥锁使用

互斥锁的核心是同一时刻只能一个线程进入临界区，并且没有进入临界区的线程就阻塞睡眠，直到有线程从临界区出来之后唤醒睡眠的线程，那么采用新的线程能进入临界区. 接下来通过一个实践案例介绍互斥锁的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] Mutex Lock  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-MUTEX-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-MUTEX-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用互斥锁控制同一时刻只能一个内核线程进入临界区。模块首先在 18 行定义了一个互斥锁，然后 BiscuitOS_init() 函数里创建 3 个内核线程但不立即启动，然后先启动内核线程 tsk1，2s 之后在运行内核线程 tsk2 和 tsk3. 内核线程都会调用 kthread_fun() 函数，函数首先调用 mutex_lock() 函数获得互斥锁信号量，如果获取成功，那么进行 while 循环，直到收到线程停止运行之后才结束 while 循环，循环结束之后调用 mutex_unlock() 函数释放锁. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread1 先运行并获得信号量，2s 之后 Kthread2 和 Kthread3 开始运行，但是由于 Kthread1 还在临界区内，所以 Kthread3 和 Kthread2 只能睡眠等待. 当 Kthread1 退出临界区之后，唤醒了互斥锁的等待队列，Kthread2 进入临界区，Kthread2 退出临界区之后 Kthread3 进入临界区. 至此互斥锁的实践完成.

读写信号量

信号量 可以控制指定数量的线程进入临界区，而读写信号量(rw_semaphore) 只允许:

• 同一时刻只能有一个写者进入临界区
• 同一时刻可以有多个读者进入临界区
• 同一时刻读者和写者不能同时进入临界区

由于读者可以同时获得锁，那么无需睡眠多个读者同时进入临界区，提高了系统的并发程度，进而提高了系统的性能. 内核严格按照先进先出(FIFO)的原则处理等待读/写信号量的进程。读进程或者写进程一旦请求信号量失败，就被写到信号量等待队列的队尾。当信号量被释放后，队列中的第一个进程先被执行，因为它先被唤醒。如果唤醒的是一个写进程，那么队列中其它进程继续休眠。如果唤醒的是一个读进程，写进程之前的所有读进程都会被唤醒获得信号量; 但是写进程之后的读进程继续休眠。读写信号量的使用场景如下:

• 共享数据结构: 如果你有一个数据结构(如链表，哈希表，树等)被多个线程访问，并且读访问比写访问更频繁，那么读写信号量是一个理想的选择。读写信号量允许多个读者同时访问共享数据，但在写者访问时提供了排他访问.
• 文件系统: 文件系统通常使用读写信号量来保护对文件和目录的访问。例如，Linux 内核中的 VFS(虚拟文件系统)使用读写信号量来同步对 inode 和 dentry 结构的访问.
• 数据库系统: 数据库系统也常常用读写信号量来保护对数据库对象(如表，行，索引等)的访问，以确保在进行读操作时的并发性，以及在进行写操作时的一致性和原子性.
• 缓存系统: 在缓存系统中，读写信号量可以用于保护缓存条目的访问，同时允许多个读者并发访问同一个缓存条目。
• 内存管理: 在操作系统的内存管理子系统中，读写信号量可以用于同步对内存区域(如页表)的访问。

读写信号量比普通的二元信号量或互斥锁提供了更高的并发性，但同时也带来了更高的复杂性。在选择使用读写信号量时，应考虑这些因素，以及可能出现的问题，如写者饥饿等.

读写信号量使用

读写信号量的核心是同一时刻只能一个写者线程进入临界区，而允许多个读线程同时进入临界区，但同一时刻读者和写者不能同时进入临界区。这将在读频繁写冷清的场景提供并发性. 接下来通过一个实践案例介绍读写信号量的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] Read/Write Semaphore  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-RW_SEMAPHORE-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-RW_SEMAPHORE-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用使用读写信号量控制对临界区的访问。模块首先在 18 行定义了一个读写信号量，然后 BiscuitOS_init() 函数里创建 3 个内核线程但不立即启动，然后先启动内核线程 tsk1，2s 之后在运行内核线程 tsk2 和 tsk3. tsk1 作为一个写者，而 tsk2 和 tsk3 作为两个读者，如果获取读写信号量成功，那么进行 while 循环，直到收到线程停止运行之后才结束 while 循环，循环结束之后释放读写信号量. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread1 先运行并获得读写信号量，以写着进入临界区，2s 之后 Kthread2 和 Kthread3 开始运行，但是由于 Kthread1 还在临界区内，所以 Kthread3 和 Kthread2 作为写者只能在外面睡眠等待. 当 Kthread1 退出临界区之后，唤醒等待队列里下一个写者之前的所有读者，Kthread2 和 Kthread3 被唤醒，那么两个读者同时进入临界区. 至此读写信号量的实践完成.

读写锁

Spinlock 可以让获得锁的一个线程进入临界区，而其他线程只能自旋等待解锁，不能睡眠，而读写锁(rwlock) 是一种特殊的自旋锁，其只允许:

• 同一时刻只能有一个写者进入临界区，其余线程自旋等待
• 同一时刻可以有多个读者进入临界区，其余写者自旋等待
• 同一时刻读者和写者不能同时进入临界区

由于读者可以同时获得锁，那么无需自旋且多个读者同时进入临界区，提高了系统的并发程度，进而提高了系统的性能. 内核严格按照先进先出(FIFO)的原则处理等待读/写锁的线程。读进程或者写进程一旦请求锁失败，就被写到信号量等待队列的队尾。当锁被释放后，队列中的第一个线程先拿锁。如果第一个线程是读者，那么下一个写者之前的读者都可以拿锁一同进入临界区; 如果队列的第一个线程是写者，那么只有该线程停止自旋进入临界区，其他线程继续自旋. 读写锁应用场景如下:

• 读多写少的共享数据: 如果你有一段数据被多个线程共享，读操作的频率远高于写操作，那么读写锁是一个好的选择。读写锁允许多个读取器同时访问，但在写入器访问时提供了排他访问。
• 大数据结构: 对于大的数据结构，如哈希表、树或图等，读写锁可能比互斥锁更加高效。它可以让多个线程同时读取数据结构，只在需要修改数据结构时才限制并发访问。
• 文件系统和数据库系统: 文件系统和数据库系统通常使用读写锁来同步对文件、记录、页或其他数据结构的访问。例如，Linux内核中的虚拟文件系统（VFS）使用读写锁来同步对文件系统元数据的访问。
• 缓存系统: 读写锁适合于保护缓存系统，其中读取缓存项的操作通常比更新缓存项的操作更频繁。

读写锁提供了比互斥锁更高的并发性，因为它允许多个读取器同时访问。但是，这也引入了更多的复杂性，因为你需要确保写入器不会被饿死（即永远等待读取器完成，从而无法获得写锁）。在选择使用读写锁时，你应该考虑这些权衡，并确保你的代码正确处理读写锁的语义。

读写锁使用

读写锁的核心是同一时刻只能一个写者线程进入临界区，而允许多个读线程同时进入临界区，但同一时刻读者和写者不能同时进入临界区，没有进入临界区的线程原地自旋，这将在读频繁写冷清的场景提供并发性. 接下来通过一个实践案例介绍读写锁的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] Read/Write Lock  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-RWLOCK-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-RWLOCK-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用使用读写锁控制对临界区的访问。模块首先在 18 行定义了一个读写锁，然后 BiscuitOS_init() 函数里创建 3 个内核线程但不立即启动，然后先启动内核线程 tsk1，2s 之后在运行内核线程 tsk2 和 tsk3. tsk1 作为一个写者，而 tsk2 和 tsk3 作为两个读者，如果获取读写信号量成功，那么进行 while 循环，直到收到线程停止运行之后才结束 while 循环，循环结束之后释放读写锁. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread1 先运行并获得读写锁，以写着进入临界区，2s 之后 Kthread2 和 Kthread3 开始运行，但是由于 Kthread1 还在临界区内，所以 Kthread3 和 Kthread2 作为写者只能在临界区外自旋等待. 当 Kthread1 退出临界区之后，自旋等待队列里下一个写者之前的所有读者，Kthread2 和 Kthread3 结束自旋，那么两个读者同时进入临界区. 至此读写锁的实践完成.

RCU 锁原理

RCU(Read-Copy-Update): Linux 内核中的一种同步机制，用于保护数据结构免受并发访问的影响。与其它锁机制(如互斥锁和读写锁)不同，RCU 允许读者并发访问数据结构，甚至在写者正在修改数据结构的时候。RCU 的主要思想是将数据的修改操作分为两个阶段:

• 复制阶段: 在这个阶段，写者复制要修改的数据结构，然后在这个副本上进行修改。在这个阶段，读者可以继续并发地访问原始的数据结构.
• 更新阶段: 在这个阶段，写者等待所有可能访问原始数据结构的读者完成他们的操作，然后更新数据结构的指针，使之指向新修改的副本。新开始的读者将访问新的数据结构，而旧的读者在完成他们的操作后不会再访问旧的数据结构.

RCU 的优点是提供了非常高的读取性能，因为读者不需要获取锁就可以访问数据结构。这使得RCU特别适用于读操作远多于写操作的场景。然而，RCU 也有其缺点。首先，它增加了编程的复杂性，因为程序员需要正确地管理数据结构的生命周期，并确保在更新阶段不会有新的读者访问旧的数据结构。其次，它可能会增加内存使用，因为在更新阶段，旧的和新的数据结构需要同时存在。RCU 的应用场景如下:

• 网络路由表: 网络路由表是一个被多个线程频繁查询但较少修改的数据结构。当路由表更新时，使用RCU可以避免阻塞查询操作，提高查询性能。
• 进程管理: 在 Linux 内核中，进程描述符（task_struct）被各种系统组件频繁访问，但较少修改。当一个进程结束时，内核需要从全局进程列表中移除它的描述符。使用RCU可以避免阻塞正在访问该进程的线程。
• 文件系统: 在文件系统中，inode 和 dentry 结构被各种操作频繁访问，但较少修改。当文件被删除或重命名时，使用 RCU 可以避免阻塞正在访问该文件的操作。
• 缓存系统: 缓存系统常常需要处理大量的查询请求，但较少的更新操作。使用 RCU 可以提高查询性能，避免查询操作被阻塞。
• 大数据结构: 对于大的数据结构，如哈希表、树或图等，RCU 可以提供更高的并发性能，因为它允许多个线程并发读取数据结构，只在需要修改数据结构时才限制并发访问。

注意，RCU 并不适用于所有场景。在写操作频繁或需要强一致性的场景中，使用互斥锁或读写锁可能更合适。在选择使用 RCU 时，你需要考虑你的具体需求和使用场景。

RCU 锁使用

RCU 锁的核心是同一时刻允许多个读者和写者同时进入临界区. 接下来通过一个实践案例介绍 RCU 锁的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] RCU Lock  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-RCU-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-RCU-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用使用 RCU 锁控制对临界区的访问。模块首先在 15-17 行定义了数据结构 struct BiscuitOS_node, 其包含了一个 int 的成员 value. 然后在 18 行定义了 struct BiscuitOS_node 对应的指针 bnode. 模块在 20-22 行定义了三个内核线程，并且提供了线程的执行函数 kthread_read() 和 kthread_write() 函数。kthread_read() 作为读者线程执行的函数，其逻辑是读者线程被调用之后，在 30 行处调用 rcu_read_lock() 进行 RCU 读者上锁操作，并在 32 调用 rcu_dereference() 函数安全的获得 bnode 指针，并存储在 bnp 变量里，如果此时 bnp 不为零，那么打印其 value 的值. 读者线程执行完读操作之后在 36 行调用 rcu_read_unlock() 函数进行 RCU 读者释放锁操作. 然后读者线程延时 1s 之后继续执行，直到线程停止运行为止. kthread_write() 函数为写者线程，当写者线程被调用执行之后，其先调用 kmalloc() 函数新分配内存存储新的 struct BiscuitOS_node 结构体，然后对新的变量进行写操作，写完毕之后在 55 行调用 rcu_replace_pointer() 函数在没有读者的情况下更新 bnode 的值，并将旧的值存储在 old 变量里，然后调用 synchronize_rcu() 函数待更新完成，最后将旧的值进行释放，并进入 1s 延时之后循环，直到线程停止运行. 模块在加载时首先调用 BiscuitOS_init() 函数，该函数创建三个线程，两个读者一个写者，接着唤醒三个线程运行，运行 4s 之后停止运行，这样会出现多个读者和写者同时在临界区内的场景. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread2 读者线程先运行，但此时没有写者所以没有可读的内容，接下来 Kthread1 写者线程运行，并写入 “-297432”, 以此同时 Kthread3 读者也进入临界区，此时可以读到最新的值 “-297432”. 接下来就是读者可以读到最新的值，符合预期，至此 RCU 锁实践完成.

顺序锁原理

顺序锁也是对读写锁 的一种优化，对于顺序锁，读者绝不会被写者阻塞，也就说读者可以在写者对被顺序锁保护的共享资源进行写操作时仍然可以继续读，而不必等待写者完成写操作，写者也不需要等待所有读者完成读操作才去进行写操作。但是写者与写者之间仍然是互斥的，即如果有写者在进行写操作，其他写者必须自旋在那里，直到写者释放了顺序锁。这种锁有一个限制，它必须要求被保护的共享资源不含有指针，因为写者可能使得指针失效，但读者如果正要访问该指针，将导致 OOPs。如果读者在读操作期间，写者已经发生了写操作，那么读者必须重新读取数据，以便确保得到的数据是完整的。这种锁对于读写同时进行的概率比较小的情况，性能是非常好的，而且它允许读写同时进行，因而更大地提高了并发性。顺序锁的使用场景包括:

• 读操作远多于写操作的场景: 由于顺序锁允许读者线程在写者线程持有锁的情况下读取数据，它特别适用于读操作远多于写操作的情况.
• 读操作需要读取多个相关字段的场景: 顺序锁可以保证读者线程读取到的多个字段是一致的。例如，如果你需要读取一个包含多个字段的数据结构，而这些字段需要一起更新，那么使用顺序锁可以保证你读取到的数据是一致的
• 时间敏感的读操作: 在一些场景中，读者线程需要尽快读取数据，不能等待写者线程释放锁。在这种情况下，使用顺序锁可以减少读者线程的等待时间

需要注意的是，顺序锁并不适用于所有场景。特别是在写操作比读操作频繁的场景中，使用顺序锁可能会导致读者线程频繁地重新读取数据，从而降低性能。在这种情况下，使用其他锁机制(如自旋锁或互斥锁)可能更合适.

顺序锁使用

顺序锁的核心是对读写锁的改进，运行读者不被写者阻塞，但多个写者只能有一个写者位于临界区，其余写者自旋. 接下来通过一个实践案例介绍顺序锁的使用，其在 BiscuitOS 上的部署逻辑如下:

cd BiscuitOS
make menuconfig

  [*] DIY BiscuitOS/Broiler Hardware -->
      (4) CPU Number
  [*] Package  --->
      [*] Memory Locking Mechanism  --->
          [*] SeqLock  --->

# 进入源码目录
cd BiscuitOS/output/linux-X.Y.Z-ARCH/package/BiscuitOS-MEMORY-LOCKING-SEQLOCK-default
# 部署源码
make download
# 在 BiscuitOS 中实践
make build

BiscuitOS-MEMORY-LOCKING-SEQLOCK-default Source Code on Gitee

实践案例通过一个内核模块进行展示，其定义三个内核线程，然后使用使用顺序锁控制对临界区的访问。模块首先在 15 行定义了一个顺序锁 BiscuitOS_seqlock, 然后在 16 行定义了共享数据 BiscuitOS_data. 模块在 18-20 行定义了三个内核线程，并且提供了线程的执行函数 kthread_read() 和 kthread_write() 函数。kthread_read() 作为读者线程执行的函数，其逻辑是读者线程被调用之后，在 28-32 行使用一个 do-while 循环，其先在 29 行调用 read_seqlock() 对顺序锁进行上锁操作，并在 32 行调用 read_seqretry() 函数确认读到值有效; kthread_write() 函数为写者线程，当写者线程被调用执行之后，其先调用 write_seqlock() 函数对顺序锁上锁，防止其他写线程进入临界区，之后写入完毕之后调用 write_sequnlock() 函数释放锁. 模块在加载时首先调用 BiscuitOS_init() 函数，该函数创建三个线程，两个读者一个写者，接着唤醒三个线程运行，运行 4s 之后停止运行，这样会出现多个读者和写者同时在临界区内的场景. 那么接下来在 BiscuitOS 上实践该案例:

BiscuitOS 运行之后，直接调用 RunBiscuitOS.sh 运行案例，可以看到 Kthread2 读者线程先运行，但此时没有写者所以没有可读的内容，接下来 Kthread1 写者线程运行，并写入 “-296783”, 以此同时 Kthread3 读者也进入临界区，此时可以读到最新的值 “-296783”. 接下来就是读者可以读到最新的值，符合预期，至此顺序锁实践完成.