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 Unix] Kiểm soát thu nhận SCHED_DEADLINE

    Admission control cho SCHED_DEADLINE

    Trước khi nhận một tiến trình SCHED_DEADLINE, nhân Linux kiểm tra điều kiện khả thi: tổng utilization (mức sử dụng CPU) của tất cả tiến trình deadline không được vượt quá năng lực CPU. Mỗi tiến trình đóng góp U = runtime / period. Trên hệ một CPU, điều kiện là tổng U ≤ 1.

    Xét các tiến trình lần lượt theo thứ tự nhập: nhận một tiến trình nếu sau khi thêm nó, tổng utilization vẫn ≤ 1; ngược lại từ chối (bỏ qua) nó. Để tránh sai số, hãy tính bằng phân số.

    In danh sách PID được nhận (theo thứ tự nhập, hoặc none), rồi tổng utilization cuối cùng (2 chữ số thập phân).

    Ví dụ

    Input:

    2
1 1 2
2 1 2

    Output:

    1 2
1.00

    Mỗi tiến trình U=0.5; tổng 1.0 ≤ 1 nên nhận cả hai.

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

      Dòng đầu n. Mỗi dòng tiếp theo: PID runtime period.

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

      1 ≤ n ≤ 1000; 1 ≤ runtime ≤ period ≤ 10^6.

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

      Dòng 1: các PID được nhận (cách nhau dấu cách) hoặc none. Dòng 2: tổng utilization (2 chữ số).

    Ví dụ:

    Đầu vào:

    2
1 1 2
2 1 2

    Đầu ra:

    1 2
1.00

    Giải thích:

    Mỗi tiến trình U=1/2; sau khi nhận cả hai tổng = 1.0 ≤ 1 nên đều được nhận.

    Đang tải editor...