futex机制介绍

1、概念

futex： a sort of fast, user-space mutual exclusion primitive.

Futex是一种用户态和内核态混合的同步机制。首先，同步的进程间通过mmap共享一段内存，futex变量就位于这段共享的内存中且操作是原子的，当进程尝试进入互斥区或者退出互斥区的时候，先去查看共享内存中的futex变量，如果没有竞争发生，则只修改futex,而不用再执行系统调用了。当通过访问futex变量告诉进程有竞争发生，则还是得执行系统调用去完成相应的处理(wait 或者 wake up)。简单的说，futex就是通过在用户态的检查，（motivation）如果了解到没有竞争就不用陷入内核了，大大提高了low-contention时候的效率。

2、futex的由来

为什么要有futex，他解决什么问题？何时加入内核的？我们来看下

经研究发现，很多同步是无竞争的，即某个进程进入互斥区，到再从某个互斥区出来这段时间，常常是没有进程也要进这个互斥区或者请求同一同步变量的。但是在这种情况下，这个进程也要陷入内核去看看有没有人和它竞争，退出的时侯还要陷入内核去看看有没有进程等待在同一同步变量上。这些不必要的系统调用(或者说内核陷入)造成了大量的性能开销。为了解决这个问题，Futex就应运而生。

前面的概念已经说了，futex是一种用户态和内核态混合同步机制，为什么会是用户态+内核态，听起来有点复杂，由于我们应用程序很多场景下多线程都是非竞争的，也就是说多任务在同一时刻同时操作临界区的概率是比较小的，大多数情况是没有竞争的，在早期内核同步互斥操作必须要进入内核态，由内核来提供同步机制，这就导致在非竞争的情况下，互斥操作扔要通过系统调用进入内核态。

我们来看一下程序

程序1：

pthread_mutex_t lock;

int count = 0;

void thread1()

{

    while(1)

    {

        pthread_mutex_lock(lock);

        count++;

        pthread_mutex_unlock(lock);

    }

}

void thread2()

{

    while(1)

    {

        sleep(60);

        pthread_mutex_lock(lock);

        count = 0;

        pthread_mutex_unlock(lock);

    }

}

pthread_create(tid1, NULL, thread1, NULL);

pthread_create(tid2, NULL, thread1, NULL);

假设系统中有2个程序，一个线程在滴答自增，一个线程周期性清除计数器。显然两个线程同时进入临界区的几率相当小，在未实现futex机制之前，每次调用pthread_mutex_lock和unlock都要通过syscall进入内核，内核检查该锁的拥有者，发现没有人持则返回到用户态，因为大部分时间2个线程并没有争抢互斥锁。显然大部分时间在做无用功，时间浪费在user-kernel和kernel→usr的切换，显然这个锁的性能不太好，因为存在大量user→kernel、kernel→usr的切换，例子可能不太恰当，get到点就好。

那么如何解决这个问题？

就像前面说的，采用用户态+内核态混合机制，在用户态使用原子操作，对持有锁的持有情况进行判断，如果锁可以占用，那么更新锁的状态并直接占用，不需要进入内核态，如果锁已经占用，则进入内核态挂起当前任务，事实上这些操作对程序员不可见的，一般都是由C库提实现好了。

Glibc中常用的线程同步方式举例:

Semaphore

变量定义：    sem_t sem;

初始化：      sem_init(sem,0,1);

进入加锁:    sem_wait(sem);

退出解锁:    sem_post(sem);

Mutex

变量定义：    pthread_mutex_t mut;

初始化：      pthread_mutex_init(mut,NULL);

进入加锁:    pthread_mutex_lock(mut);

退出解锁:    pthread_mutex_unlock(mut);

这些用于同步的函数和futex有什么关系？下面让我们来看一看:

以Semaphores为例，

进入互斥区的时候，会执行sem_wait(sem_t *sem)，sem_wait的实现如下：

int sem_wait (sem_t *sem)

