1、第四章 排隊論在計算機系統 性能評價中的應用1一、基本思路和方法簡單排隊模型：輸入過程 排隊規則 服務機構到達者離去者隊列服務裝置在一個時間段內，到達者與離去者保持相對一致，使系統達到相對平衡和穩定。23計算機中的許多現象都可以以顧客，排隊及服務的形式表示:如：資源問題數據、存儲 、計算機通信問題信號、信道、傳輸網絡路由數據包、通道、傳送并行處理任務、處理機、計算、調度4由于：數據到達的時間間隔分布，處理或傳輸部件的時間間隔分布處理部件的個數產生了對應不同特征的概率分布應用的分析。如泊松分布可以對應并行處理中的多任務多處理機的分配；多線程，多核的調度效率等網絡路由中的數據包與網絡通道服從愛尓朗

2、分布。5二、I/O性能與系統響應時間 1.模型模擬和實際測量的方法來衡量。 對I/O系統建立模型后，可以使用排隊理論進 行分析。 設計出來的I/O系統還可以通過基準測試程序 進行實際測量。 62. 衡量I/O系統的性能的標準 I/O系統的多樣性：哪些I/O設備可以和計算 機系統相連接。 I/O系統的容量：I/O系統可以容納多少I/O 設備。 I/O吞吐量有時也被稱為I/O帶寬。 I/O響應時間有時被稱為響應延遲。73. 吞吐量和響應時間 0501001502002503000%20%40%60%80%100%實際吞吐量/最大吞吐量響應時間（ms）8 獲得較大吞吐率和較小響應時間是相互矛盾的，如

3、何進行折衷是計算機體系結構要研究的問題。 051015圖形系統（0.3s）圖形系統（1s）鍵盤系統（0.3s）鍵盤系統（1s）時間（s）進入時間系統響應時間思考時間鍵盤輸入系統和圖形輸入系統的事務處理時間 9Little定律1. 黑箱（Black Box）黑箱到達任務離開任務穩定狀態：系統的輸入速率= 輸出速率 2. Little定律系統中的平均任務數到達率平均響應時間103. 證明 假定對系統一個任務測量時間:Tobserve統計在此期間: 完成的任務數:Ntasks 每個任務的實際完成時間 將這些時間求和得到Taccumulated11Little定律：系統中的平均任務數為到達率與平 均響

4、應時間的乘積。observedaccumulateTT=平均任務數tasksdaccumulateNT=平均響應時間observetasksTN=任務到達率observetaskstasksdaccumulateobservedaccumulateTNNTTT=12Little公式對于一個排隊系統，如果在它達到統計平衡狀態后，系統中任一時刻的平均隊長 、平均等待隊長 ，與每一顧客在系統中的平均逗留時間 、平均等待時間 之間有關系式：成立，則稱該排隊系統滿足Little公式。其中e表示單位時間內實際進入系統的平均顧客數。13服務的顧客，在他后面排隊等待服務的平均顧客數等于在他的平均等待時間內實際

5、進入系統的平均顧客數，即 ；又考慮一個剛服務結束的顧客，在他離開系統時留在系統中的平均顧客數等于在他的平均逗留時間內實際進入系統的平均顧客數，即 。Little公式的直觀解釋在系統達到統計平衡下，考慮一個剛開始接受 顯然，M/M/1/排隊系統中，Little公式是成立的，且e等于泊松過程的參數。14例1、對于一個穩定系統，即客戶到達該系統的平均速率=客戶離開該系統的平均速率 設：一個并發服務器，并發的訪問速率是1000客戶/分鐘，每個客戶在該服務器上將花費平均0.5分鐘，根據littles law規則，在任何時刻，服務器將承擔 10000.5500 個客戶量的業務處理。假定過了一段時間，由于客

