English

通用互斥锁子系统

由 Ingo Molnar 发起 <mingo@redhat.com>

更新者：Davidlohr Bueso <davidlohr@hp.com>

什么是互斥锁？

在 Linux 内核中，互斥锁（mutex）指的是一种特定的锁原语，用于在共享内存系统上强制实现序列化，而不仅仅是指学术界或类似理论教科书中“互斥”（mutual exclusion）的通用术语。互斥锁是休眠锁（sleeping locks），其行为类似于二值信号量（binary semaphores），并于 2006 年[1]引入作为这些信号量的替代方案。这种新的数据结构提供了许多优点，包括更简单的接口，以及在当时更小的代码量（参见缺点）。

[1] https://lwn.net/Articles/164802/

实现

互斥锁由“struct mutex”表示，定义在 include/linux/mutex.h 中，并在 kernel/locking/mutex.c 中实现。这些 locks 使用原子变量（->owner）来跟踪其生命周期内的锁状态。字段 owner 实际包含指向当前锁所有者的 struct task_struct *，因此如果当前没有被拥有，则为 NULL。由于 task_struct 指针至少按 L1_CACHE_BYTES 对齐，因此低位（3位）用于存储额外的状态（例如，等待者列表是否非空）。在其最基本的形式中，它还包括一个等待队列和一个用于将其访问串行化的自旋锁。此外，CONFIG_MUTEX_SPIN_ON_OWNER=y 系统使用一个旋转者 MCS 锁（->osq），如（ii）中所述。

获取互斥锁时，根据锁的状态，可以走三条可能的路径

  1. 快速路径（fastpath）：尝试通过用当前任务对 owner 进行 cmpxchg() 操作来原子性地获取锁。这仅在无竞争的情况下有效（cmpxchg() 检查是否为 0UL，因此上述所有 3 个状态位必须为 0）。如果锁有竞争，则进入下一条可能的路径。

  2. 中间路径（midpath）：又称乐观自旋（optimistic spinning），在锁所有者正在运行且没有其他更高优先级的就绪任务（need_resched）时，尝试自旋以获取锁。其基本原理是，如果锁所有者正在运行，它很可能会很快释放锁。互斥锁自旋者使用 MCS 锁排队，以便只有一个自旋者可以竞争互斥锁。

    MCS 锁（由 Mellor-Crummey 和 Scott 提出）是一个简单的自旋锁，具有公平性以及每个尝试获取锁的 CPU 在局部变量上自旋的理想属性。它避免了常见的 test-and-set 自旋锁实现所引起的昂贵的缓存行反弹。类 MCS 锁专门针对休眠锁实现的乐观自旋进行了定制。定制版 MCS 锁的一个重要特性是它具有一个额外属性：当需要重新调度时，自旋者能够退出 MCS 自旋锁队列。这进一步有助于避免以下情况：需要重新调度的 MCS 自旋者继续等待在互斥锁所有者上自旋，结果在获得 MCS 锁后直接进入慢速路径。

  3. 慢速路径（slowpath）：最后的手段，如果仍无法获取锁，任务将被加入等待队列并休眠，直到被解锁路径唤醒。在正常情况下，它会作为 TASK_UNINTERRUPTIBLE 阻塞。

尽管从形式上讲内核互斥锁是可休眠的锁，但正是路径 (ii) 使得它们在实际中更接近于混合类型。通过简单地不中断任务并在几个周期内进行忙等待而不是立即休眠，人们发现这种锁的性能显著改善了许多工作负载。请注意，这种技术也用于读写信号量（rw-semaphores）。

语义

互斥锁子系统检查并强制执行以下规则

  • 同一时间只能有一个任务持有互斥锁。

  • 只有所有者才能解锁互斥锁。

  • 不允许多次解锁。

  • 不允许递归加锁/解锁。

  • 互斥锁必须只能通过 API 进行初始化（见下文）。

  • 任务持有互斥锁时不得退出。

  • 持有的锁所在的内存区域绝对不能被释放。

  • 已持有的互斥锁不得重新初始化。

  • 互斥锁不得用于硬件或软件中断上下文，例如 tasklet 和定时器。

当启用 CONFIG_DEBUG_MUTEXES 时，这些语义将被完全强制执行。此外，互斥锁调试代码还实现了许多其他功能，使锁调试更加简单和快速

  • 每当在调试输出中打印互斥锁时，使用它们的符号名称。

  • 获取点跟踪、函数名的符号查找、系统中持有的所有锁的列表及其打印输出。

  • 所有者跟踪。

  • 检测自我递归锁并打印出所有相关信息。

  • 检测多任务循环死锁，并打印出所有受影响的锁和任务（且仅打印这些任务）。

互斥锁（以及大多数其他休眠锁，如 rwsem）不为其占用的内存提供隐式引用，该引用通过 mutex_unlock() 释放。

[ 这与 spin_unlock() [or completion_done()] 相反，后者

的 API 可用于保证在 spin_unlock()/completion_done() 释放锁后，锁实现不会再触碰该内存。 ]

mutex_unlock() 甚至在其内部已经释放锁之后，仍可能会访问互斥锁结构——因此，另一个上下文获取互斥锁并假设 mutex_unlock() 上下文不再使用该结构是不安全的。

互斥锁用户必须确保在释放操作仍在进行时互斥锁不会被销毁——换句话说，mutex_unlock() 的调用者必须确保互斥锁一直存活，直到 mutex_unlock() 返回。

接口

静态定义互斥锁

DEFINE_MUTEX(name);

动态初始化互斥锁

mutex_init(mutex);

获取互斥锁，不可中断

void mutex_lock(struct mutex *lock);
void mutex_lock_nested(struct mutex *lock, unsigned int subclass);
int  mutex_trylock(struct mutex *lock);

获取互斥锁，可中断

int mutex_lock_interruptible_nested(struct mutex *lock,
                                    unsigned int subclass);
int mutex_lock_interruptible(struct mutex *lock);

获取互斥锁，可中断，如果减到 0

int atomic_dec_and_mutex_lock(atomic_t *cnt, struct mutex *lock);

解锁互斥锁

void mutex_unlock(struct mutex *lock);

测试互斥锁是否已被获取

int mutex_is_locked(struct mutex *lock);

缺点

与其最初的设计和目的不同，“struct mutex”是内核中最大的锁之一。例如：在 x86-64 上它是 32 字节，而“struct semaphore”是 24 字节，rw_semaphore 是 40 字节。更大的结构体大小意味着更多的 CPU 缓存和内存占用。

何时使用互斥锁

除非互斥锁严格的语义不适用和/或临界区阻止了锁的共享，否则在任何情况下都应优先选择互斥锁，而不是其他任何锁原语。