互斥锁

互斥锁（英语：英語：Mutual exclusion，缩写 Mutex）是一种用于多线程编程中，防止两条线程同时对同一公共资源（比如全局变量）进行读写的机制。该目的通过将代码切片成一个一个的临界区域（critical section）达成。临界区域指的是一块对公共资源进行存取的代码，并非一种机制或是算法。一个程序、进程、线程可以拥有多个临界区域，但是并不一定会应用互斥锁。

需要此机制的资源的例子有：旗标、队列、计数器、中断处理程序等用于在多条并行运行的代码间传递数据、同步状态等的资源。维护这些资源的同步、一致和完整是很困难的，因为一条线程可能在任何一个时刻被暂停（休眠）或者恢复（唤醒）。

例如：一段代码（甲）正在分步修改一块数据。这时，另一条线程（乙）由于一些原因被唤醒。如果乙此时去读取甲正在修改的数据，而甲碰巧还没有完成整个修改过程，这个时候这块数据的状态就处在极大的不确定状态中，读取到的数据当然也是有问题的。更严重的情况是乙也往这块地方写数据，这样的一来，后果将变得不可收拾。因此，多个线程间共享的数据必须被保护。达到这个目的的方法，就是确保同一时间只有一个临界区域处于运行状态，而其他的临界区域，无论是读是写，都必须被挂起并且不能获得运行机会。

需求

• 不准永遠耽擱一個要求進入臨界區域的執行緒，造成死結或是飢餓發生 。
• 若沒有任何執行緒處於臨界區域時，任何要求進入臨界區域的執行緒必須立刻得到允許。
• 不能對執行緒的相對速度與處理器的數目做任何假設。
• 執行緒只能在臨界區域內停留一有限的時間。
• 任何時間只允許一個執行緒在臨界區域執行。
• 在臨界區域停止執行的執行緒，不准影響其他執行緒執行。

实现

依实现方式可分为硬件实现和软件实现两种。

硬件实现

单核心系统上最常见的方式就是关闭尽可能多的可能对共享数据段进行读写的指令中断。这样一来就可以避免在临界区域中暂停程序执行，或是来自硬件的要求修改目标共享数据段的中断请求。多核心系统上则通过检查并置位（获取原始值并指定新值）机制达成，当一个核心需要另一个核心占用的资源的时候，该核心将不断的查询所有核心间共享的占用旗标，直到另一个核心将占用旗标复位为未使用为止。相关的为代码如下所示：

while (test_and_set(lock) == 1);

lock的值为1则表示锁被占用，为0则是空闲。

在检查并置位机制中，一个核心在对旗标执行读写的过程当中不会释放占用的访问总线。该种方法又称为自旋锁。

类似的原子操作，如比较并交换机制，则更常用于对链表等数据结构进行不阻断同步。

软件实现

类似的方式也有通过软件模拟达成的。但是该种模拟会对计算机造成极大的负荷，因为申请占用自旋锁的过程中会不间断地对一个标志位进行读写，并且该种模拟不允许乱序执行，因为这会破坏其机制。

更为常见的是使用操作系统提供的互锁库，这种库通常设计为在有硬件支持时使用硬件机制，仅在找不到支持的硬件时才用软件模拟，并且结合线程调度对锁性能进行优化。比如一个线程要使用一个已经被占用的锁，这时候操作系统会把这个线程挂起，然后切换上下文到另外一个可以继续运行的线程，若是没有别的线程要继续运行的话，系统就让处理器进入低功耗状态，而不是让这个线程消耗大量处理能力进行自旋来等待锁释放。

现代的互斥锁大多使用队列和上下文切换以达到节约资源和降低延迟的目的。但是总有些情况下，挂起一个进程，然后过一阵子再恢复所用的时间会比让进程在那里自旋等待用的时间长。在这种情况下则更多会使用自旋锁。

高级的互斥锁实现

除了上述的基础互斥锁，还有一些更高级的实现方式，如：

• 信号标
• 重入锁
• 监视器
• 消息队列
• 元组空间

这些锁各有各的副作用。例如一个常见的信号标会允许死锁的发生（两条线程各自获取了一个信号标，然后都在等待对方释放另外一个）。其他可能会出现的现象有优先级倒置（高优先级的程序等待低优先级的程序完成）、资源饥荒（某个线程一直得不到足够的锁资源）等。

目前的研究多侧重于消除这些副作用上，例如不阻断同步，但是并没有完美的解决方案。

延伸阅读与参考书目

• Michel Raynal: Algorithms for Mutual Exclusion, MIT Press, ISBN 0-262-18119-3
• Sunil R. Das, Pradip K. Srimani: Distributed Mutual Exclusion Algorithms, IEEE Computer Society, ISBN 0-8186-3380-8
• Thomas W. Christopher, George K. Thiruvathukal: High-Performance Java Platform Computing, Prentice Hall, ISBN 0-13-016164-0
• Gadi Taubenfeld, Synchronization Algorithms and Concurrent Programming, Pearson/Prentice Hall, ISBN 0-13-197259-6
• Article "Common threads: POSIX threads explained - The little things called mutexes" by Daniel Robbins
• Mutual exclusion algorithm discovery
• Mutual Exclusion Petri Net
• Mutual Exclusion with Locks - an Introduction
• Mutual exclusion variants in OpenMP
• The Black-White Bakery Algorithm