6.3 Peterson's Solution

 이제 critical section 문제를 해결하기 위한 traditional한 방법인 peterson's sol'n을 보자. 현대 컴퓨터 아키텍처가 기본 machine instruction을 수행하는 방식 때문에 peterson's solution이 이러한 아키텍처에서 올바르게 작동할 것이라는 보장이 없다. 하지만, 솔루션은 M.P.B.(Mutual Exclusion, Progress, Bounded Waiting)의 요구사항을 만족하고 소프트웨어 설계의 복잡성을 잘 설명하는 알고리즘을 제안하기 때문에 보고 넘어가자.

 피터슨의 솔루션은 두 프로세스가 critical section과 remainder section 사이를 번갈아 가면서 실행하는 경우에만 적용된다. 프로세스는 P0와 P1로 번호가 매겨지며, 편의를 위해 P_i를 나타낼 때, 다른 프로세스를 나타내기 위한 P_j를 사용하겠다. 즉, j = 1-i가 된다.

/* P_i의 코드 */
int turn;
boolean flag[2];

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

 turn은 이름 그대로 누가 critical section에 들어갈 차례인지 나타낸다. flag 배열은 프로세스가 critical section에 들어갈 준비가 되었는지(true이면 준비 완료)를 나타낸다. critical section에 들어가기 위해 프로세스 P_i 는 flag[i] 를 true로 설정하고, turn 을 j 값으로 설정하여 다른 프로세스가 임계 구역에 들어갈 수 있게 바꾸고, 둘 다 turn을 i, j 로 설정했기에 둘 중 하나는 critical section에 들어가게 된다. 여기서 i가 들어갔다고 해보자. flag[i] = false; 를 실행하여 자기 자신이 들어왔음을 알리고, remainder section을 실행 후 다 실행이 되었다면 다시 자기가 critical section에 들어갈 준비가 되었다는 flag를 true로 만들어주며, turn을 넘기게 된다. 그렇게 P_j가 실행되게 된다.

 이제 이것이 요구사항 세가지를 전부 만족하는지 증명해야 한다.

1. Mutual Execlusion is preserved
2. The progress is satisfied
3. The bounded-waiting requirement is met

 첫 번째, 각 Pi가 임계 구역에 들어가기 위해서는 flag[j] == false이거나 turn == i 여야 한다. 또한, 두 프로세스가 동시에 임계 구역에서 실행될 수 있다면 flag[0] == flag[1] == true일 것인데, 이 두 가지는 P0와 P1이 동시에 while 문을 성공적으로 실행할 수 없다는 것을 의미한다(왜냐하면 turn의 값은 0이나 1일 수 있지만 동시에 두 값이 될 수는 없기 때문이다). 따라서 두 프로세스 중 하나, 즉 Pj는 while 문을 성공적으로 실행해야 하고, Pi는 최소한 하나의 추가 문장(“turn == j”)을 실행해야 한다. 그러나 그때는 flag[j] == true이고 turn == j이며, 이 조건은 Pj가 임계 구역에 있는 동안 계속 유지된다. 결과적으로, 상호 배제가 유지된다.

 2와 3을 증명하기 위해서 Pi 프로세스가 임계 구역에 못들어가는 유일한 경우는 flag[j] == true이고 turn == j인 while 루프에 갇혀 있을 때다.  P_j가 임계 구역에 들어갈 준비가 되어 있지 않다면 flag[j] == false이며, P_i는 임계 구역에 들어갈 수 있을 것이다. P_j가 flag[j]=true로 설정하고 while 문을 실행 중이라면, turn == i이거나 turn == j일 것이다. 만약 turn == i라면 P_i는 임계 구역에 들어갈 것이다. 만약 turn == j라면 Pj가 임계 구역에 들어갈 것이다. 하지만 P_j가 임계 구역을 벗어나면 flag[j]를 false로 다시 설정하여 P_i가 임계 구역에 들어갈 수 있게 한다. P_j가 flag[j]를 true로 다시 설정하려면 turn을 i로 설정해야 한다. 따라서, P_i는 while 문을 실행하는 동안 turn 변수의 값을 변경하지 않으므로, P_j가 한 번 임계 구역에 들어간 후에는 P_i가 임계 구역에 들어갈 수 있다(progress). P_j가 최대 한 번만 임계 구역에 들어간 후에 P_i가 임계 구역에 들어갈 수 있다(bounded waiting).

 

 하지만 이런 Peterson solution은 현대 컴퓨터 아키텍처에서는 작동이 보장되지 않는다. 시스템 성능을 향상시키기 위한 프로세서나 컴파일러가 dependencies가 없는 코드들을 재정렬할 수 있기 때문이다. 단일 스레드 애플리케이션에서는 이러한 재정렬이 프로그램의 정확성에 영향을 미치지 않기 때문에 재정렬을 실행하지만, 공유 데이터를 사용하는 멀티스레드 애플리케이션에서는 명령어의 재정렬이 일관성 없는 결과나 예상치 못한 결과를 초래할 수 있기 때문에 현대에서는 적합하지 않다.

 다음절을 통해 이 문제점을 해결해보자.