Lottery Scheduling — đếm số lượt thắng

Trong lottery scheduling, mỗi tiến trình được cấp một số vé (ticket). Mỗi lượt lập lịch, bộ lập lịch bốc một số ngẫu nhiên d. Để kết quả xác định, ở đây số bốc d được cho sẵn.

Thuật toán xác định người thắng mỗi lượt

1. Tính tổng số vé total của tất cả tiến trình (mọi tiến trình luôn trong cuộc, total không đổi).
2. Lấy r = d % total (chỉ số vé trúng, đánh số từ 0).
3. Duyệt các tiến trình theo thứ tự pid tăng dần, cộng dồn số vé cum. Tiến trình đầu tiên có cum > r là người thắng lượt đó.
4. Tăng bộ đếm thắng của tiến trình đó lên 1.

Sau khi xử lý hết các lượt bốc, in số lượt thắng của từng tiến trình theo pid tăng dần.

Ví dụ

2 tiến trình: pid 1 có 3 vé, pid 2 có 2 vé → total = 5. Vé được đánh số: pid 1 chiếm vé 0,1,2; pid 2 chiếm vé 3,4. Với d = 4 → r = 4 % 5 = 4 → vé 4 thuộc pid 2 → pid 2 thắng.