6、戶群的增大，并發的訪問速率提升為 2000客戶/分鐘。在這樣的情況下，我們該如何改進我們系統的性能？根據littles law規則，有兩種方案：第一：提高服務器并發處理的業務量，即提高到20000.51000。 第二：減少服務器平均處理客戶請求的時間，即減少到： 20000.25500。 15三、 M/M/1排隊模型1、 簡單的排隊系統(M/M/1/ /FCFS）應用I/O控制器及外設隊列服務員任務到達 假定I/O請求的到達時間和服務員的服務時間服從指數分布。 16排隊系統參數 S：任務的平均服務時間 ：任務的服務速率， = 1/S Wq：平均排隊時間 Ws：平均響應時間；Ws = Wq +

7、S ：任務的到達率 ：服務員利用率（服務強度）， = / ns：正在服務的平均任務數17Lq：隊列的平均長度Ls：平均任務數，n=ns+nq；n =Rm：服務員個數3. M/M/1排隊系統的一般假設 系統為一個平衡系統； 連續兩個到達請求的間隔時間服從指數分 布，其均值為平均到達時間； 請求的個數不受限制；18 隊列的長度不受限制，排隊規則為FCFS； 系統只有一個服務員。若M/M/1模型的到達率為，服務率為，1個服務員。根據穩定的生滅過程，有狀態轉換和狀態方程：19相關的分析結論有： 系統服務強度 =/ 系統中沒有任務的概率 P0=1- 系統中有n個任務的概率 Pn=(1-)*n ， n=0

8、,1,2, 系統中平均任務數量 E(n)=Ls=/(1-) 隊列中平均任務數 E(nq)=Lq=2/(1-) 系統平均響應時間 E(R)=Ws=(1/)/(1-) 任務在隊列中的平均等待時間 E(W)=Wq= r-mr1/120四個指標的關系為(Little 公式)：系統的忙期與閑期系統處于空閑狀態的概率：系統處于繁忙狀態的概率：服務強度21例1：一個CPU及具有n個中斷源的中斷系統。設CPU處理中斷的時間是指數分布，平均時間為500ms(500ns)。一個中斷源的兩個相鄰中斷請求時間間隔服從指數分布，其平均值為20ms。求：最大中斷源的個數及在相應中斷源個數的中斷響應時間。解：服從指數分布，

9、屬于M/M/1隊列，其響應時間有：若要保持系統平衡，i，共享源增多當i，共享源減少30進一步處理eMule網絡中文件的共享源個數取決于文件的流行程度，以及用戶的共享意愿這是一個泊松分布312、限定系統容量(M/M/1/N/FCFS）模型應用 當系統容量最大為N時，排隊多于N個的顧客將被拒絕。當N=1時，即為瞬時制，N時，即為容量無限制的情況。 可對應路由器，鍵盤等帶有緩沖隊列的系統分析；側重緩沖隊列長度對系統的影響。32狀態轉移方程N201狀態轉移圖33解式得： 而等比數列34 求排隊系統顧客數的分布狀況35 隊長隊列長 有關指標36 逗留時間 等待時間系統已滿顧客不能到達的概率-損失率37

10、有Buf深度為6，數據包等待排隊，超過6個包就丟失，平均包到達率3/分鐘，轉發需時平均15秒。7為系統中的最大包數。平均到達率: 3包/分 平均服務率: 4包/分先看例：路由Buf數據包排隊問題38 數據包到達就能轉發的概率 -相當于路由中無數據包待發數據包的期望值39 求有效到達率 顧客在路由器中內逗留的期望時間小時分鐘包/分40 可能的數據包有百分之幾不等待就丟失 -求系統中有7個數據包的概率41例：鍵盤緩沖隊列，緩沖隊列長度15，Int 9接收鍵盤字符送入緩沖隊列，Int 16輸出進入系統。設鍵入字符速率符合指數分布，求其損失率若給定類似：42例：設蟲孔尋徑中的交叉開關（路由器）。路由器

11、中的緩沖器，直接影響到數據片丟失。例：網站等訪問的負載平衡問題433、顧客源有限制(M/M/1/m/FCFS）模型應用 以機器修理模型為例，設有m臺機器(總體)，故障待修表示機器到達，修理工是服務員。機器修好后有可能再壞，形成循環。雖然系統沒有容量限制，但系統中的顧客也不會超過m，故又可寫成：M/M/1/mM/M/1/m/FCFS模型可以考慮對應處理具有循環狀態的數據處理過程。44 對于有限源應按每個顧客單獨考慮，求出其有效到達率e。 這樣e是隨系統內顧客數而變化的。其狀態轉移圖為：設系統內顧客數為Ls，則系統外的顧客為m-Ls。設每個顧客的平均到達率是相同的。 (這里的含義是單臺機器在單位時

12、間里發生故障的概率或平均次數)45狀態轉移方程注意到 ，46 求解狀態轉移方程得有效到達率求解顧客數概率分布47 等待時間正常運轉的平均設備臺數計算有關指標48隊長隊列長逗留時間49設定：各服務臺工作是相互獨立的，且平均服務率相同，均為 。整個服務機構的平均服務率為： c (當n c )， n (當n c );記 = / , s= /c = /c 為服務系統的平均利用率 當 / c 1時，不會排成無限隊列。二、多服務臺排隊模型M/M/c1、標準的 M/M/c 模型（ M/M/c / ）廣泛應用于多操作部件，多資源分配調度等并行系統分析50 1 2 c.服務臺C個系統人數n人51 1 2 c.服

13、務臺C個系統人數n人n c53狀態轉移圖01n-1nn(n+1)n+1. . . . .22n-1nccn+1. . . . .n c54狀態轉移方程55解差分方程，求得狀態概率為56 顧客等候的概率 計算有關指標平均正接受服務的顧客數=正忙的服務臺數解釋?57 隊長隊列長逗留時間及等待時間計算有關指標唯一58 某售票所有三個窗口，顧客到達服從Poisson過程，到達 = 0.9 人/分鐘，服務 =0.4人/分鐘。設顧客到達后依次排成一隊向空閑的窗口購票，如圖 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.9M/M/c型系統和c個M/M/1型系統的比較59M/M/c型系統和c個

14、M/M/1型系統的比較 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.960屬于M/M/c型系統 c =3, =/ =2.25, s = /c =2.25/3 1,符合要求.整個售票所空閑概率平均隊長61平均等待時間和逗留時間顧客到達后必須等待概率62 以上例說明,設顧客到達后在每個窗口前各排一隊(其它條件不變),共三隊,每隊平均到達率為: 窗口1 =0.4 窗口2 =0.4 窗口3 =0.4 = 0.3 = 0.3 = 0.3 = 0.9圖 bM/M/c型系統和c個M/M/1

15、型系統的比較63 模型指標 M/M/33個(M/M/1)P0LqLsWsWq必須等待概率0.07481.703.954.39 (分鐘)1.89 (分鐘)0.570.25 (子系統)2.25 (子)9.00 (整)10 (分鐘)7.5 (分鐘)0.75結果比較單隊列好M/M/c型系統和c個M/M/1型系統的比較645. 若M/M/m模型將M/M/1模型的服務員修改為m個， 相關的分析結論有： 系統服務強度 =/(m*) 系統中沒有任務的概率 P0= 系統中有n個任務的概率 Pn=11m1nnm!n)m()1(!m)m(1-=r+r-r+rrmn,!mmPmn,!n)m(Pnm0n065 隊列中有

16、顧客的概率 Pe= 系統中平均任務數量 E(n)=m+Pe/(1-) 隊列中平均任務數 E(nq)=Pe/(1-) 系統平均響應時間 E(R)= 隊列中的平均等待時間 E(W)=Pe/m(1-) 0mP)1(!m)m(r-r)1(mP1(1er-+m66 例：在例2的基礎上，給磁盤I/O系統增加一個磁盤，該磁盤是另一個磁盤的鏡像，故訪問可以從任意一個磁盤上得到數據。假定對磁盤的I/O操作均為讀操作，重新計算。 解 使用兩個磁盤，該系統為M/M/2系統。 磁盤I/O請求的到達率 =40(個/s) 完成I/O請求的服務率 =1/0.02=50(個/s) 磁盤的平均利用率 =(/)/2=0.4 67

17、該系統可以用M/M/m排隊模型的結論：系統中沒有任務的概率 P0=395.08.0533.01!n)2()1(!2)2(11111nn2+=r+r-r+-=隊列中有顧客的概率 Pe= 229.0395.0)4.01(!2)4.02(P)1(!2)2(202=-=r-r68平均等待時間 E(W)=Pe/m(1-) =0.229/250(1-0.4)=0.0038平均響應時間 = 平均等待時間+平均服務時間 = 0.02+0.0038=0.0238(s) 兩個慢速磁盤的等待時間是1個慢速硬盤的1/21，是1個快速硬盤的等待時間的1/1.76。69例1設有一個信息交換中心，信息流為泊松流，每分鐘到達

18、240份，線路輸出率為每秒800個字符，信息長度（包括控制字符）近似負指數分布，平均長度176個字符。要使在任何瞬間緩沖器充滿的概率不超過0.005，問緩沖器的容量K至少應取多大？70解信息平均到達率240份/分4份/秒，800/176 4.546份/秒，/0.88。按M/M/1/K系統處理，緩沖器充滿的概率pK應滿足計算有：p250.009045，p260.004464。所以K26，即緩沖器的容量至少應為26個單位。71例2：設某計算機有4個終端，用戶按泊松流到達，平均每10分鐘到達1.5個用戶。假定每個用戶平均用機時間為20分鐘，用機時間服從負指數分布，如果4個終端被占用，則用戶到其它計算

19、機處接受服務，求此系統的各項指標。72解：這是M/M/4/4損失制系統，9（人/小時），3（人/小時）,/3。顧客損失的概率為：單位時間內實際進入系統的平均顧客數為：平均忙的終端數為：732、M/M/c/K混合制：一種混合制排隊系統，系統中有K個位置，c個服務臺獨立并行服務，cK。當K個位置已被顧客占用時，新到的顧客就自動離開，當系統中有空位置時，新到的顧客就進入系統排隊等待服務。74顧客到達為參數(0)的泊松過程；每個顧客所需的服務時間獨立、服從參數為(0)的負指數分布，且到達過程與服務過程彼此獨立；容量為K，即系統中有K個位置；系統中有c個服務臺獨立地平行工作，cK；當K個位置已被顧客占用

20、時，新到的顧客就自動離開，當系統中有空位置時，新到的顧客就進入系統排隊等待服務。75平均等待時間為： 在統計平衡下，進入系統接受服務的顧客的等待時間分布函數為：平均響應時間為：76例3、磁盤陣列的預取分析：77這是一個帶有Cache的磁盤陣列的性能分析。I/O請求經過Cache 管理平滑輸入速率。對應Cache的性能分析包括：cache讀、Cache寫、讀命中率、Cache的滿替換等，影響到Cache的服務響應。可應用M/M/1模型對應磁盤陣列，具有磁盤的讀寫等響應，可采用M/M/C模型。由于經過Cache，到達磁盤的速率不是負指數分布，實際可采用M/G/C模型或多個M/G/1模型。類似前端帶

21、有緩沖，后端帶有負載平衡過程的系統都可以以此進行分析。78例4：網絡并行系統的互連路由存儲轉發，對于到達的數據包經過隊列緩沖，按照優先權進行轉發。經過統計，網絡中包的到達速率符合泊松分布，對于包的大小一致，處理過程簡單，符合一般分布，采用M/G/1/ /PS這里需要考慮優先級的問題。79例5： 目前多核結構CMP 采用共享二級Cache的CMP結構，即每個核擁有私有的一級Cache，且所有處理器核共享二級Cache。基于總線的Cache一致性帶來總線的壓力。由于一級私有Cache的的命中率和一致性以及一致性協議都會影響到總線的性能。利用M/M/1模型可以分析總線的響應。但對總線的訪問請求率等都需要另外分析。Hydra多核結構80例6：Web服務與調度策略1.靜態調度靜態資源對應不同的應用，Web請求的速率分布不同；服務的響應因素：CPU時間，網絡時間等2.動態調度動態資源（如程序，輪循的時間片等）服務的響應受到多種因素的影響81例7：可靠性分析平均無故障時間，修復時間，冗余對可靠性的影響82例： 并行系統的資源分配和調度屬于動態資源的調度資源的可用性路徑延遲的影響83三、排隊模型分析小結1、傳統排隊模型的應用，該系統主要設定：輸入為泊松過程；服務時間為負指數