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] Đếm tiến trình đói CPU và thời gian chờ lớn nhất

    Cho N tiến trình (tất cả đến tại thời điểm 0) với burst, lập lịch theo độ ưu tiên KHÔNG ưu tiên ngắt (chọn tiến trình chưa chạy có priority NHỎ nhất; nếu bằng chọn ID nhỏ hơn; chạy đến hết).

    Một tiến trình bị coi là "đói CPU" (starvation) nếu thời gian chờ của nó lớn hơn ngưỡng K cho trước (chờ = thời điểm bắt đầu chạy − arrival = thời điểm bắt đầu chạy, vì arrival=0).

    Thuật toán:

    1. Mô phỏng lập lịch ưu tiên non-preemptive, ghi lại thời điểm bắt đầu của mỗi tiến trình.
    2. Đếm số tiến trình có thời gian chờ > K.

    In ra hai số cách nhau dấu cách: số tiến trình bị đói CPU, và thời gian chờ lớn nhất trong tất cả tiến trình.

    Ví dụ: burst [4,3,2], priority [3,1,2], K=3. Thứ tự chạy P2(pri1):0..3, P3(pri2):3..5, P1(pri3):5..9. Chờ: P2=0,P3=3,P1=5. >3 chỉ P1 => 1 tiến trình đói, maxwait=5.

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

      Dòng đầu: N K. N dòng tiếp: burst priority của tiến trình ID i.

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

      1 ≤ N ≤ 100000; 0 ≤ K ≤ 10^9; 1 ≤ burst ≤ 10^6; 1 ≤ priority ≤ 10^9.

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

      Hai số nguyên: số tiến trình đói CPU, thời gian chờ lớn nhất.

    Ví dụ:

    Đầu vào:

    3 3
4 3
3 1
2 2

    Đầu ra:

    1 5

    Giải thích:

    Thứ tự ưu tiên: P2(1),P3(2),P1(3). Chờ: P2=0, P3=3, P1=5. >3: chỉ P1 => 1 đói. maxwait=5.

    Đang tải editor...