ＰＤＥＳ時間推進中保守算法的研究與實現

摘要：介紹了PDES時間推進中的保守算法，給出了保守策略，分析了死鎖的產生原因，并給出了解決死鎖的方法，最后對算法進行了實現。

關鍵詞：PDES；保守算法；死鎖；空消息

中圖分類號：TP311 文獻標識碼 A 文章編號：1009-3044(2009)05-1194-03

Research and Realization of the Conservative Arithmetic in PDES Time Advancing

MIAO Qing， DING Jing，KONG Jian-xing

(Artillery Academy， Hefei 230031，China)

Abstract: It introduces the conservative arithmetic in PDES time advancing， giving the conservative strategy， analyzing the cause of the deadlock and giving the resolvent of the deadlock. In the end， it realizes the arithmetic.

Key words: PDES; conservative arithmetic; deadlock; 1 message

1 引言

并行離散事件仿真（Parallel Discrete Event Simulation，PDES），是指在多處理器系統或網絡工作站上并行執行離散事件仿真程序。如何將不同類型的仿真系統的內部時間協調一致，是保證仿真正確運行的基本前提條件，這也正是PDES過去20年努力解決的問題。隨著近年來計算機仿真技術中高層體系結構（High Level Architecture，HLA）的飛速發展，作為HLA時間管理算法直接來源的PDES中的時間推進算法，對其的研究又掀起了新的高潮。

PDES中關鍵的時間推進同步算法始終是仿真界公認的重點和難點問題。目前PDES主要采取兩類同步算法。保守算法嚴格禁止發生因果關系錯誤，確保不會失序地處理非獨立事件，也就是保證依據時間的邏輯先后順序在并行機上處理事件，但可能發生死鎖。樂觀算法充分利用系統平臺的并行計算能力，設定分布在每個處理機上的邏輯進程可以按任意順序在空閑的處理機上執行，一旦出現任何一個關系錯誤即發生同步錯誤，則及時進行回退，并且恢復系統上一時刻的狀態。本文重點研究PDES時間推進中的保守算法。

2 PDES時間推進中保守算法的研究

2.1 保守（Conservative）策略

PDES中保守算法的基本思想是：假設物理系統滿足可實現性（Realizability）和可預測性（Predictability），并且在遵守本地因果約束條件（Local Causality Constraint）的前提下，可以實現對系統的正確仿真。

可實現性保證系統發出的t時刻消息僅依賴于t時刻以前接收到的消息狀態，可預測性保證系統能夠在t時刻預測出t+ε時刻的消息(ε＞0)。

本地因果約束條件是指由一組邏輯進程組成的離散事件仿真系統，當且僅當每個邏輯進程按非遞減的時戳順序處理事件，則系統遵守本地因果約束條件。

保守策略嚴格禁止發生因果錯誤，即保證按時間先后順序在并行機上處理各類事件。保守策略的主要任務是確定何時能“保險”地執行某一事件，它常常依賴于仿真模型行為的信息，如模型的可預測性等來確定哪個事件能被“保險”地執行。

在保守算法中，到達每個進程輸入通道的消息按時戳順序存儲，一個進程發送給另外一個進程的消息被保存在一個先進先出（FIFO）的隊列中。對每個通道都有自己的通道時鐘，時鐘的取值按照三條原則：

原則1：仿真開始時，各個時鐘取值為零；

原則2：如果隊列不為空，則時鐘取值為隊列中第一個消息的時戳，第一個消息是該隊列中時戳最小的消息；

原則3：如果隊列為空，則時鐘取值為最后一次接收到的消息時戳。

進程循環選出時鐘值最小的輸入通道，并且當該通道隊列中有消息時，處理時戳最小的消息。如果這個通道隊列是空的，那么這個進程會被阻塞。這樣就保證了每次每個進程都能按時戳遞增的順序處理一個事件，因而遵守了本地因果關系約束條件。

一個保守進程處理消息的過程可用下列算法表示。

算法1：進程處理消息過程

