Nêu giải thuật Peterson?

Biến chia sẻ: kết hợp cả giải thuật 1 và 2

• int turn; /* khởi đầu turn = 0 */
• nếu turn = i thì Pi được phép vào critical section, với i = 0 hay 1
• boolean flag[ 2 ]; /* khởi đầu flag[ 0 ] = flag[ 1 ] = false */
• Nếu flag[ i ] = true thì Pi “sẵn sàng” vào critical section.

Process Pi , với i = 0 hay 1
do {
flag[ i ] = true; /* Process i sẵn sàng */
turn = j; /* Nhường process j */
while (flag[ j ] and turn == j);
critical section
flag[ i ] = false;
remainder section
} while (1);

Thoả mãn được cả 3 yêu cầu (chứng minh)

Þ giải quyết bài toán critical section cho 2 process.
• Giải thuật 3 thỏa mutual exclusion, progress, và bounded waiting.

Mutual exclusion được bảo đảm bởi vì

• P0 và P1 đều ở trong CS nếu và chỉ nếu flag[0] = flag[1] = true và turn = i cho mỗi Pi (không thể xảy ra)

progress và bounded waiting

– Pi không thể vào CS nếu và chỉ nếu bị kẹt tại vòng lặp while() với điều kiện flag[ j ] = true và turn = j .
– Nếu Pj không muốn vào CS thì flag[ j ] = false và do đó Pi có thể vào CS.
– Nếu Pj đã bật flag[ j ] = true và đang chờ tại while() thì có chỉ hai trường hợp là turn = i hoặc turn = j
–Nếu turn = i thì Pi vào CS. Nếu turn = j thì Pj vào CS nhưng sẽ bật flag[ j ] = false khi thoát ra Þ cho phép Pi vào CS

– Nhưng nếu Pj có đủ thời gian bật flag[ j ] = true thì Pj cũng phải gán turn = i
– Vì Pi không thay đổi trị của biến turn khi đang kẹt trong vòng lặp while(), Pi sẽ chờ để vào CS nhiều nhất là sau một lần Pj vào CS (bounded waiting)



Cái giải thuật này có vẻ khó và mình cũng lơ tơ mơ quá!