Peterson 해결 방법

아래는 peterson 해결 방법에서 필요한 자료구조 이다.

bool flag[]; // 임계영역 진입 상태를 저장한다.
int turn; // 임계 영역을 실행할 프로세스의 순서를 저장한다.

Pi와 Pj가 존재하며 j는 i를 제외한 프로세스를 뜻한다. 아래는 peterson 해결 방법의 Pi 프로세스 구조 이다.

while(true){
	flag[i] = true;
	turn = j;
    
	while(flag[j] && turn == j);
    
	/* critical section */
    
	flag[i] = false;
    
	/* remainder section */   
}

코드 한줄 한줄 정리 해보겠다.

1. flag[i] = true; 는 현재 내 프로세스가 임계영역에 진입 상태를 true로 설정해준다.
2. turn = j는 임계영역에 진입할 차례를 나를 제외한 프로세스로 바꿔준다. turn을 j로 바꿔줬을때 프로세스j가 진입 가능한 상태라면 프로세스 j가 임계영역에 들어가게 된다.
3. while(flag[j] && turn == j) 는 다른 프로세스가 임계영역에 들어가 있는 중이라면 대기를 한다.
4. flag[i] = false; 임계 영역을 수행하고 빠져나오면서 나의 임계영역 진입 상태를 false로 바꿔준다.

Peterson 해결 방법의 증명

상호 배제

프로세스i가 임계 영역에 도달하기 위해선 flag[j] == false 이거나 turn==i여야 한다.
만약 두 프로세스가 임계 영역을 수행하려면 일단 flag[i] == flag[j] == true를 만족해야 한다. 이후 turn == 0 == 1을 만족해야한다. 하지만 turn 변수는 실행할 프로세스 순서 하나만 저장하므로 동시에 0과 1이라는 값을 가질 수 없다. 그렇기 때문에 단 하나의 프로세스만 임계영역에 존재할 수 있다.

진행에 대한 요구 조건

while(flag[j] && turn == j) 라는 조건을 통해 우리는 임계영역에 진입 대기 상태를 가지고 특정한 프로세스만 임계 영역에 진입할 수 있음을 알 수 있다.
그리고 임계 영역을 탈출하면서 flag[i] = false로 바꿔주기 때문에 한 프로세스가 임계영역에 존재하는 도중에 다른 프로세스가 임계영역을 진입하는 경우는 발생할 수 없다.

대기 시간이 유한하다

프로세스i가 while문을 수행하면서 대기하는 동안 turn값은 바뀌지 않으므로 번갈아가면서 실행될 수 있다.

문제점

과거의 컴퓨터 아키텍처에서는 Peterson 방식은 Critical Section의 문제를 해결할 수 있었다. 하지만 최신 컴퓨터 아키텍처에서는 항상 올바르게 작동한다고 보장할 수 없다. 이유는 시스템 성능 향상을 위해 프로세서 또는 컴파일러가 종속성 없는 데이터에 대해 읽기 쓰기 작업의 순서를 재정렬할 수 있다. 예를 들면 아래와 같다.

기존 코드
flag[i] = true;
turn = j;

프로세서나 컴파일러가 순서를 재정렬한 코드
turn = j;
flag[i] = true;

이러한 순서가 바꼈을때 두 프로세스가 동시에 임계 영역에 진입할 수 있는 경우가 발생한다.

1. process0번의 turn=1 코드까지 실행 된 후 process1번으로 스케쥴링 된다.
2. process1번은 turn=0; flag[0]=true; 코드를 실행 한다.
3. process1번은 while문의 조건(while(flag[0] && turn == 0);)을 확인한다. while문 조건에서 flag[0]은 아직 false이므로 process1번은 임계 영역에 진입하게 된다.
4. 스케쥴링을 통해 다시 process0번이 할당된다. process0번의 flag[0]=true의 코드가 실행된다.
5. process0번은 while문의 조건(while(flag[1] && turn == 1);)을 확인한다. flag[1] == true지만 현재 turn의 값은 0이다. 그렇기때문에 turn != 1이므로 임계영역에 진입하게 된다.