ＰＲＡＭ：基于Ｍａｒｋｏｖ模型的高效日歷隊列算法

摘 要：基于有限生滅過程建立了日歷隊列的數(shù)學(xué)模型，提出了一種基于馬爾可夫鏈的動態(tài)預(yù)測算法(predict resize algorithm based on Markov，PRAM)，彌補(bǔ)了上述方法的不足。給出了算法的相關(guān)數(shù)學(xué)分析，并將其實現(xiàn)在J2EE應(yīng)用服務(wù)器OnceAS中。系統(tǒng)實驗表明，當(dāng)事件到達(dá)高度密集或到達(dá)分布變化劇烈時，該算法可以解決日歷隊列的性能不穩(wěn)定問題，使其仍保持出入隊時間復(fù)雜度O(1)的特性，并且性能更優(yōu)。

關(guān)鍵詞：日歷隊列；馬爾可夫；放縮算法；應(yīng)用服務(wù)器中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2008)09-2625-06

PRAM：efficient calendar queue algorithm based on Markov model

ZHANG Lei1a，2，LI Yang1a，1b，ZHANG Wenbo1a，DENG Liujun1a，2

(1.a.Technology Center of Software Engineering，b.Key Laboratory of Computer Science， Institute of Software， Chinese Academy of Sciences， Beijing 100080， China；2.Graduate School， Chinese Academy of Sciences， Beijing 100039， China)Abstract:This paper presented a new approach called PRAM，which determined the optimum operating parameter of calendar queue by predicting the future events set based on Markov chain.It implemented the PRAM prototype in the J2EE application server——OnceAS. The experiment results show that PRAM offer consistent O(1) time complexity over uneven event distributions and achieve better performance than the other approaches.

Key words:calendar queue；Markov；resize algorithm；application server

0 引言

離散事件模擬目前被廣泛應(yīng)用于各種研究領(lǐng)域以模擬一個復(fù)雜系統(tǒng)的行為。在離散事件模擬的場景中，一個系統(tǒng)被劃分成若干個邏輯組件，各個組件通過生成帶有執(zhí)行時間戳的消息事件來進(jìn)行交互。所有還沒有得到處理的消息事件就構(gòu)成了等待事件集合（pending event set，PES）。一個PES可以被表示為一個優(yōu)先級隊列，在該隊列中，擁有最小時間戳的消息事件有著最高的執(zhí)行優(yōu)先級。通常情況下，離散事件模擬系統(tǒng)的性能主要取決于消息事件出入隊的時間復(fù)雜度，但是Comfort^[1]在研究中發(fā)現(xiàn)，當(dāng)?shù)却录虾艽髸r，模擬系統(tǒng)40%左右的時間會耗費在對消息事件的調(diào)度上。

日歷隊列^[2]是一種基于鏈表數(shù)組的數(shù)據(jù)結(jié)構(gòu)，它提供了對PES大小不敏感的時間復(fù)雜度為O（1）的出入隊操作。為了保持出入隊時間復(fù)雜度為O(1)的特性，日歷隊列在運(yùn)行過程中必須保持鏈表數(shù)組中等待事件分布的均勻性，并確保任一鏈表中等待事件的數(shù)目要約束在一定范圍內(nèi)。因此，在離散事件模擬系統(tǒng)的運(yùn)行過程中，隨著等待事件的增長和減少，日歷隊列的大小也會相應(yīng)地進(jìn)行放縮調(diào)整。但是，日歷隊列的每一次放縮都會觸發(fā)日歷隊列的重建，這種重建對于日歷隊列而言代價是高昂的。如果等待事件平穩(wěn)到達(dá)，則其對日歷隊列的放縮產(chǎn)生的影響比較小。然而，當(dāng)?shù)却录竭_(dá)高度聚集或到達(dá)分布變化劇烈時，日歷隊列的靜態(tài)放縮算法無法響應(yīng)這種動態(tài)變化，將會頻繁地進(jìn)行放縮而極大影響其性能。針對這個問題，目前已有的研究主要通過對日歷隊列進(jìn)行局部采樣來檢測等待事件的聚集到達(dá)，然后根據(jù)檢測結(jié)果給出優(yōu)化的放縮參數(shù)，以期從整體上可以減少放縮次數(shù)，如DCQ（dynamic calendar queue）^[3]、SNOOPy CQ（statistically enhanced with optimum operating parameter calendar queue）^[4]等。但是，受限于采樣技術(shù)的范圍和頻率，以上研究在實際應(yīng)用中效果并不理想。