{

int *futex = (int *) sem;

if (atomic_decrement_if_positive (futex) 0)

return 0;

int  err = lll_futex_wait (futex, 0);

return -1;

)

atomic_decrement_if_positive()的语义就是如果传入参数是正数就将其原子性的减一并立即返回。如果信号量为正，在Semaphores的语义中意味着没有竞争发生，如果没有竞争，就给信号量减一后直接返回了。

如果传入参数不是正数，即意味着有竞争，调用lll_futex_wait(futex,0),lll_futex_wait是个宏，展开后为：

#define lll_futex_wait(futex, val)

({                                         

…

__a*** __volatile (LLL_EBX_LOAD                         

LLL_ENTER_KERNEL                         

LLL_EBX_LOAD                         

: “=a” (__status)                         

: “0″ (SYS_futex), LLL_EBX_REG (futex), “S” (0),         

“c” (FUTEX_WAIT), “d” (_val),                 

“i” (offsetof (tcbhead_t, sysinfo))             

: “memory”);                         

…                                     

})

可以看到当发生竞争的时候，sem_wait会调用SYS_futex系统调用，并在val=0的时候执行FUTEX_WAIT,让当前线程休眠。2002年的ols文档，在linux-2.5.7引入了futex。

futex内核实现源码分析（2）

由上一章节可知，futex变量创建于用户空间，在进程或线程间共享，当进程或线程想要进入临界区时，通常会判断futex变量是否满足条件，若满足则成功进入临界区，否则则阻塞在该futex变量上；当进程或线程将要离开临界区时，则会唤醒阻塞在futex变量上的其他进程或线程。在内核中通过struct futex_q结构将一个futex变量与一个挂起的进程（线程）关联起来。

struct futex_q：

union futex_key：futex变量地址标识

在内核中通过一个哈希表来维护所有挂起阻塞在futex变量上的进程（线程），不同的futex变量会根据其地址标识计算出一个hash key定位到一个哈希桶链上，因此挂起阻塞在同一个futex变量的所有进程（线程）会定位到同一个哈希桶链上。

struct futex_hash_bucket ：

futex哈希表：

同一进程下不同线程阻塞在futex变量模型：

内核fuetx初始化，初始化futex哈希表的每一个哈希桶链的头。

进程间和线程间的协作区别在哪？为什么需要内核实现通信与同步

进程间和线程间的协作区别：

进程互斥、同步的概念

进程互斥、同步的概念是并发进程下存在的概念，有了并发进程，就产生了资源的竞争与协作，从而就要通过进程的互斥、同步、通信来解决资源的竞争与协作问题。

下面是根据《操作系统教程》3.1.4 中的介绍，整理的进程互斥、同步的概念。

在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。

进程的互斥、同步、通信都是基于这两种基本关系而存在的，为了解决进程间竞争关系（间接制约关系）而引入进程互斥；为了解决进程间松散的协作关系( 直接制约关系)而引入进程同步；为了解决进程间紧密的协作关系而引入进程通信。

***种是竞争关系

系统中的多个进程之间彼此无关，它们并不知道其他进程的存在，并且也不受其他进程执行的影响。例如，批处理系统中建立的多个用户进程， 分时系统中建立的多个终端进程。由于这些进程共用了一套计算机系统资源，因而， 必然要出现多个进程竞争资源的问题。当多个进程竞争共享硬设备、存储器、处理器 和文件等资源时，操作系统必须协调好进程对资源的争用。

资源竞争出现了两个控制问题：一个是死锁 （deadlock ）问题，一组进程如果都获得了部分资源，还想要得到其他进程所占有的资源，最终所有的进程将陷入死锁。另一个是饥饿（starvation ）问题，这是指这样一种情况：一个进程由于其他进程总是优先于它而被无限期拖延。

操作系统需要保证诸进程能互斥地访问临界资源，既要解决饥饿问题，又要解决死锁问题。

进程的互斥（mutual exclusion ）是解决进程间竞争关系( 间接制约关系) 的手段。 进程互斥指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。

第二种是协作关系

