互斥锁：修订间差异

删除的内容添加的内容

行内

2019年6月15日 (六) 08:37的版本

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

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

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

需求

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

实现

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

硬件实现

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

while (test_and_set(lock) == 1);

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

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

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

软件实现

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

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

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

高级的互斥锁实现

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

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

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

Windows的Mutex对象

Windows操作系统提供了mutex同步对象。它有两个状态：

signaled：如果它不被任何对象拥有；
nonsignaled：如果它被一个（且至多一个）线程拥有。

Windows API函数CreateMutex或CreateMutexEx创建mutex对象。使用OpenMutex函数打开一个mutex对象。也可以使用DuplicateHandle函数或者父子handle继承来使用一个无名mutex对象。

任何线程可以使用mutex的句柄（handle）于等待函数（wait functions）来获得这个mutex对象的拥有权。如果该mutex对象正被其他线程拥有，则请求的线程在该等待函数上被阻塞直到拥有的线程调用ReleaseMutex函数释放mutex并被该请求线程获取到拥有权。等待函数的返回值可以鉴别是否获得了拥有权（该mutex被signaled）或者其他原因（如超时返回）.

如果多个线程正在等待一个mutex对象，那么该mutex被signaled时唤醒哪一个线程不能保证遵循先进先出(FIFO)顺序。外部事件如异步过程调用可改变等待顺序。

如果一个线程拥有了一个mutex对象，该线程可以对该mutex对象执行多次等待函数调用而不会被阻塞。释放mutex对象时，该线程必须调用ReleaseMutex函数的次数必须与调用等待函数的次数相同。 mutex对象内部有一个递归计数，表示获得了该对象的线程占用该对象的次数。

拥有mutex对象的线程没有释放拥有权就结束了，那么该mutex对象被放弃（abandoned）. 等待该mutex对象的其他线程可获得拥有权，但从等待函数得到的返回值为WAIT_ABANDONED。这表示一个错误已经发生了，任何被该互斥锁保护的共享资源处于未定义的状态。

Windows操作系统的临界区（critical section）对象类似于mutex对象，但是临界区对象只能用于一个进程内部。

延伸阅读与参考书目

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

@@ 第30行： / 第30行： @@
 类似的方式也有通过软件模拟达成的。但是该种模拟会对计算机造成极大的负荷，因为申请占用自旋锁的过程中会不间断地对一个标志位进行读写，并且该种模拟不允许[[乱序执行]]，因为这会破坏其机制。
-更为常见的是使用操作系统提供的互锁库，这种库通常设计为在有硬件支持时使用硬件机制，仅在找不到支持的硬件时才用软件模拟，并且结合线程调度对锁性能进行优化。比如一个线程要使用一个已经被占用的锁，这时候操作系统会把这个线程挂起，然后[[上下文切换|切换上下文]]到另外一个可以继续运行的线程，若是没有别的线程要继续运行的话，系统就让处理器进入低功耗状态，而不是让这个线程消耗大量处理能力进行自旋来等待锁释放。
+更为常见的是使用操作系统提供的互锁库，这种库通常设计为在有硬件支持时使用硬件机制，仅在找不到支持的硬件时才用软件模拟，并且结合线程调度对锁性能进行优化。比如一个线程要使用一个已经被占用的锁，这时候操作系统会把这个线程挂起，然后進行context switching到另外一个可以继续运行的线程，若是没有别的线程要继续运行的话，系统就让处理器进入低功耗状态，而不是让这个线程消耗大量处理能力进行自旋来等待锁释放。
 现代的互斥锁大多使用队列和上下文切换以达到节约资源和降低延迟的目的。但是总有些情况下，挂起一个进程，然后过一阵子再恢复所用的时间会比让进程在那里自旋等待用的时间长。在这种情况下则更多会使用自旋锁。