浅谈Linux Futex与用户态同步机制实现原理

Mutex被用于实现多个线程对资源的互斥访问，当资源被别的线程占用时，mutex需要挂起当前线程；而当使用完资源后，mutex需要唤醒其它因等待该mutex而被挂起的线程。 因此，实现mutex需要依赖两种能力：

1. 资源互斥访问：对任何资源的互斥访问本质上可以被转化为可以对一个flag的互斥访问，而这可以由硬件提供的原子变量和内存屏障来实现。
2. 线程挂起与唤醒：进程/线程挂起和唤醒是操作系统概念，挂起的本质上为将相应线程状态设置为阻塞状态后再将其放入某个kernel等待队列，而唤醒操作则是其反向操作，因此这都是由kernel提供的能力。

在这两个能力中，基于原子变量和内存屏障的互斥访问是硬件提供的，无需OS支持。

CondVar可以实现让一个线程唤醒阻塞在某个条件上的其它线程。 ​虽然mutex.unlock()也可以唤醒其它阻塞在mutex上的线程，但是线程在执行mutex.unlock()前必须持有mutex, 也就是执行过mutex.lock(), 因此mutex无法让某个阻塞在mutex上的线程被别的未持有该mutex的线程唤醒。CondVar没有这个限制，线程在condvar.notify()之前无需执行condvar.wait(), 因此可以让一个线程唤醒阻塞在condvar上的其它线程。​ CondVar被用于实现协调具有依赖关系的多个线程之间，其可以让线程阻塞在某个未被满足的条件上，该条件最终将被其它线程实现，而该等待线程也将会被条件完成者唤醒。 例如，阻塞队列通常就是基于condvar实现的，队列生产者与消费者线程通过condvar来实现队列已满或已空时的相互等待。 CondVar的使用场景为多个线程需要互斥访问某块资源，而这些线程在实际操作资源前需要等待其它线程先对该资源进行一些前置处理。 因此，​线程在检查资源并等待某个condvar之前需要持有某个mutex (其它线程可能并发访问该资源), 在等待condvar期间时需要自动解锁该mutex (否则其它线程将无法修改该资源), 并且在被condvar唤醒后会再次自动尝试获取该mutex (确保线程被唤醒后独享该资源)​. CondVar和mutex使用场景的主要区别在于，mutex场景中间各线程间无依赖关系，而condvar场景中某些线程会依赖别的线程。 从CondVar的功能上可以看出，condvar不依赖互斥能力，而仅依赖OS等待队列提供的线程挂起和唤醒能力。

Semaphore是兼具mutex和condvar功能的同步原语，其可以实现仅允许指定数量线程同时访问某块资源。 Mutex可以看作其互斥版，但是，​mutex仅能被锁持有线程释放，而semaphore则允许被其它线程释放，这个能力也使得其可以被当作condvar来让一个线程唤醒其它线程​。

​免责声明：本小节内容可能有不少错误，请慎用。​

当原子变量在被多个线程读写时，只有一个线程能获得其读写权，并且其读写过程不会被其它线程干扰，其它线程也只能看到读写前和读写后的结果（一致性），其比较严格的定义可以参考C11 stdatomic.h atomic_{int说明文档}. 原子变量实现方法依赖硬件平台，X86提供了lock指令来锁总线以禁止并发，ARM则提供ldadd指令。 也就是说，​原子变量本质上也只是普通的内存块，只是其被操作时使用的是特殊的读写指令​。 关于atomic_{int的汇编实现}，可以参考https://stackoverflow.com/questions/31978324/what-exactly-is-stdatomic/58904448.

​悲观锁mutex和乐观锁CAS在底层逻辑上都依赖tryLock逻辑，其需要确保并发时只有一个线程能够成功修改锁原子变量​，而这需要依赖类似于X86平台​cmpxchg​的特殊硬件指令，下面将仅以X86为例分析具体原因。 在多核CPU中，为了实现tryLock逻辑，​硬件必须提供cmpxchg, 而不能通过用cmp + xchg来替代，因为在cmp和xchg之间，别的CPU核可能会改变原子变量状态​。 此外，还需要给cmpxchg加上lock prefix, 以确保其它线程不会操作原子变量内存块。

仅有原子变量是不够的，因为现代CPU具有缓存和乱序执行能力，这可能导致某些线程获取到的缓存中的无效原子变量。 另外，编译器在代码生成优化阶段也可能会“缓存数据”（依赖寄存器缓存值而不直接从内存去数据）和重排指令，也会导致同样的问题。 为了解决这些问题，CPU和编译器都提供了相应支持：

1. 针对CPU缓存数据和重排指令，X86等硬件平台提供了mfence/lfence/sfence之类指令，其可以保证该指令之前的指令的执行时间一定先于该指令之后的其它指令，并且还会刷新缓存以保证操作的是主内存中的最新数据。
2. 针对编译器缓存数据和重排指令，C语言提供了volatile关键字，GCC等编译器的volatile实现会避免这些行为. Java也提供了类似的volatile关键字，其实现时还会插入mfence等指令以避免CPU指令重排。

GCC提供的__{atomic系列内置函数}在保证原子性的同时还会执行mfence等指令以保证内存顺序，C++11也规范了内存模型来解决这些问题。

Kernel进程等待队列本质上是通过设置进程调度状态为Interruptible/Uninterruptible Sleep来实现的。 Kernel进程调度器仅会给Running/Runnable状态的进程分配时间片，因此等待队列中的进程都不会被调度执行。 操作系统教材都会讲述Kernel进程调度相关知识，这里就不赘述了。

Kernel内部实现有mutex/semaphore，理论上可以将作为系统调用syscall提供给用户态程序使用，但是这样做的话效率不高，原因如下：

1. 系统调是有代价的，因为其执行时需要将上下文从用户态切换到内核态。
2. Mutex等同步机制在lock阶段首先需要检测原子变量值，然后仅当原子变量值不符合要求时，才进入内核态以将当前进程挂入等待队列。
3. 前面分析过，mutex/semaphore理论实现上仅等待队列部分需要kernel支持，而原子变量和内存屏障部分在用户态也能通过执行相关硬件指令而实现。 因此，当原子变量值符合要求时，进入内核态后在检测之就会很不划算，而将kernel mutex内部实现作为syscall提供给用户程序的方法却需要在进入内核态后再检测原子变量，因此效率不高。

Futex (Fast Userspace muTEX)则是在用户态保存并检测mutex等所需的原子变量，其仅在需要时才执行futex syscall以进入内核态来使用kernel提供的等待队列功能，因此效率很高，而这也是futex名称中f (fast)的来源。 因此，目前用户态线程同步API所依赖的libpthread mutex/condvar/semaphore都是基于futex实现的。

Futex syscall基础版原型如下，其可以被传入用户态锁原子变量：

int futex_wait(int *uaddr, int val); // 当*uaddr == val时 (cmpxchg / CAS)，在uaddr所指锁原子变量上等待
int futex_wake(int *uaddr, int n); // 唤醒n个在uaddr所指锁原子变量上等待的进程

此外，futex还有其它几个版本，其原型和功能如下：

// bitset可以被用于实现超时和读写锁
int futex_wait_bitset(int *uaddr, int val, int bitset);
int futex_wake_bitset(int *uaddr, int n, int bitset);
// 可被用于实现condvar
int futex_requeue(int *uaddr, int n, int *uaddr2, int n2);
int futex_cmp_requeue(int *uaddr, int n, int *uaddr2, int n2, int val);

最后，futex还有Priority Inheritance系列等其它版本，本文暂不讨论之。