linux-锁实现原理

futex转载链接在计算中，futex（“快速用户空间互斥锁”的缩写）是一个Linux内核系统调用，程序员可以使用它来实现基本锁定，或作为更高级别锁定的构建块信号量和POSIX互斥量或条件变量等抽象。futex由一个内核空间等待队列组成，该队列附加到用户空间中的对齐整数。多个进程或线程完全在用户空间中对整数进行操作（使用原子操作以避免相互干扰），并且仅诉诸于相对昂贵的系统调用来请求等待队列上的操作（例如唤醒等待进程，或将等待队列中的当前进程）。一个正确编程的基于futex的锁不会使用系统调用，除非锁被争用；由于大多数操作不需要进程之间的仲裁，因此在大多数情况下不会发生这种情况。背景在传统的Unix系统中，SystemVIPC等进程间同步机制都是对一个该内核对象对所有要同步的进程可见，提供共享状态信息和原子操作。当进程之间的同步必须通过系统调用在内核中完成时。但是经过研究发现，很多同步是非竞争性的，即在一个进程进入互斥量和退出互斥量的这段时间里，往往没有进程也进入互斥量或者请求同一个同步变量.的。但是这样的话，进程也会落入内核，看看有没有人在和它竞争，退出的时候，也会落入内核，看看有没有进程在等待同一个同步变量。这些不必要的系统调用（或内核陷阱）会导致大量的性能开销。简介为了解决这个问题，Futex应运而生。Futex是一种混合了用户态和内核态的同步机制。首先，synchronized进程通过mmap共享一块内存。futex变量位于这个共享内存中，操作是原子的。当进程试图进入或退出互斥量时，它首先检查共享内存。futex变量，如果没有发生竞争，只修改futex，不执行系统调用。当你通过访问futex变量告诉进程存在竞争时，你仍然要执行系统调用来完成相应的处理（等待或唤醒）。简单的说就是在用户态检查futex。知道没有竞争就不用陷入内核，大大提高了低竞争的效率。Futex系统调用Futex是用户态和内核态的混合机制，所以需要两部分共同完成。Linux提供了sys_futex系统调用，为进程竞争情况下的同步处理提供支持。其原型及系统调用号：#include#includeintfutex(int*uaddr,intop,intval,conststructtimespec*timeout,int*uaddr2,intval3);#define__NR_futex240uaddr:用户态共享内存地址，存放一个对齐的整数计数器。op:存放操作类型(共5种):FUTEX_WAIT:原子检查uaddr中计数器的值是否为val，如果是则让进程休眠直到FUTEX_WAKE或超时，即挂进程到等待队列对应uaddr往上。FUTEX_WAKE：唤醒等待uaddr的val进程。可以看出FUTEX_WAIT和FUTEX_WAKE只是用来挂起或者唤醒进程的。当然，这部分工作只能在内核态完成。futex同步机制和futex系统调用应该有所区别。futex同步机制还包括用户态的操作，我们会在下一节提到。Futex同步机制所有的futex同步操作都应该从用户空间开始。首先，创建一个futex同步变量，它是一个位于共享内存中的整数计数器。当进程试图持有锁或进入互斥体时，对futex进行“down”操作，即futex同步变量自动减1。如果同步变量变为0，则不会发生竞争，进程照常执行。如果同步变量为负数，说明存在竞争，需要调用futex系统调用的futex_wait操作让当前进程休眠。当进程释放锁或离开互斥体时，对futex进行“up”操作，即原子地给futex同步变量加1。如果同步变量从0变为1，则不会发生争用，进程照常执行。如果添加前同步变量为负，说明存在竞争，需要调用futex系统调用的futex_wake操作唤醒一个或多个等待进程。这里的原子加减法一般是用CAS（CompareandSwap）来完成的，跟平台有关。CAS的基本形式是：CAS(addr,old,new)，当addr中存放的值等于old时，将其替换为new。在x86平台上，有一条专门的指令可以执行此操作：cmpxchg。