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

source:

Futex Cheat Sheet

A futex overview

Lightweight PI-futexes

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

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