搶占式排隊系統(tǒng)平均逗留時間研究

郭金淮，閆曉輝，張祝盛

(中國人民解放軍94201部隊，山東 濟南250002)

排隊系統(tǒng)廣泛應用于理論研究與實際系統(tǒng)設計中，通常應用于服務系統(tǒng)，如通信系統(tǒng)、交通系統(tǒng)、計算機應用系統(tǒng)、存儲系統(tǒng)、生產(chǎn)管理系統(tǒng)等領域［1-7］。根據(jù)重要程度的不同可以將排隊系統(tǒng)服務對象分為多個優(yōu)先級，將服務對象可分為多個優(yōu)先級的排隊系統(tǒng)稱為多優(yōu)先級排隊系統(tǒng)，多優(yōu)先級排隊系統(tǒng)在排隊系統(tǒng)研究中占有重要地位［2，3，4，7］。對于服務對象來說，通常關心其完成服務所需時間，即系統(tǒng)逗留時間。因此，平均逗留時間成為排隊系統(tǒng)研究的重要性能指標［1，3，6，7］。針對多優(yōu)先級排隊系統(tǒng)，有大量文獻對平均逗留時間或平均等待時間進行了研究?？紤]軍事應用，文獻［3］根據(jù)信息重要程度將服務對象分為兩種優(yōu)先級，對信息平均逗留時間進行了分析，其性能提升以損失低優(yōu)先級服務對象為代價，在無服務對象損失前提下性能并沒有改善;文獻［7］針對多媒體業(yè)務流，考慮兩類優(yōu)先級，基于馬爾科夫到達過程與離散時間模型，對穩(wěn)態(tài)隊長、平均延時性能進行了研究;針對ATM網(wǎng)絡，考慮實時業(yè)務與非實時業(yè)務，文獻［8］提出了基于門限的優(yōu)先級策略，研究表明該策略優(yōu)于靜態(tài)優(yōu)先級策略;基于ATM網(wǎng)絡不同突發(fā)業(yè)務及服務質量要求，將業(yè)務分為兩類，文獻［9］提出了動態(tài)優(yōu)先級排隊策略并進行了性能分析。

上述研究具有較強針對性，根據(jù)具體應用場景，給出了相應策略。區(qū)別于上述策略研究，本文考慮排隊系統(tǒng)存在多個優(yōu)先級服務對象的情況，證明了搶占式排隊系統(tǒng)為無性能損失排隊系統(tǒng)，采用資源分層方法，對不同優(yōu)先級服務對象的平均逗留時間作了針對性研究。文中方法具有適應性，可用于任意數(shù)目優(yōu)先級的排隊系統(tǒng)。

1 系統(tǒng)模型

文中采用系統(tǒng)模型如下。

(1)排隊模型。考慮多服務臺排隊系統(tǒng)，就性能來說，相同服務臺數(shù)目情況下，單隊列多服務臺模型優(yōu)于多隊列多服務臺模型［10］，本文采用單隊列多服務臺模型，服務臺數(shù)量為m，不考慮隊長限制，即M/M/m/∞排隊模型。服務臺數(shù)目為一時，可退化為單服務臺排隊系統(tǒng)。

(2)輸入過程。根據(jù)重要程度，將服務對象分為r個優(yōu)先級，優(yōu)先級i的服務對象服從到達率為λi的泊松分布，t時間內(nèi)到達k個優(yōu)先級i服務對象的概率為Pki(t)=，其中i=1，2，…，r，i越大優(yōu)先級越高。

(3)排隊規(guī)則。采用搶占式排隊規(guī)則，即高優(yōu)先級服務對象到達隊列時排在低優(yōu)先級服務對象之前，若服務臺全忙且有低優(yōu)先級服務對象正在接受服務，則停止低優(yōu)先級服務對象服務以搶占服務資源。

(4)服務過程。所有服務對象服務時間均服從參數(shù)μ的負指數(shù)分布。隊長可無限長，滿足∑ri=1λi＜mμ，排隊系統(tǒng)可達穩(wěn)態(tài)。

(5)研究指標。對不同優(yōu)先級服務對象的平均逗留時間進行研究。

2 性能研究

主要包括資源分層概念、時間累加等效性定理、平均逗留時間研究三部分。

2.1 資源分層概念

文中資源指服務資源，根據(jù)搶占式排隊系統(tǒng)的特點，結合系統(tǒng)模型提出資源分層的概念。具體如下。

(1)優(yōu)先級越高、擁有資源權限越大。

(2)最高優(yōu)先級服務對象擁有系統(tǒng)全部資源。

(3)對于優(yōu)先級i服務對象來說，其擁有資源為比其優(yōu)先級高服務對象的剩余資源，即優(yōu)先級為i+1，…，r-1，r服務對象的剩余資源。

2.2 時間累加等效性定理

定理:服務臺服務能力服從負指數(shù)分布，單位時間平均服務率s。時間段TT對應時間區(qū)間［ta，tb］，時間段Ti應時間區(qū)間［tai，tbi］，其中i=1，…，L，ta1≤tb1≤…tai≤tbi≤…taL≤tbL，考慮時間長度，滿足TT=。則時間段TT完成服務的平均數(shù)等于所有時間段Ti完成服務的平均數(shù)的和。

證明:根據(jù)指數(shù)分布性質，服務臺完成服務的次數(shù)服從參數(shù)為s的泊松公布。令L=2，則滿足TT=，則TT完成k次服務的概率:

