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] EDF realtime — timeline và đếm trễ deadline

    EDF (Earliest Deadline First) cho hệ thời gian thực

    Mô phỏng bộ lập lịch EDF: tại mỗi đơn vị thời gian, chạy tiến trình đã release và còn thời gian thực thi có deadline tuyệt đối nhỏ nhất.

    Thuật toán (mô phỏng từng đơn vị thời gian t = 0,1,...,T-1)

    1. Tập sẵn sàng = các tiến trình có rel ≤ t và còn rem > 0.
    2. Nếu tập sẵn sàng rỗng → CPU idle, ghi 0 vào timeline.
    3. Ngược lại chọn tiến trình có dl nhỏ nhất; nếu bằng nhau chọn pid nhỏ hơn. Chạy 1 đơn vị, ghi pid vào timeline, giảm rem đi 1.
    4. Cuối đơn vị t (tức thời điểm t+1): với mỗi tiến trình còn rem > 0 mà t+1 == dl thì coi như trễ deadline (mỗi pid chỉ đếm 1 lần).

    In timeline (mỗi đơn vị một số, 0 là idle) và tổng số tiến trình bị trễ deadline.

    Ví dụ

    1 tiến trình pid 1, release 0, deadline 2, execute 1. Tại t=0 chạy pid1 (rem→0). Timeline = 1 0 nếu T=2. Không trễ deadline → 0.

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

      Dòng 1: n. n dòng: pid rel dl ex (release, deadline tuyệt đối, thời gian thực thi). Dòng cuối: T — số đơn vị thời gian mô phỏng.

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

      1 ≤ n ≤ 50; 0 ≤ rel < T ≤ 1000; 1 ≤ ex ≤ 100; rel < dl ≤ 2000; pid phân biệt.

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

      Dòng 1: timeline gồm T số cách nhau bởi dấu cách (0 = idle). Dòng 2: số tiến trình bị trễ deadline.

    Ví dụ:

    Đầu vào:

    1
1 0 2 1
2

    Đầu ra:

    1 0
0

    Giải thích:

    t=0: chỉ pid1 sẵn sàng, chạy pid1, rem→0. t=1: không ai sẵn sàng → idle 0. Timeline `1 0`. Không tiến trình nào trễ deadline → 0.

    Đang tải editor...