Critical Section (임계구역)

임계구역이란, 공유 데이터를 액세스하는 코드 부분을 의미합니다.

 

EX)

while(count == N);

buffer(in) = next_produced;

in = (in + 1) % N;

count += 1; // 해당 부분이 임계구역에 해당

.

.

.

while(count == 0);

next_consumed = buffer(out);

out = (out + 1) % N;

count -= 1; // 해당 부분이 임계구역에 해당

 

임계구역에 해당하는 부분의 코드를 어셈블리어로 볼때 다음처럼 분리됩니다.

 

reg1 = count;

reg1 = reg1 + 1;

count = reg1;

 

reg2 = count;

reg2 = reg2 - 1;

count = reg2;

 

위 코드는 원자성이 보장되지 않으므로, 동시에 두 코드가 실행됐을 때, 어셈블리어의 실행 순서가 바뀌게 되면 사용자가 원하는 결과값이 나오지 않을 수 있습니다. 즉, 임계구역 내에는 하나의 프로세스만 접근해야 한다는 조건을 알 수 있습니다.

 

임계구역 문제를 해결하기 위해선 다음 3가지 조건이 만족해야합니다.

1. Mutual Exclusion (상호 배제)
2. Progress (진행)
3. Bounded Waiting (한정된 대기)

상호 배제는 위에서 서술했듯, 임계 구역내에서는 오직 하나의 프로세스만 있을 수 있다는 조건입니다.

진행은 임계 구역 내에 프로세스가 없고, 임계 구역에 진입하고자 하는 프로세스가 있다면, 즉시 임계 구역에 진입할 수 있어야 한다는 조건입니다.

마지막으로 한정된 대기는 임계 구역에 진입 요청 후부터 진입할 때까지 임계 구역에 진입하는 프로세스들의 횟수에 한계가 있어야한다는 조건입니다.

 

이 조건들은 프로세스들 간의 상대 속도를 가정하지 않습니다.

 

조건들이 만족하는지 예시를 통해 증명합니다.

 

EX) P1, P2가 존재

 

while(turn == 1);

Critical Section

turn = 1;

(P1)

 

while(turn == 0);

Critical Section

turn = 0;

(P2)

 

먼저 Mutual Exclusion의 증명입니다.

위 P1과 P2가 동시에 임계 구역에 진입했다고 가정하면, turn의 값은 0이면서 동시에 1이어야 합니다.

하지만, turn은 0이면서 동시에 1일 수 없으므로, 모순증명법에 의해 상호배제 조건이 만족합니다. (명제 공식 이용)

 

다음으로 Progress의 증명입니다.

P1이 먼저 진입하고 P2는 진입의사가 없을 때, turn은 1이됩니다. 그리고 다시 P1이 임계구역에 진입하고자 하면, 임계 구역에 어떤 프로세스도 없지만 진입할 수 없으므로 Progress 조건이 만족하지 않습니다.

 

다음으로 Bounded Waiting의 증명 예시입니다.

 

EX) P1과 P2가 존재

flag(0) = true;

while(flag(1) == true);

Critical Section

flag(0) = false;

(P1)

 

flag(1) = true;

while(flag(0) == true);

Critical Section

flag(1) = false;

(P2)

 

P1과 P2가 동시에 진입요청했을 때, flag(0)과 flag(1)이 둘다 true가 될 수 있어 무한 대기가 발생합니다.

따라서, Bounded Waiting 조건이 만족하지 않습니다.

 

마지막으로 임계 구역 문제를 해결한 케이스입니다.

 

EX) Pi ~ Pj가 존재

flag[i] = true;

turn = j;

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

Critical Section

flag[i] = false;

 

먼저 Mutual Exclusion의 증명입니다.

Pi와 Pj가 동시에 임계 구역에 있다고 가정할때, flag[i] = true && turn == 1 && flag[j] == true && turn == 0 이므로, turn이 0이면서 1일 수 없기 때문에 모순증명법에 의해 Mutual Exclusion 조건이 만족합니다.

 

다음으로 Progress의 증명입니다.

Pi가 진입하고 Pj가 진입의사가 없다고 가정, Pi가 다시 재진입 요청 시 while(flag[j] && turn == j)의 조건에 의해 어느 상황에서도 임계 구역이 비어있다면 즉시 진입이 가능하므로 Progress 조건이 만족합니다.

 

마지막으로 Bounded Waiting의 증명입니다.

Pi와 Pj가 동시에 진입요청 한다고 가정, flag[i] = true, flag[j] = true, turn = j. 이때, Pi가 진입하고 while 조건에 의해 Pj는 while에서 대기합니다. 이때 turn은 반드시 j. 따라서, Pi가 종료하면 Pj는 반드시 임계 구역 진입이 가능하므로, Bounded Waiting 조건이 만족하므로, 임계 구역 문제가 해결됩니다.

 

위 코드를 Peterson's Algorithm 이라고 부릅니다.