容錯分布系統

分散式系統可以簡單地定義為一個運行在一系列自治處理單元上的系統，每個自治處理單元有各自的物理存儲器空間並且它們之間的通信延遲不能忽略不計。同時在這些自治處理單元之間不是各自為政而是存在一定合作。

而容錯分散式系統，是指在系統中存在一定故障的情況下仍能正常運行的分散式系統。

基本介紹

• 中文名：容錯分布系統
• 外文名：fault-tolerant distributed system
• 簡介：系統故障時下仍能正常運行的系統
• 分散式系統：運行在一系列自治處理單元的系統
• 系統模型：通信方式、故障、同步和異步等
• 套用學科：計算機科學、控制科學、通信工程

簡介

分散式系統作為一個相對較新的領域，迄今還沒有一致、權威的定義。一般來說，分散式系統可以簡單地定義為：一個運行在一系列自治處理單元上的系統，每個自治處理單元有各自的物理存儲器空間並且它們之間的通信延遲不能忽略不計。同時在這些自治處理單元之間不是各自為政而是存在一定合作。一個自治處理單元叫做一個進程。

而容錯分散式系統，是指在系統中存在一定故障的情況下仍能正常運行的分散式系統。

系統模型

系統模型(systemmodel)是對分散式系統所作的一系列抽象的假設，也是我們研究問題的基礎。它一般包含兩方面：一、假設系統里存在一些可以互相通信的進程，如圖1所示；二、對一些與進程和通信有關的系統參數所作的假設。而一個系統模型的強弱取決於它對系統所作假設的強弱，比如無故障的模型強於允許故障的模型。

圖1 系統模型

系統模型中涉及的系統參數包括以下幾個方面。

通信方式

進程間的通信方式分為存儲器共享(sharedmemory)和訊息傳遞(messagepassing)。訊息傳遞的方式又分為點對點(point—to—point)和組播(multieast)。

其中最常見是的點對點訊息傳遞的通信方式，組播為視可用點對點的訊息傳遞來實現的一種複合的通信方式。

同步和異步

關於訊息延時和進程間的相對速度這兩者的假設被稱為同步條件，它是判斷一個系統模型是同步還是異步的標準。如果假設兩者的上界都是已知的，那么這一系統模型是同步模型；如果假設兩者都是無界的，那么這一系統模型就是異步模型。

同步的假設對系統作了嚴格的限制，現實中的很多系統(如建築在訊息延時不確定的廣域網上的系統)都無法滿足這一假設。況且為了使一些系統滿足同步假設，必須把訊息延時的上界設得很大，導致協定中的逾時時間也必須設得很長，從而犧牲了協定的效率。於是在研究中更多考慮的是異步模型，而異步模型中主要關注的是不定長的訊息延時，即一個訊息從一個進程傳遞到另一個進程的時間長度是未知的。

除了同步和異步模型，還有部分同步模型和時控異步模型。在時控異步模型中，進程的時鐘偏移率(時鐘每秒相對物理時間的偏差)可以忽略，因而進程可檢測到某事件發生的真實時間。在部分同步模型中，或者假設訊息延時和進程的相對速度都存在上界，但並非已知，或者假設兩者的上界都已知，但僅在一個未知的時間點以後生效。一般把以上兩個假設稱作部分同步條件。

故障

在容錯分散式系統中的故障(failure)可分為進程故障和通信故障。當說到在某個系統模型下假設或允許某種故障，其含義是在這一系統模型下假設這種故障是可能發生的。

1進程故障

當我們說一個進程正常運行，指的是這個進程按照指定的協定運作(包括如何收發訊息和實現內部狀態的轉換)。一般假設系統中至少存在一個正常運行的進程。若一個進程不正常運行，那么我們說它發生了故障。進程故障按照危害程度，可分為：停止故障、遺漏故障和拜占庭故障。停止故障指的是一個進程從正常運行的狀態進入到完全停止的狀態並且不再恢復。遺漏故障指的是進程在應該收發訊息的時候漏發或漏收訊息。拜占庭故障(Byzantinefailure)指的是進程不按照指定的協定運行，即它的行為完全不可預測。按照發生故障的進程數目，又可分為多數故障和少數故障。多數故障是指系統的某次運行中發生故障的進程數目超過或等於半數；少數故障是指系統的某次運行中發生故障的進程數目低於半數。

目前主要考慮允許停止故障(而不允許其他進程故障)的系統模型，因為事實證明在異步模型下考慮遺漏故障和拜占庭故障將使問題過於複雜。注意到在異步模型下由於不定長的訊息延時，當一個進程長時間沒收到另一進程的訊息時，它無法判斷這是由於訊息延時還是由於這個進程己經停止運行。因此異步模型下實際無法區分一個正常運行的進程和一個己發生停止故障的進程。

2.通信故障