While（仿真沒有結束）{

等待直到每個FIFO隊列都至少包含一個消息；

找出所有隊列中的最小的時戳消息M，并從相應的隊列中刪除；

時鐘Clock：=消息M的時戳；

處理消息M；

}

2.2 保守算法的死鎖問題

保守方法嚴格遵守本地因果約束條件，總是不斷地判斷何時可以安全處理事件，當不能確保任何可能影響事件處理的所有事件都己處理完時，進程將被阻塞，因此在保守方法中，可能發生死鎖現象。具體地說，如果進程含有一個未處理的事件E1，其時戳為T1，（并且在進程中不再有更小的時戳），進程可以確定的是，以后它不可能收到比T1更小時戳的事件，處理E1不會在將來發生本地因果關系的沖突，因此進程可以安全處理E1。如果進程無法確認這一點，就必須被阻塞。如果一直沒有適當的前因激活進程，系統可能導致死鎖。

在PDES中，常見的死鎖情況是，如果通道時鐘較小的空隊列形成回路，回路中的每個進程都被阻塞，整個系統中的所有進程均處于等待狀態，因此仿真發生死鎖。

圖1描述了三個進程處于死鎖等待狀態的情形，雖然在每個進程的其他輸入隊列中有等待處理的事件消息，但由于進程循環選出時鐘值最小的輸入通道，并且當該通道隊列中有消息時，處理時戳最小的消息。如果這個通道隊列是空的，那么這個進程會被阻塞。假如此時具有最小通道時鐘的輸入通道隊列是空隊列，那么每個進程都在等待消息的到來，此時進程A等待來自進程B的消息，進程B等待來自進程C的消息，進程C等待來自進程A的消息，即三個進程之間形成了一個圈，則發生死鎖。

2．3 保守算法的死鎖解決方法

由于在上述情況下，PDES的保守機制可能發生死鎖，所以在實際仿真中，就必須采取一些措施，打破死鎖，推進仿真時鐘。目前一般使用三種解決死鎖的方法：空消息法、命令驅動的空消息法、死鎖的探測和恢復機制。本文主要研究使用最為廣泛的空消息法。

Chandy和Misra提出了第一個保守算法，即Chandy/Misra算法，首次提出了前瞻值的概念，并提出了用于解決死鎖問題的空消息法（Null Message)。空消息法本質上就是一種基于前瞻值的方法。

空消息法基于下列幾個假設：

假設1：每個進程預先知道需要向哪些進程發送消息，以及從哪些進程接收消息；

假設2：每個進程以非遞減的時戳序發送消息；

假設3：網絡能夠確保先發送的消息被先接收到（FIFO）；

假設4：網絡是可靠的。

這種算法限定了信息按時間戳順序到達進程的接受隊列中，一個進程從另外一個進程接收到的最后一個消息表明該進程再不會接收到小于該消息時戳的消息，最后一個消息的時戳表明了以后所能夠接收到的消息的時戳下界。即假設LPi發給LPj一種新的消息（T，Null），其含義是：到T時刻為止，LPi不會發送任何消息給LPj，因此以后發出的任何消息時戳均大于T。該消息排在通道的最后，而且只有這個消息可能是空消息。

圖1所示的死鎖可以用如下方法解決：假設進程之間的網絡延遲為3個仿真時間單位，進程C的當前仿真時間為5，那么不論進程C將要發送什么消息，進程B一定在仿真時間8（8=5+3）之后才能夠收到來自進程C的消息。雖然進程B收到時戳為8的消息，但仍無法處理FIFO隊列中的時戳為10的消息，可是進程B知道它的下一個消息的時戳至少為8，進程A一定在仿真時間11（11=8+3）之后才能夠收到來自進程B的消息。這樣進程A就可以安全地處理FIFO隊列中的消息9了。也就是說，在進程A，進程B和進程C的輸入通道環中，始終有一個空消息在循環流動，其時戳值不斷累加。這樣，就避免了死鎖的發生。整個過程如圖2所示。

