锁实现分析:从glibc到futex
之前在理解条件变量时在futex上误入歧途,导致犯下死锁的错误,并且写下了错误的博文,见浅析条件变量
所以打算重新理解一下futex
虽然初衷是futex,但是由于futex最初是为了优化锁的性能而提出,因此深入理解futex实际上是对锁概念的深入了理解
因此本篇的大纲
源码分析从c++的mutex开始,然后是glibc的nptl库pthread_mutex,接着是linux内核的futex实现
在源码分析完成以后,尝试对锁这个概念进行深入的分析,说明futex的诞生原因
C++的std::mutex源码分析
先看下g++版本
1 | g++ --version |
然后在/usr/include/c++/9/bits/std_mutex.h
有如下代码,做了一些可读性调整
1 | class __mutex_base { |
可以看到c++的std::mutex几乎没有任何逻辑,就只是简单的对pthread的封装
持有了一个pthread_mutex_t类型的_M_mutex,并对其pthread_mutex_lock和pthread_mutex_unlock
glibc的mutex源码分析
pthread的实现实际上是glibc的NPTL代码
NPTL
是Native POSIX Thread Library的缩写。这是Linux的一个线程库,它提供了一种实现POSIX线程(或称为Pthreads)的方法。NPTL被设计为可以提供高性能并发,特别是在多处理器和多核心系统中,并提供与POSIX标准更一致的行为。
NPTL是作为早期Linux线程实现LinuxThreads
的替代品在2002年由IBM开发的,现在已经become了Linux系统上的默认POSIX线程库。在NPTL中,每个线程都是一个系统调度的实体,有独立的进程ID,这允许更有效率更一致的线程同步和并发。
像pthread_create这样的Pthreads API函数,实际上就是在使用NPTL(除非在非常老的Linux系统上可能是使用LinuxThreads)
这部分代码可以在https://github.com/bminor/glibc/tree/glibc-2.25/nptl中查看
首先查看x86上的pthread_mutex_t结构,代码在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/x86/bits/pthreadtypes.h#L128
主要看x86_64的代码
1 | typedef union |
pthread_mutex_t是对__pthread_mutex_s的union跨平台封装
其中__size[__SIZEOF_PTHREAD_MUTEX_T]
,这是用于标识__pthread_mutex_s的大小的
1 | #ifdef __x86_64__ |
而long int __align
则是为了确保整个 pthread_mutex_t
结构体在内存中根据 long int
的对齐规则进行对齐,以提高cpu的运行效率
所以核心部分就在__pthread_mutex_s
上了
1 | struct __pthread_mutex_s |
-
__lock
字段是这部分的重点内容了不是简单的0,1表示是否上锁,还有个2状态表示发生了竞争,需要陷入内核进行裁决
-
__kind
字段的1-7位表示锁类型,例如默认的非递归锁PTHREAD_MUTEX_NORMAL(等价于PTHREAD_MUTEX_TIMED_NP,见这里),以及可重入锁PTHREAD_MUTEX_RECURSIVE。而8位表示互斥锁是被进程内的线程共享,还是跨进程共享。一般使用
pthread_mutexattr_setpshared
函数来设置该属性。如果是进程间的同步,需要开辟一个共享内存,将mutex放入共享内存中,然后不同进程才能操作同一个mutex。另外还有一些状态位是用于标识是否支持优先级继承等
pthread_mutex_lock
在https://github.com/bminor/glibc/blob/glibc-2.25/nptl/pthread_mutex_lock.c#L600可以看到
pthread_mutex_lock
是一个指向__pthread_mutex_lock
的强符号(这是一个gcc的概念,强符号声明可以覆盖弱符号,当不存在强符号时才会使用弱符号,详见Weak symbol)
1 |
|
在默认的锁类型PTHREAD_MUTEX_NORMAL(PTHREAD_MUTEX_TIMED_NP)下,https://github.com/bminor/glibc/blob/glibc-2.25/nptl/pthread_mutex_lock.c#L63所运行的流程如下
1 |
|
可以看到除了事务性内存看不太明白,这里大部分都是一些边缘逻辑,写入owner变量,设置探测点等等,核心逻辑全在LLL_MUTEX_LOCK指向的lll_lock中了
而关于其中的事务性内存,首先需要打开gcc选项-fgnu-tm
才能使用,其次相关的FORCE_ELISION宏的逻辑,最终执行的代码LLL_MUTEX_LOCK_ELISION实际上已经废弃
1 |
|
lll_lock
在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/nptl/lowlevellock.h#L88中定义
1 | /* If FUTEX is 0 (not acquired), set to 1 (acquired with no waiters) and |
atomic_compare_and_exchange_bool_acq
是glibc的bool类型的CAS宏
原型大致是
1 | atomic_compare_and_exchange_bool_acq(type *ptr, type desired, type *expected) |
因此当__futex
- 如果为0
- 代表目前是未锁定状态
- 那么交换成功,返回0,函数继续运行
- __futex的值为1,说明进入锁定状态
- 如果为1或者2(在
__lll_lock_wait_private
设置为2)- 代表目前是锁定状态
- 那么交换失败,返回1,函数进入
__lll_lock_wait(_private)
,进行进程(线程)等待 - 这是因为__futex为1或者2,已经有线程进入临界区,新线程需要进入锁定状态
__lll_lock_wait_private
在https://github.com/bminor/glibc/blob/glibc-2.25/nptl/lowlevellock.c#L26中定义
1 | void __lll_lock_wait_private (int *futex) |
其中lll_futex_wait
在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/unix/sysv/linux/lowlevellock-futex.h#L92中定义
1 |
lll_futex_wait就是对syscall调用futex的简单封装,通过传入LLL_PRIVATE来决定调用FUTEX_WAIT_PRIVATE还是FUTEX_WAIT
回到__lll_lock_wait_private函数
- 首先,代码检查
futex
所指向的值是否为2,如果是,那么它调用lll_futex_wait
函数,等待futex
所指向的值不再为2。 - 如果
futex
所指向的值不是2,函数就进入一个循环,在这个循环中,它试图通过原子操作atomic_exchange_acq
将futex
所指向的值设为2。原子操作atomic_exchange_acq
会返回futex
所指向的旧值。 - 如果
atomic_exchange_acq
返回的旧值不为0(意味着锁被占用),那么代码就会再次调用lll_futex_wait
函数,等待futex
所指向的值不再为2。
这里的逻辑要配合unlock一起看才能看得懂,见后续的时序分析
另外,由于虚假唤醒的存在,futex系统调用有可能返回EAGAIN,因此futex系统调用是必须用while循环包住的,这里巧妙的先不进行cas判断来让当前线程陷入futex_wait,从而提高一点性能
pthread_mutex_unlock
pthread_mutex_unlock
是一个指向__pthread_mutex_unlock
的强符号
1 | int __pthread_mutex_unlock (pthread_mutex_t *mutex) { |
lll_unlock
在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/nptl/lowlevellock.h#L154中定义
1 | /* Unconditionally set FUTEX to 0 (not acquired), releasing the lock. If FUTEX |
lll_futex_wake和__lll_lock_wait_private不同,没有任何逻辑,在https://github.com/bminor/glibc/blob/glibc-2.25/sysdeps/unix/sysv/linux/lowlevellock-futex.h#L107中定义
1 |
- 首先将
futex
的值设置为 0,表示锁已释放。 - 然后检查如果原先的
futex
值大于 1,即表示锁原本是被获取的(可能有等待者),那么唤醒任何一个等待者
时序分析
对于复杂的多线程情况,进行时序分析是最有助于理解问题的
- 首先是没有发生线程争用的情况
线程1 | 线程2 | |
---|---|---|
1 | lll_lock: if (atomic_compare_and_exchange_bool_acq (futex, 1, 0)) lll_lock_wait_private (futex); 此时futex为0,因此返回1,函数直接退出,进入锁保护的临界区 |
|
2 | lll_unlock: if (atomic_exchange_rel (futex, 0) > 1) lll_futex_wake (futex, 1, private); 此时futex为1,因此返回1,函数直接退出 |
|
3 | 同1 | |
4 | 同2 |
- 接着是发生了线程争用的情况
线程1 | 线程2 | |
---|---|---|
1 | lll_lock: if (atomic_compare_and_exchange_bool_acq (futex, 1, 0)) lll_lock_wait_private (futex); 此时futex为0,因此返回1,函数直接退出,进入锁保护的临界区 |
|
2 | lll_lock: if (atomic_compare_and_exchange_bool_acq (futex, 1, 0)) lll_lock_wait_private (futex); 此时futex为1,因此返回0,进入lll_lock_wait_private |
|
3 | lll_lock_wait_private: while (atomic_exchange_acq (futex, 2) != 0) lll_futex_wait (futex, 2, LLL_PRIVATE); futex被设置为2,futex的旧值1被返回,进入lll_futex_wait 休眠直到futex不为2 |
|
4 | lll_unlock: if (atomic_exchange_rel (futex, 0) > 1) lll_futex_wake (futex, 1, private); 离开临界区 设置futex为0,由于旧值futex为2,因此返回2,进入lll_futex_wake 唤醒任何一个休眠线程 |
|
5 | lll_lock_wait_private: while (atomic_exchange_acq (futex, 2) != 0) lll_futex_wait (futex, 2, LLL_PRIVATE); futex被设置为2,旧值0被返回,函数直接退出,进入锁保护的临界区 |
|
6 | 同2,但是有点奇怪的是,这里会造成一次无效唤醒 虽然进入futex以后由于等待列表是空的也没有什么性能损耗 |
- 伪线程争用
线程1 | 线程2 | |
---|---|---|
1 | lll_lock: if (atomic_compare_and_exchange_bool_acq (futex, 1, 0)) lll_lock_wait_private (futex); 此时futex为0,因此返回1,函数直接退出,进入锁保护的临界区 |
|
2 | lll_lock: if (atomic_compare_and_exchange_bool_acq (futex, 1, 0)) lll_lock_wait_private (futex); 此时futex为1,因此返回0,进入lll_lock_wait_private |
|
3 | lll_unlock: if (atomic_exchange_rel (futex, 0) > 1) lll_futex_wake (futex, 1, private); 离开临界区 设置futex为0,由于旧值futex为1,因此返回1,进入lll_futex_wake 唤醒任何一个休眠线程,这里也是一次无效唤醒 |
|
4 | lll_lock_wait_private: while (atomic_exchange_acq (futex, 2) != 0) lll_futex_wait (futex, 2, LLL_PRIVATE); futex被设置为2,旧值0被返回,函数直接退出,进入锁保护的临界区 |
|
5 | lll_unlock: if (atomic_exchange_rel (futex, 0) > 1) lll_futex_wake (futex, 1, private); 离开临界区 设置futex为0,由于旧值futex为2,因此返回2,进入lll_futex_wake 唤醒任何一个休眠线程,这里也是一次无效唤醒 |
线程争用和伪线程争用比较,可以看出当unlock的时候futex=2才是glibc争用的情况
但是也有可能是发生了伪线程争用,没有syscall就直接退出了
小结
看到这里大致模模糊糊有个概念,锁实际上是抢的一个内存地址的值
glibc通过CAS抢1来预先判断一下有没有争用,如果没有直接退出
如果抢1失败了,就设置为2,再由futex决断是否为2来休眠和唤醒
因此简化版的锁可以通过让futex决断是否为1来休眠和唤醒,如下
1 |
|
futex源码分析
futex有两个api
futex_wait(int *uaddr, int val)
- 只有当
*uaddr
等于val
时,才进行等待。 - 这保证了在发生上下文切换之前,值没有被另一个线程更改。如果值被改变,
futex_wait
将直接返回,不会有任何等待。
- 只有当
futex_wake(int *uaddr, int n)
- 用于唤醒在
*uaddr
上等待的n
个进程或线程。
- 用于唤醒在
futex依赖的核心数据结构futex_q在https://elixir.bootlin.com/linux/v2.6.39.4/source/kernel/futex.c#L122定义
1 | struct futex_q { |
什么是锁
**所谓的锁,在计算机里本质上就是一块内存空间。**当这个空间被赋值为1的时候表示加锁了,被赋值为0的时候表示解锁了。
在多线程场景下,当多个线程抢一个锁,就是抢着要把这块内存赋值为1。
抢失败的线程就被休眠(或者死循环),这样就不会和抢成功的线程一起操作。
当抢成功的线程释放锁,抢失败的的线程就被唤醒抢锁(或者死循环抢锁)。
怎么实现锁
从刚才锁的本质分析可以看出来,锁分为休眠和死循环两种,也就是互斥锁和自旋锁。
自旋锁只依赖抢内存空间赋值成功,不需要唤醒抢失败者,因此实现是非常简单的。
1 | spinlock() { |
而互斥锁的数据结构和算法就显得复杂了很多,包含了一块待抢的内存结构,和一个抢失败线程的等待唤醒列表。
为了保证互斥锁数据结构的原子性,互斥锁本身的线程安全是由自旋锁来保证的。
纯内核态的互斥锁
最早期的互斥锁是完全的内核态的来实现的
1 | lock(){ |
futex的诞生:用户态+内核态的互斥锁
futex全称fast userspace mutex
,顾名思义,是用户态优化性能的锁
由 Rusty Russell、Hubertus Franke 和 Mathew Kirkwood 在 2.5.7 中引入,是一种用于用户态应用程序的快速、轻量级内核辅助锁定原语。它提供非常快速的无竞争锁获取和释放。
futex 状态存储在用户空间变量中(在所有平台上都是无符号 32 位整数)。
使用原子操作是为了在无竞争的情况下更改 futex 的状态,而无需系统调用的开销。在竞争的情况下,调用内核来使任务进入睡眠状态并唤醒它们。
-
2019-03-14
本篇博客会深入分析条件变量实现来理解两个问题:
- 为什么条件变量要配合锁来使用 — 信号丢失问题
- 为什么条件变量需要用while循环来判断条件,而不是if — 虚假唤醒(spurious wakeup)问题
这两个问题不仅是C会遇到,所有语言的封装几乎都不可避免
先区分一下条件和条件变量,条件是指常用情况下,signal线程修改的值,使得cond_wait判断该值后不再阻塞