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] Aging — chống đói trong lập lịch ưu tiên

    Aging — chống đói CPU trong lập lịch ưu tiên

    Lập lịch theo độ ưu tiên (số nhỏ = ưu tiên cao) dễ làm tiến trình ưu tiên thấp bị đói. Kỹ thuật aging tăng dần ưu tiên của tiến trình đang chờ.

    Thuật toán (có ngắt, mỗi đơn vị thời gian)

    • Mỗi tiến trình có base (ưu tiên gốc), prio hiện tại (khởi tạo = base), và thời gian còn lại rem. Hằng aging A.
    • Lặp đến khi mọi rem = 0:
      1. Chọn tiến trình còn rem > 0 có prio nhỏ nhất; nếu bằng nhau chọn pid nhỏ hơn. Chạy 1 đơn vị, ghi pid, giảm rem.
      2. Reset prio = base cho tiến trình vừa chạy.
      3. Aging: mọi tiến trình còn rem > 0 mà không được chạy lượt này thì prio -= A (ưu tiên tăng).

    In timeline các pid theo thứ tự chạy.

    Ví dụ

    pid1 base=1 bt=2; pid2 base=5 bt=1; A=2. t0: chọn pid1 (prio1), chạy; pid2 prio 5→3. t1: pid1 prio reset=1, pid2=3 → pid1; pid2 3→1. t2: pid1 rem0; chỉ pid2 → pid2. Timeline 1 1 2.

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

      Dòng 1: n. n dòng: pid base burst. Dòng cuối: A — bước aging mỗi đơn vị chờ.

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

      1 ≤ n ≤ 50; 1 ≤ base ≤ 100; 1 ≤ burst ≤ 100; 1 ≤ A ≤ 50.

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

      Timeline gồm các pid (cách nhau dấu cách) theo thứ tự chạy.

    Ví dụ:

    Đầu vào:

    2
1 1 2
2 5 1
2

    Đầu ra:

    1 1 2

    Giải thích:

    t0: pid1 prio1 chạy, pid2 5→3. t1: pid1 reset1 vs pid2 3 → pid1, pid2 3→1, pid1 rem0. t2: chỉ pid2 → pid2. Timeline `1 1 2`.

    Đang tải editor...