推薦閱讀這份資料：OSTEP鎖章節(jié)(https://pages.cs.wisc.edu/~remzi/OSTEP/threads-locks.pdf)

這份文檔是關(guān)于并發(fā)編程中鎖（Locks）的詳細(xì)介紹和討論。文檔從鎖的基本概念出發(fā)，探討了如何在多線程環(huán)境中保護(hù)共享資源，避免競(jìng)態(tài)條件。以下是文檔的詳細(xì)翻譯：

鎖：基本概念

在并發(fā)編程中，我們希望一系列指令能夠原子性地執(zhí)行，但由于單個(gè)處理器上的中斷存在（或者多個(gè)線程在多個(gè)處理器上并發(fā)執(zhí)行），我們無(wú)法實(shí)現(xiàn)。本章直接解決這個(gè)問(wèn)題，介紹了鎖的概念。程序員在源代碼中使用鎖來(lái)標(biāo)注臨界區(qū)，確保這些臨界區(qū)的執(zhí)行就像是單個(gè)原子指令一樣。

舉例來(lái)說(shuō)，假設(shè)我們的臨界區(qū)是這樣的，對(duì)共享變量的典型更新：

balance = balance + 1;

當(dāng)然，還有其他可能的臨界區(qū)，比如向鏈表添加元素或其他更復(fù)雜的共享結(jié)構(gòu)更新，但我們現(xiàn)在只保持這個(gè)簡(jiǎn)單的例子。使用鎖，我們?cè)谂R界區(qū)周?chē)砑右恍┐a，如下所示：

lock_t mutex; // 一些全局分配的鎖 'mutex' ...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

鎖只是一個(gè)變量，因此要使用它，你必須聲明某種類(lèi)型的鎖變量（如上面的mutex）。這個(gè)鎖變量（或簡(jiǎn)稱(chēng)"鎖"）保存了鎖在任何時(shí)刻的狀態(tài)。它要么是可用的（或未鎖定或空閑），這意味著沒(méi)有線程持有鎖，要么是已獲取的（或鎖定或持有），這意味著恰好有一個(gè)線程持有鎖，并且假定它處于臨界區(qū)。我們還可以在數(shù)據(jù)類(lèi)型中存儲(chǔ)其他信息，比如哪個(gè)線程持有鎖，或者一個(gè)用于鎖定獲取順序的隊(duì)列，但這些信息對(duì)鎖的用戶(hù)是隱藏的。lock()和unlock()例程的語(yǔ)義很簡(jiǎn)單。調(diào)用lock()例程嘗試獲取鎖；如果沒(méi)有其他線程持有鎖（即它是空閑的），線程將獲取鎖并進(jìn)入臨界區(qū)；這個(gè)線程有時(shí)被稱(chēng)為鎖的擁有者。

如果另一個(gè)線程然后對(duì)同一個(gè)鎖變量（本例中的mutex）調(diào)用lock()，它將在鎖被另一個(gè)線程持有時(shí)不會(huì)返回；這樣，其他線程就被阻止在第一個(gè)持有鎖的線程在里面時(shí)進(jìn)入臨界區(qū)。一旦鎖的擁有者調(diào)用unlock()，鎖現(xiàn)在又可用（空閑）了。如果沒(méi)有其他線程在等待鎖（即沒(méi)有其他線程調(diào)用lock()并卡在那里），鎖的狀態(tài)就簡(jiǎn)單地變?yōu)樽杂伞?

如果有等待線程（卡在lock()中），它們中的一個(gè)將（最終）注意到（或被告知）鎖狀態(tài)的變化，獲取鎖，并進(jìn)入臨界區(qū)。鎖為程序員提供了一些最基本的調(diào)度控制。一般來(lái)說(shuō)，我們認(rèn)為線程是由程序員創(chuàng)建但由操作系統(tǒng)調(diào)度的實(shí)體，以操作系統(tǒng)選擇的任何方式。鎖將其中一些控制權(quán)還給了程序員；通過(guò)在代碼段周?chē)胖靡粋€(gè)鎖，程序員可以保證不會(huì)有多個(gè)線程同時(shí)在該代碼中活躍。因此，鎖幫助將傳統(tǒng)的操作系統(tǒng)調(diào)度混亂轉(zhuǎn)變?yōu)楦锌刂频幕顒?dòng)。

Pthread 鎖

POSIX庫(kù)中鎖的名稱(chēng)是互斥鎖（mutex），因?yàn)樗糜谠诙鄠€(gè)線程之間提供互斥，即如果一個(gè)線程處于臨界區(qū)，它會(huì)排除其他線程進(jìn)入，直到它完成該部分。因此，當(dāng)你看到以下POSIX線程代碼時(shí)，你應(yīng)該理解它與上面做的是同一件事（我們?cè)俅问褂梦覀兊陌b器，在鎖和解鎖時(shí)檢查錯(cuò)誤）：

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
...
Pthread_mutex_lock(&lock); // 包裝器；在失敗時(shí)退出 balance = balance + 1;
Pthread_mutex_unlock(&lock);

