http://tsecer.blog.163.com/blog/static/15018172011102715420485/

一、说明

在linux下，这个pthread_mutex是posix多线程编程的一个规范，从名字上看，它也是一个线程间的同步机制。狭义上理解就是一个任务内部的多个线程之间的一个同步机制，这一点对于Linux系统下的futex机制实现可以产生很大影响。因为如果是同一进程的线程，那么所有线程使用的都是相同的地址空间，对应到内核的数据结构就是有相同的mm_struct实例，这样通过用户提供的唯一地址就可以区分出线程中的多个不同的锁。但是如果在不同的进程间同步，这个地址是在不同的进程地址空间中，也就是它们只能保证是物理页面级地址相同。同一个锁，在不同的进程中看到的地址是不同的，更不用说mm_struct结构了。

相比传统的IPC机制，此时的这个机制并不是依赖用户地址，而是使用内核地址，这样就不存在任务间一致性问题，因为所有的用户态任务到内核看到的都是相同的逻辑地址空间，所以使用逻辑地址是没有问题的。但是这种实现的缺点也正是体现在这个锁是在内核中，为此，所有的对这个锁的操作都必须要进入内核来操作。而锁机制的本身只是为了处理竞争条件下的同步。在典型情况下，即使是大量多线程，真正同时来试图获得同一个锁的线程也不会很多，所以大部分的锁获得都会成功，但是获得和释放的动作将会很多。如果每次这个释放和获得都进入内核，将会给系统代码很大的从效果上看无用的操作。

而futex则尝试将这个操作在用户态完成，从而避免频繁进出内核，从而提高整个程序有效负载。其中的Fast User muTEX中的前两个单词则体现了这种机制的两个重要特征，一个是速度快，另一个就是在用户态实现，而后者则是前者的实现基础。

二、内核管理

1、内核面临的问题

由于futex只需要用户传入一个逻辑地址到内核，内核可以把这个地址作为一个futex的标示，或者说一个key。这样就会带来一个问题，虽然对用户态的每一个futex来说是唯一的，但是内核的futex模块却要管理多个futex，更通用的，内核还要管理系统中所有的任务中的所有的futex锁。这样紧紧使用一个逻辑地址是远远不够的。另一方面，这样的大一统管理也要让内核如果快速索引到一个futex的效率考虑进来。

在稍微早期的2.6内核中(例如26.21)，内核并不依赖用户告诉内核这个futex是否是一个任务间共享的地址，而是内核主动的判断这个地址是不是出于一个共享的VMA结构中，从而自动做出判断。但是新的内核(例如2.6.37)要求用户态程序告诉内核这个futex是否需要在进程间共享，可能是为了提高效率把。在POSIX接口说明中，其中说了创建一个锁的时候可以通过pthread_mutexattr_setpshared来告诉线程库希望这个锁在进程间共享，如果用户不希望共享，我们在这里做这个东西明显是画蛇添足，也不符合标准。

2、共享和私有的判断

sys_futex--->>>do_futex--->>futex_wait--->>get_futex_key

……

 if (likely(!(vma->vm_flags & VM_MAYSHARE))) { 对于任务内线程互斥，这里使用了futex_key中联合成员的private结构，其中内核代劳增加了一个mm指针，用来进程不同的任务中的futex的相互区分，然后就是用户态地址，这两个就可以标识出一个任务内futex。
  key->private.mm = mm;
  key->private.address = address;
  return 0;
 }

……

 /*
  * Linear file mappings are also simple.
  */
 key->shared.inode = vma->vm_file->f_path.dentry->d_inode;
 key->both.offset++; /* Bit 0 of offset indicates inode-based key. */
 if (likely(!(vma->vm_flags & VM_NONLINEAR))) {对于线性映射，需要记录文件使用的inode指针的地址(inode节点的编号只是同一个文件系统内部唯一，但是inode结构本身在内核地址中是唯一的一个结构)，然后要记录这个地址在文件内的偏移页面数。这样大家可以推算一下，不同的进程映射同一个文件之后，即使映射方式不同，它们也将会看到相同的futex_key成员，从而可以完成匹配和进程间共享。
  key->shared.pgoff = (((address - vma->vm_start) >> PAGE_SHIFT)
         + vma->vm_pgoff);
  return 0;
 }

新的内核将会要求用户态明确传入该futex是否共享，在2.6.37中