Markov過程作為一個典型的隨機(jī)過程被廣泛用于排隊系統(tǒng)的性能評價和控制過程。本文提出了一種基于Markov過程預(yù)測的日歷隊列放縮算法(PRAM)。該算法將日歷隊列的運(yùn)行建模為一個Markov過程，通過對其動態(tài)結(jié)構(gòu)進(jìn)行分析，給出了基于等待事件到達(dá)分布的動態(tài)優(yōu)化算法，用于解決當(dāng)任務(wù)事件到達(dá)分布發(fā)生劇烈變化時日歷隊列的性能問題。隨后，本文通過數(shù)學(xué)工具給出了相關(guān)證明及分析。

本文最后在J2EE應(yīng)用服務(wù)器OnceAS^[5]中實現(xiàn)了PRAM的原型，并通過TPC組織的TPCW標(biāo)準(zhǔn)^[6]對PRAM CQ、DCQ、SNOOPy CQ進(jìn)行了比較和分析。實驗證明，PRAM算法可以更好地適應(yīng)事件的聚集到達(dá)，且日歷隊列始終保持出入隊時間復(fù)雜度為O(1)的特性。

1 研究背景及相關(guān)工作

日歷隊列的名字起源于現(xiàn)實生活中的臺歷，人們在臺歷上面記錄下自己的任務(wù)計劃，每天只要查看臺歷就可以知道一天的工作安排。圖1給出了一個日歷隊列的典型實現(xiàn)。定義一個桶（bucket）的時間段為δ，桶的容量θ為一個桶中包含的等待事件的數(shù)目，一年的時間周期M就是桶的數(shù)目，而年的時間段就是所有桶的時間段之和。圖1中，桶的時間段為10，年的時間周期為10，所以年的時間段就為10×10＝100。一個桶就如同日歷中的一天，可以包含同一天但是卻不同年的等待事件；而且在一個桶中，等待事件的位置是依照其時間戳大小遞增排序的。將當(dāng)前處理的桶定義為當(dāng)前桶i0，當(dāng)前時間為當(dāng)前桶日歷隊列的運(yùn)行原理如下：當(dāng)有一個新的事件到達(dá)時，首先按式（1）得到這個時間應(yīng)該被放置的天數(shù)，即哪一個桶；然后通過比較新事件與該桶中已有的等待事件的時間戳來決定新事件的插入位置。當(dāng)要出隊一個等待事件時，日歷隊列從上一個出隊事件的位置開始尋找當(dāng)前年中時間戳最小的等待事件，如果該桶中找不到時間戳屬于當(dāng)前年的等待事件，日歷隊列會跳到下一個桶進(jìn)行搜索，直到找到時間戳屬于當(dāng)前年的等待事件；如果直到尋找完最后一個桶都找不到，那么日歷隊列將會重新從第一個桶開始尋找屬于下一年的時間戳最小的等待事件。

日歷隊列的性能與其結(jié)構(gòu)緊密相關(guān)。R. Brown^[2]提出當(dāng)日歷隊列中等待事件均勻分布于各個桶且桶的容量平均為3、4時，日歷隊列的性能最優(yōu)。然而在現(xiàn)實場景中，日歷隊列中的等待事件不可能是均勻分布在各個桶中的，所以，日歷隊列中PES的數(shù)目與桶的數(shù)目比值過小或過大都會給日歷隊列的正常運(yùn)行帶來相當(dāng)大的性能影響^[2]。針對這種情況，解決的方法是讓日歷隊列的桶的數(shù)目隨著到達(dá)PES的增長或減少而相應(yīng)地增長或減少。傳統(tǒng)的日歷隊列的解決方法非常簡單，設(shè)日歷隊列中桶的數(shù)目為NB，隊列中等待事件的數(shù)目為NE，則日歷隊列的放縮規(guī)則如下：

if NE＞2NBNB=2NB

if NE＜NB/2NB=NB/2