你可能還會(huì)注意到這里POSIX版本傳遞了一個(gè)變量來(lái)鎖定和解鎖，因?yàn)槲覀兛赡苁褂貌煌逆i來(lái)保護(hù)不同的變量。這樣做可以增加并發(fā)性：而不是使用一個(gè)大鎖（粗粒度鎖定策略），每當(dāng)任何臨界區(qū)被訪問(wèn)時(shí)，我們通常會(huì)用不同的鎖來(lái)保護(hù)不同的數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)，從而允許更多的線程同時(shí)處于鎖定代碼中（更細(xì)粒度的方法）。

構(gòu)建一個(gè)鎖

到目前為止，你應(yīng)該已經(jīng)從程序員的角度理解了鎖的工作原理。但我們應(yīng)該如何構(gòu)建一個(gè)鎖？需要什么硬件支持？需要什么操作系統(tǒng)支持？在本章的其余部分，我們將解決這個(gè)問(wèn)題。

關(guān)鍵問(wèn)題：如何構(gòu)建一個(gè)鎖？有效的鎖以低成本提供互斥，并且可能獲得我們?cè)谙旅嬗懻摰钠渌恍傩浴Ｐ枰裁从布С?？需要什么操作系統(tǒng)支持？

要構(gòu)建一個(gè)工作的鎖，我們將需要我們老朋友硬件的幫助，以及我們好朋友操作系統(tǒng)。多年來(lái)，各種計(jì)算機(jī)架構(gòu)的指令集中添加了許多不同的硬件原語(yǔ)；雖然我們不會(huì)研究這些指令是如何實(shí)現(xiàn)的（畢竟，那是計(jì)算機(jī)體系結(jié)構(gòu)課程的主題），但我們將研究如何使用它們來(lái)構(gòu)建像鎖這樣的互斥原語(yǔ)。我們還將研究操作系統(tǒng)如何參與其中，完成整個(gè)畫(huà)面，使我們能夠構(gòu)建一個(gè)復(fù)雜的鎖定庫(kù)。

評(píng)估鎖

在構(gòu)建任何鎖之前，我們應(yīng)該首先理解我們的目標(biāo)是什么，因此我們問(wèn)如何評(píng)估特定鎖實(shí)現(xiàn)的有效性。評(píng)估鎖是否有效（并且工作得很好），我們應(yīng)該建立一些基本標(biāo)準(zhǔn)。第一個(gè)是鎖是否完成了它的基本任務(wù)，即提供互斥。

基本上，鎖是否有效，防止多個(gè)線程進(jìn)入臨界區(qū)？第二個(gè)是公平性。每個(gè)爭(zhēng)奪鎖的線程在鎖空閑時(shí)都有公平的機(jī)會(huì)獲取它嗎？另一種看待這個(gè)問(wèn)題的方式是通過(guò)檢查更極端的情況：是否有線程在爭(zhēng)奪鎖時(shí)餓死了，因此從未獲得它？最后的標(biāo)準(zhǔn)是性能，特別是使用鎖增加的時(shí)間開(kāi)銷(xiāo)。這里有幾個(gè)值得考慮的不同情況。

一個(gè)是無(wú)爭(zhēng)用的情況；當(dāng)單個(gè)線程運(yùn)行并獲取和釋放鎖時(shí)，這樣做有什么開(kāi)銷(xiāo)？

另一個(gè)是多個(gè)線程在單個(gè)CPU上爭(zhēng)奪鎖的情況；在這種情況下，是否有性能問(wèn)題？最后，當(dāng)有多個(gè)CPU參與，每個(gè)CPU上的線程都在爭(zhēng)奪鎖時(shí)，鎖的性能如何？通過(guò)比較這些不同的場(chǎng)景，我們可以更好地理解使用各種鎖定技術(shù)的性能影響，如下所述。

控制中斷

最早用于提供互斥的解決方案之一是為臨界區(qū)禁用中斷；這種解決方案是為單處理器系統(tǒng)發(fā)明的。代碼如下所示：

void lock() {
 DisableInterrupts();
} void unlock() {
 EnableInterrupts();
}

假設(shè)我們運(yùn)行在這樣的單處理器系統(tǒng)上。通過(guò)在進(jìn)入臨界區(qū)之前關(guān)閉中斷（使用某種特殊的硬件指令），我們確保臨界區(qū)內(nèi)的代碼不會(huì)被中斷，因此將像原子操作一樣執(zhí)行。當(dāng)我們完成時(shí)，我們重新啟用中斷（再次通過(guò)硬件指令），因此程序照常進(jìn)行。

