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] Ring Buffer - SPSC lock-free đếm overrun và nội dung

    Ring buffer SPSC (single-producer single-consumer)

    Ring buffer lock-free kích thước C với chỉ số wr (writer) và rd (reader), cùng đếm count. Producer ghi giá trị, consumer đọc; nếu producer ghi khi đầy thì ghi đè phần tử cũ nhất (overrun) và rd cũng tiến lên — đếm overrun += 1.

    Thao tác:

    • W v — ghi giá trị v vào ô wr; wr=(wr+1)%C. Nếu đang đầy (count==C): overrun (rd=(rd+1)%C, count giữ C, overrun+=1). Nếu chưa đầy: count+=1.
    • R — nếu count>0: đọc ô rd, in giá trị, rd=(rd+1)%C, count-=1. Nếu rỗng: in EMPTY.

    In: với mỗi R một dòng (giá trị hoặc EMPTY); dòng cuối in OVERRUN <overrun>.

    Ví dụ

    C=2: W 1,W 2,W 3(đầy→ghi đè ô cũ nhất là 1, overrun=1, rd tiến), R(đọc 2),R(đọc 3) → in 2,3,OVERRUN 1.

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

      Dòng đầu: C n. n dòng: W v hoặc R.

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

      1 ≤ C ≤ 10^5, 1 ≤ n ≤ 2000, 0 ≤ v ≤ 10^9.

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

      Mỗi R in một dòng (giá trị hoặc EMPTY); cuối cùng in OVERRUN k.

    Ví dụ:

    Đầu vào:

    2 5
W 1
W 2
W 3
R
R

    Đầu ra:

    2
3
OVERRUN 1

    Giải thích:

    W3 khi đầy ghi đè ô cũ nhất (1), overrun=1, rd tiến; R đọc 2 rồi 3.

    Đang tải editor...