當(dāng)NB被增大或縮小后，桶的時間段會被重新計算，然后日歷隊列會進(jìn)行一次重建，使得任務(wù)能夠均勻地在日歷隊列中分布，以保持其O(1)性質(zhì)。這個重建操作開銷巨大，因為必須對日歷隊列中的每一個元素重新定位并插入，所以應(yīng)該盡量避免出現(xiàn)不必要的重建。但是，如果等待事件到達(dá)分布波動很頻繁的話，就有可能使得日歷隊列的增長和縮小非常頻繁，這時大量重建會嚴(yán)重影響日歷隊列的性能。尤其是當(dāng)PES的數(shù)量在重建條件附近變化時，日歷隊列的開銷將集中在開銷巨大的重建上。

目前已有的研究主要集中于通過調(diào)整日歷隊列中桶的時間段來減少放縮次數(shù)，Oh 和 Ahn^[3]提出了DCQ算法，通過對日歷隊列進(jìn)行局部采樣來檢測等待事件的聚集到達(dá)；當(dāng)檢測到等待事件聚集到達(dá)時，DCQ計算出一個放縮參數(shù)，用于優(yōu)化桶的時間段，然后對整個日歷隊列進(jìn)行重建。Tan和Thng^[4]在DCQ的基礎(chǔ)上提出了SNOOPy算法，對日歷隊列的靜態(tài)結(jié)構(gòu)進(jìn)行了研究，同時優(yōu)化了DCQ的檢測機(jī)制，通過對采樣的分析給出了一個優(yōu)化的日歷隊列重建結(jié)構(gòu)參數(shù)，以使得重建后的日歷隊列能夠保持任務(wù)在鏈表數(shù)組中分布的均勻性。這些研究工作都集中于通過優(yōu)化對日歷隊列的局部采樣和分析日歷隊列的靜態(tài)結(jié)構(gòu)特性獲得隊列重建的優(yōu)化參數(shù)。它們的缺陷在于：a）采樣技術(shù)的精確度過于依賴采樣的范圍、頻率，并不能真正反映事件的分布狀態(tài)；b）僅僅通過分析日歷隊列的結(jié)構(gòu)來獲得調(diào)整參數(shù)而忽略了實際應(yīng)用場景下任務(wù)到達(dá)的動態(tài)變化。事實上，如果對日歷隊列的放縮不具備動態(tài)控制，那么這些靜態(tài)參數(shù)可能無法達(dá)到期望效果。

針對以往研究的缺陷，本文通過研究等待事件的到達(dá)率和服務(wù)率來描述等待事件的到達(dá)分布，并提出了PRAM算法。該算法將日歷隊列的運(yùn)行過程動態(tài)建模為一個M/M/1/N的排隊系統(tǒng)，用Markov鏈對日歷隊列動態(tài)特征進(jìn)行刻畫，給出了基于動態(tài)預(yù)測的放縮規(guī)則及放縮參數(shù)。實驗結(jié)果證明，PRAM算法有效地減少了日歷隊列的放縮次數(shù)，提高了日歷隊列的性能，并能夠更好地適應(yīng)等待事件的聚集到達(dá)，保持等待事件出入隊時間復(fù)雜度為O(1)的特性。

2 PRAM算法

如前所述，傳統(tǒng)的日歷隊列實現(xiàn)沒有給出解決其在等待時間到達(dá)波動頻繁變化下結(jié)構(gòu)不穩(wěn)定的方法，并且目前的研究主要集中在通過對日歷隊列進(jìn)行采樣來調(diào)整其整體結(jié)構(gòu)，具有很大的局限性。本節(jié)針對以上問題提出了PRAM算法，利用Markov鏈對系統(tǒng)進(jìn)行建模，以獲得對于等待事件到達(dá)分布的預(yù)測值，并將預(yù)測值用于放縮算法。

2.1 系統(tǒng)建模

假設(shè)日歷隊列中有N個任務(wù)，為便于分析，假設(shè)桶的數(shù)目為無限，在下一節(jié)會給出桶的數(shù)目有限時的相關(guān)修正及證明。桶的時間段為δ，那么可以將該日歷隊列建模為一個2.2 由無限狀態(tài)系統(tǒng)到有限狀態(tài)系統(tǒng)的完備性修正

