细节是魔鬼——基于计数器的锁机制的实现准则

有点标题党了,本意是想把对内核锁机制的一些实现细节记录下来,但多少反映了锁机制实现时的一些准则。本文讨论的锁机制主要指基于计数器的锁机制例如 spinlock、mutex,不包括 RCU 这类锁机制。

parallesim

在讨论各种锁机制之前,有必要讨论系统的并行度,即有哪些潜在的竞争场景

  1. 中断上下文与进程上下文对共享资源的访问,由于中断是异步进行的,因而中断与进程是并发执行的,当中断上下文与进程上下文同时对共享资源进行访问时,就有可能形成竞争
  2. 在 UP 与 SMP 系统中,当处理器是可抢占的时,由于可抢占的特性,同一个处理器内进程与进程间是并发执行的
  3. 在 SMP 系统中,多处理器间的进程是严格意义上的并发执行的

parallesim from preemption

在单处理器上,进程之间的抢占是并行度的一大来源,为了排除进程抢占带来的并行度,在锁机制的实现过程中必须关闭抢占

parallesim from SMP

在 SMP 系统中,多处理器之间是严格并发执行的

目前内核中大部分锁机制使用 counter based locking 来排除多处理器之间的并行度,其原理是维护一个整型数据类型的 counter 计数器,计数器的值就表示可用资源的份数,在申请占用资源的时候计数器就加 1,在申请释放资源的时候计数器就减 1

counter based 的锁机制在实现时都需要考虑 atomic 与 barrier 两个维度

atomic

首先,counter based 的锁机制的核心都是整型数据类型的 counter 计数器,需要保证对计数的操作是 atomic 的

现代处理器架构一般都保证对整型数据类型的 load 或 store 操作原生是 atomic 的,但是锁机制中大量涉及的是 add/sub 即 RMW (Read-Modify-Write) 操作,但是处理器架构一般不能保证 RMW (Read-Modify-Write) 操作原生是 atomic 的

  • x86 架构下使用 LOCK 指令来实现 atomic RMW (read-modify-write)
  • ARM 架构下提供 LDREX/STREX 指令来实现 atomic RMW (read-modify-write)

acquire/release barrier

只有 atomic RMW (read-modify-write) 还不够,因为 memory reordering 可能会将 lock 操作之后的内存访问指令重排到 lock 操作之前执行

update counter
---------------------
LOCK
---------------------
critical area

也有可能将 unlock 操作之前的内存访问指令重排到 unlock 操作之后执行

critical area
---------------------
UNLOCK
---------------------
update counter

因而 counter based 的锁机制还需要实现 acquire/release 语义,从而确保 lock 操作之后的内存访问指令不会重排到 lock 操作之前执行

update counter
---------------------
read acquire (LOCK)
---------------------
critical area stay below the line

unlock 操作之前的内存访问指令不会重排到 unlock 操作之后执行

critical area stay above the line
---------------------
write release (UNLOCK)
---------------------
update counter

这就需要在 lock 操作的最后调用 acquire barrier,在 unlock 操作的最开始调用 release barrier,从而确保 lock/unlock 之间的内存访问指令一定位于 lock/unlock 之间

x86 架构下由于只存在 StoreLoad reorder,因而天生满足 acquire/release 语义,因而 x86 架构下以上这两个 barrier 的定义都为空

aarch64 架构下则使用 dmb 指令实现 acquire/release 语义

parallesim from IRQ

以上 atomic、barrier、preemption 三个维度实现的锁机制,不是中断安全的,即并不能排除中断带来的并行度

如果锁机制需要保护的共享资源不会被中断处理程序访问,即只是在 process context 之间共享,那么以上三个维度 atomic、barrier、preemption 实现的锁机制就完全够用了

而如果共享资源还会被中断处理程序访问,也就是共享资源实际上是在 process context 和 interrupt context 之间共享,那么由 process context 这一方发起的上锁的过程中,还必须关闭全局中断,例如 spinlock 就提供了 spin_lock_irq()/spin_unlock_irq() 这类的接口

上一篇:如何获取微信公众号的关注链接?


下一篇:Block Throttle - Low Limit