1. 缘起
随着SMP(Symmetrical Multi-Processing)架构的流行和epoll类系统调用对非阻塞fd监视的支持，高性能服务器端的开发已经能够实现CPU计算和IO的分离。为了充分发挥CPU的计算能力，服务器端的设计必须要尽量减少线程切换。引起线程切换最重要的原因之一就是对mutex和semaphor等锁的使用。本文从计算机体系架构、操作系统的支持和mutex的实现彻底分析Linux用户空间mutex的实现，分析的源码版本是glib-2.3.4和kernel-2.6.8。
2.
体系结构和指令的支持
在UP(uni processor)架构下，从用户空间的角度看，中断打断了程序的正常执行。操作系统在处理完中断之后，返回用户空间的之前，重新调度系统中的线程执行。由于CPU是在执行汇编指令结束后响应中断，那么单条汇编指令的执行就是原子的。
在SMP下，由于存在CPU Local Cache和每个CPU的指令周期不同，单条汇编指令的执行不会是原子的。X86 SMP提供了一个lock指令前缀，使得某些汇编指令的执行是原子的。看如下x86_64体系结构的汇编代码，来自glibc。
Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2中对cmpxchg指令的解释如下：
This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically.
所有以lock为前缀的指令都起内存栅栏的作用。内存栅栏使编译器确保对RAM中数据的改变对所有CPU都是可见的。
上述汇编对应的伪代码：
Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2中对cmpxchg指令的解释如下：
This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically.
by gaolingfei
所有以lock为前缀的指令都起内存栅栏的作用。内存栅栏使编译器确保对RAM中数据的改变对所有CPU都是可见的。
上述汇编对应的伪代码：
3.
操作系统支持
按照操作系统的经典定义，进程是资源分配的最小单位，线程是调度的最小单位。
Linux操作系统提供了
futex系统调用以支持
mutex等锁的实现。
futex的主要功能是使得线程以
TASK_INTERRUPTIBLE状态等待处于进程空间的某变量的改变，或者使得某线程可以唤醒等待该变量的其他线程。
2.6.8版的
Kernel中，
futex的实现使用一个
futex_hash_bucket。操作系统用户空间任何线程如果在等待mutex或者semaphore的up操作，都是以每个锁的address等为key，将自身线程挂到该futex_hash_bucket等待被唤醒。
实现
wait的步骤如下：
A.
down_read得到当前线程整个地址空间的读锁，从该步起到
up_read，与线程同一个进程的其他线程mmap()和brk()系统调用都会挂起，mmap()和brk()是malloc()和free()的基础。 ()(&
current->mm->mmap_sem);
B. 调用
find_extend_vma以确认用户空间锁的地址是否是shared or private mapping. shared mapping一般是进程有多个线程引起的。
find_extend_vma会搜索整个进程地址空间段组成红黑树，以确定该地址空间的类型。 ()(),
C. 计算
key。如果是单进程单线程，
Key为用户空间地址。如果为单进程多线程，需要执行
spin_lock得到用户地址对应的page，然后
spin_unlock。 page_table_lock会影响相应进程的page fault的处理。 (&
current->mm->page_table_lock)(&
current->mm->page_table_lock);
H. 将自身从
futex_hash_bucket移除。
实现
wake up的步骤如下：
A. 执行
wait的
A到
C。
C. 唤醒在锁上的一个等待线程。
4.
pthread_mutex
实现分析
pthread_mutex_lock()实现在
glibc-2.3.4 pthread_mutex_lock.c文件的
33行，该函数会根据
mutex在
init的时候设置的属性，选择不同的执行路径。
mutex的属性有四种：
A.
PTHREAD_MUTEX_TIMED_NP：默认属性。
pthread_mutex_lock()直接调用
lll_mutex_lock()。
B.
PTHREAD_MUTEX_RECURSIVE_NP：检查
mutex owner 是否为当前线程。该属性允许线程多次获取该锁。
C.
PTHREAD_MUTEX_ERRORCHECK_NP：如果同一线程两次
lock，会返回错误。
D.
PTHREAD_MUTEX_ADAPTIVE_NP：该锁会先
n次调用
lll_mutex_trylock()，
n为用户定义和
100的最小值。如果仍然失败，则调用
lll_mutex_lock()。
lll_mutex_trylock()不会调用
futex。
5.
spin lock
实现
nginx实现了
spin lock以保护多进程对
listen port的互斥
accept。
spinlock的实现如下：
Spinlock本质上是一个“忙等”锁，由于其不存在下节中总结的
mutex的缺点，其对于小资源是最高效的锁。相比上节中
mutex的
PTHREAD_MUTEX_ADAPTIVE_NP属性，
nginx的
spinlock是一个更完美的实现方案。
6.
总结
在设置
PTHREAD_MUTEX_TIMED_NP属性和单进程多线程模型下，
pthread_mutex_lock()对同进程的其他线程的影响如下：
A.
pthread_mutex_lock()占用的大部分
CPU时间当中，直接影响其他线程调用
mmap()，
brk()，
malloc和
free()。
B. 对进程处理
page fault也会有影响。
D. 最重要的是，锁的使用会引起线程的频繁切换，导致
cpu cache miss和
TLB miss。
对于系统中，需要互斥访问的资源，如下建议：
A. 内核中对于小资源如链表的增删，多是使用
spin lock保护。
B. 在设置
PTHREAD_MUTEX_ADAPTIVE_NP属性下，
mutex既可以是
spin lock，也可以是阻塞锁。
C. 使用
atomic_add_return(i, v)，原子对变量
i增加
v值，并且返回操作后的值。相反操作：
atomic_sub_return(i, v)。
D. 使用
Per-CPU variables，例如多线程程序中要每隔
1秒，统计某项操作的值。该变量最好是
cache alignment。
E. 对于如数据库频繁更新的操作，可以使用数据库的多版本并发控制方法减少对
mutex的
lock。
本文转自百度技术51CTO博客，原文链接：http://blog.51cto.com/baidutech/1033629
，如需转载请自行联系原作者
