首頁 › 半導體、電子電路與資訊計算工具
排隊理論計算器(M/M/1、M/M/c)
輸入到達率、平均服務時間與服務台數量,即可依排隊理論的 M/M/1 模型(服務台有多個時為 M/M/c)計算使用率、平均等候時間、平均回應時間與等候中的數量。可用來驗算考試常見的「ρ/(1−ρ) × 平均服務時間」,並以圖表看出使用率升高時等候時間增加得多麼急遽。
計算結果
使用率 ρ 達到 100% 以上,處理速度跟不上到達的速度,佇列會無限制地增長。由於等候時間沒有穩定值,因此不予顯示。請降低到達率、縮短平均服務時間,或增加服務台。
使用率 ρ –
服務率 μ –
需要等候的機率 –
等候中的數量 Lq –
系統中的數量 L –
平均等候時間 Wq –
平均系統停留時間(回應時間)W –
使用率與等候時間的關係
計算的前提是隨機到達(卜瓦松到達)、服務時間服從指數分布、先到先服務(FIFO)、等候空間沒有上限,且經過足夠長的時間後已進入穩態。
以圖表檢視
橫軸的輸入
縱軸的結果
其他輸入維持目前的值,只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
M/M/1 是什麼:肯德爾記號與前提
M/M/1 是用肯德爾記號表示的排隊模型,依序列出「到達的分布/服務時間的分布/服務台 數量」。第一個 M 表示到達是隨機的(卜瓦松到達,到達間隔服從指數分布 ),第二個 M 表示服務時間服從指數分布,最後的 1 表示只有一個服務台。M 是 Markov(馬可夫性質,即無記憶性)的字首,意思是距離下一次到達或服務結束的時間,不受已經經過多少時間的影響。此外還假設等候空間沒有上限、依到達順序服務(FIFO),並考慮經過足夠長的時間後平均值已穩定的穩態。銀行櫃台、送往伺服器的請求、磁碟的輸入輸出、在路由器等待送出的封包等許多等候問題,都常以這個模型近似。
公式與考試的計算步驟
首先求出使用率 ρ = λ × Ts,其中 λ 是單位時間內到達的件數,Ts 是服務一件所需的平均時間,ρ 則是服務台 忙碌的時間比例。接著計算平均等候時間 Wq = ρ/(1 − ρ) × Ts,以及平均回應時間(系統停留時間)W = Wq + Ts = Ts/(1 − ρ)。至於排隊的長度,等候中的數量為 Lq = ρ²/(1 − ρ),包含正在服務者在內的系統中數量為 L = ρ/(1 − ρ)。以預設值 λ = 0.05 件/秒(每分鐘 3 件)、Ts = 10 秒計算,ρ = 0.5、Wq = 0.5/0.5 × 10 = 10 秒、W = 20 秒、Lq = 0.5、L = 1。考試題目也可依「求出 ρ → 乘上 ρ/(1 − ρ) 得到等候時間 → 若問回應時間再加上 Ts」的順序解題。
使用率接近 100% 時等候時間急遽增加
由於 Wq/Ts = ρ/(1 − ρ),使用率 50% 時等候時間與服務時間相同,為 1 倍,但 80% 時為 4 倍,90% 時為 9 倍,95% 時則為 19 倍。分母的 1 − ρ 是服務台 空閒的時間比例,當它趨近 0 時,就沒有餘裕消化因到達碰巧重疊而形成的佇列 。圖表中的曲線在右端急遽上升就是這個原因,只要把使用率從 80% 提高到 90%,等候時間就會增加到 2 倍以上(4 倍 → 9 倍)。反過來說,若讓使用率 90%(Ts = 10 秒、Wq = 90 秒)的服務台服務速度加快一成,使 Ts = 9 秒,則 ρ = 0.81,Wq 會縮短到約 38 秒,不到原來的一半。因此在設計 CPU、磁碟、網路線路與客服中心時,不會讓平均使用率接近 100%,而是讓尖峰時段也保有餘裕。
以利特爾法則連結數量與時間
利特爾法則 指出,系統中的平均數量 L、到達率 λ 與每件在系統中停留的平均時間 W 之間有 L = λW 的關係,只看等候的部分也成立 Lq = λWq。以預設值計算,λ = 0.05 件/秒、W = 20 秒,因此 L = 0.05 × 20 = 1 件、Lq = 0.05 × 10 = 0.5 件,與計算器的結果一致。兩者的差 L − Lq = λ × Ts 是正在接受服務的平均數量,只有一個服務台 時就等於使用率 ρ。這個法則不受到達與服務時間分布的影響,只要系統穩定就成立,因此在 M/M/1 的前提不成立時也能使用。例如每秒收到 100 件請求、每件平均耗時 0.2 秒的伺服器,平均有 20 件同時在處理中。
多個服務台的 M/M/c:排成一列比較快
有 c 個服務台 的 M/M/c,使用率為 ρ = λ × Ts/c,所有服務台都在忙而必須等候的機率由 Erlang C 公式求得,平均等候時間為 Wq = 等候機率 × Ts/(c(1 − ρ))。把預設的到達率加倍為 λ = 0.1 件/秒並設兩個服務台,ρ 仍為 0.5,需要等候的機率為 1/3,Wq ≈ 3.33 秒,W ≈ 13.3 秒。若改為把同樣的到達平均分給兩個服務台、各自排隊,每一個都成為 λ = 0.05 件/秒的 M/M/1 ,Wq = 10 秒、W = 20 秒,因此排成一列、由空出來的服務台依序叫號,等候時間只有三分之一。分開排隊時,可能發生一個服務台閒著、另一個服務台前卻有人在排隊的情形。在圖表中將 c 設為 2,使用率 80% 時的 Wq 會降到 Ts 的約 1.78 倍(c = 1 時為 4 倍)。銀行與機場採用單一排隊線,以及伺服器的執行緒從共用佇列 取出工作的設計,都是運用這個性質。
練習效能評估題目
A 500件 B 20件 C 0.002件
查看答案與解析 正確答案:B. 20件
利特爾法則 的關係是:系統中的平均數量L = 到達率λ × 每件停留於系統中的平均時間W。每秒到達100件,各停留0.2秒,所以平均有20件同時在處理。運用這個關係,就能估算所需的執行緒數量與緩衝區的大小。例如要將記憶體頻寬全部用盡,需要同時有多少未完成的請求,也可用同樣的想法求得。
A 急遽變長(使用率越高,增加的幅度越大) B 與使用率成比例,逐漸變長 C 使用率越高,等待時間越短
查看答案與解析 正確答案:A. 急遽變長(使用率越高,增加的幅度越大)
當請求不規則地到達時,即使伺服器有空閒的時間,只要碰巧請求重疊,就會形成等待佇列 。使用率越高,空閒的時間越少,形成的佇列就越難以消除,因此等待時間會以使用率為ρ時類似1÷(1−ρ)的形式急遽增加。例如使用率50%與90%的等待時間會有數倍的差距。因此在重視回應速度的系統中,會在使用率上保留餘裕。
A 即使平均很好,仍可能有部分請求非常慢,而在需要等待許多元件回應的處理中,這些慢的回應會決定整體的緩慢程度 B 第99百分位數的值一定比平均小 C 因為無法計算平均值
查看答案與解析 正確答案:A. 即使平均很好,仍可能有部分請求非常慢,而在需要等待許多元件回應的處理中,這些慢的回應會決定整體的緩慢程度
回應時間的分布往往呈現大部分很快、只有極少部分非常慢的形狀。只看平均會隱藏這些慢的部分。再者,在顯示一個畫面需要等待100個元件回應的處理中,只要有任何一個慢,整體就會變慢,所以那1%的慢回應會影響大部分的使用者。因此要以慢的一側的值(尾端延遲 ,tail latency)為目標來管理。
A 0.8 B 1.25 C 3
查看答案與解析 正確答案:A. 0.8
使用率ρ是到達率λ與平均服務時間Ts的乘積,表示窗口忙碌時間的比例。統一單位後,4分鐘 = 1/15小時,因此 ρ = 12 × 1/15 = 0.8。使用服務率 μ = 每小時15件,以 ρ = λ/μ = 12/15 求得,結果也相同。
A 20秒 B 45秒 C 60秒
查看答案與解析 正確答案:C. 60秒
使用率為 ρ = 每分鐘3件 × 15秒 ÷ 60秒 = 0.75。平均等候時間為 Wq = ρ/(1 − ρ) × Ts = 0.75/0.25 × 15 = 45秒,加上處理時間15秒,平均回應時間為 45 + 15 = 60秒。以 Ts/(1 − ρ) = 15/0.25 = 60秒求得,結果也相同。
A 1.125倍 B 2倍 C 2.25倍
查看答案與解析 正確答案:C. 2.25倍
Wq = ρ/(1 − ρ) × Ts,而Ts不變,因此要求 ρ/(1 − ρ) 的比。ρ = 0.8 時為 0.8/0.2 = 4,ρ = 0.9 時為 0.9/0.1 = 9,因此為 9 ÷ 4 = 2.25倍。使用率接近1時,1 − ρ 接近0,因此使用率稍微增加,等候時間就會急遽增長。
A 方式A較短,因為行列分成2條,每條的到達率減半 B 方式B較短,因為在方式A中,即使一個窗口有行列,另一個窗口也可能是空的 C 兩者相同,因為窗口數目與處理速度相同時,無論行列如何排,平均等候時間都不變
查看答案與解析 正確答案:B. 方式B較短,因為在方式A中,即使一個窗口有行列,另一個窗口也可能是空的
方式A可視為到達率減半的2個M/M/1 並列。方式B是2個窗口共用1條行列的M/M/2,只要有1個窗口空著,就能不必等候而接受服務。例如平均服務時間1分鐘、整體到達率每分鐘1件(使用率0.5)時,方式A的平均等候時間為 0.5/(1 − 0.5) × 1 = 1分鐘,而方式B約為0.33分鐘。因此在銀行窗口或伺服器的處理中,常採用由多個窗口共用1條行列的方式。
A 每秒4.0件 B 每秒4.2件 C 每秒5.0件
查看答案與解析 正確答案:A. 每秒4.0件
平均回應時間為 W = Ts/(1 − ρ),由 0.2/(1 − ρ) ≤ 1.0 得 1 − ρ ≥ 0.2,也就是 ρ ≤ 0.8。由於 ρ = λ × Ts,因此 λ ≤ 0.8 ÷ 0.2 = 每秒4.0件。到達率為每秒5.0件時,使用率為1,行列會無限增長。
常見問題
題目以「每小時 30 件」的形式給出時,到達率 λ 該怎麼輸入?
要讓到達率與平均服務時間的時間單位一致。若每小時到達 30 件、平均服務時間為 1.5 分鐘,就把時間單位設為「分鐘」,輸入 λ = 30 ÷ 60 = 0.5、Ts = 1.5。此時 ρ = 0.5 × 1.5 = 0.75,Wq = 0.75/0.25 × 1.5 = 4.5 分鐘,W = 6 分鐘。若題目給的是平均到達間隔 2 分鐘,到達率就是它的倒數 λ = 1/2 = 0.5 件/分鐘。
等候時間與回應時間有什麼不同?
平均等候時間 Wq 是從到達到開始接受服務為止,在佇列中排隊的時間。回應時間(系統停留時間)W 則再加上服務時間,是從到達到完成為止的時間,W = Wq + Ts。以預設值計算,Wq = 10 秒、W = 20 秒。請確認題目問的是哪一個,若是回應時間別忘了加上 Ts。
使用率 ρ 達到 1 以上會怎樣?
平均而言到達的工作量不少於能處理的量,因此佇列會隨時間無限制地增長,平均等候時間沒有確定的值。即使 ρ 剛好等於 1,只要到達與服務時間隨機變動,佇列就不會穩定。此計算器會顯示警告,而不顯示等候時間。請以增加服務台、加快服務或減少到達等方式,讓 ρ = λ × Ts/c 小於 1。
M/M/1 的前提不成立時會怎樣?
若每次服務的時間都相同、沒有變動,模型就是 M/D/1,Wq = ρ/(2(1 − ρ)) × Ts,剛好是 M/M/1 的一半;以預設值計算,Wq 會從 10 秒變成 5 秒。對一般的服務時間(M/G/1),Pollaczek–Khinchine 公式 Wq = (1 + Cs²)/2 × ρ/(1 − ρ) × Ts 顯示,服務時間的變異(變異係數 Cs)越大,等候時間越長。到達集中成批湧入時,等候時間一般也會比 M/M/1 的預測更長。
時間單位該怎麼選?
只要到達率與平均服務時間使用相同的單位,選哪一種都可以。若選「分鐘」,λ 就輸入每分鐘的件數、Ts 以分鐘輸入,Wq 與 W 也以分鐘顯示。使用率、需要等候的機率、Lq 與 L 都是沒有單位的數,換了單位數值也不變。例如把預設條件改用分鐘輸入,為 λ = 3、Ts = 1/6 ≈ 0.1667,得到 ρ = 0.5、Wq ≈ 0.1667 分鐘(10 秒)。