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

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

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

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

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

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

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

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

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

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

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

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

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

13、務臺C個系統(tǒng)人數(shù)n人n c53狀態(tài)轉移圖01n-1nn(n+1)n+1. . . . .22n-1nccn+1. . . . .n c54狀態(tài)轉移方程55解差分方程，求得狀態(tài)概率為56 顧客等候的概率 計算有關指標平均正接受服務的顧客數(shù)=正忙的服務臺數(shù)解釋?57 隊長隊列長逗留時間及等待時間計算有關指標唯一58 某售票所有三個窗口，顧客到達服從Poisson過程，到達 = 0.9 人/分鐘，服務 =0.4人/分鐘。設顧客到達后依次排成一隊向空閑的窗口購票，如圖 窗口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平均等待時間和逗留時間顧客到達后必須等待概率62 以上例說明,設顧客到達后在每個窗口前各排一隊(其它條件不變),共三隊,每隊平均到達率為: 窗口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 模型指標 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結果比較單隊列好M/M/c型系統(tǒng)和c個M/M/1型系統(tǒng)的比較645. 若M/M/m模型將M/M/1模型的服務員修改為m個， 相關的分析結論有： 系統(tǒng)服務強度 =/(m*) 系統(tǒng)中沒有任務的概率 P0= 系統(tǒng)中有n個任務的概率 Pn=11m1nnm!n)m()1(!m)m(1-=r+r-r+rrmn,!mmPmn,!n)m(Pnm0n065 隊列中有

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

17、該系統(tǒng)可以用M/M/m排隊模型的結論：系統(tǒng)中沒有任務的概率 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個字符，信息長度（包括控制字符）近似負指數(shù)分布，平均長度176個字符。要使在任何瞬間緩沖器充滿的概率不超過0.005，問緩沖器的容量K至少應取多大？70解信息平均到達率240份/分4份/秒，800/176 4.546份/秒，/0.88。按M/M/1/K系統(tǒng)處理，緩沖器充滿的概率pK應滿足計算有：p250.009045，p260.004464。所以K26，即緩沖器的容量至少應為26個單位。71例2：設某計算機有4個終端，用戶按泊松流到達，平均每10分鐘到達1.5個用戶。假定每個用戶平均用機時間為20分鐘，用機時間服從負指數(shù)分布，如果4個終端被占用，則用戶到其它計算

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

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

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