受限于計算機(jī)資源的有限性，桶的數(shù)目M在現(xiàn)實中不可能為無限。為了將上一節(jié)的結(jié)論應(yīng)用于現(xiàn)實系統(tǒng)，在此對其進(jìn)行了修正，以使該結(jié)論可以用于桶的數(shù)目M有限的現(xiàn)實系統(tǒng)。本節(jié)最后給出了將基于M無限的理想系統(tǒng)的放縮規(guī)則式（5）用于M有限系統(tǒng)時的修正規(guī)則及其證明。

Erickson等人^[8]提出了如下定理：

定理1 定義β為分布函數(shù)f的跳轉(zhuǎn)臨界點，有f(x)=0 for x＞β。如果f存在β，那么存在邊界值M*=β/δ+1。當(dāng)M≥M*時，有限狀態(tài)系統(tǒng)性能模型等價于無限狀態(tài)系統(tǒng)。

定理1給出了M有限系統(tǒng)與M無限系統(tǒng)性能等價的條件及計算方法。但是在實際計算機(jī)系統(tǒng)中，可能存在以下情況：a)f不存在β；b)f存在β，但是β/δ的值太大以至于失去實際的使用價值。對于這些情況，M*是無法給出的，定理1也不能提供解決的辦法。所以，當(dāng)M有限系統(tǒng)與M無限系統(tǒng)性能不等價時，必須給出一個可量化的性能差異的衡量標(biāo)準(zhǔn)。

首先給出以下定義：

一個任務(wù)e的時間t(e)-t0∈Φ，意味著該任務(wù)屬于當(dāng)前年，會被執(zhí)行，如圖1中時間戳為31的任務(wù)；若t(e)-t0∈Ω，即意味著該任務(wù)屬于當(dāng)前桶，卻不屬于當(dāng)前年，不會被執(zhí)行，如圖1中的時間戳為138的任務(wù)。

