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] HRRN — tỉ số đáp ứng cao nhất

    Cho N tiến trình với thời điểm đến (arrival) và thời gian CPU (burst). Mô phỏng thuật toán Highest Response Ratio Next (HRRN) — không ưu tiên ngắt:

    Thuật toán:

    1. Bắt đầu tại thời điểm nhỏ nhất. Duy trì thời gian hiện tại t.
    2. Trong các tiến trình đã đến (arrival ≤ t) và chưa chạy, tính tỉ số đáp ứng: RR = (thời gian chờ + burst) / burst, trong đó thời gian chờ = t − arrival.
    3. Chọn tiến trình có RR lớn nhất. Nếu bằng nhau, chọn ID nhỏ hơn.
    4. Cho tiến trình đó chạy đến hết (non-preemptive), cập nhật t.
    5. Nếu không có tiến trình nào đã đến, t nhảy tới arrival nhỏ nhất của các tiến trình chưa chạy (idle).

    In ra thời gian chờ trung bình (2 chữ số thập phân), với chờ = completion − arrival − burst.

    Ví dụ: arrival [0,2,4], burst [3,5,2]. Tại t=3 chọn giữa P2 (chờ1) và P3 chưa đến... mô phỏng theo công thức RR.

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

      Dòng đầu N. N dòng tiếp theo, dòng i gồm arrival burst của tiến trình ID i.

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

      1 ≤ N ≤ 1000; 0 ≤ arrival ≤ 100000; 1 ≤ burst ≤ 10000.

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

      Thời gian chờ trung bình, 2 chữ số thập phân.

    Ví dụ:

    Đầu vào:

    3
0 3 2 5 4 2

    Đầu ra:

    1.67

    Giải thích:

    t=0: chỉ P1 đến, chạy xong t=3 (chờ0). t=3: P2 đến(chờ1,RR=(1+5)/5=1.2). P3 chưa đến. Chạy P2 xong t=8(chờ1). t=8: P3 chờ=8-4=4, chạy xong t=10(chờ4). TB=(0+1+4)/3=1.67.

    Đang tải editor...