王藝遙，齊和平，李學艷，毛玉輝，柴 彪

（北方自動控制技術(shù)研究所，太原 030006）

0 引言

分布式仿真的主要思想是將單個仿真程序并行地在多個處理器上并發(fā)運行，提高并行性以打破仿真順序中時間和空間的局限，滿足仿真性能要求。分布式仿真致力于提高系統(tǒng)并發(fā)性，不可避免地會因為網(wǎng)絡(luò)延遲、時鐘不一致、節(jié)點掉線等各種問題造成因果順序錯亂。在理想條件下，仿真事件推進和通信的時延應(yīng)當與實際系統(tǒng)事件發(fā)生的時延一致，但是實際仿真過程中，信息傳輸延遲并不是穩(wěn)定的，通常不可預(yù)測，且整個仿真系統(tǒng)的各個組成部分不能確保完全一致的系統(tǒng)時間，因此，可能出現(xiàn)因果紊亂的情況。

為解決這一問題，保證仿真結(jié)果的真實性、可靠性與可讀性，需要對并行仿真系統(tǒng)做因果關(guān)系約束。并行仿真系統(tǒng)通過多個帶有時間戳的邏輯進程完成消息通信，處理器的性能和復(fù)雜的網(wǎng)絡(luò)架構(gòu)造成了消息通信的隨機性，需要通過消息傳輸策略維護并發(fā)事件之間的邏輯關(guān)系，這種方法被稱為同步策略。

1 基本原理

典型的同步策略有保守策略和樂觀策略。最早的保守策略由Chandy、Misra 和Bryant 3 人提出，因此，稱為CMB 協(xié)議。在CMB 協(xié)議中，各個邏輯進程的事件都帶有時間戳，每個消息都需要保證時間戳不會小于本地局部仿真時間，才可執(zhí)行當前事件。由此，所有事件都會嚴格按照順序執(zhí)行，整個仿真系統(tǒng)的因果性得到保證。由于保守策略對時序的嚴格要求，需要不斷判斷事件是否可以執(zhí)行，若有一個處理器上事件為空，邏輯進程將等待，直到事件不為空，這可能導致循環(huán)等待，進而產(chǎn)生死鎖。解決死鎖的方法有死鎖恢復(fù)法和死鎖避免法，死鎖恢復(fù)法需要系統(tǒng)有死鎖檢測機制，當產(chǎn)生死鎖時，邏輯進程檢測到死鎖并打開死鎖，執(zhí)行事件；死鎖避免法的一個典型案例為空消息法，邏輯進程不會發(fā)送小于空消息時間戳的消息，事件執(zhí)行完成后，邏輯進程會發(fā)送一個空消息，來保證事件的正常執(zhí)行，空消息的時間戳一般為當前事件結(jié)束時間加一較小常量。

樂觀策略與保守策略相反，它并不嚴格遵守因果邏輯，而是在因果錯誤發(fā)生后，采用回退機制來修復(fù)錯誤，典型的樂觀策略是由Jefferson 和Sowizral提出的Time Warp 機制。各處理器上的邏輯進程執(zhí)行本地事件，執(zhí)行完畢后向其他邏輯進程發(fā)送事件消息，當某邏輯進程收到時間戳小于本身事件時間戳的消息A 時，發(fā)生了因果錯誤，該邏輯進程需要將事件回退至消息A 的時間戳前，并需要向其他邏輯進程發(fā)送回退事件的逆消息，以撤銷事件執(zhí)行時發(fā)送的消息。由此可見，為保證整個仿真系統(tǒng)的因果性，每個處理器需要記錄邏輯進程執(zhí)行過的事件，否則難以精確回退，這需要占用大量資源存儲信息。為此，需要給整個系統(tǒng)設(shè)定一個全局虛擬時間，超過這一時間的事件信息認定不會回退，即可刪除這一時間前的事件，回收內(nèi)存。樂觀策略的回退機制會占用一定系統(tǒng)資源導致效率下降，因此，考慮對樂觀策略作一定限制，根據(jù)限制方法不同，產(chǎn)生了基于窗口的策略、基于懲罰的策略、基于概率的策略等。同時，也可以對回退機制進行限制，如惰性取消策略，在產(chǎn)生因果錯誤后，邏輯進程回退后先進行模擬，將模擬產(chǎn)生的消息與原發(fā)送消息對比，若二者不同再發(fā)送逆消息，這有利于提高效率。保守策略與樂觀策略的對比如表1 所示。