這種方法的主要優(yōu)點(diǎn)是其簡(jiǎn)單性。你肯定不必太費(fèi)勁就能弄清楚為什么這有效。沒(méi)有中斷，線程可以確信它執(zhí)行的代碼將被執(zhí)行，沒(méi)有其他線程會(huì)干擾它。不幸的是，缺點(diǎn)很多。首先，這種方法要求我們?cè)试S任何調(diào)用線程執(zhí)行特權(quán)操作（打開(kāi)和關(guān)閉中斷），因此相信這種設(shè)施不會(huì)被濫用。正如你已經(jīng)知道的，任何時(shí)候我們被要求相信任意程序，我們可能都有麻煩了。

在這里，麻煩以多種方式表現(xiàn)出來(lái)：一個(gè)貪婪的程序可以在執(zhí)行開(kāi)始時(shí)調(diào)用lock()，從而壟斷處理器；更糟的是，一個(gè)出錯(cuò)或惡意的程序可以在調(diào)用lock()后進(jìn)入無(wú)限循環(huán)。在這種情況下，操作系統(tǒng)永遠(yuǎn)不會(huì)重新獲得系統(tǒng)的控制權(quán)，只有一個(gè)解決辦法：重新啟動(dòng)系統(tǒng)。使用中斷禁用作為通用同步解決方案需要對(duì)應(yīng)用程序過(guò)于信任。

其次，這種方法在多處理器上不起作用。如果多個(gè)線程在不同的CPU上運(yùn)行，并且每個(gè)都試圖進(jìn)入同一個(gè)臨界區(qū)，不管是否禁用了中斷；線程將能夠在其他處理器上運(yùn)行，因此可能進(jìn)入臨界區(qū)。由于多處理器現(xiàn)在已經(jīng)很常見(jiàn)，我們的通用解決方案將不得不做得比這更好。第三，長(zhǎng)時(shí)間關(guān)閉中斷可能導(dǎo)致中斷丟失，這可能導(dǎo)致嚴(yán)重的系統(tǒng)問(wèn)題。例如，想象一下，如果CPU錯(cuò)過(guò)了磁盤(pán)設(shè)備完成讀請(qǐng)求的事實(shí)。操作系統(tǒng)將如何知道喚醒等待所述讀取的進(jìn)程？

一個(gè)失敗的嘗試：僅使用加載/存儲(chǔ)

要超越基于中斷的技術(shù)，我們將不得不依賴(lài)CPU硬件和它為我們提供的指令來(lái)構(gòu)建一個(gè)合適的鎖。讓我們首先嘗試使用一個(gè)標(biāo)志變量來(lái)構(gòu)建一個(gè)簡(jiǎn)單的鎖。在這個(gè)失敗的嘗試中，我們將看到構(gòu)建鎖所需的一些基本思想，并（希望）看到為什么僅使用單個(gè)變量并通過(guò)正常的加載和存儲(chǔ)訪問(wèn)它是不夠的。在這個(gè)第一次嘗試（圖28.1）中，想法非常簡(jiǎn)單：使用一個(gè)簡(jiǎn)單的變量（標(biāo)志）來(lái)指示某個(gè)線程是否擁有鎖。第一個(gè)進(jìn)入臨界區(qū)的線程將調(diào)用lock()，它測(cè)試標(biāo)志是否等于1（在這種情況下，不是），然后將標(biāo)志設(shè)置為1，以表明該線程現(xiàn)在持有鎖。當(dāng)完成臨界區(qū)后，線程調(diào)用unlock()并清除標(biāo)志，從而表明鎖不再被持有。

如果另一個(gè)線程恰好在第一個(gè)線程在臨界區(qū)時(shí)調(diào)用lock()，它將簡(jiǎn)單地在while循環(huán)中自旋等待，等待該線程調(diào)用unlock()并清除標(biāo)志。一旦第一個(gè)線程這樣做，等待的線程將退出while循環(huán)，為自己將標(biāo)志設(shè)置為1，并繼續(xù)進(jìn)入臨界區(qū)。不幸的是，代碼有兩個(gè)問(wèn)題：一個(gè)是正確性問(wèn)題，另一個(gè)是性能問(wèn)題。一旦你習(xí)慣了并發(fā)編程的思考，正確性問(wèn)題就很容易看到。想象一下圖28.2中的代碼交錯(cuò)；假設(shè)標(biāo)志=0開(kāi)始。正如你從這個(gè)交錯(cuò)中看到的，通過(guò)及時(shí)（不合時(shí)宜？）的中斷，我們很容易產(chǎn)生一個(gè)情況，兩個(gè)線程都設(shè)置標(biāo)志為1，因此兩個(gè)線程都能夠進(jìn)入臨界區(qū)。這種行為是專(zhuān)業(yè)人士所說(shuō)的"糟糕"——我們顯然未能提供最基本的要求：提供互斥。

