2.2 離散系統事件仿真算法

仿真算法是確定仿真時鐘推進策略的控制方法，是仿真控制的核心。目前為止，最常用的仿真算法有事件調度法（Event Scheduling）、活動掃描法（Activity Scanning）和進程交互法（Process Interaction）。

2.2.1 事件調度法

事件調度法由蘭德公司在1963年提出，在美國廣泛采用，歐洲不很流行。

事件調度法的基本思想是：將事件例程作為仿真模型的基本模型單元，按照事件發生的先后順序不斷執行相應的事件例程。每一個有確定發生時間的事件，都有一個事件例程，用事件例程來處理事件發生后對實體狀態所產生的影響，并安排后續事件。

這種方法有一個時間控制程序，從事件表中選擇具有最早發生時間的事件，并將仿真時鐘修改到該事件發生的時刻，再調用與該事件相應的程序模塊，對事件進行處理，該事件處理完畢后，返回時間控制程序。這樣，事件的選擇與處理不斷地交替進行，直到仿真終止的程序事件發生為止。在這種方法中，任何條件的測試，均在相應的事件模塊中進行，這顯然是一種面向事件的仿真方法。

事件調度法用事件的觀點分析真實系統，通過定義事件及每個事件的發生，引起系統狀態的變化，按時間順序，在每個事件發生時，確定并執行有關的邏輯關系。

1.事件調度法的基本步驟

1）初始化：給出當前仿真時鐘、系統狀態量及統計量的初始值。

2）掃描事件表，將當前仿真時鐘增加到下一個最早發生事件的時間上。

3）處理該事件，相應地改變系統狀態。

4）收集統計數據。

5）若仿真時間未結束，則返回步驟2）；否則，執行下一步。

6）分析收集的統計數據，產生報告。

2.事件調度法的參數

1）成分集合：定義為C={α₁.α₂，…，α_n}

主動成分：C_A={α₁，α₂，…，α_m}

被動成分：C_P={α_m+1，α_m+2，…，α_n}

2）描述變量：描述每一主動成分α∈C_A的變量，α的狀態s_α，值域S_α。s_α下一變化時刻的時間變量t_α。

3）描述每一被動成分α∈C_P的變量，α的狀態s_α，值域S_α（被動成分的狀態變化只有在主動成分作用下才能發生，其發生時間由主動成分來確定，因而不需要時間變量）。

4）描述所有成分的屬性的變量：參數集合P={p₁，p₂，…，p_r}；成分間的相互關系，每個主動成分α∈C_A的影響受主動α作用下其狀態變化的描述，稱為事件處理流程；各成分處理的優先級，即同時發生時的處理順序（解結規則）。注意，在事件調度法中，一般主動成分也同時具有被動成分屬性，以便接受其他主動成分的作用。

3.事件調度算法

1）執行初始化操作，包括置初始時間t=t₀，結束時間t∞=t_e；事件表初始化，置系統初始事件；成分狀態初始化：

2）操作事件表，包括：

●取出具有事件記錄，

●修改事件表。

3）推進仿真時鐘。

TIME=t(s)

while(TIME<=t_∞)則執行

case 根據事件類型i

i=1執行第1類事件處理程序*

（*第i類事件處理程序對成分的狀態變化進行建模，而且要進行統計計算）

i=2執行第2類事件處理程序

…

i=m執行第m類事件處理程序

endcase

取出具有t(s)=min{t_α |α∈C_A}事件記錄**

（**若具有t(s)=min{t_α |α∈C_A}事件記錄有若干個，則按解結規則處理）

重置仿真時間 TIME=t(s)

endwhile***

（***該算法中未包括仿真結束后對結果的分析等內容）

4.事件表處理

復雜系統運行中的事件表規模巨大，如果采用傳統的處理方式，每處理完一個事件要將事件表中的所有項向上平移一行，這樣的處理顯然需要占用時間，為了提高處理效率，采用鏈表法是可取的。

2.2.2 活動掃描法

活動掃描法的基本思想是：用活動的觀點建模。系統由成分組成，而成分包含著活動，這些活動的發生必須滿足某些條件，每一個主動成分均有一個相應的活動子例程，仿真過程中，活動的發生時間也作為條件之一，而且是較之其他條件具有更高的優先權。顯然，活動掃描法由于包括了對事件發生時間的掃描，因而它也具有事件調度法的功能。

1.活動掃描法的設置

1）設置系統仿真鐘TIME（即控制系統仿真時間）與成分仿真鐘t_α。系統仿真鐘表示系統的仿真進程的推進時間，而成分仿真鐘則記錄該成分的活動發生時刻，兩者的關系可能有三種情況。

