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 Unix] Message Queue - Ưu tiên kèm aging chống đói

    Hàng đợi ưu tiên có aging

    Để tránh thông điệp ưu tiên thấp bị bỏ đói, ta áp dụng aging: mỗi lần một thông điệp không được chọn để nhận, độ ưu tiên hiệu dụng của nó tăng 1.

    Thao tác:

    • S p x — gửi thông điệp mã x, ưu tiên gốc p (ưu tiên hiệu dụng ban đầu = p).
    • R — chọn thông điệp có ưu tiên hiệu dụng lớn nhất; nếu hoà, chọn thông điệp gửi trước (seq nhỏ hơn). In mã x. Sau đó mọi thông điệp còn lại trong hàng được +1 vào ưu tiên hiệu dụng (aging).

    Đảm bảo mọi R đều có thông điệp.

    Ví dụ

    S 5 100, S 1 200, R(chọn 100), R → sau R đầu, 200 được +1 (eff=2). R thứ hai chỉ còn 200 → in 200.

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

      Dòng đầu: n. n dòng: S p x hoặc R.

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

      1 ≤ n ≤ 2000, 0 ≤ p ≤ 10^6, 0 ≤ x ≤ 10^9.

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

      Mỗi R in mã thông điệp nhận được trên một dòng.

    Ví dụ:

    Đầu vào:

    4
S 5 100
S 1 200
R
R

    Đầu ra:

    100
200

    Giải thích:

    R đầu chọn 100 (eff 5>1); 200 được aging +1; R sau chỉ còn 200 → in 200.

    Đang tải editor...