查看“Futex”的源代码

futex: 比较快的大部分时间都只需要user space操作的mutex

source: 

[http://locklessinc.com/articles/futex_cheat_sheet/ Futex Cheat Sheet]

[http://lwn.net/Articles/360699/ A futex overview]

[https://www.kernel.org/doc/Documentation/pi-futex.txt Lightweight PI-futexes]

[https://www.kernel.org/doc/Documentation/rt-mutex.txt RT-mutex subsystem with PI support]

== 目的 ==
在没有竞争的情况下，futex不需要调用system call。每个用户线程执行一个atomic operation，没有竞争的情况下根据返回值就可以直接成功，unlock的时候也差不多。

在有竞争的情况下，后到的线程在atomic op之后会发现mutex已经被人用了，于是调用FUTEX_WAIT来等。
有竞争时，unlock的atomic op会让解锁线程发现有其他人在等，于是就会调用FUTEX_WAKE来唤醒其他人。

== API ==
linux有个很毛的复用了的api，叫做futex。基本形式是
<pre>futex(op, arg1, arg2, ...)</pre>
其中第一个参数决定了进行哪种futex操作，同时决定了后面的参数里面有几个有用以及分别是什么意思……

== PI:问题和解决 ==
关于mutex，有一个优先级反转问题。

说有三个线程优先级是high, med和low。high和low共享一个mutex。假如某天low抓到了mutex，之后high也去抓这个mutex，那high就会开始等。如果这个时候med把low给抢了，那low就会不知道被抢多久。因为high也在等那个mutex，high也会不知道被卡多久。

在这个情况下，明明优先级比high低，但是med却导致high没法继续跑。这就是优先级反转问题。

为了解决这个问题，一个办法是暂时提高low的优先级。因为high也在等，所以暂时把low提到和high一样高。这样它就不会被med抢，从而也就不会卡high了。

futex有一堆操作都是为了解决这个问题，这些操作都以_PI结尾。PI说的是priority inherit，让low的thread能够继承high thread的priority。

== private优化 ==
说futex设计的时候是可以多进程公用的。只要你们搞个shared mem，然后把同一个地方传给那些futex操作，那你们就可以共享mutex，在多个进程之间。

但是对于那些单进程的mutex，这样降低了效率。kernel需要先查一遍才知道这个地址对应的物理地址，然后才能拿来作为索引。但其实单进程里面只要直接拿虚拟地址搞就可以了。

所以好多操作还有个private版本，告诉kernel你不用翻译地址了。这些操作基本上就是在老操作上or一个FUTEX_PRIVATE_FLAG，当然也有定义好的_PRIVATE的常数，可以直接用。

== BITSET ==
FUTEX_WAKE和FUTEX_WAIT有个带BITSET的版本，多一个mask参数。说WAKE的时候，只有这个mask和WAIT时候的mask有相交的才起作用。

实际上相当于多个wait queue可以共享一个地址。但是说后来发现这样实现没效率，所以glibc现在只用mask全满的情况，也就是相当于和老的一样。

那为啥不用老的呢？因为BITSET版本还有个不同：他的timeout是绝对时间，而老版本是相对时间，但是pthread标准要求绝对时间……

== 操作 ==
=== 基本操作 ===
==== FUTEX_WAIT ====
FUTEX_WAIT提供一个地址和一个值。进syscall之后，首先观察那个地址是不是那个值，如果不是直接返回。否则开始等。

==== FUTEX_WAKE ====
FUTEX_WAKE提供一个地址和一个数量，唤醒等在这个地址的指定数量的thread。

==== FUTEX_REQUEUE ====
FUTEX_REQUEUE提供两个地址，以及两个数量。唤醒若干等在第一个地址的线程，同时把另外一些扔到等待第二个地址的队列中去。

这个用在conditional variable上。试想一个cond broadcast唤醒了所有人，这帮人接下来一起去抢控制cond var那个mutex。这很没有效率，所以不如直接唤醒一个，把剩下的扔到等那个mutex的队列里去。所以其实也是个效率优化。

==== FUTEX_CMP_REQUEUE ====
比起FUTEX_REQUEUE，这货多一个参数。如果给定的第一个地址里面的内容和这个参数不同，返回EAGAIN。

说glibc里面的cond var实现很复杂，还和另一个mutex有关系，所以要搞这个……

=== PI操作 ===
==== FUTEX_LOCK_PI ====
如果你锁一个PI mutex的时候发现被人占了，那就调用这个syscall。系统会帮你搞定提高别人优先级的事情。

==== FUTEX_UNLOCK_PI ====
如果你解锁一个PI mutex的时候发现有人等，那就调用这个。系统会帮你降低优先级的。

=== BITSET ===
==== FUTEX_WAIT_BITSET ====
比FUTEX_WAIT多一个bitmap。对应的WAKE_BITSET里的bitmap如果和这个有相交的那就WAKE，否则忽略。

==== FUTEX_WAKE_BITSET ====
比FUTEX_WAKE多一个bitmap。只wake那些WAIT_BITSET的bitmap里和这个bitmap有相交的线程。

=== 过时的操作 ===
==== FUTEX_FD ====
说有race condition来着。

==== FUTEX_WAKE_OP ====
说更新存在给定地址里的内容，然后判断一下，成功了再唤醒来着……