某些进程为完成同一任务需要分工协作，由于合作的每一个进程都是独立地以不可预知的速度推进，这就需要相互协作的进程在某些协调点上协 调各自的工作。当合作进程中的一个到达协调点后，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己，直到其他合作进程发来协调信号或消息后方被唤醒并继续执行。这种协作进程之间相互等待对方消息或信号的协调关系称为进程同步。

进程间的协作可以是双方不知道对方名字的间接协作，例如，通过共享访问一个缓冲区进行松散式协作；也可以是双方知道对方名字，直接通过通信机制进行紧密协作。允许进程协同工作有利于共享信息、有利于加快计算速度、有利于实现模块化程序设计。

进程的同步（Synchronization）是解决进程间协作关系( 直接制约关系) 的手段。进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于另一

个协作进程的消息或信号，当一个进程没有得到来自于另一个进程的消息或信号时则需等待，直到消息或信号到达才被唤醒。

不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，也是对进程使用资源次序上的一种协调。

进程通信的概念

下面是根据《操作系统教程》3.5 中的介绍，整理的进程通信的概念。

并发进程之间的交互必须满足两个基本要求：同步和通信。

进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，通过修改信号量，进程之间可建立起联系，相互协调运行和协同工作。但是信号量与PV操作只能传递信号，没有传递数据的能力。有些情况下进程之间交换的信息量虽很少，例如，仅仅交换某个状态信息，但很多情况下进程之间需要交换大批数据，例如，传送一批信息或整个文件，这可以通过一种新的通信机制来完成，进程之间互相交换信息的工作称之为进程通信IPC （InterProcess Communication）（主要是指大量数据的交换）。进程间通信的方式很多，包括：

信号（signal ）通信机制；

信号量及其原语操作（PV、读写锁、管程）控制的共享存储区（shared memory ）通信机制；

管道（pipeline）提供的共享文件（shared file）通信机制；

信箱和发信/ 收信原语的消息传递（message passing ）通信机制。

其中前两种通信方式由于交换的信息量少且效率低下，故称为低级通信机制，相应地可把发信号/ 收信号及PV之类操作称为低级通信原语，仅适用于集中式操作系统。消息传递机制属于高级通信机制，共享文件通信机制是消息传递机制的变种，这两种通信机制，既适用于集中式操作系统，又适用于分布式操作系统。

进程同步的方法

前面提到，进程互斥关系是一种特殊的进程同步关系，下面给出常见的进程同步的方法，实际上也可用于进程的互斥（个人理解）。

在何炎祥的《计算机操作系统》 3.2 节，将进程同步的机制与解决进程互斥方法看做是一样的，的明确指出互斥的软件解决方法为Dekker算法与Peterson算法，互斥的硬件解决方法为中断方法、以及使用机器指令的方法，后面又给出了信号量、管程、消息传递三种方法。

实际应用中，不同的系统有不同的进程同步方法，CSDN帖子中有一些讨论，Linux 与Windows的主要同步、通信机制如下：

Linux 下：

Linux 下常见的进程同步方法有：SysVIPC 的 sem（信号量）、file locking / record locking（通过 fcntl 设定的文件锁、记录锁）、futex（基于共享内存的快速用户态互斥锁）。针对线程（pthread）的还有 pthread_mutex 和 pthread_cond（条件变量）。

Linux 下常见的进程通信的方法有 ：pipe（管道），FIFO（命名管道），socket（套接字），SysVIPC 的 shm（共享内存）、msg queue（消息队列），mmap（文件映射）。以前还有 STREAM，不过现在比较少见了（好像）。

Windows下：

在Windwos中，进程同步主要有以下几种：互斥量、信号量、事件、可等计时器等几种技术。

在Windows下，进程通信主要有以下几种：内存映射、管道、消息等，但是内存映射是最基础的，因为，其他的进程通信手段在内部都是考内存映射来完成的。

线程的同步/通信与进程的同步/通信有区别吗？