表1 保守策略與樂觀策略對比

2 動態(tài)自適應(yīng)策略

以上策略都是靜態(tài)策略，設(shè)定好后難以根據(jù)仿真系統(tǒng)狀態(tài)變化實時調(diào)整，動態(tài)自適應(yīng)策略通過動態(tài)調(diào)整參數(shù)解決了問題，其性能曲線如圖1 所示。圖1 中實線為執(zhí)行時間，虛線為資源消耗，曲線①由于極端保守，阻塞嚴重，資源消耗增加；曲線②由于過度樂觀，不斷產(chǎn)生回退，資源消耗增大。

圖1 動態(tài)自適應(yīng)策略性能曲線

動態(tài)自適應(yīng)策略分為兩類，一類是基于局部狀態(tài)的策略，如自適應(yīng)有界時間窗（adaptive bounded time window，ABTW）。這一策略的思想是限定一個時間段，仿真系統(tǒng)在這一時間段內(nèi)按照樂觀策略執(zhí)行事件，借助時間窗來控制樂觀策略，防止回退次數(shù)過多，增加系統(tǒng)資源開銷。時間窗的大小根據(jù)系統(tǒng)實際情況動態(tài)調(diào)整，調(diào)整的依據(jù)是邏輯進程的有用工作。有用工作是反映邏輯進程所做有效工作的函數(shù)，其參數(shù)有執(zhí)行任務(wù)率、任務(wù)重新執(zhí)行次數(shù)、平均重新執(zhí)行長度以及發(fā)送的反消息數(shù)。

另一類是基于全局狀態(tài)的策略，這一策略的典型代表是近于完美狀態(tài)信息算法。算法實現(xiàn)依靠獲取的近于完美的狀態(tài)信息，這些信息來自完整的仿真系統(tǒng)。算法定義了錯誤潛在參數(shù)，每個邏輯進程都有一個對應(yīng)的錯誤潛在參數(shù)，在彈性時間算法中，錯誤潛在參數(shù)指邏輯進程的下一個待處理事件的時間戳，與全球虛擬時間設(shè)定的最早未處理時間戳下限之間的差值，在事件運行過程中加入等待時間，等待時間與錯誤潛在參數(shù)有一定函數(shù)關(guān)系，錯誤潛在參數(shù)越大，等待時間越長，進而控制了邏輯進程的樂觀策略。

3 基于向量時鐘的自適應(yīng)有界時間窗算法

以上兩類策略中，基于全局狀態(tài)的策略的狀態(tài)信息過于冗雜，帶來了較大資源開銷，因此，考慮基于局部狀態(tài)的策略。

移動時間窗算法（moving time window，MTW）是限制樂觀策略的算法，其主要思想是對邏輯進程仿真時間超過其他邏輯進程仿真時間的上限進行設(shè)置，在上限前，系統(tǒng)按照樂觀策略進行仿真，某邏輯進程達到上限時，便對其進行阻塞，直到其他邏輯進程全部達到上限。時間窗的下限為全局虛擬時間（global virtual time，GVT），時間窗上限為GVT+W，W 為設(shè)定的時間窗值，隨著全局虛擬時間推進，時間窗也在推進，但邏輯進程不能超過時間窗上限，由此限制了各邏輯進程的推進，避免發(fā)生因果錯誤時產(chǎn)生過多回退。但時間窗值設(shè)定好后無法在運行中修改，且增加了各邏輯進程間同步全局虛擬時間的開銷。

據(jù)此提出了基于向量時鐘的動態(tài)自適應(yīng)有界時間窗算法，算法思路如下。

3.1 向量時鐘

