Hàng đợi và thứ tự phục vụ trong mô phỏng hỗ trợ
Mô phỏng một nhân viên phục vụ FIFO, tính thời điểm bắt đầu và thời gian chờ, rồi phân biệt thời gian chờ trung bình với độ dài hàng đợi trung bình.
Trong mô phỏng bàn hỗ trợ, hàng đợi vào trước, ra trước trả lời một câu hỏi: yêu cầu đang chờ nào được phục vụ tiếp theo? Nó không quyết định thời gian phục vụ hoặc sự kiện tương lai nào xảy ra trước. Nếu bạn đang viết mô phỏng cơ bản, tách các quyết định này giúp tránh việc âm thầm biến hàng đợi thành bộ lập lịch ưu tiên.
Bài dùng vòng lặp và tuple Python. Giả sử chỉ có một nhân viên, không ngắt công việc đang phục vụ, và mọi thời điểm đến cùng thời lượng phục vụ đều hữu hạn, không âm. Các yêu cầu đến cùng lúc giữ thứ tự trong đầu vào. Yêu cầu mới vào cuối hàng, yêu cầu chờ lâu nhất được lấy từ đầu. Thời gian trong ví dụ là đơn vị mô phỏng tùy chọn, không phải số đo từ một đội hỗ trợ thật.
Theo dõi bốn yêu cầu
A đến lúc không và cần bốn đơn vị phục vụ. B và C cùng đến lúc một, lần lượt cần hai và một đơn vị. D đến lúc tám và cần hai đơn vị. A chiếm nhân viên đến lúc bốn. B bắt đầu sau đó, rồi C, vì thứ tự đầu vào đã giải quyết trường hợp đến cùng lúc.
Các khoảng phục vụ là A [0, 4), B [4, 6), C [6, 7) và D [8, 10). Nhân viên rảnh từ bảy đến tám. Thời gian chờ bằng thời điểm bắt đầu trừ thời điểm đến: A bằng không, B bằng ba, C bằng năm, D bằng không. Trung bình là hai đơn vị dù không yêu cầu nào chờ đúng hai.
C cần ít thời gian phục vụ hơn B nhưng vẫn phải chờ sau B. Chọn C trước nghĩa là dùng chính sách khác. Ưu tiên công việc ngắn nhất, hạn chót hoặc phân loại cấp cứu có thể hợp lý trong bối cảnh riêng, nhưng cần quy tắc khác và không nên gọi là FIFO.
Vòng lặp theo sự kiện không cần tăng đồng hồ từng nhịp
Mô phỏng không cần tăng thời gian từng đơn vị. Khi nhân viên rảnh, nhảy thẳng đến lần đến kế tiếp. Sau khi chọn yêu cầu, nhảy đến lúc phục vụ xong. Trước khi chọn yêu cầu đang chờ tiếp theo, thêm mọi yêu cầu đã đến trước hoặc đúng thời điểm hiện tại.
from collections import deque
def simulate(requests):
jobs = sorted(requests, key=lambda job: job[1])
if any(arrival < 0 or duration < 0 for _, arrival, duration in jobs):
raise ValueError('times must be nonnegative')
waiting, result = deque(), []
next_job, now = 0, 0
while next_job < len(jobs) or waiting:
if not waiting:
now = max(now, jobs[next_job][1])
while next_job < len(jobs) and jobs[next_job][1] <= now:
waiting.append(jobs[next_job])
next_job += 1
name, arrival, duration = waiting.popleft()
start = now
now += duration
result.append((name, start, now, start - arrival))
return result
requests = [('A', 0, 4), ('B', 1, 2), ('C', 1, 1), ('D', 8, 2)]
assert simulate(requests) == [
('A', 0, 4, 0), ('B', 4, 6, 3),
('C', 6, 7, 5), ('D', 8, 10, 0),
]
assert simulate([]) == []Phép sắp xếp của Python ổn định, nên các thời điểm đến bằng nhau giữ thứ tự đầu vào. Cài đặt ghi nhận những yêu cầu đến trong lúc phục vụ khi nó đến mốc hoàn thành công việc. Thứ tự FIFO vẫn giống việc thêm đúng lúc đến, vì không ngắt phục vụ và không có quyết định nào giữa lúc bắt đầu với kết thúc. Cách này chưa đủ nếu mô hình phải đo độ dài hàng đợi liên tục hoặc xử lý hủy yêu cầu khi còn chờ.
Hàng đợi dùng deque. Python ghi rõ thêm và lấy phần tử ở hai đầu có hiệu năng xấp xỉ O(1). Xóa chỉ số không khỏi danh sách thường phải dịch các tham chiếu còn lại, nên một chuỗi dài thao tác lấy đầu có thể có tổng chi phí bậc hai. Ví dụ dùng danh sách làm hàng đợi giải thích lựa chọn cấu trúc này.
Bất biến của phòng chờ
Ngay trước khi lấy một yêu cầu, deque chứa mọi yêu cầu đã đến nhưng chưa được phục vụ, theo thứ tự đến và quy tắc xử lý hòa đã nêu. Những lần phục vụ trước chỉ loại phần tử đầu. Yêu cầu mới được thêm sau các yêu cầu đang đợi. Vì vậy, mỗi lần lấy đầu đều chọn yêu cầu đến sớm nhất còn đủ điều kiện.
Chỉ số next_job ngăn cách các yêu cầu tương lai với những yêu cầu đã được đưa vào hàng. Điều kiện vòng ngoài nói rằng vẫn còn việc nếu ít nhất một trong hai nhóm chưa rỗng. Khi cả hai đều rỗng, mỗi yêu cầu đã có đúng một kết quả. Với thời lượng phục vụ bằng không, thời gian mô phỏng có thể không tăng, nhưng việc lấy một yêu cầu vẫn làm tăng số công việc hoàn tất. Vòng lặp vì thế vẫn kết thúc.
Với n yêu cầu đầu vào bất kỳ, sắp xếp tốn O(n log n). Sau đó mỗi yêu cầu vào và ra deque một lần, nên phần mô phỏng sau sắp xếp tốn O(n). Nếu giao diện bảo đảm thời điểm đến đã có thứ tự, có thể bỏ lần sắp xếp đầu. Hàng đợi có thể giữ O(n) yêu cầu khi nhiều yêu cầu đến trước lúc một công việc dài hoàn tất. Danh sách kết quả cũng dùng O(n) bộ nhớ.
Hai giá trị trung bình có mẫu số khác nhau
Bốn thời gian chờ cộng lại thành tám đơn vị thời gian. Chia cho bốn yêu cầu cho thời gian chờ trung bình bằng hai. Độ dài hàng đợi trung bình theo thời gian lại trả lời câu hỏi khác: nếu chọn đều một thời điểm trong [0, 10), có bao nhiêu yêu cầu đang chờ, không tính yêu cầu đang được phục vụ?
Từ một đến bốn, B và C cùng chờ nên đóng góp 2 * 3 = 6 đơn vị yêu cầu nhân thời gian. Từ bốn đến sáu, chỉ C chờ, đóng góp thêm hai. Phần còn lại của cửa sổ quan sát không có yêu cầu chờ. Diện tích dưới đường độ dài hàng đợi là tám. Chia cho cửa sổ dài mười đơn vị cho trung bình 0,8 yêu cầu đang chờ.
Mỗi yêu cầu tạo một hình chữ nhật cao một trên khoảng chờ riêng [arrival, start). Cộng theo từng yêu cầu cho tổng thời gian chờ. Cắt cùng các hình chữ nhật theo trục thời gian cho diện tích độ dài hàng đợi. Đây là đẳng thức tính tổng cho những yêu cầu được quan sát đầy đủ. Nó không giả định phân phối xác suất và không tạo dự báo trạng thái ổn định cho lưu lượng tương lai.
from collections import defaultdict
def waiting_area(requests):
jobs = sorted(requests, key=lambda job: job[1])
records = simulate(jobs)
changes = defaultdict(int)
for (_, arrival, _), (_, start, _, _) in zip(jobs, records):
changes[arrival] += 1
changes[start] -= 1
area, count, previous = 0, 0, 0
for time in sorted(changes):
area += count * (time - previous)
count += changes[time]
previous = time
assert count == 0
return area
records = simulate(requests)
assert sum(wait for _, _, _, wait in records) == 8
assert waiting_area(requests) == 8
assert 8 / len(records) == 2
assert 8 / 10 == 0.8Các thay đổi tại cùng một thời điểm được cộng chung trước khi số lượng được dùng cho khoảng tiếp theo. Yêu cầu bắt đầu ngay lúc đến tự thêm rồi tự bớt tại cùng thời điểm, nên không tạo diện tích. Cách này cũng xử lý thời lượng phục vụ bằng không: yêu cầu có thể không tạo khoảng phục vụ nào nhưng vẫn đã chờ lâu. Hàm phụ sắp xếp các đầu mút để dựng lại số đo; phần việc O(n log n) bổ sung này được tính riêng với vòng lặp mô phỏng ban đầu.
Không nên ước lượng diện tích bằng cách chỉ đọc độ dài deque tại các mốc phục vụ xong. Mô phỏng gọn này hoãn việc thêm một số yêu cầu đến mốc đó, nên deque đang lưu không phải bản ghi liên tục của phòng chờ thực tế. Các khoảng từ lúc đến đến lúc bắt đầu khôi phục phần lịch sử còn thiếu. Nếu cửa sổ quan sát cắt ngang một lần chờ, hãy cắt khoảng chờ theo cửa sổ trước khi tính diện tích. Khi đó, toàn bộ thời gian chờ và phần đóng góp trong cửa sổ là hai lượng khác nhau.
Hãy thêm E đến lúc một, cần không đơn vị phục vụ, đặt sau C trong đầu vào. E bắt đầu lúc bảy và chờ sáu đơn vị. Tổng thời gian chờ tăng lên mười bốn; trung bình trên năm yêu cầu thành 2,8, dù thời điểm hoàn thành cuối vẫn là mười. Dự đoán các giá trị này trước khi chạy. Bài tập làm rõ mẫu số và khác biệt giữa thời gian phục vụ với thời gian chờ.
Mở rộng khi vượt ra ngoài các giả định
Hai nhân viên phục vụ cần cấu trúc riêng cho các sự kiện hoàn tất hoặc thời điểm rảnh kế tiếp. Chọn nhân viên sắp rảnh dựa trên thời gian, còn yêu cầu đang đợi vẫn có thể tuân theo FIFO. Hàng đợi ưu tiên có thể quản lý nhân viên mà không làm đổi chính sách phòng chờ. Trộn hai trách nhiệm vào một hàng thường làm mờ quy tắc thứ tự mà từng thao tác phải giữ.
Thời gian chờ thực tế còn phụ thuộc yêu cầu bị bỏ, thử lại, loại dịch vụ và cách yêu cầu đến. Ví dụ tất định này không đưa ra dự báo thống kê về đội nào. Khi chạy thử nghiệm, cần công bố phân phối thời điểm đến và thời gian phục vụ, giữ hạt giống ngẫu nhiên, rồi nói rõ đại lượng đang ước lượng. Ngay cả khi đó, trung bình vẫn che các lần chờ lâu nhất. Hãy giữ thời điểm bắt đầu và kết thúc của từng yêu cầu để xem các trường hợp chờ lâu, thay vì suy ra từ một giá trị trung bình.