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] Monitor — bounded buffer condition variable

    Monitor — bounded buffer với condition variable

    Mô phỏng monitor bảo vệ một bounded buffer sức chứa cap, với hai biến điều kiện: not-full (cho PUT) và not-empty (cho GET).

    Quy tắc (mỗi thao tác xử lý tuần tự)

    • PUT tid: nếu count < cap → thêm 1 item (count++), thao tác hoàn thành. Sau đó signal một GET đang chờ (FIFO): đánh thức nó, nó lấy item ra (count--) và hoàn thành. Nếu count == cap → PUT bị chặn, đưa tid vào hàng chờ not-full.
    • GET tid: nếu count > 0 → lấy 1 item (count--), hoàn thành. Sau đó signal một PUT đang chờ (FIFO): đánh thức, nó thêm item (count++) và hoàn thành. Nếu count == 0 → bị chặn, đưa vào hàng chờ not-empty.

    In: số thao tác đã hoàn thành, số thread còn đang bị chặn, và count cuối cùng.

    Ví dụ

    cap=1, thao tác (1,PUT) (2,PUT). PUT 1: count 0→1, hoàn thành. PUT 2: count=cap=1 → bị chặn. Hoàn thành=1, đang chặn=1, count=1.

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

      Dòng 1: cap. Dòng 2: m. m dòng: tid action, action ∈ {PUT, GET}.

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

      1 ≤ cap ≤ 1000; 1 ≤ m ≤ 5000; tid ≥ 0.

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

      Dòng 1: số thao tác đã hoàn thành. Dòng 2: số thread còn bị chặn. Dòng 3: count cuối cùng.

    Ví dụ:

    Đầu vào:

    1
2
1 PUT
2 PUT

    Đầu ra:

    1
1
1

    Giải thích:

    cap=1. PUT 1: count 0→1, hoàn thành. PUT 2: buffer đầy → bị chặn (hàng not-full). Hoàn thành=1, đang chặn=1, count=1.

    Đang tải editor...