对于该问题，教材上没有明确的回答，教材上给出的一般是进程而非线程的同步、通信方式。但网络上很多说法将两者混为一谈。根据教材，以及网上的说法，个人的理解为：

同步机制：

信号量、管程、互斥是进程的同步机制，而信号量、互斥也可用于线程的同步，但管程只在进程同步中被用到；

线程的同步除了信号量、互斥外，还有临界区、事件，没有看到教材上将这两种方式作为进程的同步方式；

通信机制：

管道、FIFO、消息队列、信号量、共享内存是进程的同步机制，教材上没有线程的通信机制这样的说法，但可以肯定这几种方法是进程的通信方式，且其中的信号量既可用于进程的同步，又可用于进程的通信，在网络上还有说可以用于线程同步的。

管道与管程是不同的，管程是进程同步的方式，而管道则是进程通信的方式。

进程的同步/通信

下面是常见的线程之间的同步方式的详细介绍。

（注：下面转自网络，下面的同步、通信方式对于进程与线程分的不是很清楚，关于进程还是线程的解释见上面——线程的同步/通信与进程的同步/通信有区别吗？）

一、进程/线程间同步机制。

临界区、互斥区、事件、信号量四种方式

临界区（Critical Section）、互斥量（Mutex）、信号量（Semaphore）、事件（Event）的区别

1、临界区：通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。

2、互斥量：采用互斥对象机制。

只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享 .互斥量比临界区复杂。因为使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

3、信号量：它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的***线程数目 .

信号量对象对线程的同步方式与前面几种方法不同，信号允许多个线程同时使用共享资源，这与操作系统中的PV操作相同。它指出了同时访问共享资源的线程***数目。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的***线程数目。

PV操作及信号量的概念都是由荷兰科学家E.W.Dijkstra提出的。信号量S是一个整数，S大于等于零时代表可供并发进程使用的资源实体数，但S小于零时则表示正在等待使用共享资源的进程数。

P操作申请资源：

（1）S减1；

（2）若S减1后仍大于等于零，则进程继续执行；

（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转入进程调度。

V操作 释放资源：

（1）S加1；

（2）若相加结果大于零，则进程继续执行；

（3）若相加结果小于等于零，则从该信号的等待队列中唤醒一个等待进程，然后再返回原进程继续执行或转入进程调度。

4、事 件： 通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作 .

总结：

1． 互斥量与临界区的作用非常相似，但互斥量是可以命名的，也就是说它可以跨越进程使用。所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的互斥量一旦被创建，就可以通过名字打开它。

2． 互斥量（Mutex），信号灯（Semaphore），事件（Event）都可以被跨越进程使用来进行同步数据操作，而其他的对象与数据同步操作无关，但对于进程和线程来讲，如果进程和线程在运行状态则为无信号状态，在退出后为有信号状态。所以可以使用WaitForSingleObject来等待进程和线程退出。

3． 通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号灯对象可以说是一种资源计数器。

二、进程间通信方式

由于比较容易混淆，我们把进程间通信方法也列在这里做比较。

进程通信也就是所谓的IPC问题，主要是指进程间交换数据的方式。进程通信包括高级通信与低级通信，其中进程同步与互斥属于低级通信，主要用于插U农地控制信号；高级通信包括三种：共享存储系统（有的地方称作共享内存区）、消息传递系统（有的地方称作消息队列）、管道。

信号量是进程同步与互斥的常用方法，也可以作为低级的进程通信方法，用于传递控制信号。

简而言之，进程间通信方式主要包括管道、FIFO、消息队列、信号量、共享内存。

1.管道，还有命名管道和非命名管道(即匿名管道)之分，非命名管道(即匿名管道)只能用于父子进程通讯，命名管道可用于非父子进程，命名管道就是FIFO，管道是先进先出的通讯方式

2.消息队列，是用于两个进程之间的通讯，首先在一个进程中创建一个消息队列，然后再往消息队列中写数据，而另一个进程则从那个消息队列中取数据。需要注意的是，消息队列是用创建文件的方式建立的，如果一个进程向某个消息队列中写入了数据之后，另一个进程并没有取出数据，即使向消息队列中写数据的进程已经结束，保存在消息队列中的数据并没有消失，也就是说下次再从这个消息队列读数据的时候，就是上次的数据！！！！

