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] FCFS có arrival và khoảng trống idle

    Cho N tiến trình với thời điểm đến (arrival) và thời gian CPU (burst), lập lịch FCFS (theo arrival tăng dần; nếu trùng arrival thì theo ID tăng dần).

    Trong FCFS, nếu khi một tiến trình hoàn thành mà tiến trình kế tiếp chưa đến, CPU phải nằm không (idle) cho tới khi tiến trình kế tiếp đến — đó là một khoảng trống (idle gap).

    Thuật toán:

    1. Sắp xếp tiến trình theo (arrival, ID).
    2. Duy trì thời gian t = 0. Với mỗi tiến trình theo thứ tự: nếu t < arrival thì cộng (arrival − t) vào tổng idle và đặt t = arrival. Sau đó t += burst.

    In ra hai số cách nhau bởi dấu cách: tổng thời gian CPU nằm không (total idle), và thời điểm CPU kết thúc toàn bộ (makespan).

    Ví dụ: arrival [0,5,6], burst [3,2,2]. P1: 0..3. Idle 3..5 (2 đv). P2:5..7. P3:7..9. Idle=2, makespan=9.

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

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

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

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

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

      Hai số nguyên: tổng thời gian idle và makespan, cách nhau dấu cách.

    Ví dụ:

    Đầu vào:

    3
0 3 5 2 6 2

    Đầu ra:

    2 9

    Giải thích:

    Sắp xếp: P1(0,3),P2(5,2),P3(6,2). t=0->3. idle 3->5 (=2), t=5->7. P3 đến lúc 6<7 không idle, t=7->9. Tổng idle=2, makespan=9.

    Đang tải editor...