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] Peterson — đếm bước vào vùng găng

    Giải thuật Peterson — đếm bước vào vùng găng

    Giải thuật Peterson cho 2 tiến trình (0 và 1) dùng mảng flag[2] và biến turn. Mỗi tiến trình muốn vào vùng găng (CS) sẽ đặt cờ và nhường lượt; chỉ vào được khi điều kiện chờ sai.

    Mô phỏng các thao tác

    • WANT proc: flag[proc] = true; turn = other (nhường lượt cho tiến trình kia).
    • TRY proc: kiểm tra điều kiện chờ flag[other] == true AND turn == other. Nếu sai → vào CS thành công (entered += 1). Nếu đúng → bị chặn (blocked += 1).
    • DROP proc: rời CS, flag[proc] = false.

    Trạng thái khởi tạo flag = [false, false], turn = 0. In số_lần_vào_CS số_lần_bị_chặn.

    Ví dụ

    Thao tác WANT 0, TRY 0. Sau WANT 0: flag[0]=true, turn=1. TRY 0: điều kiện flag[1] && turn==1 = false && ... = false → vào được. In 1 0.

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

      Dòng 1: m. m dòng: proc action với proc ∈ {0,1}, action ∈ {WANT, TRY, DROP}.

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

      1 ≤ m ≤ 10^4; proc ∈ {0,1}.

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

      số_lần_vào_CS số_lần_bị_chặn.

    Ví dụ:

    Đầu vào:

    2
0 WANT
0 TRY

    Đầu ra:

    1 0

    Giải thích:

    WANT 0: flag[0]=true, turn=1. TRY 0: điều kiện chờ flag[1]&&turn==1 → false (flag[1]=false) → vào CS. entered=1, blocked=0.

    Đang tải editor...