3.信号量，它与WINDOWS下的信号量是一样的，所以就不用多说了

4.共享内存，类似于WINDOWS下的DLL中的共享变量，但LINUX下的共享内存区不需要像DLL这样的东西，只要首先创建一个共享内存区，其它进程按照一定的步骤就能访问到这个共享内存区中的数据，当然可读可写

以上几种方式的比较：

1.管道：速度慢，容量有限，只有父子进程能通讯

2.FIFO：任何进程间都能通讯，但速度慢

3.消息队列：容量受到系统限制，且要注意***次读的时候，要考虑上一次没有读完数据的问题

4.信号量：不能传递复杂消息，只能用来同步

5.共享内存区：能够很容易控制容量，速度快，但要保持同步，比如一个进程在写的时候，另一个进程要注意读写的问题，相当于线程中的线程安全，当然，共享内存区同样可以用作线程间通讯，不过没这个必要，线程间本来就已经共享了同一进程内的一块内存

本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。一般说来，为了获得共享资源，进程需要执行下列操作：

（1）测试控制该资源的信号量；

（2）若此信号量的值为正，则允许进行使用该资源，进程将进号量减1；

（3）若此信号量为0，则该资源目前不可用，进程进入睡眠状态，直至信号量值大于0，进程被唤醒，转入步骤（1）；

（4）当进程不再使用一个信号量控制的资源时，信号量值加1，如果此时有进程正在睡眠等待此信号量，则唤醒此进程。

套接字通信并不为Linux所专有，在所有提供了TCP/IP协议栈的操作系统中几乎都提供了socket，而所有这样操作系统，对套接字的编程方法几乎是完全一样的

三、进程/线程同步机制与进程间通信机制比较

很明显2者有类似，但是差别很大

同步主要是临界区、互斥、信号量、事件

进程间通信是管道、内存共享、消息队列、信号量、socket

共通之处是，信号量和消息（事件）

小结：

进程互斥、同步与通信的关系：进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，由此看来，进程互斥、同步都可以看做进程的通信；

信号量是进程同步与互斥的常用方法，也可以作为低级的进程通信方法，用于传递控制信号；

管道与管程是不同的，管程是进程同步的方式，而管道则是进程通信的方式；

futex内核实现源码分析（3）

futex同步机制包括用户态的原子操作和内核态的futex系统调用两部分组成，其调用原型如下：

在futex系统调用内部是通过do_futex()完成具体操作

futex系统调用的参数很多，而do_futex的参数比futex还要多出一个来。这是由于同一个futex调用要根据不同的操作类型来完成不同的操作，而具体的操作所需的参数因目的不同而有所差异，每种具体的操作类型所需的参数数目以及具体参数的含义由其参数op决定。具体op操作类型的定义具体如下：

具体的futex系统调用如下，在futex(……)中根据操作类型op对参数进行调整，然后调用do_futex(……)。主要有以下几种情况：

在do_futex(……)中，主要根据op代表的具体操作类型进行不同分支的操作。例如FUTEX_WAIT执行futex_wait(uaddr, flags, val, timeout, val3)，FUTEX_WAKE则执行futex_wake(uaddr, flags, val, val3)，这是最基本futex阻塞唤醒操作。可以看到FUTEX_WAIT_BITSET和FUTEX_WAKE_BITSET最终调用的具体操作函数也是futex_wait(uaddr, flags, val, timeout, val3)和futex_wake(uaddr, flags, val, val3)，只不过FUTEX_WAIT和FUTEX_WAKE在执行具体操作之前将bitset参数val3设置为全匹配。另外操作函数中flag参数指明该futex变量时进程间共享的还进程私有的，该参数具体值根据op的值设定。

后面会主要对futex_wait(……)和futex_wake(……)进行详细分析。