我們將在后面更詳細(xì)地解決性能問(wèn)題，即線程等待獲取已經(jīng)持有的鎖的方式：它不斷地檢查標(biāo)志的值，這種技術(shù)被稱(chēng)為自旋等待。自旋等待浪費(fèi)了等待另一個(gè)線程釋放鎖的時(shí)間。在單處理器上，浪費(fèi)尤其高，因?yàn)榈却木€程等待的線程甚至不能運(yùn)行（至少，直到上下文切換發(fā)生！）。因此，隨著我們向前發(fā)展并開(kāi)發(fā)出更復(fù)雜的解決方案，我們也應(yīng)該考慮避免這種浪費(fèi)的方法。

使用測(cè)試和設(shè)置構(gòu)建工作的自旋鎖

因?yàn)榻弥袛嘣诙鄠€(gè)處理器上不起作用，而且簡(jiǎn)單的使用加載和存儲(chǔ)的方法（如上所示）也不起作用，系統(tǒng)設(shè)計(jì)者開(kāi)始發(fā)明鎖定的硬件支持。最早的多處理器系統(tǒng)，如1960年代初的Burroughs B5000 [M82]，有這樣的支持；今天所有系統(tǒng)都提供這種類(lèi)型的支持，即使是單CPU系統(tǒng)。最簡(jiǎn)單的硬件支持是眾所周知的測(cè)試和設(shè)置（或原子交換1）指令。我們通過(guò)以下C代碼片段定義測(cè)試和設(shè)置指令的作用：

