一致性協(xié)議掛死(hang)分析

1.?前言

一致性協(xié)議(coherency protocol)掛死(hang)通常有三種情況：死鎖(deadlock)、活鎖(livelock)和餓死(starvation)。

2.?死鎖

死鎖是指兩個或多個參與者互相等待對方執(zhí)行某些操作，導(dǎo)致系統(tǒng)永遠(yuǎn)無法向前運行。通常情況下，死鎖是由資源循環(huán)依賴引起的。

舉個簡單例子，如下圖1所示，有兩個參與者節(jié)點A和B，以及兩個資源X和Y。假設(shè)A持有資源Y，B持有資源X。如果A請求X，B請求Y，那么除非一個節(jié)點放棄它已經(jīng)持有的資源，否則這兩個節(jié)點將發(fā)生死鎖。

圖1 資源循環(huán)依賴導(dǎo)致死鎖的示例。圓圈表示節(jié)點，正方形表示資源。以資源結(jié)尾的連線表示對該資源的請求，從資源開始的連線表示該資源的持有者

一般來說，如果事件A(例如，接收消息)可能導(dǎo)致事件B(例如，發(fā)送消息)，并且這兩個事件都需要分配資源(例如，網(wǎng)絡(luò)連接(network links)和緩沖區(qū)(buffer))，如果出現(xiàn)循環(huán)資源依賴，那么必須小心避免死鎖發(fā)生。下圖2為一個死鎖發(fā)生的另一個場景，有兩個一致性控制器C1和C2，它們正在響應(yīng)彼此的請求，但是輸入FIFO隊列緩沖器已經(jīng)被其它一致性請求填滿了，會導(dǎo)致各自的響應(yīng)無法繞過請求，因此無法被處理。在這時候，每個一致性控制器會暫停發(fā)送響應(yīng)，而且控制器也不能去處理后續(xù)請求或者獲得響應(yīng)，系統(tǒng)就發(fā)生死鎖了。

圖2 死鎖例子

在一致性協(xié)議中避免死鎖的常用解決方案是為每一類消息使用單獨的路由網(wǎng)絡(luò)，網(wǎng)絡(luò)可以是物理上分離的，也可以是邏輯上分離的(稱為虛擬網(wǎng)絡(luò)，virtual networks)，其實本質(zhì)就是避免消息類之間的依賴關(guān)系。

下圖3系統(tǒng)中，請求和響應(yīng)消息使用不同的物理網(wǎng)絡(luò)通道進(jìn)行傳輸，由于響應(yīng)消息不會被其它請求消息阻塞，因此它最終可以被其它目標(biāo)節(jié)點收到，從而打破了資源循環(huán)依賴關(guān)系。

圖3 使用分離網(wǎng)絡(luò)路由通道來避免死鎖

在一致性協(xié)議中，死鎖可能出現(xiàn)在協(xié)議級(Protocol Deadlock)、緩存資源分配(Cache Resource Deadlock)和網(wǎng)絡(luò)(Protocol-Dependent Network Deadlock)中。

2.1 協(xié)議死鎖

當(dāng)一致性控制器等待一個永遠(yuǎn)不會發(fā)送的消息時，就會出現(xiàn)協(xié)議死鎖。這種死鎖大多數(shù)情況下是由未經(jīng)測試的競爭條件引起的。

2.2 緩存資源死鎖

當(dāng)緩存控制器在執(zhí)行某些操作之前必須分配資源時，就會出現(xiàn)緩存資源死鎖。這種死鎖通常在處理另一個Core的請求或自己回寫時出現(xiàn)。比如有一個緩存控制器，它有一組共享緩沖區(qū)，這些緩沖區(qū)可以分配給自己發(fā)起的一致性請求或其它Core的請求。如果Core發(fā)出足夠多的一致性請求來占用所有緩沖區(qū)，那么它不能處理其它Core的請求。這樣的話，當(dāng)所有Core都達(dá)到這種狀態(tài)，系統(tǒng)就會出現(xiàn)死鎖。

2.3 協(xié)議相關(guān)的網(wǎng)絡(luò)死鎖