参考：

如何解决在c api调用中异常退出导致卡在 futex

_db.00* 称为 bdb的env文件, 你需要 做db_recovery(把 env文件删掉重做).

实际上, bdb可以检测到 进程异常退出, 并自动做 恢复, 你需要 在打开 db时加入 DB_REGISTERflag.

Linux 之mutex 源码分析

 mutex相关的函数并不是linux kernel实现的，而是glibc实现的，源码位于nptl目录下。

首先说数据结构：

typedef union

{

  struct

  {

    int __lock;

    unsigned int __count;

    int __owner;

    unsigned int __nusers;

    int __kind;

    int __spins;

  } __data;

  char __size[__SIZEOF_PTHREAD_MUTEX_T];

  long int __align;

} pthread_mutex_t;

 int __lock;  资源竞争引用计数

 int __kind; 锁类型，init 函数中mutexattr 参数传递，该参数可以为NULL，一般为 PTHREAD_MUTEX_NORMAL

结构体其他元素暂时不了解，以后更新。

int

__pthread_mutex_init (mutex, mutexattr)

     pthread_mutex_t *mutex;

     const pthread_mutexattr_t *mutexattr;

{

  const struct pthread_mutexattr *imutexattr;

  assert (sizeof (pthread_mutex_t) = __SIZEOF_PTHREAD_MUTEX_T);

  imutexattr = (const struct pthread_mutexattr *) mutexattr ?: def***lt_attr;

  memset (mutex, '', __SIZEOF_PTHREAD_MUTEX_T);

  mutex-__data.__kind = imutexattr-mutexkind ~0x80000000;

  // mutex-__count = 0;        already done by memset

  // mutex-__owner = 0;        already done by memset

  // mutex-__nusers = 0;        already done by memset

  // mutex-__spins = 0;        already done by memset

  return 0;

}

init函数就比较简单了，将mutex结构体清零，设置结构体中__kind属性。

int

__pthread_mutex_lock (mutex)

     pthread_mutex_t *mutex;

{

  assert (sizeof (mutex-__size) = sizeof (mutex-__data));

  pid_t id = THREAD_GETMEM (THREAD_SELF, tid);

  switch (__builtin_expect (mutex-__data.__kind, PTHREAD_MUTEX_TIMED_NP))

    {

     …

    def***lt:

    case PTHREAD_MUTEX_TIMED_NP:

    simple:

      LLL_MUTEX_LOCK (mutex-__data.__lock);

      break;

  …

  }

  assert (mutex-__data.__owner == 0);

  mutex-__data.__owner = id;

#ifndef NO_INCR

  ++mutex-__data.__nusers;

#endif

  return 0;

}

该函数主要是调用LLL_MUTEX_LOCK， 省略部分为根据mutex结构体__kind属性不同值做些处理。

宏定义函数LLL_MUTEX_LOCK最终调用，将结构体mutex的__lock属性作为参数传递进来

#define __lll_mutex_lock(futex)                                                

  ((void) ({                                                                

    int *__futex = (futex);                                                

    if (atomic_compare_and_exchange_bool_acq (__futex, 1, 0) != 0)        

      __lll_lock_wait (__futex);                                        

  }))

atomic_compare_and_exchange_bool_acq (__futex, 1, 0)宏定义为：

#define atomic_compare_and_exchange_bool_acq(mem, newval, oldval)

  ({ __typeof (mem) __gmemp = (mem);                                     

     __typeof (*mem) __gnewval = (newval);                             

     *__gmemp == (oldval) ? (*__gmemp = __gnewval, 0) : 1; })

这个宏实现的功能是：

如果mem的值等于oldval，则把newval赋值给mem，放回0，否则不做任何处理，返回1.

由此可以看出，当mutex锁限制的资源没有竞争时，__lock 属性被置为1，并返回0，不会调用__lll_lock_wait (__futex); 当存在竞争时，再次调用lock函数，该宏不做任何处理，返回1，调用__lll_lock_wait (__futex);