①t_α>TIME：表示該活動在將來某一時刻可能發生。

②t_α=TIME：表示該活動如果條件滿足則應立即發生。

③t_α<TIME：表示該活動按預定時間早應發生，但因條件未滿足，到目前為止實際上仍未發生，當前是否發生，則只需判斷其發生的條件。

2）設置條件處理模塊——成分活動開始與結束其他的條件是否滿足。

3）設置成分活動子程序——處理活動開始與結束時系統的狀態變化。

2.活動掃描法的步驟

1）掃描所有活動。

2）t_α≤TIME的成分進行條件檢驗，看其活動開始與結束的條件是否滿足，滿足則是可激活成分。

3）對所有激活的成分，處理其相應的活動子程序，即修改系統的有關狀態，并修改成分仿真時鐘。

4）推進系統仿真時鐘TIME。

5）繼續步驟1）～4），直至仿真結束。

2.2.3 進程交互法

進程交互法采用進程（Process）描述系統，它將模型中的主動成分所發生的事件及活動按時間順序進行組合，從而形成進程表，一個成分一旦進入進程，只要條件滿足，它將完成該進程的全部活動。

系統仿真鐘的控制程序采用兩張事件表：其一是當前事件表（Current Events List，CEL），它包含了從當前時間點開始有資格執行事件的事件記錄，但是該事件是否發生的條件（如果有的話）尚未判斷；其二是將來事件表（Future Events List，FEL），它包含在將來某個仿真時刻發生事件的事件記錄。每一個事件記錄中包括該事件的若干屬性，其中必有一個屬性，說明該事件在進程中所處位置的指針。

這種方法綜合了事件調度法和活動掃描法的特點，采用兩張事件表。它首先按一定的分布產生到達實體并置于FEL中，實體進入排隊等待；然后對CEL進行活動掃描，判斷各種條件是否滿足；再將滿足條件的活動進行處理，仿真時鐘推進到服務結束并將相應的實體從系統中清除；最后將FEL中最早發生的當前事件的實體移到CEL中，繼續推進仿真時鐘，對CEL進行活動掃描，直到仿真結束。

1.進程交互法的設置

1）設置一張當前事件表CEL，它包含了從當前時間點開始有資格執行事件的事件記錄，但是該事件是否發生的條件尚需要判斷。

2）設置一張將來事件表FEL，它包含了將來某個仿真時刻發生事件的事件記錄。

3）設置系統仿真時鐘TIME和成分仿真時鐘t_α。

2.進程交互法的步驟

1）推進系統仿真時鐘TIME。

2）把滿足t_α≤TIME的所有事件從FEL表移至CEL表中。

3）取出CEL中的每一個事件，判斷其所屬的進程及在進程中的位置。

4）判斷該事件發生的條件是否滿足。

5）如果條件允許該進程盡可能連續推進，直到進程結束，該成分離開系統。

6）該進程推進過程中，遇到條件不滿足時，記錄下進程的位置，并退出該進程。

7）重復步驟3）～6），CEL中的事件處理完畢。

8）重復步驟1）～7），直到仿真結束。

2.2.4 三種仿真策略的比較

1.系統描述

所有策略均提供主動成分及被動成分，每種成分均能接受其他成分的作用。在事件調度法中，只有主動成分才能施加作用，而在其他兩種策略中，主動成分與被動成分均可施加作用。

在事件調度法中，系統的動態特性表現為主動成分不斷產生事件，而在活動掃描法中則表現為主動成分產生活動；在進程交互法中則是通過成分在其進程中一步一步地推進來描述。

2.建模要點

在事件調度法中，用戶要對所定義的全部事件進行建模，條件的測試只能在事件處理子例程中進行。

活動掃描法設置了一個條件子例程專用于條件測試，還設置一個活動掃描模塊，該模塊對所有定義的活動進行建模。

進程交互法則將一個進程分成若干步，每一步包括條件測試及執行活動兩部分。

3.仿真時鐘的推進

在事件調度法中，主動成分的下一事件發生時間保存在事件表中，定時模塊不斷地從事件表中取出具有最早發生事件的事件記錄，并將仿真時鐘推進到該事件發生時間，并轉向該事件處理子例程執行。

活動掃描法除了設置了系統仿真時鐘之外，每一個主動成分還沒有成分仿真時鐘。定時模塊選擇那些大于當前系統仿真時鐘的值且是所有成分仿真時鐘最小的那個成分仿真時鐘，然后將系統仿真時鐘推進到該時刻，并開始對活動掃描。

