Bài tập | NEU OJ

Cho N tiến trình, mỗi tiến trình có thời điểm đến (arrival), thời gian sử dụng CPU (burst) và độ ưu tiên (priority — số càng NHỎ thì ưu tiên càng CAO).

Hãy mô phỏng thuật toán Lập lịch theo độ ưu tiên CÓ ƯU TIÊN NGẮT (Preemptive Priority):

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

Xét thời gian theo từng đơn vị, bắt đầu từ thời điểm nhỏ nhất.
Tại mỗi đơn vị thời gian, trong các tiến trình đã đến và còn thời gian chạy, chọn tiến trình có độ ưu tiên cao nhất (priority nhỏ nhất). Nếu bằng nhau, chọn tiến trình có ID nhỏ hơn.
Cho tiến trình đó chạy 1 đơn vị thời gian.
Nếu một tiến trình mới đến có ưu tiên cao hơn tiến trình đang chạy, lập tức chuyển sang (ngắt).
Khi một tiến trình chạy xong, ghi nhận thời điểm hoàn thành.

Thời gian chờ (waiting) = turnaround − burst, với turnaround = completion − arrival.

In ra thời gian chờ trung bình của tất cả tiến trình (2 chữ số thập phân).

Ví dụ: 3 tiến trình ID 1..3, arrival [0,1,2], burst [4,3,1], priority [3,2,1]. Tiến trình 3 đến lúc t=2 có ưu tiên cao nhất nên ngắt và chạy trước.

Định dạng đầu vào:
Dòng đầu là số nguyên N. N dòng tiếp theo, dòng thứ i gồm 3 số nguyên: arrival, burst, priority của tiến trình ID i (ID đánh số từ 1).
Ràng buộc đầu vào:
1 ≤ N ≤ 1000; 0 ≤ arrival ≤ 10000; 1 ≤ burst ≤ 1000; 1 ≤ priority ≤ 100.
Định dạng đầu ra:
Một số thực: thời gian chờ trung bình, làm tròn 2 chữ số thập phân.

solution

Đề bài: [Hệ điều hành] Lập lịch ưu tiên có ngắt (Preemptive Priority)