【VIP專享】第四章-排隊論在計算機(jī)性能評價中應(yīng)用-148課件

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17、該系統(tǒng)可以用M/M/m排隊模型的結(jié)論：系統(tǒng)中沒有任務(wù)的概率 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平均響應(yīng)時間 = 平均等待時間+平均服務(wù)時間 = 0.02+0.0038=0.0238(s) 兩個慢速磁盤的等待時間是1個慢速硬盤的1/21，是1個快速硬盤的等待時間的1/1.76。69例1設(shè)有一個信息交換中心，信息流為泊松流，每分鐘到達(dá)

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

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

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

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