Erickson等人給出了LM(δ)的計算公式及下界，如式(6）所示： 

根據(jù)以上結(jié)論可以得到主要理論如下：

命題1 對于一個桶數(shù)目為M的日歷隊列，設(shè)

b為遍歷一個空bucket的時間；

c為遍歷一個非空bucket，找到下一個待處理任務(wù)的時間；

d為隊列處理時間，包括一個任務(wù)的出隊和一個新任務(wù)的入隊時間之和；

EM()為在M有限系統(tǒng)時，任務(wù)處理時間的數(shù)學(xué)期望；

至此，放縮規(guī)則（式（5））可通過參數(shù)η進(jìn)行修正，以適應(yīng)M有限系統(tǒng)。放縮規(guī)則具體修正如下所示：

PRAM算法基于式（14），以下為算法細(xì)節(jié)實現(xiàn)：

enqueue(){

Enqueue new event to the appropriate bucket;

NE++;

update;

if(NE＞3NB){//CQ trigger for a growing PES

Calculate variable L by formula (3)

NB=L/3+0.01L;

δ:=use sampling method;

//just as conventional CQimplementation

calendar_Resize(NB，δ);}

return;}

dequeue(){

Dequeue event from the head of the appropriate bucket;

NE;

update;

if (NE＜NB/3){//CQ trigger for a growing PES

calculate variable L by formula (3)

NB=L/3+0.01L

δ:=use sampling method;

//just as conventional CQimplementation

calendar_Resize(NB，δ);}

return;}

Calendar_Resize()重建函數(shù)只是在滿足式（14）中的條件時才會被觸發(fā)，此時enqueue()和dequeue()的時間復(fù)雜度為O(n)。如果放縮規(guī)則（式（14））中的條件沒有被觸發(fā)，那么enqueue()和dequeue()的時間復(fù)雜度僅為O(1)。由于calendar_Resize()函數(shù)的時間復(fù)雜度相對較高，PRAM算法的時間復(fù)雜度完全取決于calendar_Resize()函數(shù)被調(diào)用的次數(shù)。傳統(tǒng)的日歷隊列算法如DCQ、SNOOPy CQ正是由于在等待事件到達(dá)高度聚集的情況下calendar_Resize()函數(shù)被調(diào)用的次數(shù)過多，才導(dǎo)致了它們無法保持出入隊時間復(fù)雜度O(1)的特性。PRAM算法由于基于動態(tài)模型對系統(tǒng)特征進(jìn)行刻畫，有效地避免了不必要的放縮對于整體算法性能的不利影響，保持了出入隊時間復(fù)雜度O(1)的特性。

3 算法應(yīng)用

PRAM算法已經(jīng)在中國科學(xué)院軟件研究所的J2EE應(yīng)用服務(wù)器OnceAS^[5]的WorkManager^[9]組件中進(jìn)行了原型實現(xiàn)。本節(jié)通過與DCQ、SNOOPy CQ比較來驗證PRAM算法的有效性。

3.1 實驗系統(tǒng)原型

WorkManager是JSR237^[10]正式標(biāo)準(zhǔn)，它提出了一種介于應(yīng)用服務(wù)器與系統(tǒng)資源之間的中間層，其目的在于對線程的創(chuàng)建、分配、調(diào)度乃至銷毀提供一個統(tǒng)一的框架。

如圖3所示，本文引入了日歷隊列作為WorkManager的調(diào)度框架。在應(yīng)用服務(wù)器中所有任務(wù)均通過WorkManager執(zhí)行，無論是Web容器、EJB容器還是系統(tǒng)內(nèi)部事務(wù)。但是在日歷隊列中，對于任務(wù)的區(qū)分僅僅是通過任務(wù)的時間戳，顯然這不能滿足應(yīng)用服務(wù)器對于任務(wù)差分的要求。因為應(yīng)用服務(wù)器處理的任務(wù)存在一定的優(yōu)先級順序，可能先到的任務(wù)由于優(yōu)先級低反而較后得到響應(yīng)。為了解決這個問題，本文使用了虛擬時間戳（virtual timestamp）的概念，通過為每一個到達(dá)的任務(wù)生成一個虛擬時間戳，將任務(wù)的優(yōu)先級順序映射到虛擬時間戳中以保證任務(wù)的優(yōu)先級順序。

虛時間戳=實際時間戳+時間增量

時間增量=任務(wù)類型/任務(wù)優(yōu)先級×100

一個任務(wù)進(jìn)入WorkManager后，它進(jìn)入調(diào)度隊列——日歷隊列的時間戳并不是它實際到達(dá)的時間戳，而是由WorkManager處理的虛時間戳。任務(wù)的優(yōu)先級與時間增量成反比，即任務(wù)優(yōu)先級越高，其時間增量越小，這個性質(zhì)映射到日歷隊列中后，時間戳越小的任務(wù)執(zhí)行得越早。 

關(guān)于時間增量的生成，由任務(wù)的類型和優(yōu)先級兩個參數(shù)決定，任務(wù)類型包括Web任務(wù)、EJB任務(wù)和其他任務(wù)。任務(wù)類型相同且優(yōu)先級相同的任務(wù)的時間增量相同。

圖3所示的系統(tǒng)流程如下：

a）應(yīng)用服務(wù)器接收外部任務(wù)及應(yīng)用服務(wù)器自己產(chǎn)生的任務(wù)；

b）應(yīng)用服務(wù)器將任務(wù)轉(zhuǎn)發(fā)到WorkManager中，WorkManager接收到任務(wù)后，首先用服務(wù)差分器對任務(wù)進(jìn)行處理，產(chǎn)生虛擬時間戳以實現(xiàn)服務(wù)差分；

c）任務(wù)以虛擬時間戳在日歷隊列中入隊；

d)任務(wù)從日歷隊列中出隊到執(zhí)行器中開始執(zhí)行；

e)將任務(wù)處理結(jié)果返回給用戶。

3.2 實驗環(huán)境

實驗環(huán)境由一臺PC機(jī)、兩臺服務(wù)器構(gòu)成。PC機(jī)模擬客戶端；兩臺服務(wù)器上分別運(yùn)行應(yīng)用服務(wù)器OnceAS和數(shù)據(jù)庫DB2。PC機(jī)配置為Pentium D CPU 3.4 GHz，2 GB內(nèi)存，軟件環(huán)境為Windows Vista Ultimate。兩臺服務(wù)器的配置為XeonTM MP CPU 3.5 GHz，4 GB內(nèi)存，軟件環(huán)境為Windows 2000 Professional Service。機(jī)器之間通過百兆以太網(wǎng)連接。