在點對點的訊息傳遞中，當我們說從進程A到B的鏈路(link)是可靠的，指的是此鏈路滿足以下兩點：一、當A和B都正常運行時，A傳送給B的訊息將最終到達B；二、如果B收到了來自A的某個訊息，那么此訊息的確是由A發出的。若一條鏈路不是可靠的，那么我們說它發生了故障。通信(或鏈路)故障按照危害程度，可分為訊息丟失和任意鏈路。訊息丟失指的是某條鏈路違反以上第一點，但滿足第二點。任意鏈路指的是某條鏈路違反以上第一點或第二點。

目前主要考慮允許訊息丟失(而不允許其他通信故障)的系統模型。和停止故障不同，訊息丟失是一種不穩定的故障，即有無故障的兩種狀態可以互相切換。如果在某段時間內，從某鏈路的傳送端發出的訊息全部丟失，那么我們稱這條鏈路在那段時間內是斷開的。注意到在異步模型下由於不定長的訊息延時，當一個進程長時間沒收到另一進程的訊息時，它無法判斷這是由於訊息延時還是訊息丟失，因此異步模型下實際無法區分一條可靠的鏈路和一條斷開的鏈路。

網路拓撲

網路拓撲(network topology)主要是指一張由正常運行的進程和這些進程間可靠的鏈路構成的有向圖。其中的每一條有向邊A→B的存在，是若且唯若A和B都正常運行，而它們間的通信鏈路存在且可靠。因此進程故障和通信故障是網路拓撲變化的主要原因。比如在圖2中，虛實箭頭表示存在的鏈路，當進程a和b、c和d之間的鏈路可靠時整個網路拓撲是強連通的，而當這兩條鏈路都斷開後網路拓撲便被分割成了兩個互不連通的分量。

圖2 網路拓撲的實例

一般把網路拓撲由於進程或通信故障被分成兩個或兩個以上互不連通的分量的現象被叫做網路分割。注意到在異步模型下，訊息延時可能導致無法判斷一條鏈路是否己斷開，因此異步模型下存在一種和真實網路分割不可區分的虛網路分割。對於網路拓撲中的某一個子圖S，若存在某一時刻，從這一時刻起S滿足以下三點：一、S中的進程不是停止就是正常運行(且沒有進程加入和退出S)；二、S中的每對進程間的鏈路都是可靠的；三、S中的進程和系統中其他進程間的鏈路都是斷開的，那么我們稱S是一個穩定分量。

系統模型中對網路拓撲的假設最常見的有兩種，一種假設網路拓撲總是強連通的(stronglyconneeted)或全連通的(completelyconneeted)，作這種假設的系統模型一般同時假設可靠的通信鏈路；另一種是假設網路拓撲是可分割的(partitionable)，即假設可能出現網路分割現象，作這種假設的系統模型一般同時允許訊息丟失的通信故障。

兩個經典問題

故障檢測器和共識是容錯分散式系統中兩個經典的問題，同時也是最常用的兩個服務。早在80年代，它們己被證明在異步模型下是不可解的。正因為不可解，它們常常在異步模型下被當作神諭使用。這兩個不可能性結果對於異步模型下的系統設計起到極其重要的作用，並且自此以後，研究一個規格的可解性時，常常把它和FD以及Consensus的規格作比較。

共識

共識(Consensus)是分散式系統中常常需要解決的問題，也就是要使得系統中的進程在某一變數的值上達成一致。通常Consensus規格的接口是由每個進程向Consensus提供一個可選變數值(提出一個變數值)，而後從Consensus得到一個最終變數值(決定一個變數值)。Consensus最常見的規格如下，它被證明在經典模型下是不可解的。

如無特殊說明，Consensus(規格)指的就是下述規格。

輸入：進程提出一個變數值

輸出：進程決定一個變數值

1、終止性termination)：每個正常運行的進程最終決定某個值

2、一致性(agreemcnt)：沒有兩個進程決定不同的值

3、有效性(validity)：每個進程最多決定一次，且它所決定的值一定被某個進程提出過

一種特殊的Consensus規格叫二進制共識，它規定了進程提出和決定的變數值只能是0或1。已經證明，二進制Consensus規格和上述規格是一樣強的。

Consensus的實例

故障檢測器

故障檢測器(FailureDeteetor，FD)概括了容錯分散式系統中最需要解決的一個問題，也就是要使得系統中的進程儘可能精確地檢測到有哪些進程或鏈路己經發生故障。大部分FD規格是在經典模型下被提出，因此它們需要檢測的僅僅是哪些進程已停止運行。在這種情況下，FD規格的輸出既可以是被認為停止的進程，又可以是被認為正常運行的進程。

