排隊理論計算器(M/M/1、M/M/c)

輸入到達率、平均服務時間與服務台數量,即可依排隊理論的 M/M/1 模型(服務台有多個時為 M/M/c)計算使用率、平均等候時間、平均回應時間與等候中的數量。可用來驗算考試常見的「ρ/(1−ρ) × 平均服務時間」,並以圖表看出使用率升高時等候時間增加得多麼急遽。

輸入條件

計算結果

使用率 ρ
–
服務率 μ
–
需要等候的機率
–
等候中的數量 Lq
–
系統中的數量 L
–
平均等候時間 Wq
–
平均系統停留時間(回應時間)W
–

使用率與等候時間的關係

計算的前提是隨機到達(卜瓦松到達)、服務時間服從指數分布、先到先服務(FIFO)、等候空間沒有上限,且經過足夠長的時間後已進入穩態。

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 倍)。銀行與機場採用單一排隊線,以及伺服器的執行緒從共用佇列取出工作的設計,都是運用這個性質。

練習效能評估題目

某伺服器每秒收到100件請求,每件的處理平均花0.2秒(假設為穩態)。伺服器內同時處理中的請求平均有幾件(利特爾法則,Little's law)?

  1. A500件
  2. B20件
  3. C0.002件
查看答案與解析

正確答案:B. 20件

利特爾法則的關係是:系統中的平均數量L = 到達率λ × 每件停留於系統中的平均時間W。每秒到達100件,各停留0.2秒,所以平均有20件同時在處理。運用這個關係,就能估算所需的執行緒數量與緩衝區的大小。例如要將記憶體頻寬全部用盡,需要同時有多少未完成的請求,也可用同樣的想法求得。

當伺服器的使用率(忙碌時間的比例)接近100%時,請求的等待時間會如何變化?

  1. A急遽變長(使用率越高,增加的幅度越大)
  2. B與使用率成比例,逐漸變長
  3. C使用率越高,等待時間越短
查看答案與解析

正確答案:A. 急遽變長(使用率越高,增加的幅度越大)

當請求不規則地到達時,即使伺服器有空閒的時間,只要碰巧請求重疊,就會形成等待佇列。使用率越高,空閒的時間越少,形成的佇列就越難以消除,因此等待時間會以使用率為ρ時類似1÷(1−ρ)的形式急遽增加。例如使用率50%與90%的等待時間會有數倍的差距。因此在重視回應速度的系統中,會在使用率上保留餘裕。

評估Web服務的回應時間時,常不只看平均值,還會看第99百分位數(從慢的一端算起1%的分界)的值,其理由下列何者正確?

  1. A即使平均很好,仍可能有部分請求非常慢,而在需要等待許多元件回應的處理中,這些慢的回應會決定整體的緩慢程度
  2. B第99百分位數的值一定比平均小
  3. C因為無法計算平均值
查看答案與解析

正確答案:A. 即使平均很好,仍可能有部分請求非常慢,而在需要等待許多元件回應的處理中,這些慢的回應會決定整體的緩慢程度

回應時間的分布往往呈現大部分很快、只有極少部分非常慢的形狀。只看平均會隱藏這些慢的部分。再者,在顯示一個畫面需要等待100個元件回應的處理中,只要有任何一個慢,整體就會變慢,所以那1%的慢回應會影響大部分的使用者。因此要以慢的一側的值(尾端延遲,tail latency)為目標來管理。

某伺服器每分鐘平均收到3件請求,每件平均需要15秒處理,將其視為M/M/1等候系統。從請求到達到處理完成的平均時間(平均回應時間)為下列何者?

  1. A20秒
  2. B45秒
  3. C60秒
查看答案與解析

正確答案: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秒求得,結果也相同。

在可視為M/M/1等候系統的伺服器中,平均服務時間不變而到達率增加,使用率從0.8上升到0.9。平均等候時間Wq(在行列中等候的時間)變為幾倍?最接近的是下列何者?

  1. A1.125倍
  2. B2倍
  3. C2.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,因此使用率稍微增加,等候時間就會急遽增長。

有2個速度相同的窗口。方式A中,使用者到達時以相等機率選擇其中一個窗口,排在各窗口自己的行列中。方式B中,使用者排在1條行列中,依序到空出來的窗口接受服務。到達為隨機,且整體的到達率與處理速度兩種方式都相同。關於平均等候時間的比較,下列何者適當?

  1. A方式A較短,因為行列分成2條,每條的到達率減半
  2. B方式B較短,因為在方式A中,即使一個窗口有行列,另一個窗口也可能是空的
  3. 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條行列的方式。

將平均服務時間0.2秒的伺服器視為M/M/1等候系統。要把平均回應時間(等候時間與處理時間的合計)壓在1.0秒以下時,可接受的到達率上限最接近下列何者?

  1. A每秒4.0件
  2. B每秒4.2件
  3. 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 秒)。

相關術語

利特爾法則(Little's law) 吞吐量(Throughput) 尾端延遲(Tail latency) 批次大小(Batch size) 延遲隱藏(Latency hiding)

相關計算工具

半導體、電子電路與資訊計算工具 →