[Operating System] Peterson's Solution

Peterson's Solution

• Peterson's solution : software-based solution to the critical-section problem.
• 두 프로세스가 critical section과 remainder section을 왔다갔다하는 상황에 사용 가능하다. 각 프로세스를 $P_0$, $P_1$이라고 하고, 편의를 위해 $P_i$라고 표현하면 $P_j$는 다른 프로세스를 가리킨다.
• 두 프로세스는 다음 두 데이터를 공유한다.

  int turn;
  boolean flag[2];

• turn 변수는 누가 다음으로 critical section을 들어갈 것인지를 결정하는 변수.
  • ex) turn == i -> $P_i$가 critical section을 실행할 것을 나타냄.
• flag 배열은 프로세스가 critical section으로 들어갈 준비가 되었는지를 나타낸다.
  • ex) flag[i] == true -> $P_i$가 critical section으로 들어갈 준비가 되었음을 나타냄.
• Peterson's Solution(algorithm)
  
  세 가지를 증명해야 함.
  1. Mutual Exclusion
     • pf)
       1. $P_i$, $P_j$가 동시에 critical section에 진입하는 경우
          while문의 조건이 동시에 만족되어야 하지만, turn이라는 변수는 i, j의 값을 동시에 가질 수는 없으므로 동시에 critical section에 진입되지 않고 하나만 가능하다.
       2. 둘 중 하나가 먼저 critical section에 들어간 상태, 나머지 하나가 들어가려고 시도하는 경우
          일관성을 잃지 않고 $P_i$가 critical section에 들어가 있고, $P_j$가 들어가려고 시도하는 경우에 대해서만 증명한다.
          $P_i$가 critical section에 들어가 있다는 것은 이전에 $P_i$에 의해 flag[i]값이 true로 설정이 되었고, flag[i]의 값은 $P_i$에 의해서만 바뀌므로 flag[i] == true임이 보장되어 있다.
          이 상태에서 $P_j$가 critical section에 들어갈 수 있다고 가정해보자.(귀류법)
          그렇다면 flag[i] == false or turn == j여야 하는데, 앞서 말한 조건에 의해 flag[i] == true이므로 turn == j여야 한다.
          $P_j$의 입장에서 보면, turn을 i로 바꾸고 나서 while문으로 들어왔는데, turn == j라는 뜻은 그 사이에 $P_i$에 의해 turn이 j로 바뀌었다는 뜻이다.
          그러면 turn == i -> turn == j -> $P_i$가 critical section에 들어감 -> '지금 상황'이 될 텐데, 애초에 turn == j인 상태에서 $P_i$가 critical section에 들어갈 수 없으므로 모순이다.
          그러므로 둘 중 하나가 critical section에 들어가 있는 상태에서 다른 프로세스는 들어갈 수 없다.
  2. Process
     • 비어있을 때 remainder section이 아닌 상태에서 들어가려고 하는 경우 들어갈 수 있게 해준다.
  3. Bounded Waiting
     • 애초에 한 프로세스가 critical section에 들어가려고 while문을 돌고 있다는 뜻은 다른 프로세스가 critical section을 실행 중이라는 뜻이다. 그 동안 나머지 프로세스가 실행을 종료하면 flag값이 바뀌어 기다리던 프로세스는 바로 들어갈 수 있게 된다. 물론 while문을 돌지 않고 바로 실행될 수도 있다. 결국 한 프로세스는 최대 1번 기다리게 된다.
• 현대 아키텍쳐의 특징 : 성능을 위해 compiler나 processor가 서로 관계없는 read나 write 명령의 순서를 바꾸기도 한다.
  • 발생할 수 있는 문제
    
    • 분명히 x = 100; 후에 flag = true;를 실행했기 때문에 x가 print되어야 하지만, 두 명령은 서로 독립적이므로 성능을 위해 임의적으로 순서가 바뀔 수가 있다. -> 결국 flag = true; -> while문 탈출 -> print x -> x = 100 의 순서로 실행이 되므로 결국 0이라는 값이 출력되게 된다.
    • 또 다른 경우로 Thread 1에서 x값을 가져오는 과정을 flag값을 가져오는 것 보다 우선했을 경우에도 0이 출력되게 된다.
• 그래서 이게 Peterson's Solution이랑 무슨 상관임?
  
  • flag[i] = true;부분과 turn = j;라는 부분의 코드 순서를 바꾸었다고 생각해보자.
  • 위 그림처럼 순서가 진행된다고 했을 때, i와 j의 critical section이 동시에 실행된다는 것을 알 수 있다. -> synchronization이 제대로 동작하지 않음. -> synchronization tools가 필요하다.

참고 자료

• Abraham Silberschatz, Operating System Concepts, 10th edition