公認的經典模型下的FD規格有很多，這些FD規格所滿足的屬性一般是完備性和不同程度的準確性的組合。簡而言之，FD的完備性是指出故障的進程應最終被檢測到，FD的準確性(accuracy)是指正常運行的進程不應被檢測到(或者說被凡是檢測到的都是已出故障的進程)，而FD的精確性(preejsion)是完備性和準確性的組合。證明了同時具有完備性和(不同程度)準確性的FD規格在經典模型下都是不可解的。

完備性和四種不同程度的準確性的組合可產生四種FD規格：(若輸出是被認為正常運行的進程，只須把屬性中的“輸出”和“不輸出”反置

輸出：(被認為)已停止運行的進程的記

1、完備性(completeness)：存在一個時刻t₁，從t₁起每個停止的進程都將被每個正常運行的進程的FD輸出

2、強準確性(strongaccuracy)：任何正常運行的進程都不會被任何進程的FD輸出(每個被FD輸出的進程都是停止的進程)

3、弱準確性(weakaccuracy)：存在一個正常運行的進程，它不會被任何進程的FD輸出

4、最終強準確性(eventuallystrongaccuracy)：存在一個時刻t₂，從t₂起任何正常運行的進程都不會被任何進程的FD輸出(最終每個被FD輸出的進程都是停止的進程)

5、最終強準確性：存在t₂和一個正常運行的進程，從t₂起這個進程不會被任何進程的FD輸出

系統維修策略

許多實際系統在使用過程中，往往由於對維修性問題考慮不周，致使系統的維修費用增加；另一方面如果對系統進行過多的維修，不僅不能提高系統的可靠性和可用度，反而使系統的性能降低。因此系統採用何種維修策略，將關係到系統的性能和維修費用。

維修策略連續時間的基本維修策略主要有：年齡更換策略、成批更換策略、故障小修的周期更換策略、年齡維修策略、備用部件的預防維修策略、故障小修的周期維修策略等。由於計算機及其外部設備都極其昂貴，若採用故障更換的方法顯然不合適，而採用故障維修的方法則是較為經濟的維修策略。

年齡維修策略是指：當系統達到指定的年齡T仍然正常，則對系統進行預防維修，預防維修時間均值為α。若系統在指定的時間T之前發生故障，就立即進行事後維修，維修時間均值為β，圖3為其示意圖。

圖3 年齡維修策略

機載容錯分散式系統

研究背景及意義

作為嵌入式系統在航空航天領域的套用，機載容錯分散式系統是新一代航空電子系統的核心，而綜合化航空電子系統又是現代飛行器的神經中樞。航空電子系統的發展直接促進了機載計算機技術的發展，新一代飛機的航空電子系統是以高度集成化、模組化為特徵，以機載實時容錯分散式計算機系統為載體，高度綜台化、高可靠性、具有容錯能力的系統。

新一代航空電子系統是一種綜合化、模組化的機載分散式體系結構，原“子系統”的概念演變為在統一的計算機處理平台上運行的軟體功能組件．不再存在“子系統”的專用計算機資源。機載容錯分散式系統將承擔著大量飛行任務的執行、控制和飛機安全性保障等工作，美國的F35就是典型的代表。

機載容錯分散式系統的軟體已成為影響整個飛機性能的關鍵因素之一，而按國外一些關於新一代航空電子系統的規範和標準，確定性設計是至關重要的。

系統結構

機載容錯分散式系統的系統結構由多個計算機群及系統大容量存儲器SMM(SystemMass Memory)組成，整個系統通過一個具有雙余度的FC環網連線成分散式系統。每個計算機群由多個信號處理模組和數據處理模組組成。每個計算機群除與系統FC環網連線之外，還與本地的FC開關網路連線．實現機群內的局部通訊。SMM為整個系統的系統軟體、應用程式以及相關數據參數提供載入、存儲、記錄和管理服務以及關鍵信息的存儲。

機載容錯分散式系統將是新一代航空電子系統的核心，而其系統軟體又是整個系統的關鍵，其軟體結構由美國的“寶石台”計畫的“系統執行、分布執行和核心執行”三個執行發展到歐洲的ASAAC規範的航電系統軟體新結構。按這種結構，系統軟體是一個立體結構，系統軟體的結構按水平方向分為套用層、作業系統層、模組支持層，這稱為三層棧TLS結構(TlhrccLayerStack)；按垂直方向分為實時作業系統部分和系統管理部分。系統管理又分為套用管理AM和通用系統管理GSM。AM在套用層，GSM在作業系統層；按立體方向進行劃分系統管理可分為三級；飛機級AC(Aircraft)、綜合區級IA(Integration Area)和資源元素級RE(ResourceElement)。飛機級的系統管理負責控制和監控整個IMA(IntegratedModuleAvionics)。IA級系統管理負責控制某一子功能模組，RE級系統管理是最底層的系統管理，負責管理單個PE(ProcessingElemeat)的功能。

如圖4給出了機載容錯分散式系統的軟體結構。

圖4 機載容錯分散式系統的軟體結構圖