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] Rate-Monotonic — kiểm tra khả lập lịch

    Rate-Monotonic — kiểm tra khả lập lịch

    Rate-Monotonic (RM) gán độ ưu tiên cố định: tiến trình có chu kỳ nhỏ hơn có ưu tiên cao hơn. Mỗi tiến trình i có thời gian thực thi c_i và chu kỳ p_i; cứ mỗi p_i đơn vị nó phát sinh một job cần c_i đơn vị CPU và phải hoàn thành trước job kế tiếp (deadline = chu kỳ).

    Thuật toán (mô phỏng trong 1 hyperperiod = BCNN các chu kỳ)

    1. Tính H = lcm(p_1, …, p_n).
    2. Sắp ưu tiên theo (p_i tăng, chỉ số tăng).
    3. Với mỗi t = 0…H-1: tiến trình nào tới thời điểm release (t là bội của p_i) thì cộng c_i vào lượng còn lại rem_i. Chọn tiến trình ưu tiên cao nhất còn rem > 0 để chạy 1 đơn vị.
    4. Cuối đơn vị t (thời điểm t+1): nếu t+1 là bội của p_i mà rem_i > 0 (job cũ chưa xong khi job mới tới) → trễ deadline.

    In SCHEDULABLE nếu không có lần trễ nào, ngược lại NOT SCHEDULABLE.

    Ví dụ

    Task1 c=1,p=2; Task2 c=1,p=4. H=4. Mỗi job đều kịp → SCHEDULABLE.

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

      Dòng 1: n. n dòng: c p (thời gian thực thi, chu kỳ).

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

      1 ≤ n ≤ 6; 1 ≤ c ≤ p ≤ 20; hyperperiod ≤ 5000.

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

      SCHEDULABLE hoặc NOT SCHEDULABLE.

    Ví dụ:

    Đầu vào:

    2
1 2
1 4

    Đầu ra:

    SCHEDULABLE

    Giải thích:

    H=lcm(2,4)=4. RM: task1 (p=2) ưu tiên cao. Mọi job hoàn thành trước job kế → SCHEDULABLE.

    Đang tải editor...