3. Giải thuật peterson

-Giải pháp thuộc nhóm phần mềm

-Đề xuất ban đầu cho đồng bộ 2 tiến trình

-P0 và P1 thực hiện đồng thời với một tài nguyên chung và một đoạn nguy hiểm chung

-Mỗi tiến trình thực hiện vô hạn và xen kẽ giữa đoạn nguy hiểm với phần còn lại của tiến trình

-Yêu cầu 2 tiến trình trao đổi thông tin qua 2 biến chung:

+Turn: xác định đến lượt tiến trình nào được vào đoạn nguy hiểm

+Cờ cho mỗi tiến trình: flag[i]=true nếu tiến trình thứ i yêu cầu được vào đoạn nguy hiểm

bool flag[2]; int turn;

-Thỏa mãn các yêu cầu:

+Điều kiện loại trừ tương hỗ

+Điều kiện tiến triển:

*P0 chỉ có thể bị P1 ngăn cản vào đoạn nguy hiểm nếu flag[1] = true và turn =1 luôn đúng

*Có 2 khả năng với P1 ở ngoài đoạn nguy hiểm:

~P1 chưa sẵn sàng vào đoạn nguy hiểm => flag[1] = false, P0 có thể vào ngay đoạn nguy hiểm

~P1 đã đặt flag[1]=true và đang trong vòng lặp while => turn = 1 hoặc 0

^Turn = 0: P0 vào đoạn nguy hiểm ngay

^Turn = 1: P1 vào đoạn nguy hiểm, sau đó đặt flag[1] = false => quay lại khả năng 1.

+ Chờ đợi có giới hạn.

-Sử dụng trên thực tế tương đối phức tạp

Đòi hỏi tiến trình đang yêu cầu vào đoạn nguy hiểm phải nằm trong trạng thái chờ đợi tích cực

Chờ đợi tích cực: tiến trình vẫn phải sử dụng CPU để kiểm tra xem có thể vào đoạn nguy hiểm?

=> Lãng phí CPU.