futex 设计成用户空间快速锁操作，由用户空间实现fastpath，以及内核提供锁竞争排队仲裁服务，由用户空间使用futex系统调用来实现slowpath。futex系统调用提供了三种配对的调用接口，满足不同使用场合的，分别为noraml futex，pi-futex，以及 requeue-pi。

futex的同步（锁）状态定义由用户空间去执行，futex系统调用并不需要理解用户空间是如何定义和使用这个地址对齐的4字节长的整型的futex，但是pi-futex除外，用户空间必须使用futex系统调用定义的锁规则。用户空间通过总线锁原子访问这个整型futex，进行状态的修改，上锁，解锁和锁竞争等。当用户空间发现futex进入了某种定义需要排队服务的状态时，用户空间就需要使用futex系统调用进行排队，待排队唤醒后再回到用户空间再次进行上锁等操作。当锁竞争时，每次的Lock和Unlock，都必需先后进行用户空间的锁操作和futex系统调用，并且两步并非原子性执行的，Lock和Unlock的执行过程可能会发生乱序。

这是我们希望的

task A futex in user futex queue in kerenl task B
owned empty 1. own futex
1.try lock (尝试修改futex) empty
2.mark waiter (发现锁竞争，修改futex状态) owned -> waiters empty
3.futex_wait 0 empty 2. unlock (修改futex，得到旧状态为waiters)

1. enqueue 0 has waiter 3. futex_wake (发现有锁竞争)


2. sleep and schedule 0 has waiter 4. dequeue
   0 empty 5. wakeup


3. wokenup 0 empty
   7.try lock again (被唤醒后，并不知道还有没有其它任务在等待，

所以锁竞争状态来上锁，以确保自己unlock时进行slowpath，

进行内核检查有没有其它等待的任务)

0 -> waiters empty

1. own futex waiters empty


2. unlock (approach to slowpath) waiters
   但是总会发生我们不希望的情况，虽然总线锁原子操作使得Lock和Unlock的用户空间阶段的操作以Lock为先，让futex进行锁竞争状态，使得Lock和Unlock都要进行slowpath。然而，在它们各自调用futex系统调用时，执行futex_wait的cpu被中断了，futex_wake先于futex_wait执行了。futex_wake发现没有可唤醒的任务就离开了。然后迟到的futex_wait却一无所知，毅然排队等待在一个已经释放的锁。这样一来，如果这个锁将来不发生锁竞争，那么task A就不会被唤醒而被遗忘。

task A futex in user futex queue in kerenl task B
owned empty 1. own futex
1.try lock (尝试修改futex) empty
2.mark waiter (发现锁竞争，修改futex状态) owned | waiters empty
3.futex_wait 0 empty 2. unlock (修改futex，得到旧状态为owned | waiters)
interupted 0 empty 3. futex_wake (发现有锁竞争)
interupted 0 empty 4. quit

1. enqueue 0 has waiter


2. sleep and schedule 0 has waiter

所以需要进行排队等待的futex系统调用，都要求将futex当前的副本作为参数传入，futex系统调用在执行排队之前都通过副本和用户空间的futex最新值进行对比，决定是否要返回用户空间，让用户空间重新判断。对于pi-futex的futex_lock_pi系统调用操作入口，并不需要用户空间传入当前futex的副本，是因为用户空间必须使用由futex系统调用对pi-futex的锁规则，futex_lock_pi 函数则以pi-futex的锁规则来判断pi-futex是否被释放。当一个用户空间的futex遵照futex.h对pi-futex锁状态规则，并使用futex系统调用的futex_lock_pi和futex_unlock_pi操作，这个futex就是一个pi-futex。

futex系统调用配对的操作入口：

1. normal futex:

static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset)

static int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset)

1. pi-futex:

static int futex_lock_pi(u32 __user *uaddr, unsigned int flags, int detect, ktime_t *time, int trylock)

static int futex_unlock_pi(u32 __user *uaddr, unsigned int flags)

1. requeue-pi:

static int futex_wait_requeue_pi(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset, u32 __user *uaddr2)

static int futex_requeue(u32 __user *uaddr1, unsigned int flags, u32 __user *uaddr2, int nr_wake, int nr_requeue, u32 *cmpval, int requeue_pi)

1. robust-futex:

SYSCALL_DEFINE3(get_robust_list, int, pid, struct robust_list_head __user * __user *, head_ptr, size_t __user *, len_ptr)

SYSCALL_DEFINE2(set_robust_list, struct robust_list_head __user *, head, size_t, len)

futex_wait 应用于non-pi futex，futex的规则由用户空间定义，要求用户空间将non-pi futex副本值传入来，过滤工作是由 futex_wait_setup子函数完成，再由 futex_wait_queue_me子函数进行non-pi futex的排队和睡眠等待。

futex_wait_requeue_pi 整合了对futex从non-pi到pi的requeue，以及non-pi到non-pi的requeue。但它首先是对non-pi的futex进行futex_wait，所以它和futex_wait 一样要求用户空间将non-pi futex副本值传入来。所以futex_wait_requeue_pi 如其名字一样，拆分成两个阶段，或者说组合了两种操作，futex_wait和 requeue_pi 。先进行futex_wait ，待被futex_requeue 唤醒后执行requeue_pi 。可以从代码看到futex_wait_requeue_pi 前半段和 futex_wait 代码流程是差不多的。

futex_lock_pi 应用于pi-futex，futex的规则由futex系统调用（头文件）定义，用户空间必须遵从规则来使用。由于规则是由内核定义的，并不要求用户空间传入一个futex当前副本，并且还会在内核中，在使用rt_mutex代理排队等待之前，进行 futex_lock_pi_atomic上锁的尝试，失败后才进入rt_mutex代理排队等待。待排队唤醒后，通过 fixup_owner 和 fixup_pi_state_owner 对用户空间的pi-futex进行上锁。这里有两点注意，rt_mutex的上锁规则是使用task_struct的指针标记，而pi-futex的上锁规则是使用pid(tid)号标记。另外pi-futex的排队也要注意，pi-futex虽然在rt_mutex代理上进行排队，但是还要像non-pi futex一样插入到futex_hash_bucket的链表中，为的不是排队，而是让后面进来的排队，可以在futex_hash_bucket中找出futex_queue，从而得到futex_pi_state（rt_mutex代理所在）。

futex的pi-support以及robust-support都跟task_struct偶合在一起。

robust futex 依赖的是进程（或线程）的task_struct结构体中的 robust_list 链表。futex的使用者（用户空间）通过（系统调用）将 用户空间维护的 robust_list 添加进内核中task_struct->robust_list。当进程（或线程）在退出的时候，内核可以遍历用户空间的robust_list链表，并对没有释放的robust futex进行recovery处理。

进程（或线程）在退出时，exit_mm -> mm_release 会调用futex的服务，exit_robust_list 去对用户空间使用的未释放的futex进行recovery处理 handle_futex_death。

对于pi-futex，它所使用的rtmutex代理也是会被恢复的，但不必经过robust_list，mm_release 会调用futex的服务 exit_pi_state_list 进行恢复处理。

对于pthread，当使用pthread_create创建线程时，同时会调用系统调用set_robust_list将内核的task_strust->robust_list，与用户空间的pthread维护的robust_list关联起来。

引子
在编译2.6内核的时候，你会在编译选项中看到[*] Enable futex support这一项，上网查，有的资料会告诉你”不选这个内核不一定能正确的运行使用glibc的程序”，那futex是什么？和glibc又有什么关系呢？

1. 什么是Futex
   Futex 是Fast Userspace muTexes的缩写，由Hubertus Franke, Matthew Kirkwood, Ingo Molnar and Rusty Russell共同设计完成。几位都是linux领域的专家，其中可能Ingo Molnar大家更熟悉一些，毕竟是O(1)调度器和CFS的实现者。