對整個仿真系統(tǒng)建模如下：G=（V，E，M）表示整個仿真系統(tǒng)的通信部分，其中，V 表示所有邏輯進程（logical process，LP）的集合，E 表示所有邏輯進程間信道的集合，即所有的通信連接，M 表示所有消息的集合。對于消息m和m，若兩者從同一個節(jié)點發(fā)出，且m發(fā)出后的下一條消息為m，或兩者從不同節(jié)點發(fā)出，且m是m被接收后的下一個消息，稱m和m存在因果關(guān)系，可記為m→m，即m是事件的原因，m是事件的結(jié)果。顯然因果關(guān)系是傳遞，非對稱、不可自反的。記S（m，u，v）表示節(jié)點u 通過信道（u，v）發(fā)送消息m，R（m，u，v）表示節(jié)點v 通過信道（u，v）接收消息m。顯然S（m，u，v）對R（m，u，v）是發(fā)生在先的，可記為S（m，u，v）＜R（m，u，v）。則因果異?？杀硎緸椋喝鬽→m，但R（m，c，v）＜R（m，c，v），其中，c 表示任意節(jié)點。將因果異常記為A（m，m，v），其中，m→m，v 為接收節(jié)點。記（u，v）為節(jié)點u 到節(jié)點v 的直接連接，［u，v］為節(jié)點u 到節(jié)點v 的間接連接。由此可知，當A（m，m，v），存在［u，v］。

分布式仿真中沒有內(nèi)在的物理時鐘，只能對此進行近似，在邏輯進程中，可以通過事件因果關(guān)系確定事件順序，各進程之間的時序共享則通過邏輯時鐘實現(xiàn)。邏輯時鐘（logical clock，LC）由Lamport 提出，每個邏輯進程LP有一個邏輯時鐘LC，將邏輯進程發(fā)出的消息記為一個三元組（m，LC，i），即為消息內(nèi)容，邏輯時鐘，進程序號。邏輯時鐘的更新原理如下。

在發(fā)生事件前，邏輯進程LP更新邏輯時鐘LC=LC+x，x 為根據(jù)實際情況設(shè)置的定值，當邏輯進程LP收到其他邏輯進程LP的消息（m，LC，j）時，根據(jù)LC=max（LC，LC）+x 進行更新。這種邏輯時鐘是線性的，可以解決互斥問題，但其不具有強一致性，在高并發(fā)的情況下不夠完備。為彌補邏輯時鐘的缺點，提出向量時鐘（vector clock，VC）的觀點，使用n 維整數(shù)向量表示時間，每個邏輯進程LP關(guān)聯(lián)一個向量LC［1，…，n］，LC［i］表示邏輯進程本身的信息，LC［j］表示邏輯進程i 關(guān)于邏輯進程j 的信息，由此LC［1，…，n］就表明了邏輯進程i 關(guān)于全局的信息。由于邏輯進程LP推進向量時鐘的第i 個分量，即邏輯進程LP總是對向量時鐘第i 個分量有最精確的了解，則對邏輯進程LP恒有LC［j］≤LC［i］。

向量時鐘的更新規(guī)則為：LC［i］初始值為0，在發(fā)送和提交消息前增加時鐘值，由此可以保證在同一邏輯進程，有因果關(guān)系的消息的時間單調(diào)遞增。在事件發(fā)生前，更新LC［i］=LC［i］+x，當邏輯進程LP接收到消息（m，LC，j）時，消息的向量時間和邏輯進程的向量時間具有相同的結(jié)構(gòu)和意義。因此，可以進行比較，為確定消息是否會引發(fā)因果異常，僅需考慮LC［k］和LC［k］，更新LC［k］=max（LC［k］，LC［k］），LC［i］=LC［i］+x。根據(jù)這一更新規(guī)則可知，由邏輯進程發(fā)送的消息在邏輯進程被接收時，若LC［j］≤LC［j］，則存在消息m已被接收提交，且有m→m，A（m，m，i）。使用向量時鐘，可以降低消息之間的關(guān)聯(lián)性，減少回退消息的數(shù)量，降低回退對仿真系統(tǒng)推進的影響。向量時鐘由各節(jié)點的因果時間組成，對于監(jiān)控節(jié)點，其向量時鐘的各個向量只是表示其對系統(tǒng)其他節(jié)點的觀測，不存在監(jiān)控節(jié)點的本地時鐘。仿真運行中，不需要比較各個消息的時間序，只需要將消息的時間與接收節(jié)點的時間比較，即可確定這一消息是否可以直接發(fā)送給目標節(jié)點。向量時鐘的更新規(guī)則如圖2 所示。

圖2 向量時鐘更新規(guī)則

3.2 算法周期運行