對于部署在應(yīng)用服務(wù)器OnceAS上的WorkManager，本文實現(xiàn)了三個算法版本，分別基于DCQ、SNOOPy CQ、PRAM CQ。以下測試也基于這三個版本。采用事務(wù)流程性能委員會（Transaction Processing Performance Council，TPC）組織公布的TPCW基準(zhǔn)^[6]作為部署在OnceAS中的應(yīng)用。該基準(zhǔn)基于Markov過程，用戶請求的到達(dá)是基于指數(shù)分布的^[11]，其跳轉(zhuǎn)行為如圖4所示。

TPC僅僅提供了TPCW的設(shè)計規(guī)范，實驗中采用由WisconsinMadison大學(xué)PHARM（Predictive HighPerformance Architecture Research Mavens）小組開發(fā)的開源的基于Java的TPCW系統(tǒng)實現(xiàn)^[12]。

4 實驗結(jié)果

4.1 TPCW的到達(dá)分布

實驗首先模擬了300個用戶按照圖4的訪問模式對部署在OnceAS上的TPCW應(yīng)用持續(xù)訪問10 min，以收集任務(wù)的到達(dá)分布。

實驗結(jié)果如圖5所示，坐標(biāo)橫軸為時間（s），坐標(biāo)縱軸為normalized WIPS（normalized Web interactions per second，可以理解為每秒到達(dá)任務(wù)數(shù)）。圖5中的點代表了任務(wù)的聚集程度，點越密集，表示任務(wù)到達(dá)越密集；虛線為WIPS的均值，在本圖中WIPS的均值為98.6；實線表示了TPCW任務(wù)到達(dá)的一個周期，實驗設(shè)置為360 s。

在客戶數(shù)為300的環(huán)境下，TPCW的任務(wù)到達(dá)分布高密度聚集且波幅比較大，即已經(jīng)頻繁發(fā)生事件密集到達(dá)。以下的實驗都基于客戶數(shù)為300的TPCW測試環(huán)境。

4.2 日歷隊列的性能比較

在實驗中使用TPCW對基于DCQ、SNOOPy CQ和PRAM CQ三個版本的OnceAS進(jìn)行測試。筆者關(guān)注的參數(shù)有兩個：a)放縮次數(shù)，即在運(yùn)行過程中，日歷隊列進(jìn)行了多少次收縮；b)平均等待時間，即事件從進(jìn)入日歷隊列到離開日歷隊列的時間。前者越少越好，而后者越短越好。

圖6給出了DCQ、SNOOPy CQ、PRAM CQ在測試中放縮次數(shù)的比較。其中：橫軸表示日歷隊列所容納的等待事件數(shù)；縱軸表示日歷隊列在運(yùn)行過程中進(jìn)行的放縮次數(shù)。從圖6中可以看到，PRAM CQ受到事件到達(dá)分布的影響最少，其放縮次數(shù)始終在3～7次；SNOOPy CQ在運(yùn)行過程中對事件到達(dá)分布較敏感，其放縮次數(shù)在5～10次擺動；在三種算法中，DCQ對于事件到達(dá)分布最敏感，它在運(yùn)行過程中放縮次數(shù)在4～17擺動，且波幅最大。這種結(jié)果是由于DCQ的實現(xiàn)通過局部采樣來決定是否放縮，缺乏對于當(dāng)前運(yùn)行狀況的預(yù)測機(jī)制，當(dāng)事件到達(dá)的波動性增大時，基于DCQ的日歷隊列無法有效檢測到這種波動而頻繁地進(jìn)行放縮。SNOOPy雖然也同樣基于局部采樣，但是它在DCQ的基礎(chǔ)上對采樣算法進(jìn)行了優(yōu)化，并添加了對日歷隊列結(jié)構(gòu)的估測算法，所以放縮次數(shù)相對平穩(wěn)一些，但是也并不能完全適應(yīng)分布的變化。而基于PRAM的日歷隊列實現(xiàn)有著動態(tài)的預(yù)測機(jī)制，當(dāng)事件到達(dá)波動性增大時，PRAM會反饋出這種變化，并及時應(yīng)用到日歷隊列的放縮中去，所以基于PRAM的日歷隊列實現(xiàn)與傳統(tǒng)的日歷隊列實現(xiàn)相比有著更好的適應(yīng)性和穩(wěn)定性。如圖6所示，PRAM CQ的放縮次數(shù)與DCQ、SNOOPy CQ相比，分別減少了50％和30％，而且在整個運(yùn)行中變化更加平穩(wěn)。

