1520
1.?前言
一致性協(xié)議(coherency protocol)掛死(hang)通常有三種情況：死鎖(deadlock)、活鎖(livelock)和餓死(starvation)。
2.?死鎖
死鎖是指兩個或多個參與者互相等待對方執(zhí)行某些操作，導致系統(tǒng)永遠無法向前運行。通常情況下，死鎖是由資源循環(huán)依賴引起的。
舉個簡單例子，如下圖1所示，有兩個參與者節(jié)點A和B，以及兩個資源X和Y。假設A持有資源Y，B持有資源X。如果A請求X，B請求Y，那么除非一個節(jié)點放棄它已經持有的資源，否則這兩個節(jié)點將發(fā)生死鎖。
圖1 資源循環(huán)依賴導致死鎖的示例。圓圈表示節(jié)點，正方形表示資源。以資源結尾的連線表示對該資源的請求，從資源開始的連線表示該資源的持有者
一般來說，如果事件A(例如，接收消息)可能導致事件B(例如，發(fā)送消息)，并且這兩個事件都需要分配資源(例如，網絡連接(network links)和緩沖區(qū)(buffer))，如果出現(xiàn)循環(huán)資源依賴，那么必須小心避免死鎖發(fā)生。下圖2為一個死鎖發(fā)生的另一個場景，有兩個一致性控制器C1和C2，它們正在響應彼此的請求，但是輸入FIFO隊列緩沖器已經被其它一致性請求填滿了，會導致各自的響應無法繞過請求，因此無法被處理。在這時候，每個一致性控制器會暫停發(fā)送響應，而且控制器也不能去處理后續(xù)請求或者獲得響應，系統(tǒng)就發(fā)生死鎖了。
圖2 死鎖例子
在一致性協(xié)議中避免死鎖的常用解決方案是為每一類消息使用單獨的路由網絡，網絡可以是物理上分離的，也可以是邏輯上分離的(稱為虛擬網絡，virtual networks)，其實本質就是避免消息類之間的依賴關系。
下圖3系統(tǒng)中，請求和響應消息使用不同的物理網絡通道進行傳輸，由于響應消息不會被其它請求消息阻塞，因此它最終可以被其它目標節(jié)點收到，從而打破了資源循環(huán)依賴關系。
圖3 使用分離網絡路由通道來避免死鎖
在一致性協(xié)議中，死鎖可能出現(xiàn)在協(xié)議級(Protocol Deadlock)、緩存資源分配(Cache Resource Deadlock)和網絡(Protocol-Dependent Network Deadlock)中。
2.1 協(xié)議死鎖
當一致性控制器等待一個永遠不會發(fā)送的消息時，就會出現(xiàn)協(xié)議死鎖。這種死鎖大多數(shù)情況下是由未經測試的競爭條件引起的。
2.2 緩存資源死鎖
當緩存控制器在執(zhí)行某些操作之前必須分配資源時，就會出現(xiàn)緩存資源死鎖。這種死鎖通常在處理另一個Core的請求或自己回寫時出現(xiàn)。比如有一個緩存控制器，它有一組共享緩沖區(qū)，這些緩沖區(qū)可以分配給自己發(fā)起的一致性請求或其它Core的請求。如果Core發(fā)出足夠多的一致性請求來占用所有緩沖區(qū)，那么它不能處理其它Core的請求。這樣的話，當所有Core都達到這種狀態(tài)，系統(tǒng)就會出現(xiàn)死鎖。
2.3 協(xié)議相關的網絡死鎖
網絡死鎖有兩種原因：一種是由錯誤的路由算法引起的死鎖，這種算法與消息的類型和一致性協(xié)議無關；另一種是由于在一致性協(xié)議操作期間，交換特定的消息而引起的網絡死鎖。本文主要講述后一類依賴于協(xié)議的網絡死鎖。比如定義了一個目錄協(xié)議，其中一個請求消息可能導致一個轉發(fā)的請求，而一個轉發(fā)的請求可能導致一個響應。該協(xié)議必須確保三個原則，才能避免循環(huán)依賴的死鎖。
每一類的消息必須在自己的網絡通道上傳播，網絡可以時物理的，也可以是虛擬的，但關鍵是避免在FIFO緩沖區(qū)中出現(xiàn)某一類的消息被卡在另一類消息后面的情況。在本例中，請求、轉發(fā)的請求和響應都需要再不同的網絡上傳輸。因此，一致性控制器必須有三個輸入FIFO，每個網絡通道都需要一個。
每一類消息必須具有依賴順序。例如A類消息可以引起一致性控制器發(fā)出B類消息，那么如果某個一致性控制器在等待A類消息時，不能停止處理收到的B類消息。比如在本例中，一致性控制器不能在等自己請求過程中停止對收到的轉發(fā)請求進行處理，也不能在等待轉發(fā)請求過程中停止對響應的處理。
如果一致性控制器接收到響應消息，那么沒有任何消息類可以阻止它被一致性控制器處理。
這三個原則消除了協(xié)議網絡循環(huán)的可能性。盡管請求在等待響應或轉發(fā)請求時會被停止住，但每個請求最終都會得到處理，因為響應和轉發(fā)請求的數(shù)量收到未完成請求事務數(shù)量的限制。
3.?餓死
餓死是指一個或多個Core未能取得進展，而其它Core仍然可以取得進展，沒有進展的Core被認為是餓死的。餓死有幾個根本原因，但它們往往分為兩類：不公平的仲裁和不正確地使用否定確認響應。
如果某個資源總是由其它Core獲得或持有，當至少一個Core無法獲得該關鍵資源，就會出現(xiàn)餓死現(xiàn)象。典型例子是監(jiān)聽協(xié)議中的不公平總線仲裁機制，如果總線對不同Core的訪問按固定優(yōu)先級順序進行的，Core C1發(fā)出的請求可以馬上被響應，Core C2發(fā)出的請求必須在沒有C1請求的情況下才會被響應，C3必須等C1和C2的請求處理后才會被響應，以此推理等等。在這樣的系統(tǒng)中，具有低優(yōu)先級的Core可能永遠無法獲得請求的響應，因此就會餓死。這個問題的常用解決辦法就是：公平仲裁。
另一類導致餓死的主要原因是否定確定響應的不正確使用。在某些協(xié)議中，接收到一致性請求的一致性控制器可以向請求者發(fā)送NACK，通知請求者請求未被滿足，必須重新發(fā)出。協(xié)議通常使用NACK來簡化請求塊正在被其它事務進行處理的情況。例如，在一些目錄協(xié)議中，如果請求塊正在被其它事務處理，那么新的請求訪問請求塊會得到NACK的響應。用NACK解決協(xié)議的競爭條件似乎比設計協(xié)議來處理這些罕見和復雜的情況更容易，但是挑戰(zhàn)在于NACK請求一定要最終成功。如果有很多Core同時訪問請求塊，那么保證不會被餓死具有一定的挑戰(zhàn)性。
4.?活鎖
活鎖是指兩個或多個參與者執(zhí)行操作并改變狀態(tài)，但最終從未取得進展的情況。活鎖是餓死的一個特例。多個Core使用exclusive操作進行搶鎖比較容易出現(xiàn)活鎖。
如下表1所示，在一個監(jiān)聽協(xié)議中，Core C1發(fā)出一個GetS請求操作來獲取B塊內容，并將B塊的狀態(tài)更改為ISAD(B塊為I，目標是轉到S狀態(tài)，等待Own-GetS和數(shù)據(jù)(Data))。稍后，C1在總線上觀察到Own-GetS，并將B塊的狀態(tài)更改為ISD。在B塊進入ISD和C1接收到數(shù)據(jù)響應之間，C1很容易收到來自總線上其它Core對B塊的GetM請求，這時候C1會將B塊的狀態(tài)變?yōu)镮SDI。在這種瞬態(tài)狀態(tài)下，就算C1稍后接收到數(shù)據(jù)響應時，C1會把B塊的狀態(tài)改成I，因此C1暫時無法獲取數(shù)據(jù)給load操作，所以它必須重新發(fā)出另一個GetS操作去獲得B塊。但是下一個GetS也同樣容易收到其它Core的影響，因此，C1可能永遠也無法取得進展。這樣就出現(xiàn)了活鎖，Core仍然是活躍的，但是系統(tǒng)永遠不會向前執(zhí)行?；铈i容易出現(xiàn)在高度競爭的場景中，這意味著大多數(shù)或所有Cores可能都同時被卡住了，系統(tǒng)陷入活鎖。可以通過要求C1在接收到數(shù)據(jù)響應時至少把數(shù)據(jù)轉發(fā)一次給load操作，這樣也不會違法一致性。
表1 在監(jiān)聽協(xié)議中l(wèi)oad B塊的活鎖示例
同樣的問題也可能出現(xiàn)在store操作對塊的操作狀態(tài)為IMDS，IMDSI或IMDI。在這些情況下，塊的結束狀態(tài)是I或S，store對塊的操作永遠不會執(zhí)行。幸運的是，我們?yōu)镮SDI中的load操作提供的解決方案同樣適用于這些狀態(tài)中的store操作。Core發(fā)出GetM操作在收到數(shù)據(jù)時必須至少執(zhí)行一次store操作，并且Core必須將新寫入的數(shù)據(jù)轉發(fā)給處于S或M請求塊的其它Core。
5. 知識拓展
虛擬網絡(virtual network)
除了使用物理上的不同網絡，我們還可以使用不同的虛擬網絡。虛擬網絡防止不同類型的消息相互堵塞，從而避免消息級死鎖。
下圖4(a)為使用單個點對點鏈路連接的兩個Cores，在每條鏈路的末端都有一個FIFO隊列，用于在預接收傳入的消息，最后Core會一一順序處理其中消息。4(b)添加了另一個物理網絡，它復制了一份鏈路和FIFO隊列，請求消息在一個物理網絡上傳輸，而響應消息在另一個物理網絡上傳輸。
為了避免復制一份鏈路和交換機的面積成本，我們可以添加一個虛擬網絡，如圖4(c)所示。虛擬網絡的唯一代價是在網絡中的每個交互機和端點上增加一個FIFO隊列，在本例中添加第二個虛擬網絡，使得請求消息不會和響應消息互相影響。
圖4?虛擬網絡
除了虛擬網絡，還有虛擬通道(virtual channel)，它們兩者有所不同。在網絡級別上，虛擬通道用于避免由于路由而導致的死鎖，不看消息類型如何。為了避免路由死鎖，消息可以在多個虛擬通道上傳輸。虛擬通道像虛擬網絡，是通過在每個交換機和端點上增加額外的FIFO隊列來實現(xiàn)的。但是每個虛擬網絡可能有一定數(shù)量的虛擬通道，以避免路由死鎖。