int TestAndSet(int *old_ptr, int new) { int old = *old_ptr; // 獲取old_ptr處的舊值 *old_ptr = new; // 將'new'存儲(chǔ)到old_ptr return old; // 返回舊值 }

每個(gè)支持測(cè)試和設(shè)置的架構(gòu)都用不同的名稱(chēng)來(lái)稱(chēng)呼它。在SPARC上，它被稱(chēng)為加載/存儲(chǔ)無(wú)符號(hào)字節(jié)指令（ldstub）；在x86上，它是原子交換（xchg）的鎖定版本。

評(píng)估自旋鎖

鑒于我們的基本自旋鎖，我們現(xiàn)在可以沿著我們之前描述的軸評(píng)估它的有效性。鎖最重要的方面是正確性：它是否提供互斥？答案是肯定的：自旋鎖只允許單個(gè)線程一次進(jìn)入臨界區(qū)。因此，我們有一個(gè)正確的鎖。下一個(gè)軸是公平性。自旋鎖對(duì)等待線程有多公平？你能保證等待線程最終會(huì)進(jìn)入臨界區(qū)嗎？不幸的是，這里的答案是壞消息：自旋鎖不提供任何公平性保證。事實(shí)上，一個(gè)自旋的線程可能會(huì)永遠(yuǎn)自旋，在爭(zhēng)用中。簡(jiǎn)單的自旋鎖（到目前為止討論的）是不公平的，可能導(dǎo)致饑餓。最后一個(gè)軸是性能。

使用自旋鎖的成本是什么？為了更仔細(xì)地分析這個(gè)問(wèn)題，我們建議考慮幾種不同的情況。首先，想象線程在單個(gè)處理器上爭(zhēng)奪鎖；其次，考慮線程分布在許多CPU上。對(duì)于自旋鎖，在單個(gè)CPU的情況下，性能開(kāi)銷(xiāo)可能相當(dāng)痛苦；想象一下，持有鎖的線程在臨界區(qū)內(nèi)被搶占。調(diào)度器可能會(huì)運(yùn)行每個(gè)其他線程（想象有N-1個(gè)其他線程），每個(gè)線程都試圖獲取鎖。在這種情況下，這些線程中的每一個(gè)都會(huì)在時(shí)間片期間自旋，然后放棄CPU，浪費(fèi)CPU周期。然而，在多個(gè)CPU上，自旋鎖工作得相當(dāng)好（如果線程的數(shù)量大致等于CPU的數(shù)量）。

思考如下：想象線程A在CPU 1上，線程B在CPU 2上，都爭(zhēng)奪一個(gè)鎖。如果線程A（CPU 1）抓住了鎖，然后線程B嘗試，B將在（CPU 2上）自旋。然而，假設(shè)臨界區(qū)很短，很快鎖就可用，被線程B獲取。在這種情況下，等待另一個(gè)處理器上持有的鎖并不會(huì)浪費(fèi)太多周期，因此可以是有效的。

比較和交換

一些系統(tǒng)提供的另一個(gè)硬件原語(yǔ)被稱(chēng)為比較和交換指令（例如，在SPARC上），或比較和交換（在x86上）。這個(gè)單指令的C偽代碼可以在圖28.4中找到?；舅枷胧潜容^和交換測(cè)試ptr指定的地址處的值是否等于expected；如果是，用新值更新ptr指向的內(nèi)存位置。

如果不是，什么也不做。在這兩種情況下，返回該內(nèi)存位置的原始值，從而允許調(diào)用比較和交換的代碼知道它是否成功。有了比較和交換指令，我們可以以與測(cè)試和設(shè)置非常相似的方式構(gòu)建鎖。例如，我們可以簡(jiǎn)單地將上面的lock()例程替換為以下內(nèi)容：

void lock(lock_t *lock) { while (CompareAndSwap(&lock->flag, 0, 1) == 1)
 ; // 自旋 }

其余代碼與上面的測(cè)試和設(shè)置示例相同。這段代碼的工作方式相當(dāng)相似；它只是檢查標(biāo)志是否為0，如果是，則原子地交換1，從而獲取鎖。試圖在持有鎖時(shí)獲取鎖的線程將被卡住自旋，直到鎖最終被釋放。

如果你想看看如何真正制作一個(gè)C可調(diào)用的x86版本的比較和交換，代碼序列（來(lái)自[S05]）可能很有用2。最后，正如你可能已經(jīng)感覺(jué)到的，比較和交換是一個(gè)比測(cè)試和設(shè)置更強(qiáng)大的指令。我們將在未來(lái)簡(jiǎn)要探討鎖無(wú)關(guān)同步[H91]等主題時(shí)利用這種力量的一些用途。然而，如果我們只是用它構(gòu)建一個(gè)簡(jiǎn)單的自旋鎖，它的行為與我們上面分析的自旋鎖相同。

加載鏈接和存儲(chǔ)條件

一些平臺(tái)提供了一對(duì)指令，它們協(xié)同工作以幫助構(gòu)建臨界區(qū)。例如，在MIPS架構(gòu)[H93]上，加載鏈接和存儲(chǔ)條件指令可以一起使用來(lái)構(gòu)建鎖和其他并發(fā)結(jié)構(gòu)。這些指令的C偽代碼可以在圖28.5中找到。Alpha、PowerPC和ARM提供了類(lèi)似的指令[W09]。加載鏈接的操作與典型的加載指令非常相似，它只是從內(nèi)存中獲取一個(gè)值并將其放入寄存器中。

存儲(chǔ)條件的關(guān)鍵區(qū)別在于，它只有在沒(méi)有對(duì)地址進(jìn)行干預(yù)存儲(chǔ)的情況下才會(huì)成功（并更新剛剛從加載鏈接中加載的地址處的值）。在成功的情況下，存儲(chǔ)條件返回1并更新ptr處的值為value；如果失敗，ptr處的值不會(huì)更新，返回0。作為對(duì)自己的挑戰(zhàn)，嘗試思考如何使用加載鏈接和存儲(chǔ)條件構(gòu)建鎖。然后，當(dāng)你完成時(shí)，看看下面的代碼，它提供了一個(gè)簡(jiǎn)單的解決方案。去做吧！lock()代碼是唯一有趣的部分。首先，線程自旋等待標(biāo)志被設(shè)置為0（從而表明鎖沒(méi)有被持有）。

一旦如此，線程嘗試通過(guò)存儲(chǔ)條件獲取鎖；如果成功，線程已經(jīng)原子地將標(biāo)志的值更改為1，因此可以繼續(xù)進(jìn)入臨界區(qū)。注意存儲(chǔ)條件失敗可能發(fā)生的情況。一個(gè)線程調(diào)用lock()并執(zhí)行加載鏈接，返回0，因?yàn)殒i沒(méi)有被持有。在它可以嘗試存儲(chǔ)條件之前，它被中斷，另一個(gè)線程進(jìn)入鎖代碼，也執(zhí)行加載鏈接指令，

int LoadLinked(int *ptr) { return *ptr;
} int StoreConditional(int *ptr, int value) { if (no update to *ptr since LL to this addr) {
 *ptr = value; return 1; // 成功！ } else { return 0; // 更新失敗 }
} 

并且也得到0并繼續(xù)。此時(shí)，兩個(gè)線程都已經(jīng)執(zhí)行了加載鏈接，每個(gè)線程都即將嘗試存儲(chǔ)條件。這些指令的關(guān)鍵特性是，只有其中一個(gè)線程會(huì)成功更新標(biāo)志為1并因此獲得鎖；第二個(gè)嘗試存儲(chǔ)條件的線程將失?。ㄒ?yàn)榱硪粋€(gè)線程在其加載鏈接和存儲(chǔ)條件之間更新了標(biāo)志的值），因此不得不嘗試再次獲取鎖。幾年前在課堂上，本科生David Capel提出了上述更簡(jiǎn)潔的形式，供那些喜歡短路布爾條件的人使用?？纯茨隳芊衽宄槭裁此葍r(jià)。它當(dāng)然更短！

void lock(lock_t *lock) { while (LoadLinked(&lock->flag) ||
 !StoreConditional(&lock->flag, 1))
 ; // 自旋 }

獲取和添加

最后一個(gè)硬件原語(yǔ)是獲取和添加指令，它原子地遞增一個(gè)值，同時(shí)返回特定地址的舊值。獲取和添加指令的C偽代碼如下所示：

int FetchAndAdd(int *ptr) { int old = *ptr;
 *ptr = old + 1; return old;
}

在這個(gè)例子中，我們將使用獲取和添加來(lái)構(gòu)建一個(gè)更有趣的票鎖，由Mellor-Crummey和Scott [MS91]引入。鎖和解鎖代碼可以在圖28.7（第14頁(yè)）中找到。與單個(gè)值不同，這種解決方案結(jié)合了票和輪次變量來(lái)構(gòu)建鎖?；静僮鞣浅：?jiǎn)單：當(dāng)線程希望獲取鎖時(shí)，它首先對(duì)票值進(jìn)行原子獲取和添加；該值現(xiàn)在被認(rèn)為是該線程的"輪次"（myturn）。

全局共享的lock->turn用于確定哪個(gè)線程的輪次；當(dāng)（myturn == turn）對(duì)于給定線程時(shí)，就是該線程進(jìn)入臨界區(qū)的時(shí)候。通過(guò)簡(jiǎn)單地遞增turn來(lái)解鎖，以便下一個(gè)等待的線程（如果有）現(xiàn)在可以進(jìn)入臨界區(qū)。

注意這個(gè)解決方案與我們之前的嘗試的一個(gè)重要區(qū)別：它為所有線程確保了進(jìn)展。一旦線程被分配了它的票值，它將在未來(lái)的某個(gè)時(shí)候被調(diào)度（一旦前面的線程通過(guò)臨界區(qū)并釋放了鎖）。在我們之前的嘗試中，沒(méi)有這樣的保證；一個(gè)在測(cè)試和設(shè)置上自旋的線程（例如）可能會(huì)永遠(yuǎn)自旋，即使其他線程獲取和釋放鎖。

太多自旋：現(xiàn)在怎么辦？

我們的基于硬件的鎖很簡(jiǎn)單（只有幾行代碼），它們有效（如果你愿意，你甚至可以證明這一點(diǎn)，通過(guò)編寫(xiě)一些代碼），這是任何系統(tǒng)或代碼的兩個(gè)極好的屬性。然而，在某些情況下，這些解決方案可能非常低效。

想象一下你在單個(gè)處理器上運(yùn)行兩個(gè)線程?，F(xiàn)在想象一個(gè)線程（線程0）在臨界區(qū)內(nèi)，因此持有鎖，不幸的是被中斷了。第二個(gè)線程（線程1）現(xiàn)在試圖獲取鎖，但發(fā)現(xiàn)它被持有。因此，它開(kāi)始自旋。然后它再自旋。然后它再自旋一些。最后，定時(shí)器中斷發(fā)生，線程0再次運(yùn)行，釋放了鎖，最后（下一次運(yùn)行時(shí)，比如說(shuō)），線程1不需要那么多自旋就能獲取鎖。

因此，任何時(shí)候線程被卡在自旋中，就像這樣，它都會(huì)浪費(fèi)整個(gè)時(shí)間片，什么都不做，只是檢查一個(gè)不會(huì)改變的值！當(dāng)N個(gè)線程爭(zhēng)奪鎖時(shí)問(wèn)題變得更糟；N-1個(gè)時(shí)間片可能會(huì)以類(lèi)似的方式被浪費(fèi)，只是自旋等待一個(gè)線程釋放鎖。因此，我們接下來(lái)的問(wèn)題：關(guān)鍵問(wèn)題：如何避免在CPU上無(wú)謂地浪費(fèi)時(shí)間自旋？

僅靠硬件支持無(wú)法解決問(wèn)題。我們還需要操作系統(tǒng)支持！現(xiàn)在讓我們弄清楚這可能如何工作。

一個(gè)簡(jiǎn)單的方法：只是讓步，寶貝

硬件支持讓我們走得相當(dāng)遠(yuǎn)：工作的鎖，甚至（如票鎖的情況）在鎖獲取中的公平性。然而，我們?nèi)匀挥幸粋€(gè)問(wèn)題：當(dāng)上下文切換發(fā)生在臨界區(qū)內(nèi)，線程開(kāi)始無(wú)休止地自旋等待被中斷的（持有鎖的）線程再次運(yùn)行時(shí)，該怎么辦？我們第一次嘗試是一個(gè)簡(jiǎn)單而友好的方法：當(dāng)你即將自旋時(shí)，相反，放棄CPU讓另一個(gè)線程運(yùn)行。正如Al Davis可能會(huì)說(shuō)的，"只是讓步，寶貝！"[D91]。圖28.8（第15頁(yè)）展示了這種方法。