進程交互法采用將來事件表及當前事件表。當前事件表中的進程掃描完后，從將來事件表中取出具有最早發生事件的事件記錄置于當前事件表中，將仿真時鐘推進到該事件發生時間。一旦某個進程被執行，則要求盡可能多地走下去，但并不改變系統仿真時鐘；如果該進程并未完成，則將其斷點記錄下來，即將中斷時間及事件類型放到將來事件表中，如果當前事件表中有一項或幾項的發生時間小于當前系統仿真時鐘的值，則說明在以前的掃描中，發生該事件的條件未得到滿足，本次應再次進行掃描。

4.評述

事件調度法：建模靈活，可應用范圍廣泛，但一般要求用戶用通用的高級語言編寫事件處理子例程，建模工作量大。

活動掃描法：對于各成分相關性很強的系統來說模型執行效率高。但是，建模時，除了要對各成分的活動進行建模外，仿真執行程序結構比較復雜，其流程控制要十分小心。

進程交互法：建模最為直觀，其模型表示接近實際系統，特別適用于活動可以預測、順序比較確定的系統，但是其流程控制復雜，建模靈活性不如事件調度法。

2.2.5 時間推進算法

時間推進算法是指隨著仿真的進程將仿真時間從一個時刻推進到另一個時刻的機制。對某一系統進行仿真時所采用的時間推進算法的種類以及仿真時間單位所代表的實際時間量的長短，不僅直接影響到計算機仿真的效率，甚至影響到仿真結果的有效性。

1.仿真驅動方式

仿真的驅動方式主要分為以下兩種。

（1）時間驅動方式

仿真過程是由時間驅動而不是由事件驅動的。當仿真運行時，系統不考慮一個實體的輸入信息是否發生變化，而是以仿真時間間隔為基本驅動信息，依次遍歷各實體。雖然這種方式非常簡單，容易實現，但執行效率比較低。因為不論一個實體是否需要運行，它在每一仿真時刻都要被訪問掃描到，這對于存在許多低運行頻率實體的仿真系統而言，資源的浪費是極其可觀的。

（2）事件驅動方式

該算法首先保證仿真系統不是在每一仿真時刻都將內部的實體掃描一遍，而是由事件作為驅動信息來運行實體。事件驅動算法在仿真系統中定義一個全局時鐘變量，每次實體運行后修改全局時鐘，同時確定下一事件對實體的觸發時刻，很顯然這種方式的仿真時間推進效率相對于時間驅動方式要高很多。

2.時間推進算法分類

（1）保守時間推進算法

它最大的特征是嚴格禁止在仿真過程中發生因果關系錯誤，保證各類事件是按時間的先后順序處理執行。保守算法的主要任務是確定何時能安全地執行某一事件，它常常依賴于仿真模型的行為信息，如模型內子模塊之間通信的拓撲結構，或模型的超前性等來確定哪個事件是“安全”的，能被安全地處理。

（2）樂觀時間推進算法

所謂樂觀時間推進算法是指依賴于退回機制來消除由于接收到落后的信息而對事件產生錯誤處理的一種方法，它更為積極地允許節點更加樂觀地處理事件。它的目標是最大程度地發掘仿真系統的并行性，提高系統的運行效率。這種算法具有風險性，如果發生因果關系錯誤就要求回退到發生錯誤之前的時刻重新開始執行，因此需要大量的系統資源來保存仿真過程中的狀態和數據。

（3）受約束的樂觀時間推進算法

樂觀方法曾一度廣泛地被認為是一種能夠始終獲得高效率的方法，但是實踐證明對樂觀性缺乏理智的控制往往會導致極差的性能，所以有必要對樂觀的方法進行一定的限制。依據不同的約束控制標準又可以分為基于窗口的策略、基于懲罰的策略、基于知識的策略、基于概率的策略等。

（4）混合時間推進算法

該算法是保守時間推進算法與樂觀時間推進算法的混合，將兩者結合起來，取長補短，則有可能獲得更好的性能，由此人們提出了混合時間推進算法。通過比較研究，保守算法和樂觀算法的優缺點恰恰具有一定的互補性：保守算法的仿真并行性利用不高，運行效率較低，但不會發生因果關系錯誤；相比之下樂觀算法則較容易發生因果錯誤，從而增加仿真運行的復雜性，但能有效地利用仿真系統現有的資源，最大限度地發掘潛在的并行性。

（5）自適應時間推進算法

該算法可以看作是一種動態調整的混合時間推進算法，但它的基本思想是隨著仿真狀態的變化而動態地選擇或修改其執行方式。主要是通過動態地改變一個或多個變量，從而使系統在保守與樂觀之間適當調整。自適應時間推進算法在保守與樂觀之間架起了一座橋梁，并且可以根據需要使自適應時間推進算法逼近任何一種策略。很顯然，這種算法在混合時間推進算法基礎上又進了一步。