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] SJF không ưu tiên - thời gian chờ trung bình

    Mô phỏng thuật toán SJF (Shortest Job First) không ưu tiên (non-preemptive) và tính thời gian chờ trung bình.

    Tại mỗi thời điểm CPU rảnh, trong số các tiến trình đã đến và chưa chạy, chọn tiến trình có burst nhỏ nhất. Tie-break: burst bằng nhau → arrival nhỏ hơn trước → vẫn bằng thì ID nhỏ hơn trước. Khi đã chọn, tiến trình chạy đến hết (không bị ngắt).

    Thuật toán từng bước:

    1. time = 0, đánh dấu mọi tiến trình chưa xong.
    2. Lặp đến khi mọi tiến trình xong: tìm tập tiến trình có arrival ≤ time và chưa xong. Nếu rỗng, nhảy time tới arrival sớm nhất của tiến trình chưa xong.
    3. Trong tập đó chọn theo tie-break ở trên. Cộng time - arrival vào tổng chờ, rồi time += burst, đánh dấu xong.
    4. In tổng chờ / n.

    Ví dụ: (0,7),(2,4),(4,1),(5,4). Trình tự chạy: P0(0..7), rồi trong số đã đến chọn P2(burst1) 7..8, rồi P1(burst4) 8..12, rồi P3 12..16. Chờ = 0,6,3,7 → TB = 4.00.

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

      Dòng đầu n. n dòng arrival burst. ID đánh từ 0 theo thứ tự nhập.

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

      1 ≤ n ≤ 1000; 0 ≤ arrival ≤ 10000; 1 ≤ burst ≤ 10000.

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

      Thời gian chờ trung bình, làm tròn 2 chữ số ({:.2f}).

    Ví dụ:

    Đầu vào:

    4
0 7
2 4
4 1
5 4

    Đầu ra:

    4.00

    Giải thích:

    P0 chạy 0..7 (chờ 0). Tại t=7 đã đến {P1,P2,P3}; burst nhỏ nhất P2=1 → chạy 7..8 (chờ 7-4=3). Còn {P1,P3} cùng burst 4, arrival P1=2<P3=5 → P1 chạy 8..12 (chờ 8-2=6). P3 chạy 12..16 (chờ 12-5=7). Tổng=0+6+3+7=16, TB=16/4=4.00.

    Đang tải editor...