Futex按英文翻译过来就是快速用户空间互斥体。其设计思想其实 不难理解，在传统的Unix系统中，System V IPC(inter process communication)，如 semaphores, msgqueues, sockets还有文件锁机制(flock())等进程间同步机制都是对一个内核对象操作来完成的，这个内核对象对要同步的进程都是可见的，其提供了共享 的状态信息和原子操作。当进程间要同步的时候必须要通过系统调用(如semop())在内核中完成。可是经研究发现，很多同步是无竞争的，即某个进程进入 互斥区，到再从某个互斥区出来这段时间，常常是没有进程也要进这个互斥区或者请求同一同步变量的。但是在这种情况下，这个进程也要陷入内核去看看有没有人 和它竞争，退出的时侯还要陷入内核去看看有没有进程等待在同一同步变量上。这些不必要的系统调用(或者说内核陷入)造成了大量的性能开销。为了解决这个问 题，Futex就应运而生，Futex是一种用户态和内核态混合的同步机制。首先，同步的进程间通过mmap共享一段内存，futex变量就位于这段共享 的内存中且操作是原子的，当进程尝试进入互斥区或者退出互斥区的时候，先去查看共享内存中的futex变量，如果没有竞争发生，则只修改futex,而不 用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生，则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说，futex就是通过在用户态的检查，（motivation）如果了解到没有竞争就不用陷入内核了，大大提高了low-contention时候的效率。 Linux从2.5.7开始支持Futex。

1. Futex系统调用
   Futex是一种用户态和内核态混合机制，所以需要两个部分合作完成，linux上提供了sys_futex系统调用，对进程竞争情况下的同步处理提供支持。
   其原型和系统调用号为
   #include <linux/futex.h>
   #include <sys/time.h>
   int futex (int *uaddr, int op, int val, const struct timespec *timeout,int *uaddr2, int val3);
   #define __NR_futex 240

虽然参数有点长，其实常用的就是前面三个，后面的timeout大家都能理解，其他的也常被ignore。
uaddr就是用户态下共享内存的地址，里面存放的是一个对齐的整型计数器。
op存放着操作类型。定义的有5中，这里我简单的介绍一下两种，剩下的感兴趣的自己去man futex
FUTEX_WAIT: 原子性的检查uaddr中计数器的值是否为val,如果是则让进程休眠，直到FUTEX_WAKE或者超时(time-out)。也就是把进程挂到uaddr相对应的等待队列上去。
FUTEX_WAKE: 最多唤醒val个等待在uaddr上进程。

可见FUTEX_WAIT和FUTEX_WAKE只是用来挂起或者唤醒进程，当然这部分工作也只能在内核态下完成。有些人尝试着直接使用futex系统调 用来实现进程同步，并寄希望获得futex的性能优势，这是有问题的。应该区分futex同步机制和futex系统调用。futex同步机制还包括用户态 下的操作，我们将在下节提到。

1. Futex同步机制
   所有的futex同步操作都应该从用户空间开始，首先创建一个futex同步变量，也就是位于共享内存的一个整型计数器。
   当 进程尝试持有锁或者要进入互斥区的时候，对futex执行”down”操作，即原子性的给futex同步变量减1。如果同步变量变为0，则没有竞争发生， 进程照常执行。如果同步变量是个负数，则意味着有竞争发生，需要调用futex系统调用的futex_wait操作休眠当前进程。
   当进程释放锁或 者要离开互斥区的时候，对futex进行”up”操作，即原子性的给futex同步变量加1。如果同步变量由0变成1，则没有竞争发生，进程照常执行。如 果加之前同步变量是负数，则意味着有竞争发生，需要调用futex系统调用的futex_wake操作唤醒一个或者多个等待进程。

这里的原子性加减通常是用CAS(Compare and Swap)完成的，与平台相关。CAS的基本形式是：CAS(addr,old,new),当addr中存放的值等于old时，用new对其替换。在x86平台上有专门的一条指令来完成它: cmpxchg。

可见: futex是从用户态开始，由用户态和核心态协调完成的。

1. 进/线程利用futex同步
   进程或者线程都可以利用futex来进行同步。
   对于线程，情况比较简单，因为线程共享虚拟内存空间，虚拟地址就可以唯一的标识出futex变量，即线程用同样的虚拟地址来访问futex变量。
   对 于进程，情况相对复杂，因为进程有独立的虚拟内存空间，只有通过mmap()让它们共享一段地址空间来使用futex变量。每个进程用来访问futex的 虚拟地址可以是不一样的，只要系统知道所有的这些虚拟地址都映射到同一个物理内存地址，并用物理内存地址来唯一标识futex变量。

小结：

1. Futex变量的特征：1)位于共享的用户空间中 2)是一个32位的整型 3)对它的操作是原子的


2. Futex在程序low-contention的时候能获得比传统同步机制更好的性能。


3. 不要直接使用Futex系统调用。


4. Futex同步机制可以用于进程间同步，也可以用于线程间同步。