線程基礎之資料競争與鎖

大多數現代多線程程式設計語言都可以避免順序一緻性與性能之間的沖突，因為它們知道：

順序一緻性的問題是由于某些程式轉換引起的，例如我們的例子中交換了無關變量的通路順序，這不會改變單線程程式的意圖，但是會改變多線程程式的意圖（例如例子中允許r1和r2都為0）。

隻有當代碼允許兩個線程同時通路相同的共享資料，并且是以某種沖突的方式通路時（例如當一個線程讀取資料的同時另一個線程寫入該資料），才有可能察覺到這種程式轉換。如果程式強制以特定順序來通路共享變量，那麼我們就無法判斷對獨立變量的通路是否被重排序，就如同在單線程程式中也無法判斷。

無限制地同時通路普通共享變量會讓程式變得難以處理，一般需要避免這種情況。堅持完全的順序一緻性對我們沒有好處。我們将在下文用單獨的一節來讨論這個問題。

是以程式設計語言通常會提供友善的機制來限制通過不同的線程同時通路變量，并且僅當不存在不受控的并發通路時（例如我們的示例程式）才保證順序一緻性。更準确地說：

如果兩個普通記憶體操作通路相同的記憶體位置（例如變量、數組元素），并且至少一個記憶體操作寫入該存儲單元，則稱這兩個記憶體操作是沖突的。

如果程式存在順序一緻的執行，則稱其允許在特定輸入集合上有資料競争（data race），即線上程操作的交錯執行中兩個沖突的操作可以“同時”執行。為了我們的目的，如果兩個操作在交錯執行中相鄰，并對應不同的線程，則這兩個操作可以被“同時”執行。如果兩個對應不同線程的正常記憶體操作在交錯執行中相鄰，我們知道如果他們以相反順序執行也會得到相同結果；如果一些操作強制了順序，則他們就必須要在交錯執行中間出現。是以模型中的相鄰實際上意味着他們本應該在真正的并發模型中同時發生。

僅當程式避免了資料競争時我們才保證順序一緻性。

這種保證是java和下一代c++标準的線程程式設計模型的核心。

注意本文簡介中的例子确實有資料競争，至少當變量x和y是普通整型變量時是這樣。

大多數現代程式設計語言都提供了簡單的方法來指定同步變量（synchronization variables）用于線上程間通信，同步變量是特意用來進行并發通路的。這種形式的并發通路不被認為是資料競争。換言之，隻要當沖突的并發通路僅發生在同步變量上時，就能確定順序一緻性。

是以如果把我們例子中的x和y都設為同步變量，那麼程式就能保證程式按預期執行。在java中，可以将它們聲明為volatile int。

将變量聲明為同步變量不僅保證了變量能被不可分割地通路，還能阻止編譯器和硬體以對程式可見的方式對記憶體通路進行重排序。這就能防止上文例子中出現r1 = r2 = 0這種結果。另一個更常見的例子如下，該例中隻有标志位x_init（初始值為false）是同步變量：

thread 2

x = 42;

x_init = true;

while(!x_init) {}

r1 = x;

這裡的思路是線程1初始化x，在實際程式中，可能比僅僅指派為42更為複雜。然後設定x_init标志位表明它已經完成了指派。另一個線程2将等待x_init标志位被設定，然後就能知道x已被初始化。

雖然x是一個普通變量，但這個程式中沒有資料競争。線程2能保證直到線程1完成并設定了x_init之後才會執行第二條語句。是以交錯執行中不可能出現x = 42和r1 = x相鄰的情況。

這意味着我們確定了順序一緻的執行，即保證r1 = 42。為了保證這一點，實作時必須讓線程1對x和x_init的指派操作對其他線程按照順序可見，并且隻有當設定了x_init之後線程2才能開始r1 = x操作。在許多機器架構中，這兩點都要求編譯器遵循額外的限制，生成特殊的代碼來防止潛在的硬體優化，例如防止線程1因為先通路到x_init的記憶體就在對x指派之前先對x_init指派。

實際上，大多數情況下不會通過将普通變量變為同步變量來避免資料競争，而是通過防止對普通變量的并發通路來避免資料競争。這通常通過引入鎖（有時稱為互斥鎖）來實作，鎖是程式設計語言或支援庫提供的特殊同步變量。例如，如果我們想維護一個共享計數器變量c，它的值可以被多個線程遞增，并線上程結束時讀取其值。我們可以引入一個對應的鎖l，編寫如下代碼：

<code>1</code>

<code>void</code> <code>increment_c()</code>

<code>2</code>

<code>{</code>

<code>3</code>

<code>    </code><code>l.lock();</code>

<code>4</code>

<code>    </code><code>++c;</code>

<code>5</code>

<code>    </code><code>l.unlock();</code>

<code>6</code>

<code>}</code>

lock()和unlock()的實作確定了在這兩個調用之間同時至多隻能有一個線程，是以同時隻有一個線程能通路c。我們可以将這看做對交錯執行進行了限制：對于給定的鎖l，l.lock()和l.unlock()交替調用，并且初始調用是l.lock()。（一般情況下還有一個額外的需求：鎖必須由擷取它的那個線程釋放，但不總是這樣。）是以即便increment_c()被多個線程并發調用，在c也上是沒有資料競争的。交錯執行中任何兩個對c的通路都會至少被第一個線程中的unlock()和第二個線程中的lock()分開。

舉例說明，假設一個程式有兩個線程，每個線程都執行increment_c()。如下是一個可接受的交錯執行：

這個交錯執行沒有資料競争。唯一的相鄰的對應不同線程的操作就是中間兩步。而這兩步操作都是對同步變量鎖l進行的，是以不會參與資料競争。

如果我們想要重排操作來産生資料競争，可能會是如下這種交錯存取：

但是這種交錯執行無疑是被禁止的，因為規則要求對鎖l的擷取和釋放必須交替進行。在任何可接受的交錯執行中，第二個l.lock()隻有當第一個unlock()調用完成後才有可能在交錯執行中出現。是以，作為唯一潛在的資料競争，兩次++c調用一定會被這兩個調用分開。

這也闡釋了資料競争的另一個等價描述：資料競争要求不同線程對相同普通共享位置的任意兩次沖突通路必須被這兩次通路中的同步（synchronization ）所隔離，同步確定了通路的順序。通常這可以通過在一個線程中釋放鎖并在另一個線程中擷取該鎖來實作。但是還可以這樣實作：在一個線程中設定一個整型同步變量（例如java中的volatile），然後再第二個線程中等待該變量被設定（可能用一個簡單的循環）。程式設計語言标準通常用這種方式來定義資料競争。