Máy tính Erlang C (hàng đợi M/M/c)

Máy tính Erlang C (hàng đợi M/M/c)

Phổ biến AI Skill PRO

Nhập phép tính

Để trống số máy chủ để xem kết quả ở số nhỏ nhất đạt mục tiêu. Mục tiêu 80% trong 20 giây chỉ là ví dụ: hãy nhập mục tiêu của bạn.

Công thức

B0=1,Bk=ABk−1k+ABk−1C(c,A)=cBcc−A(1−Bc),A<c\begin{aligned}&B_0=1,\quad B_k=\dfrac{A\,B_{k-1}}{k+A\,B_{k-1}}\\&C(c,A)=\dfrac{c\,B_c}{c-A\,(1-B_c)},\quad A<c\end{aligned}
Xem các bước tính (2)
  1. Thời gian chờ, thời gian trong hệ thống và độ dài hàng đợi

    Wq=C(c,A)cμ−λ,W=Wq+1μLq=λWq,L=λW\begin{aligned}&W_q=\dfrac{C(c,A)}{c\mu-\lambda},\quad W=W_q+\dfrac{1}{\mu}\\&L_q=\lambda W_q,\quad L=\lambda W\end{aligned}

    Thời gian chờ trung bình trong hàng, thời gian trung bình trong hệ thống và định luật Little.

  2. Mức phục vụ

    SL=P(Wq≤T)=1−C(c,A)e−(cμ−λ)T\begin{aligned}&\text{SL}=P(W_q\le T)\\&\quad=1-C(c,A)\,e^{-(c\mu-\lambda)T}\end{aligned}

    Tỷ lệ lượt đến phải chờ không quá T (phục vụ theo thứ tự đến trước).

Thống kê sử dụng

Quảng cáo

Kết quả

Số máy chủ cần để đạt mục tiêu
11
Mục tiêu: P(Wq ≤ 20 s) ≥ 80%
Mức phục vụ với số lượng đó: 80,92%
Số lượng hiện có chưa đạt mục tiêu. Hãy tăng thêm máy chủ đến con số ở trên.
Kết quả với c = 10
Lưu lượng tải (A = λ/μ)
8 Erl
Hệ số sử dụng (ρ = A/c)
80%
Hàng đợi ổn định (ρ < 1)
Có
Xác suất phải chờ (Erlang C)
40,92%
Mức phục vụ
65,36%
P(Wq ≤ 20 s)
Chờ lâu hơn T
34,64%
Thời gian chờ trung bình (Wq)
49,1 s
Thời gian trung bình trong hệ thống (W)
4,82 min
Độ dài hàng đợi trung bình (Lq)
1,637
Số lượt trung bình trong hệ thống (L)
9,637
Thời gian chờ trung bình của người phải chờ
2 min
Thời gian phục vụ trung bình
4 min
Số máy chủ và mức phục vụ
Số máy chủ (c) Hệ số sử dụng P(chờ) Chờ TB Mức phục vụ
10 hiện có 80% 40,9% 49,1 s 65,4%
11 72,7% 24,5% 19,6 s 80,9% đạt
12 66,7% 14% 8,39 s 90% đạt
13 61,5% 7,6% 3,65 s 95% đạt
14 57,1% 3,9% 1,57 s 97,6% đạt
Kiểm tra định luật Little: λ × W = L 0,033333/s × 289,1016 s = 9,637
Mô hình: M/M/c (Erlang C): lượt đến theo Poisson, thời gian phục vụ phân phối mũ, đến trước phục vụ trước, hàng chờ không giới hạn, không ai bỏ cuộc. Nếu người gọi có bỏ máy, mô hình Erlang A phù hợp hơn.

Báo lỗi nội dung trang này

Máy tính Erlang C trả lời câu hỏi gì?

"Cần bao nhiêu nhân viên trực tổng đài?" và "cần bao nhiêu máy chủ khi ra mắt?" thực chất là cùng một bài toán. Yêu cầu đến ngẫu nhiên, mỗi yêu cầu chiếm một máy chủ trong một khoảng thời gian, ai đến lúc mọi máy chủ đều bận thì phải xếp hàng. Công cụ này mô hình hoá tình huống đó bằng hàng đợi M/M/c và dùng công thức Erlang C, do kỹ sư người Đan Mạch A. K. Erlang công bố năm 1917, để tính xác suất phải chờ, thời gian chờ trung bình, độ dài hàng đợi và tỷ lệ lượt đến được phục vụ trong thời gian mục tiêu.

Sau đó công cụ tính ngược: tìm số máy chủ nhỏ nhất đạt mức phục vụ mục tiêu (và thời gian chờ trung bình tối đa nếu bạn đặt), kèm bảng ngắn quanh con số đó để thấy thêm hoặc bớt một máy chủ thay đổi ra sao.

Sơ đồ hàng đợi M/M/c: khách đến với tốc độ λ, chờ trong một hàng chung và được phục vụ bởi c máy chủ song song.
Hàng đợi M/M/c: khách đến ngẫu nhiên với tốc độ λ xếp thành một hàng chung, được phục vụ bởi c máy chủ giống nhau, mỗi máy mất thời gian phục vụ trung bình s.