在這個(gè)方法中，我們假設(shè)操作系統(tǒng)原始的yield()，當(dāng)線程想要放棄CPU并讓另一個(gè)線程運(yùn)行時(shí)可以調(diào)用。線程可以處于三種狀態(tài)之一（運(yùn)行、就緒或阻塞）；yield只是一個(gè)系統(tǒng)調(diào)用，將調(diào)用者從運(yùn)行狀態(tài)移動(dòng)到就緒狀態(tài)，從而提升另一個(gè)線程到運(yùn)行狀態(tài)。因此，讓步的線程基本上是自我調(diào)度的?？紤]兩個(gè)線程在單個(gè)CPU上的例子；在這種情況下，我們的基于讓步的方法相當(dāng)好。如果線程碰巧調(diào)用lock()并發(fā)現(xiàn)鎖被持有，它將簡(jiǎn)單地讓出CPU，因此另一個(gè)線程將運(yùn)行并完成其臨界區(qū)。

在這個(gè)簡(jiǎn)單的案例中，讓步方法工作得很好?，F(xiàn)在讓我們考慮有許多線程（比如說(shuō)100個(gè)）反復(fù)爭(zhēng)奪鎖的情況。在這種情況下，如果一個(gè)線程獲取了鎖并在釋放它之前被搶占，其他99個(gè)將各自調(diào)用lock()，發(fā)現(xiàn)鎖被持有，并讓出CPU。假設(shè)某種輪詢(xún)調(diào)度器，99個(gè)中的每一個(gè)都將執(zhí)行這個(gè)運(yùn)行和讓步模式，然后持有鎖的線程再次運(yùn)行。

