Completely Fair Scheduler (CFS) chọn tiến trình có vruntime (thời gian ảo đã chạy) nhỏ nhất. Tiến trình có trọng số (weight) lớn hơn thì vruntime tăng chậm hơn nên được CPU nhiều hơn.
vruntime = 0. Hằng SLICE = 10. base = trọng số của tiến trình đầu tiên trong input.rounds lượt. Mỗi lượt:
vruntime nhỏ nhất; nếu bằng nhau chọn pid nhỏ hơn.pid vào thứ tự chạy.vruntime += (SLICE * base) // weight (chia nguyên).In thứ tự chạy (các pid) và vruntime cuối cùng của từng tiến trình (theo pid tăng dần).
2 tiến trình pid1 w=1, pid2 w=2. base=1. Lượt 1: cả hai vr=0 → chọn pid1 (pid nhỏ), pid1.vr += 101//1 = 10. Lượt 2: pid1=10, pid2=0 → chọn pid2, pid2.vr += 101//2 = 5.
Dòng 1: n.
n dòng: pid weight.
Dòng cuối: rounds.
1 ≤ n ≤ 50; 1 ≤ weight ≤ 1000; 1 ≤ rounds ≤ 1000.
Dòng 1: thứ tự rounds pid được chọn.
Tiếp n dòng: pid vruntime theo pid tăng dần.
Ví dụ:
Đầu vào:
2
1 1
2 2
4
Đầu ra:
1 2 2 1
1 20
2 10
Giải thích:
Đang tải editor...