Cách sử dụng

  • Tốc độ đến λ: số cuộc gọi, phiên chat, phiếu hỗ trợ hoặc request mỗi giây, phút hoặc giờ. Hãy dùng tốc độ của khung giờ cao điểm, không dùng trung bình cả ngày.
  • Thời gian phục vụ trung bình: thời gian xử lý trung bình cho mỗi lượt (thời gian nói chuyện cộng thời gian hoàn tất sau cuộc gọi ở tổng đài, hoặc thời gian xử lý request ở máy chủ). Bạn cũng có thể nhập tốc độ phục vụ μ của mỗi máy chủ.
  • Số máy chủ c: số nhân viên, worker, luồng hoặc máy phục vụ song song. Để trống nếu muốn xem kết quả ở số lượng được đề xuất.
  • Mục tiêu mức phục vụ: tỷ lệ lượt đến phải chờ không quá T. Giá trị mặc định 80% trong 20 giây chỉ là ví dụ thường gặp, không phải quy định hay tiêu chuẩn. Hãy nhập mục tiêu của bạn.

Công cụ cũng dùng được cho bài toán năng lực hệ thống IT: nhập số request mỗi giây, thời gian phục vụ tính bằng mili giây, và hiểu "máy chủ" là số worker chạy đồng thời.

Công thức

Với tốc độ đến λ và thời gian phục vụ trung bình s (tốc độ phục vụ μ = 1/s), lưu lượng tải là A = λ/μ erlang và hệ số sử dụng là ρ = A/c. Hàng đợi chỉ ổn định khi A < c. Nếu không, hàng đợi dài mãi và công cụ báo rõ điều đó thay vì hiện một con số.

Xác suất một lượt đến phải chờ là Erlang C, C(c, A). Công cụ tính qua đệ quy Erlang B: Bk = A·Bk−1 / (k + A·Bk−1) và C = c·B / (c − A(1 − B)). Cách này không dùng giai thừa nên vẫn chính xác với hàng nghìn máy chủ. Từ C suy ra:

  • thời gian chờ trung bình trong hàng Wq = C / (cμ − λ), thời gian trung bình trong hệ thống W = Wq + 1/μ;
  • độ dài hàng đợi trung bình Lq = λWq, số lượt trung bình trong hệ thống L = Lq + A;
  • mức phục vụ P(Wq ≤ T) = 1 − C·e−(cμ−λ)T (đến trước phục vụ trước).

Các kết quả thoả định luật Little L = λW, được hiện ngay trong kết quả để đối chiếu. Bạn có thể kiểm tra chéo bằng công cụ tính throughput (định luật Little).

Quảng cáo
Biểu đồ xác suất chờ Erlang C giảm khi thêm máy chủ, với số máy chủ đầu tiên nằm dưới mục tiêu được làm nổi bật.
Xác suất phải chờ, C(c, A), giảm mạnh khi thêm máy chủ; số c đầu tiên đạt mục tiêu chính là đáp án bố trí nhân lực.

Ví dụ minh hoạ

Một bộ phận hỗ trợ nhận 120 cuộc gọi mỗi giờ (2 cuộc mỗi phút), thời gian xử lý trung bình 4 phút, nên A = 2 × 4 = 8 erlang. Với 10 nhân viên, hệ số sử dụng là 80%, 40,9% người gọi phải chờ, thời gian chờ trung bình khoảng 49 giây và chỉ 65,4% cuộc gọi được trả lời trong 20 giây. Với 11 nhân viên, xác suất phải chờ giảm còn 24,5%, thời gian chờ trung bình còn 19,6 giây và mức phục vụ lên 80,9%. Vậy 11 nhân viên đạt mục tiêu 80% trong 20 giây. Với 12 nhân viên con số là 90,0%.

Đối chiếu sách giáo khoa: trong Teletraffic Engineering and Network Planning của Iversen (Ví dụ 9.3.1), hệ thống có lưu lượng 20 erlang, thời gian phục vụ trung bình 100 giây và 32 kênh có thời gian chờ trung bình 0,075 giây. Công cụ này cho 0,0747 giây.

Ví dụ IT: 5.000 request mỗi giây, mỗi request 120 ms, tức A = 600 erlang. Để 99% request bắt đầu được xử lý trong 50 ms, cần 610 worker đồng thời. Khi đó hệ số sử dụng là 98,4% và thời gian chờ trung bình khoảng 7 ms.

Giả định và giới hạn

  • Lượt đến ngẫu nhiên và độc lập (quá trình Poisson), thời gian phục vụ có phân phối mũ.
  • Các máy chủ giống nhau, phục vụ theo thứ tự đến trước, hàng chờ không giới hạn.
  • Không ai bỏ cuộc. Thực tế người gọi có cúp máy, khi đó Erlang C ước lượng thời gian chờ và số nhân sự cần cao hơn thực tế. Mô hình Erlang A (M/M/N+M, Garnett, Mandelbaum & Reiman, 2002) có tính đến việc bỏ cuộc.
  • Kết quả là số nhân viên thực sự sẵn sàng nghe máy. Cần cộng thêm thời gian nghỉ, đào tạo và vắng mặt (shrinkage).
  • Lưu lượng dồn cục, gửi lại request và thời gian phục vụ dao động mạnh thường làm hàng đợi tệ hơn mô hình. Hãy coi kết quả là mức tối thiểu và kiểm chứng bằng tải thật.

Muốn xem giới hạn tăng tốc khi chạy song song một tác vụ, dùng máy tính định luật Amdahl.

Nguồn tham khảo

Cập nhật lần cuối:

Phổ biến nhất trong Toán học và Thống kê

Xem tất cả máy tính Toán học và Thống kê