基于向量時(shí)鐘的動(dòng)態(tài)自適應(yīng)同步策略研究*

王藝遙，齊和平，李學(xué)艷，毛玉輝，柴 彪

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

0 引言

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

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

1 基本原理

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

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

表1 保守策略與樂(lè)觀策略對(duì)比

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

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

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

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

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

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

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

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

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

3.1 向量時(shí)鐘

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

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

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

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

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

3.2 算法周期運(yùn)行

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

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

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

2）當(dāng)節(jié)點(diǎn)收到下一周期開(kāi)始標(biāo)志后，停止當(dāng)前推進(jìn)，向其他節(jié)點(diǎn)發(fā)送下一周期開(kāi)始標(biāo)志。

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

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

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

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

圖4 ABTW-VC 算法流程圖

4 實(shí)驗(yàn)

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

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

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

5 結(jié)論

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