futex: 比较快的大部分时间都只需要user space操作的mutex
source:
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。基本形式是
futex(op, arg1, arg2, ...)
其中第一个参数决定了进行哪种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
说更新存在给定地址里的内容，然后判断一下，成功了再唤醒来着……