圖2中的進程之間發送的消息僅僅用于進程同步，不是仿真系統中實際發生的事件，不需要消息體，因此將這類消息稱之為“空消息”，相應的算法稱之為空消息法。空消息用來表示進程之間“發送消息”時的一種承諾，表示不會發送時戳低于某一下界的消息。更一般地講，空消息法實際上是一種基于前瞻值的一種算法。上述“進程之間的網絡延遲”的“3個仿真時間單位”即為前瞻值。

當進程處理完事件，就向每個輸出端口發出空消息，通知這個下限，于是收到空消息的接收方就能根據這個信息，計算出它的輸出通道的新的下限，并把該信息通知它的鄰居。

從接收方而言，處理空消息的方法和處理其他消息的方法一樣：該消息都會使邏輯進程更新內部狀態，以及仿真時鐘，并在必要的情況下發出消息。

Chandy/Misra空消息法可參見算法2：

算法2 ：Chandy/Misra空消息法

While（仿真沒有結束）{

等待直到每個FIFO隊列都至少包含一個消息；

找出所有隊列中的最小的時戳消息M，并從相應的隊列中刪除；

時鐘Clock：=消息M的時戳；

處理消息M；

向相鄰進程發送空消息，空消息的時戳為Clock+Lookahead。

}

3 算法實現

基于保守算法，我們采用C#.net編寫程序，構建了用空消息法實現保守時間推進策略的系統。

系統的初始界面如圖3所示，界面左邊三欄分別顯示三個進程通道中的當前狀態，主要是收發消息（包括帶有具體內容的實消息和只帶有時戳的空消息）和處理消息的過程，右邊一欄顯示的是各個進程當前的進程時鐘和當前接收通道中接收其他進程發送的消息時戳（包括帶有具體內容的實消息和只帶有時戳的空消息）。本系統的前瞻量設定為3個仿真時間單位。點擊“Start”鍵系統開始運行，點擊“Reset”鍵系統重啟。

當系統運行時，帶有“message”字樣的消息表示具有實際內容的實消息的發送，括號里的數字表示該消息的時戳。帶有“empty message” 字樣的消息表示只具有時戳的空消息的發送，括號里的數字表示空消息的時戳。無論空消息或者實消息被處理后，系統都對該消息打上“handled”標記。如圖4所示，此時進程A，B，C的仿真時鐘已分別推進到“9”，“8”，“8”。

依此類推，系統總是保證每次每個進程都能按時戳遞增的順序處理一個事件。當某一進程處理完一個事件后，就向每個輸出端口發出空消息，空消息的時戳為當前進程時鐘值Clock+Lookahead，通知其他進程不會再發送時戳低于Clock+Lookahead的消息了。因而遵守了本地因果關系約束條件。

4 結束語

實現的具體代碼在此就不一一列出了，有需要的同仁可直接向作者索取。空消息法最大的優點是簡單，只需要對源代碼作少量修改，增加空消息的發送就可以了。此外，對進程間的通訊緩存區也沒有額外的要求，如果進程間的緩存區的大小有限，發送消息的進程只需等到有空余緩存區的時候，再發送消息，得到的仿真結果是一樣的。

該方法最大的缺點是將產生大量的空消息，增加了網絡負載，降低了算法性能。另外，對于處于環中進程的時間前瞻值大于0的情況，這種機制可以避免死鎖。但這種方法不能解決所有的死鎖問題，如時間前瞻值為0的情況，因此空消息不能解決那些最小服務時間為0的隊列型網絡仿真中的死鎖。所以，在HLA的保守時間推進算法中，采取了查詢前瞻量和計算最大可用邏輯時間相結合的方法，有效地避免了這一缺陷。

參考文獻：

[1] Richard Fujimoto.Parallel Discrete Event Simulation [J].Communications of the ACM，1990，33(10).

[2] 歐陽伶俐.并行離散事件仿真算法及其在HLA時間管理中的應用[D].北京:航天二院，1999.

[3] 歐陽伶俐，宋星，卿杜政，等.HLA時間管理與PDES仿真算法研究[J].系統仿真學報，2000，12(3)：237-240.

[4] 蔡吉淼，汪厚祥.保守PDES中時間管理問題研究[J].計算機工程與設計，2007，28（14）：3536-3538.