為了進(jìn)一步說明問題，對基于DCQ、SNOOPy和PRAM的日歷隊列實現(xiàn)的平均等待時間進(jìn)行了統(tǒng)計比較。圖7中橫軸表示日歷隊列容納的等待事件數(shù)；縱軸代表事件在日歷隊列中的平均等待時間。在理想的日歷隊列模型中，日歷隊列中平均等待時間的時間復(fù)雜度應(yīng)該為O(1)且與隊列長度無關(guān)，但是從圖7中可以看到，DCQ和SNOOPy CQ基本上呈一個線性增長的趨勢。這是由于基于DCQ和SNOOPy CQ的日歷隊列的放縮次數(shù)比較頻繁，導(dǎo)致巨大的重建開銷而無法保持O(1)的特性；與之相比，基于PRAM的日歷隊列由于其在放縮次數(shù)上的穩(wěn)定性，避免了代價昂貴的放縮對性能的影響。在圖7中，PRAM CQ在事件到達(dá)迅速增長的過程中，平均等待時間始終處于平穩(wěn)狀態(tài)，保持了與隊列長度無關(guān)的出入隊時間復(fù)雜度O(1)的特性。

由圖6和7可以看到，無論是從放縮次數(shù)還是到達(dá)事件的平均等待時間上來看，PRAM CQ都優(yōu)于DCQ和SNOOPy CQ，在事件聚集到達(dá)且到達(dá)分布波動較大時，這種性能差異尤其明顯。

最后圖8和9分別給出了TPCW基準(zhǔn)在基于PRAM CQ、SNOOPy CQ和DCQ三種系統(tǒng)上的性能參數(shù)。圖8是TPCW基準(zhǔn)在PRAM CQ、SNOOPy CQ、DCQ三種實現(xiàn)上的系統(tǒng)吞吐量比較。TPCW具有三種模式，即browsing（95% read）、shopping（80% read）、ordering（50% read）。Browsing模式中95%的任務(wù)涉及數(shù)據(jù)庫的讀操作，涉及數(shù)據(jù)庫寫操作的僅有5%。TPCW從browsing模式改變到shopping模式和ordering模式時，數(shù)據(jù)庫寫操作分別占到15%和45%。從圖8可以看出，在這三種模式下，基于PRAM CQ的系統(tǒng)吞吐量始終優(yōu)于基于SNOOPy CQ和DCQ的系統(tǒng)。在browsing模式下，吞吐量差距比較明顯；而ordering模式下差距相對小一點。這是因為browsing模式下，數(shù)據(jù)庫寫操作很少，日歷隊列的調(diào)度時間在任務(wù)執(zhí)行時間中占的比例較高，所以日歷隊列性能的提高對整個系統(tǒng)性能的提高影響較大；而ordering模式下，數(shù)據(jù)庫寫操作較多，日歷隊列的調(diào)度時間在任務(wù)執(zhí)行時間中占的比例較低，所以日歷隊列性能的提高對整個系統(tǒng)的影響并不明顯。圖9是TPCW基準(zhǔn)在PRAM CQ、SNOOPy CQ、DCQ三種實現(xiàn)上的系統(tǒng)任務(wù)平均處理時間的比較。可以看出，基于PRAM CQ的系統(tǒng)任務(wù)平均處理時間要比基于SNOOPy CQ和DCQ的系統(tǒng)小得多。

從以上實驗結(jié)果可以看出，相對于DCQ和SNOOPy CQ，PRAM CQ是一種性能更加優(yōu)異的日歷隊列實現(xiàn)。

4.3 性能損失評價

本文通過完備性證明給出了將基于M無限系統(tǒng)的放縮規(guī)則用于M有限系統(tǒng)的修正規(guī)則，該規(guī)則構(gòu)成了PRAM算法的核心。以下將對該修正規(guī)則在實際應(yīng)用中的有效性進(jìn)行驗證。

