Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Hệ điều hành] Completely Fair — đếm CPU theo nice

    Completely Fair Scheduler — đếm CPU theo nice

    Mở rộng CFS: mỗi tiến trình có giá trị nice xác định trọng số (weight):

    • nice ≥ 0: weight = 1024 >> nice (dịch phải).
    • nice < 0: weight = 1024 << (-nice) (dịch trái).
    • Nếu kết quả < 1 thì lấy weight = 1.

    Thuật toán

    • Mọi tiến trình vruntime = 0, lượng CPU đã dùng cpu = 0, thời gian cần rem. SLICE = 1.
    • Lặp đến khi mọi rem = 0: chọn tiến trình còn rem > 0 có vruntime nhỏ nhất (tie-break pid nhỏ), chạy 1 đơn vị: rem -= 1, cpu += 1, vruntime += (SLICE*1024) // weight.

    In pid cpu cho từng tiến trình theo pid tăng dần.

    Ví dụ

    pid1 nice=0 → w=1024; pid2 nice=1 → w=512. Khi cả hai cùng cần CPU, pid1 (weight gấp đôi) sẽ nhận xấp xỉ gấp đôi số đơn vị CPU so với pid2.

    • Định dạng đầu vào:

      Dòng 1: n. n dòng: pid nice burst.

    • Ràng buộc đầu vào:

      1 ≤ n ≤ 50; -5 ≤ nice ≤ 10; 1 ≤ burst ≤ 200.

    • Định dạng đầu ra:

      n dòng: pid tổng_đơn_vị_CPU theo pid tăng dần.

    Ví dụ:

    Đầu vào:

    2
1 0 4
2 1 4

    Đầu ra:

    1 4
2 4

    Giải thích:

    w1=1024, w2=512. vruntime của pid2 tăng gấp đôi pid1, nên pid1 được chọn thường xuyên hơn cho tới khi cả hai chạy hết burst của mình. Kết quả: pid1 4, pid2 4 (mỗi tiến trình chạy đủ burst của nó).

    Đang tải editor...