[프로세스 동기화] 3. 임계구역 해결 방법

1. 피터슨 알고리즘

 

임계구역 문제를 해결하기 위해서 게리 피터슨이 제안한 알고리즘.

 

[프로세스 P1이 임계구역에 진입하는 방법] 

1. 프로세스 P1은 임계구역에 진입하기 전에 먼저 잠금(lock1 = true) 을 한 후, turn을 2로 설정
   변수 turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못 들어가는 상황에 대비하기 위한 장치
2. while(lock2 == true && turn == 2) 문 실행 
3. 만약 프로세스2가 잠금을 설정하지 않았거나 잠금을 설정했더라도 곧바로 turn = 1로 바꾸면 프로세스 P1은 임계구역에 진입하여 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나온다. 

 

• 상호배제, 한정대기, 진행의 융퉁성 임계구역 해결의 3가지 조건을 만족
• 2개의 프로세스만 사용 가능하다는 한계가 있다. 
• 여러 프로세스가 사용하려면 공유 변수를 추가해야함

 

2. 데커 알고리즘

 

테오도뤼스 데커가 제안한 알고리즘으로 임계구역 해결의 세 가지 조건을 모두 만족한다.

 

[프로세스 P1이 임계구역에 진입하는 방법]

1. 프로세스 P1은 우선 잠금을 건다.
2. 프로세스 P2의 잠금이 걸렸는지 확인한다.
3. 만약 프로세스 P2도 잠금을 걸었다면 누가 먼저 걸었는지 turn을 통해서 확인한다. 

• turn = 1 이라면 프로세스 P1의 차례이므로 임계구역으로 진입, 임계구역 나올 때 turn = 2로 변경, lock 해제
• turn = 2 라면 프로세스 P2의 차례이므로 P1은 lock을 풀고, P2가 작업을 마칠 때 까지( turn = 1) 기다린다. 

 

피터슨 알고리즘과 데커 알고리즘은 하드웨어의 도움 없이도 가능하고, 임계구역 해결의 3가지 조건을 모두 만족하지만

프로세스가 늘어날 수록 변수도 늘어나고 전체적인 알고리즘도 복잡해진다. 또한 바쁜 대기를 사용해서 자원을 낭비한다. 임계구역을 보호하기 위해 복잡한 알고리즘을 구현하도록 주문하는 것은 바람직한 접근 방법이 아니다. 

 

3. 세마포어 

 

에츠허르 다익스트라가 제안한 알고리즘. 

임계구역에 진입하기 전에 스위치를 사용 중으로 놓고 임계구역으로 들어간다. 

이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 

프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다. 

 

문제점

세마포어의 잘못된 사용으로 인해서 임계구역이 보호받지 못하는 문제가 발생할 수 있다. 

• 프로세스가 세마포어를 사용하지 않고 바로 임계구역에 들어간 경우
• P()를 두번 사용하여 wake_up 신호가 발생하지 않은 경우, 프로세스 간의 동기화가 이뤄지지 않아 세마포어 큐에서 대기하고 있는 프로세스들이 무한 대기에 빠진다.
• P()와 V()를 반대로 사용하여 상호 배제가 보장되지 않은 경우

 

4. 모니터

 

공유 자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 굳이 P()와 V()를 사용할 필요가 없이 자동으로 처리하면 된다. 이를 구현한 것이 모니터이다.

 

모니터는 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공함으로써 자원을 보호하고 프로세스 간에 동기화를 시킨다. 

 

 

1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.