雖然比我們的自旋方法更好（這將浪費(fèi)99個(gè)時(shí)間片自旋），這種方法仍然成本很高；上下文切換的成本可能相當(dāng)大，因此有很多浪費(fèi)。更糟的是，這種方法沒(méi)有解決饑餓問(wèn)題。線程可能會(huì)陷入無(wú)盡的讓步循環(huán)，而其他線程反復(fù)進(jìn)入和退出臨界區(qū)。我們顯然需要一種直接解決饑餓問(wèn)題的方法。

使用隊(duì)列：睡眠而不是自旋

一些先前方法（除了票鎖）的真正問(wèn)題是，它們留給機(jī)會(huì)太多。調(diào)度器決定了下一個(gè)運(yùn)行的線程；如果調(diào)度器做出了錯(cuò)誤的選擇，運(yùn)行的線程必須要么自旋等待鎖（我們的第一種方法），要么立即讓出CPU（我們的第二種方法）。無(wú)論如何，都有浪費(fèi)的潛力，也沒(méi)有防止饑餓的方法。

因此，我們必須明確控制哪個(gè)線程在當(dāng)前持有者釋放鎖后下一個(gè)獲得鎖。為此，我們將需要更多的操作系統(tǒng)支持，以及一個(gè)隊(duì)列來(lái)跟蹤哪些線程正在等待獲取鎖。為簡(jiǎn)單起見(jiàn)，我們將使用Solaris提供的支持，以?xún)蓚€(gè)調(diào)用的形式：park()讓調(diào)用線程睡眠，unpark(threadID)喚醒由threadID指定的特定線程。這兩個(gè)例程可以一起使用，構(gòu)建一個(gè)鎖，如果調(diào)用者試圖獲取一個(gè)被持有的鎖，就讓調(diào)用者睡眠，并在鎖空閑時(shí)喚醒它。讓我們看看圖28.9中的代碼，以理解這種原始的一種可能用途。

不同的操作系統(tǒng)，不同的支持

到目前為止，我們已經(jīng)看到了操作系統(tǒng)可以提供的一種支持，以構(gòu)建線程庫(kù)中更有效的鎖。其他操作系統(tǒng)提供了類(lèi)似的支持；細(xì)節(jié)各不相同。例如，Linux提供了futex，它與Solaris接口類(lèi)似，但提供了更多的內(nèi)核功能。具體來(lái)說(shuō)，每個(gè)futex都有一個(gè)與之相關(guān)的特定物理內(nèi)存位置，以及一個(gè)每futex的內(nèi)核隊(duì)列。調(diào)用者可以使用futex調(diào)用（下面描述）來(lái)睡眠和喚醒，如需。具體來(lái)說(shuō)，有兩個(gè)調(diào)用可用。調(diào)用futex wait(address, expected)讓調(diào)用線程睡眠，假設(shè)address處的值等于expected。如果它不相等，調(diào)用立即返回。調(diào)用例程futex wake(address)喚醒等待在隊(duì)列上的一個(gè)線程。

圖28.10（第19頁(yè)）中展示了這些調(diào)用在Linux互斥鎖中的使用。這個(gè)代碼片段來(lái)自nptl庫(kù)（GNU libc庫(kù)的一部分）[L09]中的lowlevellock.h，由于幾個(gè)原因很有趣。首先，它使用一個(gè)整數(shù)來(lái)跟蹤鎖是否被持有（整數(shù)的最高位）以及鎖上的等待者數(shù)量（所有其他位）。因此，如果鎖是負(fù)數(shù)，它就被持有（因?yàn)樽罡呶槐辉O(shè)置，而該位決定了整數(shù)的符號(hào)）。

