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] Synchronization - Phát hiện deadlock khi giành 2 khoá

    Phát hiện deadlock giữa hai tiến trình giành hai khoá

    Hai tiến trình A, B cùng cần hai mutex L1, L2. Mỗi mutex tại một thời điểm chỉ một tiến trình giữ. Thao tác X ACQ k nghĩa tiến trình X xin khoá Lk; X REL k nghĩa nhả khoá.

    Quy tắc ACQ: nếu khoá đang rảnh → X chiếm; nếu khoá do chính X giữ → bỏ qua; nếu do tiến trình khác giữ → X bị chặn, chờ khoá đó.

    Deadlock xảy ra khi cả hai tiến trình đồng thời đang chờ một khoá mà tiến trình kia đang giữ (chờ vòng tròn). Khi phát hiện deadlock, in DEADLOCK <số_thao_tác> (số thứ tự 1-based của thao tác gây ra) và dừng. Nếu hết thao tác mà không deadlock, in OK.

    Ví dụ

    A ACQ 1; B ACQ 2; A ACQ 2 (A chờ B); B ACQ 1 (B chờ A) → deadlock tại thao tác 4 → DEADLOCK 4.

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

      Dòng đầu: n. n dòng: X ACQ k hoặc X REL k, X∈{A,B}, k∈{1,2}.

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

      1 ≤ n ≤ 2000.

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

      DEADLOCK i (i là chỉ số thao tác gây deadlock) hoặc OK.

    Ví dụ:

    Đầu vào:

    4
A ACQ 1
B ACQ 2
A ACQ 2
B ACQ 1

    Đầu ra:

    DEADLOCK 4

    Giải thích:

    A giữ L1, B giữ L2; A chờ L2, B chờ L1 → chờ vòng tròn, deadlock tại thao tác 4.

    Đang tải editor...