[OS] Peterson's Solution( 피터슨의 알고리즘 )

 

Peterson’s Solution

 

두 개 이상의 프로세스의 동기화(Synchronization) 문제를 해결하는 방법 중 하나

 

※ Critical-section problem 의 예전 버전 해결 방법이다.

예전 버전이므로 현대 버전에 적용되는 것이 보장 되지 않지만 알고리즘 자체가 동기화 문제 해결 방법 들의 기반이 된다.

 

 

Peterson’s Solution Code

 

 

variables

 

int turn;
boolean flag[2];

 

Turn 은 critical section에 들어갈 수 있는 프로세스를 나타내는 변수

Flag 는 critical section에 들어갈 준비 상태를 나타내는 변수

 

 

 

Algorithm

 

// P_i 프로세스 의 알고리즘

while (true) {

	flag[i] = true;
    turn = j ;		// 또 다른 프로세스 를 j라고 가정.
	
    while(flag[j] && turn == j);
    
    /* critical section */
    
    flag[i] = false;
    
    /* remainder section */

}

 

◎임계 구역(critical section) 진입 전

 

자신의 flag를 true로 , turn을 상대방으로 바꾸어 둠.

 

 

 

◎임계 구역(critical section) 진입 후

 

자신의 flag를 false로 만듬.

 

 

 

◎ while() - wait

 

상대방이 들어갈 준비가 되었고 ( flag[j] == true )

상대방의 차례이면( turn == j )

while 속에 갇혀서 조건이 false 되기를 기다린다. (왜냐하면 임계 구역에 상대방과 동시에 들어가면 안되기 때문이다.)

 

 

Example : P0 와 P1 두개의 프로세스가 Critical section에 접근 하려 할 때

 

 

 

상황 1 :  P0 접근 O , P1 접근 X

 

P0 출발

 

-> flag[0] = true , turn = 1

-> while 조건 false 이므로 임계 구역 진입

 

 

 

상황 2 : P0 임계 구역 , P1 접근 O

 

P0 임계 구역 , P1 출발

 

-> flag[1] = true , turn = 0

-> flag [0] 는 true 이고 turn 는 0 이므로 while 조건 true

-> P1 while 속에 갇힘

-> P0 임계 구역 끝

-> flag[0] = false

-> P1 while 조건 false 이므로 임계 구역 진입

 

 

 

 

상황 3 : P0 다시 접근 O , P1 임계 구역

 

P0 remainder section , P1은 임계 구역

 

-> P0 remainder section 마치고 다시 while통해 접근

-> flag[0] = true , turn = 1

-> flag[1] 는 true , turn 는 1이므로 while 조건 true

-> P0 while 속에 갇힘

-> P1 임계 구역 끝

-> flag[1] = false

-> P0 while 조건 false 

 

 

 

Peterson's Solution은 critical section problem을 해결 하기 위한 세 가지 조건인

mutual exclusion    progress   bounded waiting 을 모두 충족 한다.

 

 

●Mutual exclusion

flag , turn 두 변수를 통해 충족

 

●progress

프로세스가 critical section을 나오자마자 flag 변수를 false로 설정함으로써

critical section 입장을 기다리던 프로세스가 바로 진입할 수 있도록 도와 주기 때문에 progress 또한 충족

 

●Bounded waiting

두 개의 프로세스이기 때문에 충족

 

---

세 가지 조건을 잘 모르는 분들을 위해..!

 

1.    Mutual Exclusion : 프로세스가 자신의 critical section에 진입해 있을 때 다른 process들이 자신들의 critical section에 들어오지 못하는 것.

 

2.     Progress : 만약 critical section에 들어가 있는 프로세스가 없고 , 들어 오려는 프로세스가 있을 때 프로세스가 critical section에 들어오는 것이 무기한 연장 될 수 없는 상태를 말한다.

 

3.     Bounded waiting : 한 프로세스가 자신의 critical section에 들어갈 수 있게 요청을 한 이후부터 그 요청이 수락 될 때 까지 다른 프로세스들은 자신들의 critical section 진입에 대한 요청을 횟수 제한 받는다.

 

---

 

 

Perterson’s Solution 의 문제점

 

만약 코드의 순서가 바뀌게 된다면 critical section problem이 발생할 수 있다.

 

 

 

 

 

Turn과 flag 부분의 두 줄 코드는 임계 구역에 들어가기 전의 코드 부분이다.

위 그림에서 파란색 글씨로 된 P1의 코드 두 줄은 순서가 바뀐 코드이다. 이 경우 두 프로세서가 임계 구역에 동시에 들어갈 수 있게 된다.

 

코드는 개발자에 의해 수정될 수 있다.

하지만 Peterson's Solution은 수정하면 제 기능을 못할 수 있다.

 

따라서 해결책으로 하드웨어 기반으로 한 적절한 Synchronization tools 를 함께 사용한다.