피터슨의 해결안

임계 구역에 대한 고전적인 소프트웨어 기반 해결책

임계구역 문제를 해결하기 위한 좋은 알고리즘적 설명을 제공한다.

피터슨의 해결안은 두 프로세스가 두 개의 데이터 항목을 공유하도록 하여 해결한다.

 

Int turn; - 임계구역으로 진입할 순번을 나타냄

Turn == i 이면 프로세스 Pi가 임계구역에서 실행됨

Boolean flag[2]; - 프로세스가 임계구역으로 진입할 준비가 되었다는 것을 나타냄

Flag[i] == true 이면 Pi 가 임계구역으로 진입할 준비가 되었다는 것을 나타낸다.

 

프로세스 Pi의 구조

do {     Flag[i] = TRUE;     turn = j;     while (flag[j] && turn == j );      // 임계구역     flag[i] = FALSE;      // 나머지 구역 } while (TRUE);

 

 

증명

상호배제

Turn이 동시에 두 개의 값을 가질 수 없으므로

두 개중 하나의 프로세스는 while 문에 갇히게 된다.

그러므로 상호배제가 지켜진다.

 

진행

Pj가 임계구역에 들어갈 준비가 안되어 있다면 flag[j] == false 이므로

Pi는 while 문을 탈출하여 임계구역에 진입할 수 있게 된다.

즉 진행 조건을 충족한다.

 

한정된 대기

Pj가 임계구역을 빠져 나올 때 flag[j]를 false로 지정해주기 때문에

Pi가 진입할 수 있도록 보장하여 준다.

Turn을 상대방 위주로 해놓았기 때문에

한정대기도 지켜진다.