網(wǎng)絡(luò)死鎖有兩種原因：一種是由錯誤的路由算法引起的死鎖，這種算法與消息的類型和一致性協(xié)議無關(guān)；另一種是由于在一致性協(xié)議操作期間，交換特定的消息而引起的網(wǎng)絡(luò)死鎖。本文主要講述后一類依賴于協(xié)議的網(wǎng)絡(luò)死鎖。比如定義了一個目錄協(xié)議，其中一個請求消息可能導(dǎo)致一個轉(zhuǎn)發(fā)的請求，而一個轉(zhuǎn)發(fā)的請求可能導(dǎo)致一個響應(yīng)。該協(xié)議必須確保三個原則，才能避免循環(huán)依賴的死鎖。

每一類的消息必須在自己的網(wǎng)絡(luò)通道上傳播，網(wǎng)絡(luò)可以時物理的，也可以是虛擬的，但關(guān)鍵是避免在FIFO緩沖區(qū)中出現(xiàn)某一類的消息被卡在另一類消息后面的情況。在本例中，請求、轉(zhuǎn)發(fā)的請求和響應(yīng)都需要再不同的網(wǎng)絡(luò)上傳輸。因此，一致性控制器必須有三個輸入FIFO，每個網(wǎng)絡(luò)通道都需要一個。

每一類消息必須具有依賴順序。例如A類消息可以引起一致性控制器發(fā)出B類消息，那么如果某個一致性控制器在等待A類消息時，不能停止處理收到的B類消息。比如在本例中，一致性控制器不能在等自己請求過程中停止對收到的轉(zhuǎn)發(fā)請求進(jìn)行處理，也不能在等待轉(zhuǎn)發(fā)請求過程中停止對響應(yīng)的處理。

如果一致性控制器接收到響應(yīng)消息，那么沒有任何消息類可以阻止它被一致性控制器處理。

這三個原則消除了協(xié)議網(wǎng)絡(luò)循環(huán)的可能性。盡管請求在等待響應(yīng)或轉(zhuǎn)發(fā)請求時會被停止住，但每個請求最終都會得到處理，因為響應(yīng)和轉(zhuǎn)發(fā)請求的數(shù)量收到未完成請求事務(wù)數(shù)量的限制。

3.?餓死

餓死是指一個或多個Core未能取得進(jìn)展，而其它Core仍然可以取得進(jìn)展，沒有進(jìn)展的Core被認(rèn)為是餓死的。餓死有幾個根本原因，但它們往往分為兩類：不公平的仲裁和不正確地使用否定確認(rèn)響應(yīng)。

如果某個資源總是由其它Core獲得或持有，當(dāng)至少一個Core無法獲得該關(guān)鍵資源，就會出現(xiàn)餓死現(xiàn)象。典型例子是監(jiān)聽協(xié)議中的不公平總線仲裁機制，如果總線對不同Core的訪問按固定優(yōu)先級順序進(jìn)行的，Core C1發(fā)出的請求可以馬上被響應(yīng)，Core C2發(fā)出的請求必須在沒有C1請求的情況下才會被響應(yīng)，C3必須等C1和C2的請求處理后才會被響應(yīng)，以此推理等等。在這樣的系統(tǒng)中，具有低優(yōu)先級的Core可能永遠(yuǎn)無法獲得請求的響應(yīng)，因此就會餓死。這個問題的常用解決辦法就是：公平仲裁。

另一類導(dǎo)致餓死的主要原因是否定確定響應(yīng)的不正確使用。在某些協(xié)議中，接收到一致性請求的一致性控制器可以向請求者發(fā)送NACK，通知請求者請求未被滿足，必須重新發(fā)出。協(xié)議通常使用NACK來簡化請求塊正在被其它事務(wù)進(jìn)行處理的情況。例如，在一些目錄協(xié)議中，如果請求塊正在被其它事務(wù)處理，那么新的請求訪問請求塊會得到NACK的響應(yīng)。用NACK解決協(xié)議的競爭條件似乎比設(shè)計協(xié)議來處理這些罕見和復(fù)雜的情況更容易，但是挑戰(zhàn)在于NACK請求一定要最終成功。如果有很多Core同時訪問請求塊，那么保證不會被餓死具有一定的挑戰(zhàn)性。

4.?活鎖

活鎖是指兩個或多個參與者執(zhí)行操作并改變狀態(tài)，但最終從未取得進(jìn)展的情況。活鎖是餓死的一個特例。多個Core使用exclusive操作進(jìn)行搶鎖比較容易出現(xiàn)活鎖。