void

__lll_lock_wait (int *futex)

{

  do

    {

      int oldval = atomic_compare_and_exchange_val_acq (futex, 2, 1);

      if (oldval != 0)

lll_futex_wait (futex, 2);

    }

  while (atomic_compare_and_exchange_bool_acq (futex, 2, 0) != 0);

}

atomic_compare_and_exchange_val_acq (futex, 2, 1); 宏定义：

#define atomic_compare_and_exchange_val_acq(mem, newval, oldval)

  ({ __typeof (mem) __gmemp = (mem);                                     

     __typeof (*mem) __gret = *__gmemp;                                     

     __typeof (*mem) __gnewval = (newval);                             

     if (__gret == (oldval))                                             

       *__gmemp = __gnewval;                                             

     __gret; })

这个宏实现的功能是，当mem等于oldval时，将mem置为newval，始终返回mem原始值。

此时，futex等于1，futex将被置为2，并且返回1. 进而调用

lll_futex_wait (futex, 2);

#define lll_futex_timed_wait(ftx, val, timespec)                        

({                                                                        

   DO_INLINE_SYSCALL(futex, 4, (long) (ftx), FUTEX_WAIT, (int) (val),        

     (long) (timespec));                                

   _r10 == -1 ? -_retval : _retval;                                        

})

该宏对于不同的平台架构会用不同的实现，采用汇编语言实现系统调用。不过确定的是调用了Linux kernel的futex系统调用。

futex在linux kernel的实现位于：kernel/futex.c

SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,

struct timespec __user *, utime, u32 __user *, uaddr2,

u32, val3)

{

struct timespec ts;

ktime_t t, *tp = NULL;

u32 val2 = 0;

int cmd = op FUTEX_CMD_MASK;

if (utime (cmd == FUTEX_WAIT || cmd == FUTEX_LOCK_PI ||

      cmd == FUTEX_WAIT_BITSET ||

      cmd == FUTEX_WAIT_REQUEUE_PI)) {

if (copy_from_user(ts, utime, sizeof(ts)) != 0)

return -EFAULT;

if (!timespec_valid(ts))

return -EINVAL;

t = timespec_to_ktime(ts);

if (cmd == FUTEX_WAIT)

t = ktime_add_safe(ktime_get(), t);

tp = t;

}

if (cmd == FUTEX_REQUEUE || cmd == FUTEX_CMP_REQUEUE ||

    cmd == FUTEX_CMP_REQUEUE_PI || cmd == FUTEX_WAKE_OP)

val2 = (u32) (unsigned long) utime;

return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);

}

futex具有六个形参，pthread_mutex_lock最终只关注了前四个。futex函数对参数进行判断和转化之后，直接调用do_futex。

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;

clockrt = op FUTEX_CLOCK_REALTIME;

if (clockrt cmd != FUTEX_WAIT_BITSET cmd != FUTEX_WAIT_REQUEUE_PI)

return -ENOSYS;

switch (cmd) {

case FUTEX_WAIT:

val3 = FUTEX_BITSET_MATCH_ANY;

case FUTEX_WAIT_BITSET:

ret = futex_wait(uaddr, fshared, val, timeout, val3, clockrt);

break;

         …

def***lt:

ret = -ENOSYS;

}

return ret;

}

省略部分为对其他cmd的处理，pthread_mutex_lock函数最终传入的cmd参数为FUTEX_WAIT，所以在此只关注此分之，分析futex_wait函数的实现。

static int futex_wait(u32 __user *uaddr, int fshared,

      u32 val, ktime_t *abs_time, u32 bitset, int clockrt)

{

struct hrtimer_sleeper timeout, *to = NULL;

struct restart_block *restart;

struct futex_hash_bucket *hb;

struct futex_q q;

int ret;

           … … //delete parameters check and convertion

retry:

ret = futex_wait_setup(uaddr, val, fshared, q, hb);

if (ret)

goto out;

futex_wait_queue_me(hb, q, to);

… … //other handlers

return ret;

}

