為了保證并行程序執行的正確性和高效性，構建一個共享存儲多處理器系統的硬件必須要解決緩存一致性、存儲一致性和同步原語的支持等問題。

被廣泛使用的同步原語包括鎖lock、柵欄barrier和點對點同步(signal和wait信號量)。舉例來說，鎖和柵欄被大量使用在DOALL并行性和具有鏈式數據結構的應用程序中，而signal/wait同步對流水線DOCROSS并行性來說至關重要。

如今一種很使用的方式是將最低級別的同步原語以原子指令的形式在硬件上實現，然后將其他所有高級別的同步原語在軟件中實現。通常在可擴展性（同步延遲和帶寬如何隨著更大數量的線程而擴展）和無競爭延遲（線程不同時嘗試同步所帶來的延遲）之間會作出權衡。

對于大型系統來說，在原子指令之上實現的軟件柵欄和鎖可能不具有足夠的可擴展。對于這些系統來說，硬件柵欄的實現很常見。

8.1 鎖的實現

8.1.1 對鎖實現性能的評估

性能評價標準，考慮鎖的實現：

? ? ? ? 1）無競爭獲取鎖延遲：當線程間沒有競爭時，獲取一個鎖所花費的時間。
? ? ? ? 2）通信量：總的通信量，是參與競爭鎖的線程或者處理器數的函數。通信量可以分為三個子部分，即當一個鎖空間時獲取產生的通信量、當一個鎖不空閑 時鎖 獲取產生的通信量：鎖釋放時產生的通信量。
????????3）公平性：線程同其他線程相比被允許持有鎖的程度。公平性的標準是在一個鎖實現中，線程饑餓的情況是否存在，即一個線程不能長時間地持有鎖，即使這個鎖在這段時間內是空閑的。
?????????4）存儲：需要的存儲空間時線程數的函數。一些鎖的實現要去一個恒定的存儲空間，這個存儲空間與共享鎖的線程數無關；而另一些鎖的實現要求的存儲空間是隨著共享鎖的線程數而線性增長的。

8.1.2 對原子指令的要求

? ? ? ? 軟件機制并不能擴展，因為執行的靜態指令的數量，已經為了查看線程是否能夠獲得鎖而需要檢查的變量的數量，都會隨著線程數的增加而增加。相反，如果一個原子指令能夠執行一系列加載、比較其他指令和存儲指令，那么可以實現一個簡單的鎖

int is_turn;
int is_ready[n] = {0};    // n是處理器數目void Lock(int porcess)
{int other = 1- process;is_ready[process] = TRUE;is_turn = process;while (is_turn == process && is_ready[other] == TRUE)
}void Unlock(int process)
{is_ready[process] = FALSE;
}

? ?在當今的系統中，大部分的處理器支持將一個原子指令作為最低級的原語，同時基于它還可以構建其他同步原語。一個原子指令以一種不可分割的方式執行一系列的讀、修改和寫操作，這些操作在執行時不可能分割。

lock: ld    R1, &lockvarbnz   R1, lockst    &lockvar, #1retunlock: st    &lockvar, #0ret 

以上指令必須原子性地執行，“原子”這個詞表達了兩件事。首先，它意味著要么整個序列都被完整執行，要么其中任何一條指令都不執行。其次，它表達了在任何給定的時間內，只有一條原子指令（無論來自那個處理器）能夠被執行。下面列出一些經常使用：

? ? ? ? test-and-set Rx，M： 讀取存儲在存儲單元M的值，將這個值與一個常數進行比較，如果他們想匹配，那么將寄存器Rx中的到存儲單元M中。

? ? ? ? fetch-and-op M： 讀取存儲在在存儲單元M的值，對這個值執行操作（如自增、減值、加法、減法），然后將得到的新值存儲到存儲單元M中。在有些情況下，會指定額外的操作數。

? ? ? ? exchange Rx, M：自動交換在存儲單元M中的值和寄存器Rx的值。

? ? ? ? compare-and-swap Rx, Ry,?M：比較存儲單元M中的值和寄存器Rx中的值，如果它們匹配，將寄存器Ry中的值寫到存儲單元M中，然后拷貝寄存器Rx中的值到寄存器Ry中。

除了以上指令之外，最通用的一個指令是比較并交換CAS：與test-adn-set指令相比較，它能執行一個比較，但是與之相比較的是一個寄存器中任意值，而不是一個常數；與一個exchange指令相比，它可以交換寄存器和內存中的值，但是需要附加的條件。

讀者可能會提出兩個問題：

? ? ? ? 1）一個原子指令如何確保原子性？
? ? ? ? 2）一個原子指令如何被用于同步控制結構？

一個原子指令本質上為程序提供了一個保障：指令所代表的一系列操作將會被完整地執行。

緩存一致性協議提供了原子性被保障的基礎。當遇到一個原子指令時，這個緩存一致性協議知道需要保證其原子性。他首先會獲得存儲單元M的“獨家所有權”（通過將其他包含M的緩存塊中的拷貝都置為無效）。當獲得獨家所有權后，這個協議會確保只有只有一個處理器能夠訪問這個塊，而如果其他處理器在此時想要訪問的話就會經歷緩存缺失，接下來原子指令就可以執行了。而如果其他處理器在此時想要訪問的話就會經歷緩存缺失，接下來原子指令就可以執行了。在原子指令持續期間，其他處理器不允許“偷走”這個塊。

在一個基于總線的多處理器中，一個阻止塊（在基于總線的多處理器上）被“偷走”的方法是鎖上或者預約總線直到指令完成。

一個更加常用的解決辦法（亦可用在非基于總線的多處理器系統中）不是阻止其他對總線的請求，而是使用執行原子指令的處理器的一致性控制器，來對塊的其他所有請求延遲響應直到原子指令完成，或者否定確認請求，這樣請求者會在未來重復請求。

8.1.3 TS鎖

在獲取鎖的嘗試中的第一條指令時test-and-set指令，它原子地執行下面幾個步驟：首先從lockvar所在的存儲單元中讀取值到寄存器R1中（使用一個獨占的讀指令，如BusRfx或者BusUpgr），將寄存器R1中的值與0相比較。第二條指令時分支指令，當R1中的值非0的時候分支指令回到標簽lock，這樣鎖的獲取可以被重新嘗試。如果R1中的值是0，就意味著當到達分支指令時，因為原子性，test-and-set指令已經成功了。鎖的釋放只需要將0賦給lockvar即可，而不需要原子指令，因為此時只有一個線程在臨界區，所有只有一個線程能夠對鎖進行釋放，在鎖釋放的時候不會產生沖突。

lock: t&s    R1, &lockvarbnz    R1, lockretunlock:    st, &lockvar,    #0ret

? 評價一下test-and-set鎖實現。因為在成功獲得一個鎖的時候只需要一條原子指令和一條分支指令，所以無競爭獲取鎖的延遲很低，但是通信量需求非常高。每個鎖獲取都試圖使其他拷貝失效，而不管這個獲取成功與否。比如