如下表1所示，在一個監(jiān)聽協(xié)議中，Core C1發(fā)出一個GetS請求操作來獲取B塊內(nèi)容，并將B塊的狀態(tài)更改為ISAD(B塊為I，目標(biāo)是轉(zhuǎn)到S狀態(tài)，等待Own-GetS和數(shù)據(jù)(Data))。稍后，C1在總線上觀察到Own-GetS，并將B塊的狀態(tài)更改為ISD。在B塊進(jìn)入ISD和C1接收到數(shù)據(jù)響應(yīng)之間，C1很容易收到來自總線上其它Core對B塊的GetM請求，這時候C1會將B塊的狀態(tài)變?yōu)镮SDI。在這種瞬態(tài)狀態(tài)下，就算C1稍后接收到數(shù)據(jù)響應(yīng)時，C1會把B塊的狀態(tài)改成I，因此C1暫時無法獲取數(shù)據(jù)給load操作，所以它必須重新發(fā)出另一個GetS操作去獲得B塊。但是下一個GetS也同樣容易收到其它Core的影響，因此，C1可能永遠(yuǎn)也無法取得進(jìn)展。這樣就出現(xiàn)了活鎖，Core仍然是活躍的，但是系統(tǒng)永遠(yuǎn)不會向前執(zhí)行?；铈i容易出現(xiàn)在高度競爭的場景中，這意味著大多數(shù)或所有Cores可能都同時被卡住了，系統(tǒng)陷入活鎖。可以通過要求C1在接收到數(shù)據(jù)響應(yīng)時至少把數(shù)據(jù)轉(zhuǎn)發(fā)一次給load操作，這樣也不會違法一致性。

表1 在監(jiān)聽協(xié)議中l(wèi)oad B塊的活鎖示例

同樣的問題也可能出現(xiàn)在store操作對塊的操作狀態(tài)為IMDS，IMDSI或IMDI。在這些情況下，塊的結(jié)束狀態(tài)是I或S，store對塊的操作永遠(yuǎn)不會執(zhí)行。幸運的是，我們?yōu)镮SDI中的load操作提供的解決方案同樣適用于這些狀態(tài)中的store操作。Core發(fā)出GetM操作在收到數(shù)據(jù)時必須至少執(zhí)行一次store操作，并且Core必須將新寫入的數(shù)據(jù)轉(zhuǎn)發(fā)給處于S或M請求塊的其它Core。

5. 知識拓展

虛擬網(wǎng)絡(luò)(virtual network)

除了使用物理上的不同網(wǎng)絡(luò)，我們還可以使用不同的虛擬網(wǎng)絡(luò)。虛擬網(wǎng)絡(luò)防止不同類型的消息相互堵塞，從而避免消息級死鎖。

下圖4(a)為使用單個點對點鏈路連接的兩個Cores，在每條鏈路的末端都有一個FIFO隊列，用于在預(yù)接收傳入的消息，最后Core會一一順序處理其中消息。4(b)添加了另一個物理網(wǎng)絡(luò)，它復(fù)制了一份鏈路和FIFO隊列，請求消息在一個物理網(wǎng)絡(luò)上傳輸，而響應(yīng)消息在另一個物理網(wǎng)絡(luò)上傳輸。

為了避免復(fù)制一份鏈路和交換機的面積成本，我們可以添加一個虛擬網(wǎng)絡(luò)，如圖4(c)所示。虛擬網(wǎng)絡(luò)的唯一代價是在網(wǎng)絡(luò)中的每個交互機和端點上增加一個FIFO隊列，在本例中添加第二個虛擬網(wǎng)絡(luò)，使得請求消息不會和響應(yīng)消息互相影響。

圖4?虛擬網(wǎng)絡(luò)

除了虛擬網(wǎng)絡(luò)，還有虛擬通道(virtual channel)，它們兩者有所不同。在網(wǎng)絡(luò)級別上，虛擬通道用于避免由于路由而導(dǎo)致的死鎖，不看消息類型如何。為了避免路由死鎖，消息可以在多個虛擬通道上傳輸。虛擬通道像虛擬網(wǎng)絡(luò)，是通過在每個交換機和端點上增加額外的FIFO隊列來實現(xiàn)的。但是每個虛擬網(wǎng)絡(luò)可能有一定數(shù)量的虛擬通道，以避免路由死鎖。