futex_wait_setup 将线程放进休眠队列中，

futex_wait_queue_me(hb, q, to);将本线程休眠，等待唤醒。

唤醒后，__lll_lock_wait函数中的while (atomic_compare_and_exchange_bool_acq (futex, 2, 0) != 0); 语句将被执行，由于此时futex在pthread_mutex_unlock中置为0，所以atomic_compare_and_exchange_bool_acq (futex, 2, 0)语句将futex置为2，返回0. 退出循环，访问用户控件的临界资源。

int

internal_function attribute_hidden

__pthread_mutex_unlock_usercnt (mutex, decr)

     pthread_mutex_t *mutex;

     int decr;

{

  switch (__builtin_expect (mutex-__data.__kind, PTHREAD_MUTEX_TIMED_NP))

    {

   … …

    def***lt:

    case PTHREAD_MUTEX_TIMED_NP:

    case PTHREAD_MUTEX_ADAPTIVE_NP:

      break;

    }

  mutex-__data.__owner = 0;

  if (decr)

    --mutex-__data.__nusers;

  lll_mutex_unlock (mutex-__data.__lock);

  return 0;

}

省略部分是针对不同的__kind属性值做的一些处理，最终调用 lll_mutex_unlock。

该宏函数最终的定义为：

#define __lll_mutex_unlock(futex)                        

  ((void) ({                                                

    int *__futex = (futex);                                

    int __val = atomic_exchange_rel (__futex, 0);        

    if (__builtin_expect (__val 1, 0))                

      lll_futex_wake (__futex, 1);                        

  }))

atomic_exchange_rel (__futex, 0);宏为：

#define atomic_exchange_rel(mem, value)

  (__sync_synchronize (), __sync_lock_test_and_set (mem, value))

实现功能为：将mem设置为value，返回原始mem值。

__builtin_expect (__val 1, 0) 是编译器优化语句，告诉编译器期望值，也就是大多数情况下__val 1 ？是0，其逻辑判断依然为if(__val 1)为真的话执行 lll_futex_wake。

现在分析，在资源没有被竞争的情况下，__futex 为1，那么返回值__val则为1，那么 lll_futex_wake (__futex, 1);        不会被执行，不产生系统调用。 当资源产生竞争的情况时，根据对pthread_mutex_lock 函数的分析，__futex为2， __val则为2，执行 lll_futex_wake (__futex, 1); 从而唤醒等在临界资源的线程。

lll_futex_wake (__futex, 1); 最终会调动同一个系统调用，即futex, 只是传递的cmd参数为FUTEX_WAKE。

在linux kernel的futex实现中，调用

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

{

struct futex_hash_bucket *hb;

struct futex_q *this, *next;

struct plist_head *head;

union futex_key key = FUTEX_KEY_INIT;

int ret;

if (!bitset)

return -EINVAL;

ret = get_futex_key(uaddr, fshared, key);

if (unlikely(ret != 0))

goto out;

hb = hash_futex(key);

spin_lock(hb-lock);

head = hb-chain;

plist_for_each_entry_safe(this, next, head, list) {

if (match_futex (this-key, key)) {

if (this-pi_state || this-rt_waiter) {

ret = -EINVAL;

break;

}

if (!(this-bitset bitset))

continue;

wake_futex(this);

if (++ret = nr_wake)

break;

}

}

spin_unlock(hb-lock);

put_futex_key(fshared, key);

out:

return ret;

}

该函数遍历在该mutex上休眠的所有线程，调用wake_futex进行唤醒，

static void wake_futex(struct futex_q *q)

{

struct task_struct *p = q-task;

get_task_struct(p);

plist_del(q-list, q-list.plist);

***p_wmb();

q-lock_ptr = NULL;

wake_up_state(p, TASK_NORMAL);

put_task_struct(p);

}

wake_up_state(p, TASK_NORMAL);  的实现位于kernel/sched.c中，属于linux进程调度的技术。

futex的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于、futex的信息别忘了在本站进行查找喔。