令時間段T1，T2完成服務次數(shù)分別為n1，n2，則時間段T1，T2共完成k次服務的概率:

根據(jù)二項式定理，可得到式(1)等于式(2)。

基于數(shù)學歸納法，上述結論適用于L為任意正整數(shù)的情況，定理得證。也就是說，只要累加時間和相同，則完成服務的平均數(shù)相同，與時間段數(shù)目無關。該定理成立的原因是指數(shù)分布的無記憶性。

基于時間累加等效性定理可知，搶占式排隊系統(tǒng)服務能力與非搶占式排隊系統(tǒng)服務能力相同，為無性能損失排隊系統(tǒng)。

2.3 平均逗留時間

基于上述資源分層概念與時間累加等效性定理，下面對不同優(yōu)先級服務對象平均逗留時間進行研究。

2.3.1 最高優(yōu)先級服務對象

最高優(yōu)先級服務對象擁有系統(tǒng)全部資源，可按無優(yōu)先級單隊列多服務臺模型研究。設pm為隊列有n個最高優(yōu)先級服務對象的概率，得到:

2.3.2 一般優(yōu)先級服務對象

不失一般性，考慮優(yōu)先級i服務對象，其平均逗留時間分析如下。

(1)將優(yōu)先級i到r的服務對象看作一類，記Si→r，其到達率λi→r=。根據(jù)式(5)，其平均逗留時間wi→r為:

(2)將優(yōu)先級i+1到r的服務對象看作一類，記Si+1→r，其到達率λi+1→r=。同理，其平均逗留時間wi+1→r:

顯然，把所有服務對象看作一類時，直接計算所得平均逗留時間與式(9)相同。

3 實例分析

信息服務系統(tǒng)是軍隊信息化建設的重要組成部分，需要處理各種不同信息。根據(jù)重要程度，將信息分為三個優(yōu)先級:①后勤保障信息，包括物資和給養(yǎng)的保障情況;②武器裝備狀態(tài)信息，指武器作戰(zhàn)平臺的方位、運動速度、運動方向及燃料儲備等;③戰(zhàn)場態(tài)勢信息，敵我友三方的兵力部署、火力配置等。

戰(zhàn)場態(tài)勢信息優(yōu)先級最高，武器裝備狀態(tài)信息次之，后勤保障信息優(yōu)先級最低。結合系統(tǒng)模型，優(yōu)先級高的信息優(yōu)先接受服務，將該信息服務系統(tǒng)等價為搶占式排隊系統(tǒng)。其中，平均逗留時間是重要系統(tǒng)設計指標，基于文中方法，對不同優(yōu)先級信息的平均逗留時間進行分析。假設優(yōu)先級1、2、3信息的到達率分別2、3、5，單服務臺服務率3，服務臺數(shù)目分別為5、6、7、8時，不同優(yōu)先級服務對象及所有優(yōu)先級服務對象平均逗留時間如圖1所示。由圖可以看出，服務臺數(shù)量同樣存在瓶頸效應，即當服務臺達到一定數(shù)量后，數(shù)量的進一步增加不會明顯減少平均逗留時間。

圖1 平均逗留時間示意圖

根據(jù)分析數(shù)據(jù)，可以在滿足不同優(yōu)先級信息服務要求的前提下，對信息服務系統(tǒng)進行優(yōu)化，比如系統(tǒng)需要的服務臺數(shù)量等等。

4 結論

考慮存在多優(yōu)先級服務對象的搶占式排隊系統(tǒng)，提出了資源分層概念，并基于時間累加等效性定理，對排隊系統(tǒng)不同優(yōu)先級服務對象的平均逗留時間進行了分析。基于文中方法，可進一步對不同優(yōu)先級服務對象的其他性能作針對性分析，對多優(yōu)先級排隊系統(tǒng)的設計具有重要指導意義。

1 盛友招.排隊論及其在計算機通信中的應用［M］.北京:北京郵電大學出版社，2000.

2 胡根生，朱翼雋.帶有兩個優(yōu)先權M/M/s排隊的通信網(wǎng)交換性能分析［J］.江蘇大學學報(自然科學版)，2002，23(4):91-94.

3 趙軼飛，齊和平，劉伶平，等.排隊論在軍事信息服務中的應用［J］.火力與指揮控制，2011，36(7):111-113，118.

4 王知人，侯培國，關新平.具有優(yōu)先級排隊系統(tǒng)輸入隊列調(diào)度算法性能比較［J］.黑龍江自動化技術與應用，1999，18(2):10-14.

5 吳錦標，劉再明，尹小玲，等.基于排隊論的一個物流模型［J］.系統(tǒng)工程理論與實踐，2009，29(9):78-83.

6 甘應愛.運籌學(第三版)［M］.北京:清華大學出版社，2005.

7 孟坤.基于排隊論的通信網(wǎng)絡QoS研究［D］.鎮(zhèn)江:江蘇大學，2008.

8 LEE D，SENGUPTA B.Queueing Analysis of a Threshold based Priority Scheme for ATM Networks［J］.IEEE/ACM Trans.Netw.，1993，1(6):709-717.

9 CHOI D I，LEE Y.Performance Analysis of a Dynamic Ppriority Queue for Traffic Control of Bursty Traffic in ATM Networks［J］.IEE Proc.-Commun.，2001，148(3):181-187.

10 岳立業(yè).排隊方式在優(yōu)化排隊系統(tǒng)中的應用［J］.科技信息，2007(36):154-155.