本文提出的基于向量時鐘的動態(tài)自適應(yīng)動態(tài)有界時間窗算法，簡記為ABTW-VC 算法，這一算法以周期循環(huán)方式推進仿真運行，每個周期運行如下：

1）每個節(jié)點存在兩個隊列，一個先進先出隊列，隊列中的消息可以直接發(fā)送，即將消息放在先進先出隊列中，就認為其可以發(fā)送給接收節(jié)點了。另一個是等待隊列，用于存儲先接收的消息，這些消息一般是結(jié)果信息，如果結(jié)果信息先于原因信息發(fā)送，則產(chǎn)生因果錯誤。因此，只有先進先出隊列的消息可以發(fā)送，這個過程的流程圖如圖3 所示。

圖3 消息發(fā)送流程圖

2）當節(jié)點收到下一周期開始標志后，停止當前推進，向其他節(jié)點發(fā)送下一周期開始標志。

3）將節(jié)點先進先出隊列中的消息按時間序發(fā)送，將等待隊列中的消息按時序排列，判斷是否所有節(jié)點都收到了下一周期開始標志，若收到，計算全局虛擬時鐘，同步系統(tǒng)時間，等待下一周期執(zhí)行。

4）開始下一周期。如圖3 所示，每個節(jié)點要發(fā)送消息時，首先判斷消息時間是否可能產(chǎn)生因果錯誤，如果不會產(chǎn)生因果錯誤，將消息送入先進先出隊列，實時發(fā)送消息給其他節(jié)點；如果可能會發(fā)生因果錯誤，需要確認可能發(fā)生因果錯誤的原因消息，結(jié)果消息和消息發(fā)生的路徑，然后在仿真運行過程中對相關(guān)路徑進行監(jiān)控。當收到結(jié)果消息時，接收節(jié)點判斷消息時間與本身向量時鐘的關(guān)系，如果結(jié)果消息先于原因消息，則結(jié)果消息在等待隊列中等待，直到原因消息發(fā)出才進入先入先出隊列。對于其他路徑的消息，認為其在本節(jié)點不會發(fā)生因果錯誤，可直接提交，消息會直接進入先入先出隊列，節(jié)點的向量時鐘也向前推進，然后根據(jù)新向量時鐘檢驗等待隊列中的消息，由此保證系統(tǒng)的因果性。

這一過程的算法實現(xiàn)如下：

由此ABTW-VC 算法運行完畢，算法流程圖如圖4 所示。

圖4 ABTW-VC 算法流程圖

4 實驗

本文采用2 臺計算機模擬分布式仿真系統(tǒng)，一臺計算機模擬服務(wù)器，一臺計算機用程序模擬100個節(jié)點作為仿真成員，每個節(jié)點按照一定頻率發(fā)送一定數(shù)量的消息模擬服務(wù)器與仿真成員之間的信息傳輸。消息設(shè)定為每發(fā)送一條原因消息，發(fā)送一條與之相對的結(jié)果消息，消息發(fā)送頻率設(shè)定為每個節(jié)點每100 ms 發(fā)送一條消息。除本算法外，采用Time Warp 樂觀策略，CMB 保守策略進行比對，結(jié)果如圖5 所示。

圖5 3 種算法結(jié)果圖

由圖5 可知，雖然在消息數(shù)量較少時，3 種算法的仿真時間十分接近，但隨著仿真系統(tǒng)消息數(shù)量的增加，Time Warp 樂觀策略和CMB 保守策略因存在缺陷而產(chǎn)生阻塞，ABTW-VC 算法仍可流暢運行，且運行時間短于另外兩種策略。在發(fā)送100 萬條消息時，本算法的運行時間比另外兩者分別縮短了16.59%，24.41%。

5 結(jié)論

本文提出了基于向量時鐘的自適應(yīng)有界時間窗算法，在傳輸消息較多的仿真系統(tǒng)中，經(jīng)驗證可以減少系統(tǒng)運行時間，避免因果錯誤。采用這一算法雖然有優(yōu)點，但也存在一些問題。從性能角度考慮，這一算法需要各邏輯進程大量記錄事件時間信息，若仿真規(guī)模過大，事件發(fā)生過密集，存儲事件時間就會占用較多存儲資源，但不影響系統(tǒng)運行性能，可在指揮控制、火力控制等工程中應(yīng)用推廣。