long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
  u32 __user *uaddr2, u32 val2, u32 val3)
{
 int clockrt, ret = -ENOSYS;
 int cmd = op & FUTEX_CMD_MASK;
 int fshared = 0;

 if (!(op & FUTEX_PRIVATE_FLAG))
  fshared = 1;
也就是通过op的#define FUTEX_PRIVATE_FLAG 128标志位作为是否共享的标志，也就是一个byte的最高一个bit为1则表示进程间共享，具体细节不再详述，大家可以看一下2.6.37的源代码。

3、futex的管理

这里对所有的用户态地址进行了hash管理，通过hash_futex函数对futex_key结构中的三个成员进行hash，从而得出一个系统唯一值，这样可以满足共享和非共享的futex查找。根据惯例，hash之后的数据结构都是通过hash队列管理的，所以这里也不例外，通过了queue_me将这个futex添加到指定的队列中，然后通过match_key进行冲突之后的精确匹配。注意：这里是一个系统级的概念，内核在这里将会看到所有进程中的所有futex，所以这里的hash是有必要的。

我们在queue_me函数中看到一个细节，就是对于futex的管理天生就是使用了优先级队列管理，而这个优先级就是执行wait的线程的优先级。所以对于实时任务来等待一个锁的时候，即使高优先级的任务最迟进行等待，它依然是最早被唤醒的一个线程，这一点可能对系统一些诡异问题分析有帮助。

4、用户态优先级继承实现

用户态在创建一个mutex的时候，可以通过pthread_mutexattr_setprotocol(attr,PTHREAD_PRIO_INHERIT)来设置一个锁是优先级继承的，这一般是高优先级的任务可以这么设置，也就是可以高优先级的线程主动授权这个锁的当前持有者可以狐假虎威的暂时使用自己的高优先级，赶紧执行完自己的工作然后退出好由自己活得这个锁。但是futex的接口是没有变化的，也就是这个锁本身还是在用户态的，用户提供的同样只是一个用户地址，但是为了和非优先级区别，这里的futex操作码变成了FUTEX_UNLOCK_PI，也就是要求内核进行优先级继承。

在内核中，优先级的继承是通过rt_mutex来实现优先级继承的。为了复用内核中已有的优先级代码，内核就必须负责创建这样的一个rt_mutex结构，通过代码可以看到，这个内核是通过动态分配一个futex_pi_state结构来实现的，这个结构内嵌了一个struct rt_mutex pi_mutex;并且还有futex最为基本的futex_key结构。也就是优先级集成的锁动作将会使用另一个futex_pi_state结构。

由于一个线程不可能同时等待两个不同的锁(一个锁已经足以将一个线程挂起)，所以一个线程只需要一个这样的结构就可以了。为了提高效率，内核将会在第一次需要使用这个结构的时候通过refill_pi_state_cache函数动态申请这个结构，之后将这个结构的地址缓存在该线程的task_struct结构的pi_state_cache指针中。最终通过rt_mutex_timed_lock接口来使用内核已经存在的优先级继承代码，从而完成优先级的继承。

5、pthread_mutex实现的一个小细节

从PTHREAD_MUTEX_INITIALIZER的内容来开，是全部清空了pthread_mutex_t实例的内容，但是第一次执行pthread_mutex_lock的时候依然是可以成功的。这里就说明了一点，pthread_mutex中的一个锁是否已经被占有是通过结构中的owner判断的，而不是直接通过这个结构中的计数来判断。

三、测试futex的默认优先级队列

[tsecer@Harry futexp]$ uname -a
Linux Harry 2.6.31.5-127.fc12.i686.PAE #1 SMP Sat Nov 7 21:25:57 EST 2009 i686 athlon i386 GNU/Linux
[tsecer@Harry futexp]$ cat futexp.c
#include <pthread.h>
#define THREADS 2
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void * routing(void * num)
{
 if((void *) 1 == num)
 {
  struct sched_param rtparam = {.__sched_priority =1};
  sched_setscheduler(0,SCHED_FIFO,&rtparam);
  perror("after schedule\n");
 }
 pthread_mutex_lock(&mutex);
 printf("pthread %d got the lock \n",(int)num);
}
int main()
{
int i ;
pthread_t     pthreads[THREADS];
pthread_mutex_lock(&mutex);
printf("Main got the mutex\n");
for(i =0 ; i < THREADS;i++)
 pthread_create(pthreads+i,NULL,routing,i);
sleep(1);
pthread_mutex_unlock(&mutex);
sleep(100);
}
[tsecer@Harry futexp]$ cat Makefile
default:
 gcc -static -o futexp.exe futexp.c -lpthread
[tsecer@Harry futexp]$ su -c "./futexp.exe" 在 fedoracore 发行版中 , 要使用特权用户设置实时任务优先级 。
Password:
Main got the mutex
after schedule
: Success
pthread 1 got the loc 这里是后创建的 1 号线程获得了解锁 , 而不是新创建并尝试进行获得锁的 0 号线程 。