ＰＲＡＭ：基于Ｍａｒｋｏｖ模型的高效日歷隊列算法
2008-12-31 00:00:00張磊李洋張文博鄧柳軍
計算機應用研究 2008年9期
摘 要：基于有限生滅過程建立了日歷隊列的數學模型，提出了一種基于馬爾可夫鏈的動態預測算法(predict resize algorithm based on Markov，PRAM)，彌補了上述方法的不足。給出了算法的相關數學分析，并將其實現在J2EE應用服務器OnceAS中。系統實驗表明，當事件到達高度密集或到達分布變化劇烈時，該算法可以解決日歷隊列的性能不穩定問題，使其仍保持出入隊時間復雜度O(1)的特性，并且性能更優。
關鍵詞：日歷隊列；馬爾可夫；放縮算法；應用服務器中圖分類號：TP301.6 文獻標志碼：A
文章編號：1001-3695(2008)09-2625-06
PRAM：efficient calendar queue algorithm based on Markov model
ZHANG Lei1a，2，LI Yang1a，1b，ZHANG Wenbo1a，DENG Liujun1a，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 引言
離散事件模擬目前被廣泛應用于各種研究領域以模擬一個復雜系統的行為。在離散事件模擬的場景中，一個系統被劃分成若干個邏輯組件，各個組件通過生成帶有執行時間戳的消息事件來進行交互。所有還沒有得到處理的消息事件就構成了等待事件集合（pending event set，PES）。一個PES可以被表示為一個優先級隊列，在該隊列中，擁有最小時間戳的消息事件有著最高的執行優先級。通常情況下，離散事件模擬系統的性能主要取決于消息事件出入隊的時間復雜度，但是Comfort[1]在研究中發現，當等待事件集合很大時，模擬系統40%左右的時間會耗費在對消息事件的調度上。
日歷隊列[2]是一種基于鏈表數組的數據結構，它提供了對PES大小不敏感的時間復雜度為O（1）的出入隊操作。為了保持出入隊時間復雜度為O(1)的特性，日歷隊列在運行過程中必須保持鏈表數組中等待事件分布的均勻性，并確保任一鏈表中等待事件的數目要約束在一定范圍內。因此，在離散事件模擬系統的運行過程中，隨著等待事件的增長和減少，日歷隊列的大小也會相應地進行放縮調整。但是，日歷隊列的每一次放縮都會觸發日歷隊列的重建，這種重建對于日歷隊列而言代價是高昂的。如果等待事件平穩到達，則其對日歷隊列的放縮產生的影響比較小。然而，當等待事件到達高度聚集或到達分布變化劇烈時，日歷隊列的靜態放縮算法無法響應這種動態變化，將會頻繁地進行放縮而極大影響其性能。針對這個問題，目前已有的研究主要通過對日歷隊列進行局部采樣來檢測等待事件的聚集到達，然后根據檢測結果給出優化的放縮參數，以期從整體上可以減少放縮次數，如DCQ（dynamic calendar queue）[3]、SNOOPy CQ（statistically enhanced with optimum operating parameter calendar queue）[4]等。但是，受限于采樣技術的范圍和頻率，以上研究在實際應用中效果并不理想。
Markov過程作為一個典型的隨機過程被廣泛用于排隊系統的性能評價和控制過程。本文提出了一種基于Markov過程預測的日歷隊列放縮算法(PRAM)。該算法將日歷隊列的運行建模為一個Markov過程，通過對其動態結構進行分析，給出了基于等待事件到達分布的動態優化算法，用于解決當任務事件到達分布發生劇烈變化時日歷隊列的性能問題。隨后，本文通過數學工具給出了相關證明及分析。
本文最后在J2EE應用服務器OnceAS[5]中實現了PRAM的原型，并通過TPC組織的TPCW標準[6]對PRAM CQ、DCQ、SNOOPy CQ進行了比較和分析。實驗證明，PRAM算法可以更好地適應事件的聚集到達，且日歷隊列始終保持出入隊時間復雜度為O(1)的特性。
1 研究背景及相關工作
日歷隊列的名字起源于現實生活中的臺歷，人們在臺歷上面記錄下自己的任務計劃，每天只要查看臺歷就可以知道一天的工作安排。圖1給出了一個日歷隊列的典型實現。定義一個桶（bucket）的時間段為δ，桶的容量θ為一個桶中包含的等待事件的數目，一年的時間周期M就是桶的數目，而年的時間段就是所有桶的時間段之和。圖1中，桶的時間段為10，年的時間周期為10，所以年的時間段就為10×10＝100。一個桶就如同日歷中的一天，可以包含同一天但是卻不同年的等待事件；而且在一個桶中，等待事件的位置是依照其時間戳大小遞增排序的。將當前處理的桶定義為當前桶i0，當前時間為當前桶日歷隊列的運行原理如下：當有一個新的事件到達時，首先按式（1）得到這個時間應該被放置的天數，即哪一個桶；然后通過比較新事件與該桶中已有的等待事件的時間戳來決定新事件的插入位置。當要出隊一個等待事件時，日歷隊列從上一個出隊事件的位置開始尋找當前年中時間戳最小的等待事件，如果該桶中找不到時間戳屬于當前年的等待事件，日歷隊列會跳到下一個桶進行搜索，直到找到時間戳屬于當前年的等待事件；如果直到尋找完最后一個桶都找不到，那么日歷隊列將會重新從第一個桶開始尋找屬于下一年的時間戳最小的等待事件。
日歷隊列的性能與其結構緊密相關。R. Brown[2]提出當日歷隊列中等待事件均勻分布于各個桶且桶的容量平均為3、4時，日歷隊列的性能最優。然而在現實場景中，日歷隊列中的等待事件不可能是均勻分布在各個桶中的，所以，日歷隊列中PES的數目與桶的數目比值過小或過大都會給日歷隊列的正常運行帶來相當大的性能影響[2]。針對這種情況，解決的方法是讓日歷隊列的桶的數目隨著到達PES的增長或減少而相應地增長或減少。傳統的日歷隊列的解決方法非常簡單，設日歷隊列中桶的數目為NB，隊列中等待事件的數目為NE，則日歷隊列的放縮規則如下：
if NE＞2NBNB=2NB
if NE＜NB/2NB=NB/2
當NB被增大或縮小后，桶的時間段會被重新計算，然后日歷隊列會進行一次重建，使得任務能夠均勻地在日歷隊列中分布，以保持其O(1)性質。這個重建操作開銷巨大，因為必須對日歷隊列中的每一個元素重新定位并插入，所以應該盡量避免出現不必要的重建。但是，如果等待事件到達分布波動很頻繁的話，就有可能使得日歷隊列的增長和縮小非常頻繁，這時大量重建會嚴重影響日歷隊列的性能。尤其是當PES的數量在重建條件附近變化時，日歷隊列的開銷將集中在開銷巨大的重建上。
目前已有的研究主要集中于通過調整日歷隊列中桶的時間段來減少放縮次數，Oh 和 Ahn[3]提出了DCQ算法，通過對日歷隊列進行局部采樣來檢測等待事件的聚集到達；當檢測到等待事件聚集到達時，DCQ計算出一個放縮參數，用于優化桶的時間段，然后對整個日歷隊列進行重建。Tan和Thng[4]在DCQ的基礎上提出了SNOOPy算法，對日歷隊列的靜態結構進行了研究，同時優化了DCQ的檢測機制，通過對采樣的分析給出了一個優化的日歷隊列重建結構參數，以使得重建后的日歷隊列能夠保持任務在鏈表數組中分布的均勻性。這些研究工作都集中于通過優化對日歷隊列的局部采樣和分析日歷隊列的靜態結構特性獲得隊列重建的優化參數。它們的缺陷在于：a）采樣技術的精確度過于依賴采樣的范圍、頻率，并不能真正反映事件的分布狀態；b）僅僅通過分析日歷隊列的結構來獲得調整參數而忽略了實際應用場景下任務到達的動態變化。事實上，如果對日歷隊列的放縮不具備動態控制，那么這些靜態參數可能無法達到期望效果。
針對以往研究的缺陷，本文通過研究等待事件的到達率和服務率來描述等待事件的到達分布，并提出了PRAM算法。該算法將日歷隊列的運行過程動態建模為一個M/M/1/N的排隊系統，用Markov鏈對日歷隊列動態特征進行刻畫，給出了基于動態預測的放縮規則及放縮參數。實驗結果證明，PRAM算法有效地減少了日歷隊列的放縮次數，提高了日歷隊列的性能，并能夠更好地適應等待事件的聚集到達，保持等待事件出入隊時間復雜度為O(1)的特性。
2 PRAM算法
如前所述，傳統的日歷隊列實現沒有給出解決其在等待時間到達波動頻繁變化下結構不穩定的方法，并且目前的研究主要集中在通過對日歷隊列進行采樣來調整其整體結構，具有很大的局限性。本節針對以上問題提出了PRAM算法，利用Markov鏈對系統進行建模，以獲得對于等待事件到達分布的預測值，并將預測值用于放縮算法。
2.1 系統建模
假設日歷隊列中有N個任務，為便于分析，假設桶的數目為無限，在下一節會給出桶的數目有限時的相關修正及證明。桶的時間段為δ，那么可以將該日歷隊列建模為一個2.2 由無限狀態系統到有限狀態系統的完備性修正
受限于計算機資源的有限性，桶的數目M在現實中不可能為無限。為了將上一節的結論應用于現實系統，在此對其進行了修正，以使該結論可以用于桶的數目M有限的現實系統。本節最后給出了將基于M無限的理想系統的放縮規則式（5）用于M有限系統時的修正規則及其證明。
Erickson等人[8]提出了如下定理：
定理1 定義β為分布函數f的跳轉臨界點，有f(x)=0 for x＞β。如果f存在β，那么存在邊界值M*=β/δ+1。當M≥M*時，有限狀態系統性能模型等價于無限狀態系統。
定理1給出了M有限系統與M無限系統性能等價的條件及計算方法。但是在實際計算機系統中，可能存在以下情況：a)f不存在β；b)f存在β，但是β/δ的值太大以至于失去實際的使用價值。對于這些情況，M*是無法給出的，定理1也不能提供解決的辦法。所以，當M有限系統與M無限系統性能不等價時，必須給出一個可量化的性能差異的衡量標準。
首先給出以下定義：
一個任務e的時間t(e)-t0∈Φ，意味著該任務屬于當前年，會被執行，如圖1中時間戳為31的任務；若t(e)-t0∈Ω，即意味著該任務屬于當前桶，卻不屬于當前年，不會被執行，如圖1中的時間戳為138的任務。
Erickson等人給出了LM(δ)的計算公式及下界，如式(6）所示：
根據以上結論可以得到主要理論如下：
命題1 對于一個桶數目為M的日歷隊列，設
b為遍歷一個空bucket的時間；
c為遍歷一個非空bucket，找到下一個待處理任務的時間；
d為隊列處理時間，包括一個任務的出隊和一個新任務的入隊時間之和；
EM()為在M有限系統時，任務處理時間的數學期望；
至此，放縮規則（式（5））可通過參數η進行修正，以適應M有限系統。放縮規則具體修正如下所示：
PRAM算法基于式（14），以下為算法細節實現：
enqueue(){
Enqueue new event to the appropriate bucket;
NE++;
update;
if(NE＞3NB){//CQ trigger for a growing PES
Calculate variable L by formula (3)
NB=L/3+0.01L;
δ:=use sampling method;
//just as conventional CQimplementation
calendar_Resize(NB，δ);}
return;}
dequeue(){
Dequeue event from the head of the appropriate bucket;
NE;
update;
if (NE＜NB/3){//CQ trigger for a growing PES
calculate variable L by formula (3)
NB=L/3+0.01L
δ:=use sampling method;
//just as conventional CQimplementation
calendar_Resize(NB，δ);}
return;}
Calendar_Resize()重建函數只是在滿足式（14）中的條件時才會被觸發，此時enqueue()和dequeue()的時間復雜度為O(n)。如果放縮規則（式（14））中的條件沒有被觸發，那么enqueue()和dequeue()的時間復雜度僅為O(1)。由于calendar_Resize()函數的時間復雜度相對較高，PRAM算法的時間復雜度完全取決于calendar_Resize()函數被調用的次數。傳統的日歷隊列算法如DCQ、SNOOPy CQ正是由于在等待事件到達高度聚集的情況下calendar_Resize()函數被調用的次數過多，才導致了它們無法保持出入隊時間復雜度O(1)的特性。PRAM算法由于基于動態模型對系統特征進行刻畫，有效地避免了不必要的放縮對于整體算法性能的不利影響，保持了出入隊時間復雜度O(1)的特性。
3 算法應用
PRAM算法已經在中國科學院軟件研究所的J2EE應用服務器OnceAS[5]的WorkManager[9]組件中進行了原型實現。本節通過與DCQ、SNOOPy CQ比較來驗證PRAM算法的有效性。
3.1 實驗系統原型
WorkManager是JSR237[10]正式標準，它提出了一種介于應用服務器與系統資源之間的中間層，其目的在于對線程的創建、分配、調度乃至銷毀提供一個統一的框架。
如圖3所示，本文引入了日歷隊列作為WorkManager的調度框架。在應用服務器中所有任務均通過WorkManager執行，無論是Web容器、EJB容器還是系統內部事務。但是在日歷隊列中，對于任務的區分僅僅是通過任務的時間戳，顯然這不能滿足應用服務器對于任務差分的要求。因為應用服務器處理的任務存在一定的優先級順序，可能先到的任務由于優先級低反而較后得到響應。為了解決這個問題，本文使用了虛擬時間戳（virtual timestamp）的概念，通過為每一個到達的任務生成一個虛擬時間戳，將任務的優先級順序映射到虛擬時間戳中以保證任務的優先級順序。
虛時間戳=實際時間戳+時間增量
時間增量=任務類型/任務優先級×100
一個任務進入WorkManager后，它進入調度隊列——日歷隊列的時間戳并不是它實際到達的時間戳，而是由WorkManager處理的虛時間戳。任務的優先級與時間增量成反比，即任務優先級越高，其時間增量越小，這個性質映射到日歷隊列中后，時間戳越小的任務執行得越早。
關于時間增量的生成，由任務的類型和優先級兩個參數決定，任務類型包括Web任務、EJB任務和其他任務。任務類型相同且優先級相同的任務的時間增量相同。
圖3所示的系統流程如下：
a）應用服務器接收外部任務及應用服務器自己產生的任務；
b）應用服務器將任務轉發到WorkManager中，WorkManager接收到任務后，首先用服務差分器對任務進行處理，產生虛擬時間戳以實現服務差分；
c）任務以虛擬時間戳在日歷隊列中入隊；
d)任務從日歷隊列中出隊到執行器中開始執行；
e)將任務處理結果返回給用戶。
3.2 實驗環境
實驗環境由一臺PC機、兩臺服務器構成。PC機模擬客戶端；兩臺服務器上分別運行應用服務器OnceAS和數據庫DB2。PC機配置為Pentium D CPU 3.4 GHz，2 GB內存，軟件環境為Windows Vista Ultimate。兩臺服務器的配置為XeonTM MP CPU 3.5 GHz，4 GB內存，軟件環境為Windows 2000 Professional Service。機器之間通過百兆以太網連接。
對于部署在應用服務器OnceAS上的WorkManager，本文實現了三個算法版本，分別基于DCQ、SNOOPy CQ、PRAM CQ。以下測試也基于這三個版本。采用事務流程性能委員會（Transaction Processing Performance Council，TPC）組織公布的TPCW基準[6]作為部署在OnceAS中的應用。該基準基于Markov過程，用戶請求的到達是基于指數分布的[11]，其跳轉行為如圖4所示。
TPC僅僅提供了TPCW的設計規范，實驗中采用由WisconsinMadison大學PHARM（Predictive HighPerformance Architecture Research Mavens）小組開發的開源的基于Java的TPCW系統實現[12]。
4 實驗結果
4.1 TPCW的到達分布
實驗首先模擬了300個用戶按照圖4的訪問模式對部署在OnceAS上的TPCW應用持續訪問10 min，以收集任務的到達分布。
實驗結果如圖5所示，坐標橫軸為時間（s），坐標縱軸為normalized WIPS（normalized Web interactions per second，可以理解為每秒到達任務數）。圖5中的點代表了任務的聚集程度，點越密集，表示任務到達越密集；虛線為WIPS的均值，在本圖中WIPS的均值為98.6；實線表示了TPCW任務到達的一個周期，實驗設置為360 s。
在客戶數為300的環境下，TPCW的任務到達分布高密度聚集且波幅比較大，即已經頻繁發生事件密集到達。以下的實驗都基于客戶數為300的TPCW測試環境。
4.2 日歷隊列的性能比較
在實驗中使用TPCW對基于DCQ、SNOOPy CQ和PRAM CQ三個版本的OnceAS進行測試。筆者關注的參數有兩個：a)放縮次數，即在運行過程中，日歷隊列進行了多少次收縮；b)平均等待時間，即事件從進入日歷隊列到離開日歷隊列的時間。前者越少越好，而后者越短越好。
圖6給出了DCQ、SNOOPy CQ、PRAM CQ在測試中放縮次數的比較。其中：橫軸表示日歷隊列所容納的等待事件數；縱軸表示日歷隊列在運行過程中進行的放縮次數。從圖6中可以看到，PRAM CQ受到事件到達分布的影響最少，其放縮次數始終在3～7次；SNOOPy CQ在運行過程中對事件到達分布較敏感，其放縮次數在5～10次擺動；在三種算法中，DCQ對于事件到達分布最敏感，它在運行過程中放縮次數在4～17擺動，且波幅最大。這種結果是由于DCQ的實現通過局部采樣來決定是否放縮，缺乏對于當前運行狀況的預測機制，當事件到達的波動性增大時，基于DCQ的日歷隊列無法有效檢測到這種波動而頻繁地進行放縮。SNOOPy雖然也同樣基于局部采樣，但是它在DCQ的基礎上對采樣算法進行了優化，并添加了對日歷隊列結構的估測算法，所以放縮次數相對平穩一些，但是也并不能完全適應分布的變化。而基于PRAM的日歷隊列實現有著動態的預測機制，當事件到達波動性增大時，PRAM會反饋出這種變化，并及時應用到日歷隊列的放縮中去，所以基于PRAM的日歷隊列實現與傳統的日歷隊列實現相比有著更好的適應性和穩定性。如圖6所示，PRAM CQ的放縮次數與DCQ、SNOOPy CQ相比，分別減少了50％和30％，而且在整個運行中變化更加平穩。
為了進一步說明問題，對基于DCQ、SNOOPy和PRAM的日歷隊列實現的平均等待時間進行了統計比較。圖7中橫軸表示日歷隊列容納的等待事件數；縱軸代表事件在日歷隊列中的平均等待時間。在理想的日歷隊列模型中，日歷隊列中平均等待時間的時間復雜度應該為O(1)且與隊列長度無關，但是從圖7中可以看到，DCQ和SNOOPy CQ基本上呈一個線性增長的趨勢。這是由于基于DCQ和SNOOPy CQ的日歷隊列的放縮次數比較頻繁，導致巨大的重建開銷而無法保持O(1)的特性；與之相比，基于PRAM的日歷隊列由于其在放縮次數上的穩定性，避免了代價昂貴的放縮對性能的影響。在圖7中，PRAM CQ在事件到達迅速增長的過程中，平均等待時間始終處于平穩狀態，保持了與隊列長度無關的出入隊時間復雜度O(1)的特性。
由圖6和7可以看到，無論是從放縮次數還是到達事件的平均等待時間上來看，PRAM CQ都優于DCQ和SNOOPy CQ，在事件聚集到達且到達分布波動較大時，這種性能差異尤其明顯。
最后圖8和9分別給出了TPCW基準在基于PRAM CQ、SNOOPy CQ和DCQ三種系統上的性能參數。圖8是TPCW基準在PRAM CQ、SNOOPy CQ、DCQ三種實現上的系統吞吐量比較。TPCW具有三種模式，即browsing（95% read）、shopping（80% read）、ordering（50% read）。Browsing模式中95%的任務涉及數據庫的讀操作，涉及數據庫寫操作的僅有5%。TPCW從browsing模式改變到shopping模式和ordering模式時，數據庫寫操作分別占到15%和45%。從圖8可以看出，在這三種模式下，基于PRAM CQ的系統吞吐量始終優于基于SNOOPy CQ和DCQ的系統。在browsing模式下，吞吐量差距比較明顯；而ordering模式下差距相對小一點。這是因為browsing模式下，數據庫寫操作很少，日歷隊列的調度時間在任務執行時間中占的比例較高，所以日歷隊列性能的提高對整個系統性能的提高影響較大；而ordering模式下，數據庫寫操作較多，日歷隊列的調度時間在任務執行時間中占的比例較低，所以日歷隊列性能的提高對整個系統的影響并不明顯。圖9是TPCW基準在PRAM CQ、SNOOPy CQ、DCQ三種實現上的系統任務平均處理時間的比較。可以看出，基于PRAM CQ的系統任務平均處理時間要比基于SNOOPy CQ和DCQ的系統小得多。
從以上實驗結果可以看出，相對于DCQ和SNOOPy CQ，PRAM CQ是一種性能更加優異的日歷隊列實現。
4.3 性能損失評價
本文通過完備性證明給出了將基于M無限系統的放縮規則用于M有限系統的修正規則，該規則構成了PRAM算法的核心。以下將對該修正規則在實際應用中的有效性進行驗證。
在實際應用中，將PRAM算法用于M有限系統帶來的性能損失必須是可以量化的。在實驗中，根據式（12）取定兩個邊界，當系統性能損失η為5%和1%時，M/N的值分別為1.92和3.02；而在測試中，對日歷隊列中桶的數目與任務數目的比值進行了計算并記錄。圖10橫軸表示日歷隊列中包含的任務數目；縱軸表示測試周期中平均的M/N值。從圖10中可以看到，在測試過程中M/N的值始終在1.92~3.02。這就意味著在整個測試過程中，基于PRAM的現實系統性能與基于PRAM的理想系統的性能差異η始終在1%~5%，換句話說，系統性能始終在理想模型的95%以上。
5 結束語
離散事件模擬的性能一方面由它所在的運行支撐環境決定，另一方面由它所使用的數據結構及調度算法決定；對于離散事件模擬的調度算法的研究是目前一個熱門的研究領域，本文的工作側重于研究在離散事件模擬中被廣泛應用的數據結構——日歷隊列的調度算法。
鑒于日歷隊列在事件到達聚集情況下的結構不穩定，本文提出了一種基于Markov過程的預測算法PRAM，通過添加動態預測機制，使得PRAM可以及時反饋出任務到達的變化，并將反饋應用到日歷隊列的放縮中去。本文最后通過一個系統原型對算法進行了驗證。實驗結果表明，與以往的日歷隊列算法DCQ、SNOOPy CQ相比，PRAM可以有效地解決日歷隊列結構不穩定的缺陷，保證了日歷隊列在實際應用場景下仍然保持出入隊時間復雜度O(1)的特性。在同等條件下，與已有研究相比，PRAM CQ不僅可以有效減少日歷隊列的放縮次數，而且在運行過程中平均等待時間減少了10%～20%。然而，本文在實現中沒有考慮桶的時間段變化給日歷隊列調度帶來的影響，這個問題將在以后的工作中加以解決。
參考文獻：
［1］COMFORT J C.The simulation of a masterslave event set processor[J].Simulation，1984，42(3):117124.
[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):11201227.
[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 Guochuang，LIN Shibiao，DONG Weichuan，et al.Web Frame:an extensible multilayer Web application server[J].Chinese Journal of Computers，2004，27(4):451-460.
[6]The Transaction Processing Council （TPC）.TPCW site[EB/OL].http://www.tpc.org/tpcw/. [7]KLEINROCK L.Queueing systems，volume1:theory[M].New York:WileyInterscience 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.TPCW:a benchmark for ecommerce[J].IEEE Internet Computing，2002，6(3):83-87.
[12]PHARM[EB/OL].http://www.ece.wisc.edu/~pharm/
