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] Shared Memory - Race condition lost update

    Race condition: cập nhật bị mất

    Hai tiến trình cùng tăng một biến counter trong bộ nhớ chia sẻ mà không khóa. Mỗi thao tác tăng gồm 3 bước: LOAD (đọc counter vào thanh ghi riêng), INC (tăng thanh ghi), STORE (ghi thanh ghi về counter).

    Cho một lịch trình đan xen các bước của hai tiến trình A và B. Mỗi tiến trình có thanh ghi riêng regA, regB. Mô phỏng đúng theo lịch trình rồi in giá trị counter cuối cùng.

    Bước được ghi dạng A LOAD, A INC, A STORE, B LOAD, ... counter khởi tạo bằng giá trị cho trước.

    Ví dụ

    counter=0, lịch trình: A LOAD,B LOAD,A INC,A STORE,B INC,B STORE → cả hai đọc 0; A ghi 1; B cũng ghi 1 ⇒ counter=1 (mất 1 lần tăng).

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

      Dòng đầu: c0 m — giá trị khởi tạo và số bước. m dòng tiếp theo: P OP với P ∈ {A,B}, OP ∈ {LOAD,INC,STORE}.

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

      -10^9 ≤ c0 ≤ 10^9, 1 ≤ m ≤ 2000. Lịch trình hợp lệ (LOAD trước INC trước STORE cho mỗi chu kỳ).

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

      Một số nguyên: giá trị counter cuối cùng.

    Ví dụ:

    Đầu vào:

    0 6
A LOAD
B LOAD
A INC
A STORE
B INC
B STORE

    Đầu ra:

    1

    Giải thích:

    A và B cùng đọc 0; A ghi 1; B cũng ghi 1 → mất 1 lần tăng, counter=1.

    Đang tải editor...