Một semaphore đếm có giá trị khởi tạo S. Có thêm một hàng đợi chờ (FIFO) cho các tiến trình bị chặn.
Thao tác:
P k (wait/down của tiến trình ID k): giảm S đi 1. Nếu sau khi giảm S ≥ 0 → tiến trình k đi tiếp (running). Nếu S < 0 → tiến trình k bị chặn, đưa vào CUỐI hàng đợi chờ.V k (signal/up): tăng S lên 1. Nếu trước khi tăng S < 0 (tức có tiến trình đang chờ) → đánh thức tiến trình ở ĐẦU hàng đợi (FIFO), tiến trình đó chuyển sang running.(Lưu ý ID trong V k chỉ là tiến trình phát signal, không nhất thiết liên quan tới ai được đánh thức.)
In ra hai dòng: dòng 1 là giá trị cuối cùng của semaphore S; dòng 2 là danh sách ID các tiến trình vẫn còn đang chờ trong hàng đợi theo thứ tự FIFO (cách nhau dấu cách; nếu rỗng in dòng trống).
Ví dụ: S=1. P 1 (S=0, chạy). P 2 (S=-1, chờ). P 3 (S=-2, chờ). V 1 (S=-1, đánh thức 2). Cuối: S=-1, hàng chờ còn [3].
Dòng đầu: S Q (giá trị khởi tạo semaphore, số thao tác). Q dòng tiếp, mỗi dòng: thao tác (P hoặc V) và ID tiến trình.
−10^9 ≤ S ≤ 10^9; 1 ≤ Q ≤ 100000.
Dòng 1: giá trị semaphore cuối cùng. Dòng 2: ID các tiến trình còn chờ theo FIFO (có thể dòng rỗng).
Ví dụ:
Đầu vào:
1 4
P 1
P 2
P 3
V 1
Đầu ra:
-1
3
Giải thích:
Đang tải editor...