在實際應(yīng)用中，將PRAM算法用于M有限系統(tǒng)帶來的性能損失必須是可以量化的。在實驗中，根據(jù)式（12）取定兩個邊界，當(dāng)系統(tǒng)性能損失η為5%和1%時，M/N的值分別為1.92和3.02；而在測試中，對日歷隊列中桶的數(shù)目與任務(wù)數(shù)目的比值進(jìn)行了計算并記錄。圖10橫軸表示日歷隊列中包含的任務(wù)數(shù)目；縱軸表示測試周期中平均的M/N值。從圖10中可以看到，在測試過程中M/N的值始終在1.92~3.02。這就意味著在整個測試過程中，基于PRAM的現(xiàn)實系統(tǒng)性能與基于PRAM的理想系統(tǒng)的性能差異η始終在1%~5%，換句話說，系統(tǒng)性能始終在理想模型的95%以上。

5 結(jié)束語

離散事件模擬的性能一方面由它所在的運(yùn)行支撐環(huán)境決定，另一方面由它所使用的數(shù)據(jù)結(jié)構(gòu)及調(diào)度算法決定；對于離散事件模擬的調(diào)度算法的研究是目前一個熱門的研究領(lǐng)域，本文的工作側(cè)重于研究在離散事件模擬中被廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)——日歷隊列的調(diào)度算法。

鑒于日歷隊列在事件到達(dá)聚集情況下的結(jié)構(gòu)不穩(wěn)定，本文提出了一種基于Markov過程的預(yù)測算法PRAM，通過添加動態(tài)預(yù)測機(jī)制，使得PRAM可以及時反饋出任務(wù)到達(dá)的變化，并將反饋應(yīng)用到日歷隊列的放縮中去。本文最后通過一個系統(tǒng)原型對算法進(jìn)行了驗證。實驗結(jié)果表明，與以往的日歷隊列算法DCQ、SNOOPy CQ相比，PRAM可以有效地解決日歷隊列結(jié)構(gòu)不穩(wěn)定的缺陷，保證了日歷隊列在實際應(yīng)用場景下仍然保持出入隊時間復(fù)雜度O(1)的特性。在同等條件下，與已有研究相比，PRAM CQ不僅可以有效減少日歷隊列的放縮次數(shù)，而且在運(yùn)行過程中平均等待時間減少了10%～20%。然而，本文在實現(xiàn)中沒有考慮桶的時間段變化給日歷隊列調(diào)度帶來的影響，這個問題將在以后的工作中加以解決。

參考文獻(xiàn)：

［1］COMFORT J C.The simulation of a masterslave event set processor[J].Simulation，1984，42(3):117124.

[2]BROWN R.Calendar queue:a fast O(1) priority queue implementation for the simulation event set problem[J].Communications of the ACM，1998，31(10):11201227.

[3]OH S，AHN J.Dynamic calendar queue[C]//Proc of the 32nd Annual Simulation Symposium.1999：20-25.

[4]TAN K L，THNG L.SNOOPy calendar queue[C]//Proc of the 32nd Conference on Winter Simulation.Piscataway:IEEE Press，2000:487-495.

[5]FAN Guochuang，LIN Shibiao，DONG Weichuan，et al.Web Frame:an extensible multilayer Web application server[J].Chinese Journal of Computers，2004，27(4):451-460.

[6]The Transaction Processing Council （TPC）.TPCW site[EB/OL].http://www.tpc.org/tpcw/. [7]KLEINROCK L.Queueing systems，volume1:theory[M].New York:WileyInterscience Publication，1975.

[8]ERICKSON K B，LADNER R E，LAMARCA A.Optimizing static calendar queues[J].ACM Trans on Modeling and Computer Simulation，2000，10(3):179-214.

[9]CommonJ specifications[EB/OL].http://dev2dev.bea.com/wlplatform/commonj/.

[10]JSR 237:work manager for application servers[EB/OL].http://jcp.org/en/jsr/detail?id=237.

[11]MENASCE D A.TPCW:a benchmark for ecommerce[J].IEEE Internet Computing，2002，6(3):83-87.

[12]PHARM[EB/OL].http://www.ece.wisc.edu/~pharm/