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] Wait-die / Wound-wait — đếm theo timestamp

    Wait-Die / Wound-Wait — phòng tránh bế tắc theo timestamp

    Hai sơ đồ phòng bế tắc dựa trên timestamp giao tác (ở đây timestamp = pid; pid nhỏ = giao tác già hơn). Tiến trình Ti xin khóa đang được Tj giữ.

    Quy tắc

    • WAIT-DIE (giao tác già được chờ):
      • ts(Ti) < ts(Tj) (Ti già hơn): Ti chờ (wait).
      • ngược lại: Ti chết (abort/die).
    • WOUND-WAIT (giao tác già giành quyền):
      • ts(Ti) < ts(Tj) (Ti già hơn): Ti làm bị thương Tj → Tj abort (wound).
      • ngược lại: Ti chờ (wait).
    • Nếu khóa đang rảnh (Tj = -1): cấp ngay (granted), không xét quy tắc.

    In số_cấp_ngay số_lần_chờ số_lần_abort.

    Ví dụ

    WAITDIE, yêu cầu Ti=1, Tj=2 (1 già hơn 2): Ti chờ. In phần wait tăng. Kết quả 0 1 0.

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

      Dòng 1: WAITDIE hoặc WOUNDWAIT. Dòng 2: m. m dòng: Ti Tj (Tj = -1 nếu khóa rảnh).

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

      1 ≤ m ≤ 10^4; 0 ≤ Ti; Tj = -1 hoặc 0 ≤ Tj; Ti ≠ Tj khi Tj ≥ 0.

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

      số_cấp_ngay số_lần_chờ số_lần_abort.

    Ví dụ:

    Đầu vào:

    WAITDIE
1
1 2

    Đầu ra:

    0 1 0

    Giải thích:

    WAIT-DIE: Ti=1 già hơn Tj=2 (1<2) → Ti chờ. granted=0, wait=1, abort=0.

    Đang tải editor...