Bài toán critical-section là gì? Ba yêu cầu và giải pháp Peterson?

Critical section là đoạn code truy cập tài nguyên chia sẻ (biến, file...) mà nếu nhiều tiến trình vào cùng lúc sẽ gây race condition. Một lời giải đúng phải thỏa 3 điều kiện:

1. Mutual exclusion: tối đa 1 tiến trình trong critical section tại một thời điểm.
2. Progress: nếu không ai trong critical section, việc chọn ai vào tiếp không được trì hoãn vô hạn; chỉ các tiến trình đang muốn vào mới tham gia quyết định.
3. Bounded waiting: có giới hạn trên cho số lần tiến trình khác được vào trước một tiến trình đang chờ → không starvation.

Peterson (cho 2 tiến trình): dùng 2 biến chia sẻ — flag[2] (muốn vào chưa) và turn (tới lượt ai):

flag[i] = true;
turn = j;                      // nhường lượt cho đối phương
while (flag[j] && turn == j) ; // bận-chờ
// --- critical section ---
flag[i] = false;

Peterson thỏa cả 3 điều kiện. Hạn chế: chỉ 2 tiến trình, và trên CPU hiện đại cần memory barrier vì reorder lệnh có thể phá tính đúng → thực tế dùng lệnh atomic phần cứng (test-and-set, compare-and-swap) hoặc mutex của OS.