상호배제의 문제점 코드들, 그리고 해결책 (Peterson 알고리즘)

<임계구역 해결을 위한 3가지 요구 조건>

① 상호배제(mutual exclusion): 한 프로세스만 임계구역에 진입.

② 진행(progress): 임계구역에 진입할 프로세스 선택이 영원히 지연되지 않음.

③ 한계 대기(bounded waiting): 한 프로세스가 임계구역 진입 요청 후 기다리는데 한계가 있음.

1. 임계영역의 첫번째 진입이 고정되는 문제

 

문제점.1

turn의 초기 값이 0으로 되어 있으므로 임계영역의 첫 번째 진입은 P0만 가능. (초깃값을 1로 바꾸면 P1이 됨)

문제는 두 프로세스에서 임계영역의 첫번째 진입이 고정되어 있다는 사실이고 이것은 임계영역이 비어있을 경우 진입을 원하는 프로세스를 방해해서는 안 된다는 원칙에 위배한다.

또 다른 문제는 임계영역의 진입이 turn 값을 바꾸어줌으로써 가능하므로 P0와 P1은 정확하게 한 번씩 번갈아가며 진입이 가능하고 누구든 연속해서 두 번 이상 진입할 수 없다.

2. CPU 인터럽트로 인한 임계영역 중복 할당문제.

 

문제점.2

flag 두 개를 사용할 경우 임계영역의 최초 진입에 제한이 없어졌으며, 상대적으로 많은 횟수의 진입이나 상대 프로세스가 먼저 종료되어도 진입이 가능하다.

하지만, P0가 flag[1]을 검사한 후 while문을 벗어난 다음 flag[0]를 true로 만들기 전에 P1에게 CPU가 넘어간다면, P1 역시 while문을 벗어나 임계영역을 들어가게 되고 실행 도중 다시 CPU가 P0에게 넘어갔을 때 P0는 이전에 중단되었던 작업인 flag[0]를 true로 만드는 것부터 실행한 후 임계영역으로 진입하게 된다. 결과적으로 임계영역에 둘 다 있게 되는 것이므로 상호배제가 지켜지지 못함을 알 수 있다.

다중처리의 경우라면, 동시에 while문을 검사한 후 둘 다 각자의 flag를 true로 만든 다음 임계영역으로 같이 진입할 수 있기 때문에 상호배제가 지켜지지 않게 된다.

3. CPU인터럽트로 인한 교착상태 발생

 

 

문제점.3

두번째 문제에서 flag를 while문 앞으로 옮겨본 것이 세 번째 시도이다.

이번에는 P0가 flag[0]를 true로 만든 다음 CPU는 P1에게, P1은 flag[1]을 true로 한 다음 while문에서 맴돌다 다시 CPU는 P0에게, P0 역시 while문에서 맴돌게 되는 현상이 발생할 수 있고 두 프로세스 모두 임계영역을 들어갈 수 없게 될 것이다.

<Peterson 알고리즘>

void P0

{

while(true) {

flag[0] = true;

turn = 1;

while(flag[1] && turn == 1);

<critical section>;

flag[0] = false;

<remainder>;

}

}

void P1

{

while(true) {

flag[1] = true;

turn = 0;

while(flag[0] && turn == 0);

<critical section>;

flag[1] = false;

<remainder>;

}

}

Copyrightⓒ2014 By 휴먼사이언스