其次，代碼片段展示了如何針對(duì)常見(jiàn)情況進(jìn)行優(yōu)化，特別是當(dāng)沒(méi)有鎖爭(zhēng)用時(shí)；只有一個(gè)線程獲取和釋放鎖時(shí)，做的工作很少（原子位測(cè)試和設(shè)置以鎖定和原子加以釋放鎖）?？纯茨隳芊衽宄@個(gè)"真實(shí)世界"鎖的其余部分是如何工作的。去做吧，成為L(zhǎng)inux鎖定的大師，或者至少是當(dāng)一本書(shū)告訴你去做某事時(shí)會(huì)聽(tīng)的人3。

兩階段鎖

最后一點(diǎn)：Linux方法有一種舊方法的味道，多年來(lái)時(shí)而使用，至少可以追溯到1960年代初的Dahm鎖[M82]，現(xiàn)在被稱(chēng)為兩階段鎖。兩階段鎖意識(shí)到自旋可能是有用的，特別是如果鎖即將被釋放。因此，在第一階段，鎖自旋一段時(shí)間，希望它可以獲取鎖。然而，如果在第一階段自旋期間沒(méi)有獲取鎖，則進(jìn)入第二階段，在此階段，調(diào)用者被放入睡眠狀態(tài)，只有在鎖稍后變?yōu)榭臻e時(shí)才會(huì)被喚醒。

上面的Linux鎖是一種這樣的鎖，但它只自旋一次；這種鎖的一般化可以在使用futex支持睡眠之前，在循環(huán)中自旋固定時(shí)間。兩階段鎖是混合方法的另一個(gè)實(shí)例，結(jié)合兩個(gè)好主意確實(shí)可能產(chǎn)生一個(gè)更好的主意。當(dāng)然，是否如此取決于許多事情，包括硬件環(huán)境、線程數(shù)量和其他工作負(fù)載細(xì)節(jié)。像往常一樣，制造一個(gè)適用于所有可能用例的通用鎖是非常具有挑戰(zhàn)性的。

總結(jié)

上述方法展示了如今如何構(gòu)建真正的鎖：一些硬件支持（以更強(qiáng)大的指令形式）加上一些操作系統(tǒng)支持（例如，在Solaris上的park()和unpark()原語(yǔ)，或Linux上的futex）。當(dāng)然，細(xì)節(jié)各不相同，執(zhí)行這種鎖定的確切代碼通常高度優(yōu)化。如果你想了解更多細(xì)節(jié)，可以查看Solaris或Linux代碼庫(kù)；它們是非常有趣的閱讀[L09, S09]。還可以查看David等人的優(yōu)秀工作，比較現(xiàn)代多處理器上不同的鎖定策略[D+13]。

文檔的最后部分提供了一些參考文獻(xiàn)，以及一些關(guān)于并發(fā)編程和鎖的實(shí)驗(yàn)性問(wèn)題，這些問(wèn)題旨在幫助讀者更好地理解鎖的工作原理和它們?cè)诓l(fā)環(huán)境中的行為。

---

現(xiàn)在不少朋友都在準(zhǔn)備校招，常規(guī)的技術(shù)學(xué)習(xí)只是提高了代碼能力，還沒(méi)有提升從 0 到 1 整體做項(xiàng)目和解決問(wèn)題的能力！

為此我們特別推出了C++訓(xùn)練營(yíng)，帶著你從 0 到 1 做 C++ 項(xiàng)目（你可以從項(xiàng)目池中任選項(xiàng)目），幫助你提升做項(xiàng)目的能力，提升從0到1的能力，熟悉做項(xiàng)目的完整流程，比如開(kāi)發(fā)環(huán)境、編譯腳本、架構(gòu)設(shè)計(jì)、框架搭建、代碼發(fā)布、問(wèn)題調(diào)試、單元測(cè)試。

除了上面的，還有需求分析、項(xiàng)目規(guī)劃、架構(gòu)設(shè)計(jì)、任務(wù)拆解、時(shí)間規(guī)劃、版本管理。另外做項(xiàng)目的過(guò)程中必然會(huì)遇到種種問(wèn)題，可以逐步提升你的調(diào)試能力，分析問(wèn)題的能力，掌握更多的調(diào)試手段。

遇到棘手的問(wèn)題，我們還有專(zhuān)門(mén)的導(dǎo)師1V1答疑解惑，給出具體建議。

項(xiàng)目池里面的項(xiàng)目，是導(dǎo)師團(tuán)隊(duì)花費(fèi)大量時(shí)間完成的，不僅有完整的代碼及清晰的注釋還有詳細(xì)的文檔和視頻，并且有專(zhuān)門(mén)的項(xiàng)目導(dǎo)師答疑，完全不用擔(dān)心自己學(xué)不會(huì)。