深层次探讨mutex与semaphore之间的区别
背景
本文依旧和《PostgreSQL 同步流复制锁瓶颈分析》这篇文章有关。
本文主要介绍一下Linux下面信号量(semaphore)和互斥锁(mutex)的区别。
原文地址
http://www.aichengxu.com/view/2456963
原文
看过Linux内核的同学都知道，Linux内核中除了有semaphore之外，还有一个mutex lock。
前者我们的操作系统教科书称之为信号量，后者不知道教科书有没有具体的名称，但是在Linux内核中，它的称谓是”互斥锁”或者“互斥体”(总之，称谓不是问题)。
为了提升一下本帖的理论密度，特从Wiki中摘录一段关于semaphore的描述：
In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment.
A useful way to think of a semaphore is as a record of how many units of a particular resource are available, coupled with operations to safely
(i.e., without race conditions) adjust that record as units are required or become free, and if necessary wait until a unit of the resource becomes available.
Semaphores are a useful tool in the prevention of race conditions and deadlocks;
however, their use is by no means a guarantee that a program is free from these problems.
Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available)
are called binary semaphores (same functionality that mutexes have).
其中关键信息主要是
a semaphore is a data type for controlling access by multiple processes to a common resource in a parallel programming environment...
Semaphores which allow an arbitrary resource count are called counting semaphores, while semaphores which are restricted to the values 0 and 1 (or locked/unlocked, unavailable/available)
are called binary semaphores (same functionality that mutexes have)
也即信号量在并行处理环境下对多个processes访问某个公共资源进行保护，后面提到的binary semaphore，本质上应该就是mutex了，从same functionality that mutexes have这句话来看，
mutex和binary semaphore功能应该相同。从以上的文字中显然可以看到，相对mutex而言信号量的适用范围更广(mutex只是信号量的用途之一)，这个我们接下来在后续的Linux源码中也可以看到这其中某些细微之处的区分。
注：
昨天写这个帖子时手头没有操作系统方面的书籍拿来参考，今天我翻了一下《现代操作系统》(陈向群等译，机械工业出版社 1999年11月第1版)，
关于这个话题，书里明确提到的只有”2.2.5 信号量”，至于mutex，书中并没有作为一个独立的概念提出来，只是在讲信号量时提到了上面所说的binary semaphore，
并且说“信号量mutex(应该是指binary semaphore)用于互斥…互斥是避免混乱所必需的操作…信号量的另一种用途是用于实现同步(synchronization)。
信号量full和empty用来保证一定的事件顺序发生或不发生。
在本例中，它们保证缓冲区满的时候生产者停止运行，或者当缓冲区空的时候消费者停止运行。这种用法与互斥是不同的
P30-31
OK，理论上的概念有了，那么就来看看实际当中Linux下的semaphone到底长的啥样。以下是semaphore在Linux源码中的定义，源码来自3.2.9：
<include/linux/semaphore.h>
/* Please don't access any members of this structure directly
*/
struct semaphore
{
raw_spinlock_t lock;
unsigned
int count;
struct list_head wait_list;
};
如果count=1的话，那么semaphore就可以用来进行互斥操作了，早先内核源码中曾有一个专门的宏用来定义一个count=1的信号量DECLARE_MUTEX:
#define DECLARE_MUTEX(name)
\
struct semaphore name
= __SEMAPHORE_INITIALIZER(name, 1)
因为我们知道在Linux内核源码中还有一个DEFINE_MUTEX宏，所以Marcin Slusarz同学认为DECLARE_MUTEX宏容易让人困惑，毕竟它其实只是定义了一个count=1的信号量，因此该同学早在08年就向内核社区提交了一个PATCH，要求Rename DECLARE_MUTEX to DEFINE_SEMAPHORE
https://lkml.org/lkml/2008/10/26/74 ， 这个PATCH最终被社区所接受 (应该是在2.6.35和2.6.39版本之间，2.6.39已经没有了DECLARE_MUTEX，取而代之的是DEFINE_SEMAPHORE，但2.6.35还有，我当时在写《深入Linux设备驱动程序内核机制》时，最早引用的是2.6.35的版本，虽然在写作的中晚期将内核版本切换到2.6.39并在定稿阶段曾试图将之前写的文档全部修正到39版，但是DECLARE_MUTEX的残留显然是条漏网之鱼…)。
因为只是rename，所以DEFINE_SEMAPHORE的定义和原来的DECLARE_MUTEX完全相同。
那么既然count=1的信号量可以用来完成mutex lock的功能，那么内核何必再多此一举弄出个mutex lock出来呢？
关于Linux内核中的mutex机制，一篇很重要的文档来自内核源码中的Documentation/mutex-design.txt，由Ingo molnar同学起头，标题是”Generic Mutex Subsystem”，这篇文档开宗名义，直接将1楼中最后一个问题给端了出来(因此我估计这个问题此前已经有很多人骚扰过Ingo等同学了)：
“Why on earth do we need a new mutex subsystem, and what’s wrong with semaphores?” 前面已经讲过，当struct semaphore中的成员变量为1，就可以用来实现mutex这种东西，而且内核也明确定义了DEFINE_SEMAPHORE宏将count初始化为1，信号量上的DOWN与UP操作就更不用说了，在内核中也都有很好的实现，难道这种binary semaphore机制还不能满足我们的要求吗，干嘛还非得弄一个新的mutex机制出来呢？
下面是Ingo同学对此的解释，他说“firstly, there’s nothing wrong with semaphores. But if the simpler mutex semantics are sufficient for your code, then there are a couple of advantages of mutexes”，就是说，信号量在Linux中的实现是没任何问题的(上来先安抚一下大家躁动的心情)，但是mutex的语义相对来说要较信号量要来得简单，所以如果你的代码若只是想对某一共享资源进行互斥访问的话，那么使用这种简化了的mutex机制可以带来如下的一坨好处。
这句话字面上的理解是，mutex将binary semaphore的实现简化了(the simper mutex)，因此如果单纯从互斥的角度，用mutex会有很多好处。
其实后面我们会看到，在内核源码中，相对于semaphore的DOWN和UP实现，因为后期引入的特别针对binary semaphore的性能优化，也就是现在看到的mutex机制，其实现代码要更为复杂。
接下来Ingo列出的一大堆使用mutex的好处，在这个帖子中我们将一条一条地来看，再结合内核源码，看看事实是否的确象他说的那样：
mutex相比binary semaphore的优势
1. mutex更小，实际上随着LINUX的变化，可能又会不一样。
'struct mutex' is smaller on most architectures:
E.g. on x86, 'struct semaphore' is 20 bytes,
'struct mutex' is 16 bytes.
A smaller structure size means less RAM footprint, and better CPU-cache utilization.
这条最好验证，尤其还是x86平台，找个简单的内核模块，打印一下sizeof就可以了。
在我的x86-64 32位Linux系统(内核版本2.6.37)上，struct semaphore的大小是16字节，而struct mutex的大小则是20字节，
另两台x86-64 64位Linux系统(内核版本3.x)上的结果则是，struct semaphore的大小是24字节，而struct mutex的大小则是32字节。
这里不妨看一下struct mutex在内核中的定义：
<include/linux/mutex.h>
struct mutex
{
/* 1: unlocked, 0: locked,
negative: locked, possible waiters
*/
atomic_t count;
spinlock_t wait_lock;
struct list_head wait_list;
#if defined(CONFIG_DEBUG_MUTEXES)
|| defined(CONFIG_SMP)
struct task_struct
*owner;
#endif
#ifdef CONFIG_DEBUG_MUTEXES
const char
*name;
void
*magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
struct lockdep_map dep_map;
#endif
};
可以看到stuct mutex的定义其实比semaphore要来得复杂，里面有一些条件编译选项在里面。因为我们实际使用当中很少会使用它的调试功能，但是SMP现在则很普遍，我上面测试用的Linux环境都是多处理器系统。所以，mutex的定义实际上可简化为：
struct mutex
{
/* 1: unlocked, 0: locked,
negative: locked, possible waiters
*/
atomic_t count;
spinlock_t wait_lock;
struct list_head wait_list;
struct task_struct
*owner;
};
对比一下前面struct semaphore的定义你会发现，struct mutex比semaphore多了一个owner指针，因此上面的结果也就不难理解了，指针在32位系统上是4字节，而64位系统则是8字节。
我相信Ingo同学肯定不会胡说八道，那么明显地，相对于Ingo当时写mutex-design.txt时的情形，Linux内核源码发生了变化，这个在Linux的开发过程中实在是太正常不过的一件事了：
文档总是远远落后于代码的更新–大家都忙着写code，而很少有人想着去更新文档。
所以接下来Ingo提到的tighter code的优势，估计对mutex而言也不复存在了…
(他本人对mutex相对于semaphore在RAM footprint方面的优势不复存在的最新回复是：”Mutex got larger due to the adaptive spin-mutex performance optimization”，
因此我很自然地将这句话理解成，由于要实现所谓的“adaptive spin-mutex performance optimization”，那么就不惜牺牲了”less RAM footprint, and better CPU-cache utilization”，
所以我们有理由期待接下来的spin-mutex performance optimization会给mutex带来性能上比较大的提升…)
2. mutex所做的性能优化
下面我们来讨论一下mutex所做的性能优化，在将mutex的引入Linux内核这件事上，Ingo同学是带头大哥，喜欢围观Linux内核开发的同学对这厮肯定不会陌生，在我看来，这厮简直是牛逼得一塌糊涂，将kgdb引入内核也是这厮的杰作…
在mutex的性能提升方面，mutex-design.txt文档中有个具体的测试，采用了一个test-mutex的工具，因为google没找到这个东西，所以我个人猜测是Ingo自己搞出来的东西，本来想趁这两天放假将最新版下的binary semaphore和mutex的性能测试一把的，结果这两天啥都没干成。
我本来是想索要那个test-mutex程序的，但是Ingo只是建议采用perf来做。我自己找了个sysbench,但是还没时间用,貌似这个是针对数据库的。
之所以做这个测试，是我想知道采用mutex到底能比binary semaphore能带来多大的性能提升。
按照Ingo的测试数据，”the mutex based kernel was 2.4 times faster than the semaphore based kernel, and it also had 2.8 times less CPU utilization”，因为事先看过mutex的实现源码，所以我对这个数据有点怀疑，这也是为什么我自己要做性能分析的原因。
semaphore和mutex的代码实现中都有fast path和slow path两条路径，所谓的fast path，就是当前的代码直接获得信号量，而所谓的slow path，则是当前代码没能第一时间获得信号量。
semaphore和mutex在fast path上性能上的变化应该微乎其微，这个在metex-design.txt文档中也有说明。
两者之间最大的差别来自对slow path的处理，先看semaphore，
semaphore的slow path的调用链
down_interruptible –> __down_interruptible –> __down_common,
__down_common的代码实现为：
<kernel/semaphore.c>
static inline
int __sched __down_common(struct semaphore
*sem, long state,
long timeout)
{
struct task_struct
*task = current;
struct semaphore_waiter waiter;
list_add_tail(&waiter.list,
&sem->wait_list);
waiter.task
= task;
waiter.up
= 0;
for
(;;)
{
if
(signal_pending_state(state, task))
goto interrupted;
if
(timeout <= 0)
goto timed_out;
__set_task_state(task, state);
raw_spin_unlock_irq(&sem->lock);
timeout
= schedule_timeout(timeout);
raw_spin_lock_irq(&sem->lock);
if
(waiter.up)
return 0;
}
timed_out:
list_del(&waiter.list);
return
-ETIME;
interrupted:
list_del(&waiter.list);
return
-EINTR;
}
相对mutex对slow path的处理，semaphore要简单多了，它的主要流程是设置当前进程状态为TASK_INTERRUPTIBLE，然后睡眠到一个等待队列中。
所以semaphore如果第一时间没有获得信号量，那么它接下来就会sleep。
但是mutex的slow path呢，所有关于性能优化的代码都集中在该条路径中，所有它看起来比semaphore复杂许多…
mutex_lock的slow path的调用链
mutex_lock –> __mutex_lock_slowpath –> __mutex_lock_common，
所有的性能优化的代码又都集中在__mutex_lock_common中，这个函数有点长，等下我们不妨肢解来慢慢看。。。
mutex_lock在slow path当中优化的基本原理是：
拥有mutex lock的进程总是会在尽可能短的时间里释放。
基于此，mutex_lock的slow path部分会尽量避免进入睡眠状态，它试图通过短暂的spin来等待拥有互斥锁的进程释放它。
__mutex_lock_common的主体结构是两个for循环，中间加入对能否再次获得锁的判断逻辑。
<kernel/mutex.c>
/*
* Lock a mutex (possibly interruptible), slowpath:
*/
static inline int __sched
__mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
struct lockdep_map *nest_lock, unsigned long ip)
{
struct task_struct *task = current;
首先，我们能够达到这里，表明当前进程在一次争夺互斥锁的战争中失败了，此时几方争夺的互斥锁mutex中的owner即为成功获得该锁的task_struct对象…
先关闭内核可抢占性，是因为在后续的处理中，我们不希望被别的进程抢占出处理器，因为对当前进程而言，1st priority的事情是获得锁。高优先级进程在此时出现也不用抢占当前进程，因为当前进程接下来要么睡眠(那么就无需被抢占了)，要么获得锁而再次打开可抢占性。
preempt_disable();
内核配置选项，目前是内核默认的配置
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
源码中下面是一段很重要的注释，核心要点是mutex优化所基于的现实基础：
一个获得互斥锁的进程极大的可能会在很短的时间内释放掉它。
所以不同于semaphore的实现，mutex在第一次没获得锁的情形下，如果发现拥有该锁的进程正在别的处理器上运行且锁上没有其他等待者 (也即只有当前进程在等待该锁)，那么当前进程试图spin (说白了就是忙等待)，
这样有极大的概率是可以免去两次进程切换的开销，而重新获得之前竞争但未能成功的互斥锁—-性能提升处。
理论上，为了获得锁而进行的spin，其时间长短不应该超过两次进程切换的时间开销，否则此处优化将没有意义。
下面是第一个for循环, 循环中有两个break，一个直接return 0
for (;;) {
struct task_struct *owner;
/*
* If there's an owner, wait for it to either
* release the lock or go to sleep.
*/
owner = ACCESS_ONCE(lock->owner);
if (owner && !mutex_spin_on_owner(lock, owner))
break;
if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
lock_acquired(&lock->dep_map, ip);
mutex_set_owner(lock);
preempt_enable();
return 0;
}
/*
* When there's no owner, we might have preempted between the
* owner acquiring the lock and setting the owner field. If
* we're an RT task that will live-lock because we won't let
* the owner complete.
*/
if (!owner && (need_resched() || rt_task(task)))
break;
/*
* The cpu_relax() call is a compiler barrier which forces
* everything in this loop to be re-loaded. We don't need
* memory barriers as we'll eventually observe the right
* values at the cost of a few extra spins.
*/
arch_mutex_cpu_relax();
} //the first for loop
先看第一个break，if条件里owner基本上都会满足，如果owner=NULL则说明当前拥有锁的进程可能已经释放了锁，所以可以立刻退出该循环。
if条件中的mutex_spin_on_owner()是个非常有意思的函数，它通过per-jiffies的方式来确保可以在极短的时间里break那个while循环。
这段代码设计是如此地富有想象力，它通过if (need_resched())使得函数能在jiffies级别上跳出while循环，但是代码优化的性能提升则体现在owner_running中，
因为拥有锁的进程在极短的时间(肯定是低于jiffies这个级别的，可能在us级甚至更低)释放锁，如果通过if (need_resched())退出循环，则基本说明了本次优化的失败，
事实上还导致了性能的倒退(因为即便在HZ=1000的系统中，jiffies的级别也是非常粗糙的，现代处理器的进程切换的开销可能只在几个us或者几十个us，
如果让一个进程为了获得mutex lock而去spin几个jiffies，那么这简直就是暴敛天物了，如果这个时间让当前进程睡眠，那么其他进程就可以获得CPU资源，
而1个jiffies可以抵得上几十上百个进程切换的时间开销，根本就不需要在乎两次进程切换的时间开销。
但是IBM的Paul同学认为，如果让一个进程在获得mutex lock的情形下运行几个jiffies再释放lock，那么这可能是个bug。
我不认为这是对的，mutex lock不同于spin lock，不应该对mutex_lock与mutex_unlock之间的代码执行时间做什么限定)。
代码在mutex_spin_on_owner()中通过while循环来密切关注拥有锁的进程运行情况，一旦从while中跳出来，说明当前进程已经释放锁(通过owner_running)，或者当前拥有锁的进程运行的时间够长(可能为几个jiffies)，
最后返回前检查lock->owner，如果是NULL，源码注释中也讲得很清楚，”which is a sign for heavy contention”，在当前进程还没来得及下手前，lock已经被他人横刀夺爱了，
此种情形下最好去sleep了，否则spin的时间就足以抵得上一次进程切换的代价。。。
中间的return 0是个非常理想的情况，当前进程spin的过程中，锁的拥有者已经释放了锁，这个最简单，二次获得锁成功而直接返回。
接下来的break是当前进程在对方先行抢占到了锁但是还没来得及设定owner的时候抢占了它，或者当前进程是个实时进程，此时需要进入后半段处理。
在第二个for循环之前，从代码明显看到设计者已经在为当前进程进入sleep状态做最后的准备
(如果代码进入到第二个for循环，实际上意味着本次优化的失败，从性能的角度，这条路径上的性能肯定没有semaphore来得高，至少是没什么优势，因为你前面毕竟spin了一下，最后才sleep，
但是semaphore根本就不spin，第一次没拿到锁的话直接就sleep了)，
不过它在进入第二个for循环之前还是要做了个atomic_xchg动作，主要是对第一个for循环中的两个break进行处理，看看是否足够幸运能再次获得锁。
第二个for循环的代码已经和semaphore的slow path实现基本一样了，所以我们看到对mutex的优化集中在第一个for循环之中，而且有很大的概率在那里会重新获得锁。
小结
我们看到对mutex的优化其实遵循了代码优化的一般原则，即集中优化整个代码执行中出现的hot-spot(引申到高概率spot)。
因为在实际使用当中，大多数情况下，mutex_lock与mutex_unlock之间的代码都比较简短，使得获得锁的进程可以很快释放锁(因此，从性能优化的角度，这个也可以作为使用mutex的一条一般原则)。
如果系统中大部分拥有互斥锁的进程在mutex_lock与unlock之间执行时间比较长，那么相对于使用semaphore，我相信使用mutex会使得系统性能降低：
因为很大的概率，mutex都经过一段spin(虽然这段时间极短)之后最终还是进入sleep，而semaphore则直接进入sleep，没有了spin的过程。