피터슨, 데커 알고리즘

피터슨 알고리즘

임계구역 문제를 해결하기 위해 게리 피터슨이 제안

turn 이라는 변수를 추가하여 이를 해결
두 프로세스가 동시에 lock을 설정하여, 임계구역에 못 들어가는 상황에 대비하기 위한 장치로
turn 을 사용, 다른 프로세스에 양보한다.

lock1 = true;
turn = 2;
while(lock2 == true && turn == 2);

/**
임계구역

**/

lock1 = false;

------------------------

lock2 = true;
turn = 1;
while(lock1 == true && turn == 1);

/**
임계구역

**/
lock2 = false;

임계구역 해결의 3가지 조건 (상호배제, 한정 대기, 진행의 융통성)을 만족하지만 프로세스당 공유 변수가 추가된다는 단점이 있다.

---

데커 알고리즘

피터슨 알고리즘을 제외하고는 임계구역 문제를 해결하기 위해서는, 검사와 지정(test-and-set) 같은 하드웨어의 도움이 필요
연산 중간에 타임아웃이 발생하지 않도록, 하드웨어적으로 막아야 임계구역 문제가 해결되었음

하드웨어의 도움 없이도 임계구역 문제를 해결 가능

// 공유 변수
boolean lock1 = false;
boolean lock2 = false;
int turn = 1;

// P1
...
lock1 = true;
while(lock2 == true) {
	if (turn == 2) {
    	lock1 = false;
        while(turn == 2);
        lock1 = true;
    }
}
/******
임계구역
*****/

turn = 2;
lock1 = false;


-------------

// P2
lock2 = true;
while(lock1 == true) {
	if (turn == 1) {
    	lock2 = false;
    	while(turn == 1);
        lock2 = true;
    }
}

turn = 1;
lock2 = false;

...

1. 프로세스 P1이 우선 잠금을 건다 (lock1 = true)
2. 프로세스의 P2의 잠금이 걸린지 확인한다 (while(lock2 == true))
3. 프로세스 P2의 잠금이 걸려있다며 누구의 차례인지 확인한다.
   • 만약 P1의 차례라면, 임계구역에 진입한다.
   • 만약 P2의 차례라면, 잠금을 풀고 (lock1 = false), P2가 작업이 끝날 떄 까지 (while(turn ==2) 까지 기다린다. 프로세스 P2가 작업이 끝나면 작업을 다시 걸고 (lock1=true) 임계 구역으로 접근 한다.

---

결론

피터슨 알고리즘이나 데커 알고리즘은 임계구역 해결의 3가지 조건을 모두 만족하지만, 매우 복잡하다.
프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
임계구역을 보호하기 위해 복잡한 알고리즘을 주문하는 것은 바람직한 접근 방법은 사실 아니다.