[운영체제] Peterson's solution(피터슨 알고리즘)

Race Condition을 해결하기 위한 방식 가운데 Busy Waiting을 이용한 Mutual Exclusion을 제공하는 방식이 있다.

그 중 Dekker의 솔루션을 간소화한 Peterson 방식을 알아보자.

peterson의 알고리즘

Peterson의 솔루션 알고리즘

알고리즘을 분석해보자

전체적인 흐름을 살펴보자면,
1. call enter region processor
2. enter critical region
3. call leave region processor
정도로 요약이 가능하다.

critical region에 들어가려고 하는 Process 0와 Process 1이 있다고 가정하자.

Process 0는 enter_region(0)를 콜하고, Process 1은 enter_region(1)을 콜한다.

또한 알고리즘 내에는 두 프로세스가 공유하는 공유변수 turn, interested가 존재한다.

turn : critical region 진입하게 될 process를 나타내는 변수 (process 0의 차례인지, process 1의 차례인지 나타내는 변수)
interested : critical region에 들어가려고 하는 관심을 나타내는 변수(1이 되면 관심이 있다 -> 처음에는 0으로 초기화)

Process 0

Process 0부터 따져보며 코드를 한 줄씩 뜯어보자!

1. Process 0이 enter_region(0)를 call했다.

2. 변수 other는 1 - 0이므로 1. 즉 상대방 프로세스 넘버를 의미한다.

3. interested[0]은 true process 0는 critical region 진입에 관심이 있다는 것을 명세한다.

4. turn 또한 0로 세팅

5. 두 조건의 논리곱이 참인 경우 while loop 안으로 들어가게 된다.
   while문의 조건식을 살펴보면,
   turn은 프로세스와 같다. 지금 turn은 0! 즉 앞 조건은 true
   other는 1인데, 관심값 배열의 초기값은 0이고 other는 아직 관심값을 세팅하지 않았으니 뒷조건은 false

6. 따라서 반복문의 조건식이 거짓이므로 루프에서 빠져나간다.

7. 다음에 기다리는 것은? critical region code!

8. 야호! Process 0는 critical region에 진입했다.

9. Process 0가 critical region을 전부 수행하고 난 다음 leave region을 call한다.

10. interested[0] = False;

Process 0가 critical region 수행 중 Process 1이 enter region을 call한다면?

1. Process 1이 enter_region(1)을 call했다

2. other, 즉 상대방 프로세스는 0으로 세팅

3. interested[1] = TRUE;
   나도 관심 있어요!

4. turn = 1;

5. while문을 살펴봅시다
   turn값이 지금 1, 프로세스 지금 1 -> 앞조건 참
   interested[other], 지금 상대방은 critical region에 들어가 있는 상태. 자기 관심을 true로 세팅해 놓고 critical region에 들어가 있는 상태이기에 상대방의 관심은 현재 true! -> 뒷조건 참

6. 따라서 반복문의 조건식이 참이므로 루프 실행

7. 루프를 돌리면서 empty statement 수행하며 다시 체크(busy waiting)

8. until Process 0가 critical region 다 수행하고 leave region을 불러 Process의 관심이 false가 될 때까지
   -> 뒷조건이 거짓이 되어 Process 1이 while문을 빠져나갈 수 있음

Race Condition이 일어날 수 있는 경우

두 프로세스가 동시에 접근하여 race condition이 발생할 수 있는 경우에 Peterson's solution에서 어떻게 Mutual Exclusion이 제공되는지 알아보자.

두 프로세스가 거의 동시에 enter region을 call한 경우 간발의 차이로 Process 0가 먼저 수행했다고 가정한다.

그 경우 공유 variable, turn의 값은 0.
간발의 차이로 늦은 프로세스 1이 enter_region(1)로 해서 들어갔을 때 turn의 값은 1로 바뀐다.
결과적으로는 프로세스 0가 enter region을 먼저 수행하고 프로세스 1이 조금 늦게 수행함으로써 최종적으로 turn의 값은 프로세스 1의 값인 1로 세팅이 된다.

그 다음 while loop에서 또 부딪히게 되는데, while문에서 공유 variable turn의 값은 프로세스 0 입장에서는 0이지만 현재는 1이다. 따라서 turn == process 조건은 거짓이된다.

프로세스 0는 앞조건이 거짓이므로 바로 while loop를 빠져나와서 critical region을 수행한다.

프로세스 1이 while loop에 도착했을 때 프로세스 1에서는 enter_region(1)을 call한 상태이므로 turn == process 는 참이다. (앞조건 참)

뒷조건을 살펴보면, 지금 상대방(프로세스 0)는 critical region에 들어가 수행중이므로 interested[0]를 true로 해놓고 진입했기에 뒷조건 또한 참이다.

프로세스 1의 입장에서는 while문의 두 조건이 모두 참이므로 두 조건의 논리곱인 반복문의 조건식도 참이기에 while loop 속으로 들어가고 마찬가지로 empty statement를 수행하며 기다린다. 루프를 돌며 busy waiting한다.

프로세스 0가 critical region을 다 수행하고 leave region을 call해서 interested[0]를 false로 바꿀 때까지 프로세스 1은 busy waiting 상태이므로 Mutual Exclusion을 제공할 수가 있는 것이다.