[转载]LinuxFutex的设计与实现
Linux Futex的设计与实现
引⼦
在编译2.6内核的时候，你会在编译选项中看到[*] Enable futex support这⼀项，上⽹查，有的资料会告诉你"不选这个内核不⼀定能正确的运⾏使⽤glibc的程序"，那futex是什么？和glibc⼜有什么关系呢？
1. 什么是
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。
2. 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同步机制还包括⽤户态下的操作，我们将在下节提到。
3. 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是从⽤户态开始，由⽤户态和核⼼态协调完成的。
4. 进/线程利⽤futex同步
进程或者线程都可以利⽤futex来进⾏同步。
对于线程，情况⽐较简单，因为线程共享虚拟内存空间，虚拟地址就可以唯⼀的标识出futex变量，即线程⽤同样的虚拟地址来访问futex变量。
对于进程，情况相对复杂，因为进程有独⽴的虚拟内存空间，只有通过mmap()让它们共享⼀段地址空
间来使⽤futex变量。每个进程⽤来访问futex的虚拟地址可以是不⼀样的，只要系统知道所有的这些虚拟地址都映射到同⼀个物理内存地址，并⽤物理内存地址来唯⼀标识futex 变量。
1. Futex变量的特征：1)位于共享的⽤户空间中 2)是⼀个32位的整型 3)对它的操作是原⼦的
2. Futex在程序low-contention的时候能获得⽐传统同步机制更好的性能。
3. 不要直接使⽤Futex系统调⽤。
4. Futex同步机制可以⽤于进程间同步，也可以⽤于线程间同步。
Linux中的线程同步机制(⼆
在linux中进⾏多线程开发，同步是不可回避的⼀个问题。在POSIX标准中定义了三种线程同步机制: Mutexes(互斥量), Condition Variables(条件变量)和POSIX Semaphores(信号量)。NPTL基本上实现了POSIX，⽽glibc⼜使⽤NPTL作为⾃⼰的线程库。因此glibc中包含了这三种同步机制的实现(当然还包括其他的同步机制，如APUE⾥提到的读写锁)。
Glibc中常⽤的线程同步⽅式举例
变量定义： sem_t sem;
初始化： sem_init(&sem,0,1);
进⼊加锁: sem_wait(&sem);
退出解锁: sem_post(&sem);
变量定义： 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) \
({ \
...
__asm __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，让当前线程休眠。
从这个例⼦我们可以看出，在Semaphores的实现过程中使⽤了futex，不仅仅是说其使⽤了futex系统调⽤(再重申⼀遍只使⽤futex系统调⽤是不够的)，⽽是整个建⽴在futex机制上，包括⽤户态下的操作和核⼼态下的操作。其实对于其他glibc的同步机制来说也是⼀样，都采纳了futex作为其基础。所以才会在futex的manual中说：对于⼤多数程序员不需要直接使⽤futexes，取⽽代之的是依靠建⽴在futex之上的系统库，如NPTL线程库(most programmers will in fact not be using futexes directly but instead rely on system libraries built on them, such as the NPTL pthreads implementation)。所以才会有如果在编译内核的时候不 Enable futex support，就"不⼀定能正确的运⾏使⽤Glibc的程序"。
⼩结
1. Glibc中的所提供的线程同步⽅式，如⼤家所熟知的Mutex,Semaphore等，⼤多都构造于futex之上了，除了特殊情况，⼤家没必要再去
实现⾃⼰的futex同步原语。
2. ⼤家要做的事情，似乎就是按futex的manual中所说得那样: 正确的使⽤Glibc所提供的同步⽅式，并在使⽤它们的过程中，意识到它们
是利⽤futex机制和linux配合完成同步操作就可以了。
Linux中的线程同步机制(三
上回说到Glibc中(NPTL)的线程同步⽅式如Mutex,Semaphore等都使⽤了futex作为其基础。那么实际使⽤是什么样⼦，⼜会碰到什么问题呢？
先来看⼀个使⽤semaphore同步的例⼦。
sem_t sem_a;
void *task1();
int main(void){
int ret=0;
pthread_t thrd1;
sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL); //创建⼦线程
pthread_join(thrd1,NULL); //等待⼦线程结束
}
void *task1()
{
int sval = 0;
sem_wait(&sem_a); //持有信号量
sleep(5); //do_nothing
sem_getvalue(&sem_a,&sval);
printf("sem value = %d\n",sval);
sem_post(&sem_a); //释放信号量
}
程序很简单，我们在主线程(执⾏main的线程)中创建了⼀个线程，并⽤join等待其结束。在⼦线程中，先持有信号量，然后休息⼀会⼉，再释放信号量，结束。
因为这段代码中只有⼀个线程使⽤信号量，也就是没有线程间竞争发⽣，按照futex的理论，因为没有竞争，所以所有的锁操作都将在⽤户态中完成，⽽不会执⾏系统调⽤⽽陷⼊内核。我们⽤strace来跟踪⼀下这段程序的执⾏过程中所发⽣的系统调⽤:
...
20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished ...>
20534 futex(0x8049870, FUTEX_WAKE, 1) = 0
20533 <... futex resumed> ) = 0
...
20533是main线程的id,20534是其⼦线程的id。出乎我们意料之外的是这段程序还是发⽣了两次futex系统调⽤，我们来分析⼀下这分别是什么原因造成的。
1. 出⼈意料的
20534 futex(0x8049870, FUTEX_WAKE, 1) = 0
⼦线程还是执⾏了FUTEX_WAKE的系统调⽤，就是在sem_post(&sem_a)；的时候，请求内核唤醒⼀个等待在sem_a上的线程, 其返回值是0，表⽰现在并没有线程等待在sem_a(这是当然的，因为就这么⼀个线程在使⽤sem_a)，这次futex系统调⽤⽩做了。这似乎和 futex的理论有些出⼊，我们再来看⼀下sem_post的实现。
int sem_post (sem_t *sem)
{
int *futex = (int *) sem;
int nr = atomic_increment_val (futex);
int err = lll_futex_wake (futex, nr);
return 0;
}
我们看到，Glibc在实现sem_post的时候给futex原⼦性的加上1后，不管futex的值是什么，都执⾏了lll_futex_wake()，即
linux内核设计与实现 pdffutex(FUTEX_WAKE)系统调⽤。
在第⼆部分中(见前⽂)，我们分析了sem_wait的实现，当没有竞争的时候是不会有futex调⽤的，现在看来真的是这样，但是在sem_post的时候，⽆论有⽆竞争，都会调⽤sys_futex()，为什么会这样呢？我觉得应该结合semaphore的语义来理解。在semaphore的语义
中，sem_wait()的意思是："挂起当前进程，直到semaphore的值为⾮0，它会原⼦性的减少semaphore计数值。" 我们可以看到,semaphore 中是通过0或者⾮0来判断阻塞或者⾮阻塞线程。即⽆论有多少线程在竞争这把锁，只要使⽤了 semaphore，semaphore的值都会是0。这样，当线程推出互斥区，执⾏sem_post()，释放semaphore的时候，将其值由0改 1，并不知道是否有线程阻塞在这个semaphore上，所以只好不管怎么样都执⾏futex(uaddr, FUTEX_WAKE, 1)尝试着唤醒⼀个进程。⽽相反的，当sem_wait()，如果semaphore由1变0，则意味着没有竞争发⽣，所以不必去执⾏futex系统
调⽤。我们假设⼀下，如果抛开这个语义，如果允许semaphore值为负，则也可以在sem_post()的时候，实现futex机制。
2. 半路杀出的
那另⼀个futex系统调⽤是怎么造成的呢? 是因为pthread_join();
在Glibc中，pthread_join也是⽤futex系统调⽤实现的。程序中的pthread_join(thrd1,NULL); 就对应着
20533 futex(0xb7db1be8, FUTEX_WAIT, 20534, NULL <unfinished ...>
很好解释，主线程要等待⼦线程(id号20534上)结束的时候，调⽤futex(FUTEX_WAIT)，并把var参数设置为要等待的⼦线程号 (20534)，然后等待在⼀个地址为0xb7db1be8的futex变量上。当⼦线程结束后，系统会负责把主线程唤醒。于是主线程就
20533 <... futex resumed> ) = 0
恢复运⾏了。
要注意的是，如果在执⾏pthread_join()的时候，要join的线程已经结束了，就不会再调⽤futex()阻塞当前进程了。
3. 更多的竞争。
我们把上⾯的程序稍微改改:
在main函数中:
int main(void){
...
sem_init(&sem_a,0,1);
ret=pthread_create(&thrd1,NULL,task1,NULL);
ret=pthread_create(&thrd2,NULL,task1,NULL);
ret=pthread_create(&thrd3,NULL,task1,NULL);
ret=pthread_create(&thrd4,NULL,task1,NULL);
pthread_join(thrd1,NULL);
pthread_join(thrd2,NULL);
pthread_join(thrd3,NULL);
pthread_join(thrd4,NULL);
...
}
这样就有更的线程参与sem_a的争夺了。我们来分析⼀下，这样的程序会发⽣多少次futex系统调⽤。
第⼀个进⼊的线程不会调⽤futex，⽽其他的线程因为要阻塞⽽调⽤，因此sem_wait会造成3次futex(FUTEX_WAIT)调⽤。
所有线程都会在sem_post的时候调⽤futex, 因此会造成4次futex(FUTEX_WAKE)调⽤。
别忘了还有pthread_join()，我们是按thread1, thread2, thread3, thread4这样来join的，但是线程的调度存在着随机性。如果thread1最后被调度，则只有thread1这⼀次futex调⽤，所以 pthread_join()造成的futex调⽤在1-4次之间。(虽然不是必然的，但是4次更常见⼀些)
所以这段程序⾄多会造成3+4+4=11次futex系统调⽤，⽤strace跟踪，验证了我们的想法。
19710 futex(0xb7df1be8, FUTEX_WAIT, 19711, NULL <unfinished ...>
19712 futex(0x8049910, FUTEX_WAIT, 0, NULL <unfinished ...>
19713 futex(0x8049910, FUTEX_WAIT, 0, NULL <unfinished ...>
19714 futex(0x8049910, FUTEX_WAIT, 0, NULL <unfinished ...>
19711 futex(0x8049910, FUTEX_WAKE, 1 <unfinished ...>
19710 futex(0xb75f0be8, FUTEX_WAIT, 19712, NULL <unfinished ...>
19712 futex(0x8049910, FUTEX_WAKE, 1 <unfinished ...>
19710 futex(0xb6defbe8, FUTEX_WAIT, 19713, NULL <unfinished ...>
19713 futex(0x8049910, FUTEX_WAKE, 1 <unfinished ...>
19710 futex(0xb65eebe8, FUTEX_WAIT, 19714, NULL <unfinished ...>
19714 futex(0x8049910, FUTEX_WAKE, 1) = 0
(19710是主线程，19711，19712，19713,19714是4个⼦线程)
4.
事情到这⾥就结束了吗？如果我们把semaphore换成Mutex试试。你会发现当⾃始⾃终没有竞争的时候，mutex会完全符合futex机制，不管是lock还是 unlock都不会调⽤futex系统调⽤。有竞争的时候，第⼀次pthread_mutex_lock的时候不会调⽤futex调⽤，看起来还正常。但是最后⼀次pthread_mutex_unlock的时候，虽然已经没有线程在等待mutex了，可还是会调⽤futex(FUTEX_WAKE)。原因是什么？欢迎讨论！！！
1. 虽然semaphore，mutex等同步⽅式构建在futex同步机制之上。然⽽受其语义等的限制，并没有完全按futex最初的设计实现。
2. pthread_join()等函数也是调⽤futex来实现的。
3. 不同的同步⽅式都有其不同的语义，不同的性能特征，适合于不同的场景。我们在使⽤过程中要知道他们的共性，也得了解它们之间
的差异。这样才能更好的理解多线程场景，写出更⾼质量的多线程程序。
Linux中的线程同步机制(四)--C语⾔实现
futex 的逻辑可以⽤如下C语⾔表⽰
int val = 0;
void lock()
{
int c
if ((c = cmpxchg(val, 0, 1)) != 0) {
if (c != 2)
c = xchg(val, 2);
while (c != 0) {
futex_wait((&val, 2);
c = xchg(val, 2);
}
}
}
void unlock()
{
if (atomic_dec(val) != 1)
futex_wake(&val, 1);
}
val 0: unlock
val 1: lock, no waiters
val2 : lock , one or more waiters
参见： futex are tricky
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论