임계구역 문제와 해결방법 (피터슨 알고리즘)

임계구역이란?

임계구역이란, 공유 자원에 접근하는 코드의 일부를 말합니다.

일반적으로 둘 이상의 프로세스는 공유 자원에 대해 동시에 접근할 수 없습니다.

하나가 먼저 실행하고 난 뒤 끝나면 다음 프로세스가 들어가서 실행해야 합니다.

do {
entry section
critical section
exit section
remainder section
} while (TRUE);

따라서 각 프로세스는 자신의 임계 구역에 들어가려면 들어가도 되는지 요청해야 합니다.

이런 요청이 entry section 에서 이루어지게 됩니다.

만약, 이미 들어가 있는 프로세스가 있다면 entry section 에서 기다리다가

들어가도 된다는 신호가 오면 critical section 으로 들어갑니다.

이렇게 잘 돌아가면 좋을텐데 임계구역에는 여러 문제가 생깁니다.

---

임계구역 문제의 해결 조건

임계구역 문제를 해결하기 위해서는 다음과 같이 3가지 조건을 충족해야 합니다.

1. 상호 배제 (Mutual Exclusion)

하나의 프로세스가 임계구역에 들어가 있다면 다른 프로세스는 들어갈 수 없습니다.

2. 진행 (Prograss)

임계 구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면,

어느 것이 들어갈지를 적절히 결정해줘야 합니다.

3. 한정 대기 (Bounded Waiting)

하나의 프로세스가 들어가서 오랫동안 나오지 않으면 다른 프로세스는 실행시킬 수 없게 됩니다.

이러한 기아(Starvation)을 방지하기 위해 

한 번 임계구역에 들어간 프로세스는 다음 번 들어갈 때 제한을 둬야 합니다.

---

임계구역 문제의 해결 방법

위에서 말했던 조건을 만족시키는 해결방법에는 여러 가지가 있습니다.

먼저 피터슨 알고리즘(Peterson's Algorithm)을 이용한 방법입니다.

피터슨은 flag와 turn 변수를 사용하여 프로세스가 임계구역에 들어가려고 하는 것을 구분했습니다.

shared int turn, flag[2];
do {
flag[me] = true;
turn =! me;
while(flag[!me] && turn ==! me);
critical section
flag[me] = false;
remainder section
} while(true);

위와 같이 flag 값이 true 이면 프로세스가 임계구역에 들어가려고 하는 것을 나타냅니다.

이 알고리즘은 임계구역 문제 해결의 3가지 조건을 모두 만족합니다.

그렇다면 문제 해결을 위한 완벽한 알고리즘일까요? 안타깝게도 아닙니다.

만약, 프로세스가 많이 몰리게 되면 critical section 앞의 while 문에서 계속 루프를 돌아야 하는 문제가 생깁니다.

이를 Busy waiting 이라고 부릅니다. 

문제를 해결하기 위한 방법으로 sleep()과 wakeup() 함수가 있습니다.

이 내용은 다음 세마포어 포스팅을 통해 이어 나가겠습니다.