임계영역 해결 조건
1. 상호 배제 문제
프로세스 P1과 P2는 임계영역에 진입하기 전에 코드를 통해 임계구역에 잠금이 걸려 있는지 확인한다(lock == true).
잠겨있다면 다른 프로세스가 임계영역에서 작업하고 있다는 뜻이므로 잠금이 해제될 때까지 무한 루프를 돌며 기다린다(lock == false).
임계영역에 있는 프로세스가 작업을 마치고 잠금을 해제하면 무한 루프를 빠져나와 작업을 한다.
'lock = false;'는 임계구역을 사용해도 좋다고 다른 프로세스에 보내는 동기화 신호이다.
잠금이 풀려 새로 임계영역에 진입하는 프로세스는 다른 프로세스가 진입하지 못하도록 잠금을 걸고 작업을 하며 작업을 끝내면 다른 프로세스가 사용할 수 있도록 잠금을 해제한다.
동시 진입 상황(상호 배제 조건을 충족하지 않는 경우)
1. 프로세스 P1은 while(lock == true);문을 실행한다. 임계구역에 프로세스가 없으므로 무한 루프를 빠져나오는데, 다음 문장을 실행하려던 순간 자신에게 주어진 CPU 시간을 다 써서(타임아웃) 준비 상태로 옮겨진다. 문맥 교환이 발생하고 프로세스 P2가 실행 상태로 전환된다.
2. 프로세스 P2는 while(lock == true);문을 실행한다. lock은 false이며 P2는 임계영역에 진입할 수 있게 된다.
3. P1은 lock=true;을 실행하고 임계구역에 잠금을 걸고 진입한다.
4. P2도 lock=true;을 실행하고 임계구역에 잠금을 걸고 진입하게 된다. 결국 둘 다 임계영역에 진입하게 된다.
- P1은 while(lock==true)을 실행하고 나서 곧바로 lock=true;를 실행해야 다른 프로세스가 임계영역에 진입하는 것을 막을 수 있다. 그러나 lock=true를 하기 전에 P2가 while(lock==true);을 실행하게 되어 둘 다 임계구역으로 진입하게 되었다. 이 같은 경우에선 상호 배제 조건을 보장할 수 없게 된다.
또 다른 문제점은 잠금이 풀리기를 기다리려면 바쁜 대기를 한다는 것ㅅ이다. while(lock == true) 부분에서 작업을 할 필요가 없는 시간인데도 무한 루프를 돌면서 시스템 자원을 낭비하게 된다.
2. 한정 대기 문제
앞의 문제를 보완하여 작성한 코드이다.
P1은 임계구역에 진입하기 전에 먼저 잠금을 설정하고 P2가 잠금을 설정했는지 확인한다. 잠겨있지 않다면 임계구역에 진입하여 작업을 마친후 잠금을 해제한다. P2도 마찬가지이다.
잠금을 2개 사용하여 일단 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 두 프로세스의 상호 배제가 보장된다.
무한 대기 상황(한정 대기 조건을 충족하지 않는 경우)
1. P1은 lock1=true를 실행한 후 자신의 CPU 시간을 다 소모하고, 문맥 교환이 발생하여 P2가 실행 상태로 전환된다.
2. P2도 lock2=true를 실행한 후 자신의 CPU 시간을 다 소모하고 문맥 교환이 발생하여 P1이 실행 상태로 전환된다.
3. P2이 lock2=true를 실행했으므로 P1은 while(lock2==true)에서 무한루프에 빠진다.
4. P2도 마찬가지로 while(lock1==true)에서 무한루프에 빠지게 된다.
- 결국 P1, P2 둘다 무한 루프에 빠져 임계영역에 진입할 수 없게 되었다. 이는 한정 대기 조건을 만족하지 못하는 상황으로 Deadlock이라 말한다. 교착 상태에서는 프로세스가 살아 있으나 작업이 진행되지 못하는 상태를 말한다.
확장성의 문제도 있다. P1은 자신의 lock1을 잠그고 lock2를 검사하는데, 만약 프로세스가 3개 이상이라면 프로세스의 개수대로 검사해야알 전역변수 lock의 개수가 늘어나 비효율적이다.
3. 진행 문제
상호 배제와 한정 대기 조건을 만족하나 진행의 융통성은 만족하지 않는 코드이다. lock 값이 1이면 프로세스 P1이 임계구역을 사용한다는 뜻이고 2이면 P2가 임계구역을 사용한다는 뜻이다.
공유 변수 lock의 값을 통해 다른 프로세스가 임계구역에 있는지 확인하고 없다면 진입한다. 상호배제와 한정 대기 조건은 만족하지만 서로 번갈아가면서 실행된다는 것이 문제이다. 한 프로세스가 연속으로 두번 진입하고 싶어도 매커니즘상 불가능하다. 우선순위에 상관없이 임계구역에 번갈아가며 진입하므로 다른 프로세스의 진행을 방해한다고 볼 수 있다. 이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(Lockstep synchronization)라고 한다.
4. 하드웨어적 해결 방법
잠금이 걸렸는지 검사하는 부분과 잠금 설정하는 부분이 분리되어 실행되면 문제가 발생할 수 있으므로 하드웨어적으로 두 명령어를 동시에 실행하면 임계구역 문제를 쉽게 해결할 수 있다. 하지만 바쁜 대기를 사용하여 자원 낭비 문제가 발생한다.
피터슨 알고리즘
P1은 임계구역에 진입하기 전 잠구고 turn을 2로 설정한다. turn은 두 프로세스가 동시에 lock을 설정하여 임계구역에 못들어가는 상황에 대비하기 위한 장치이다. 즉 두 프로세스가 동시에 lock을 설정했더라도 turn을 이용하여 다른 프로세스에게 양보한다. 이어서 while문을 실행한다. 만약 P2가 잠금을 설정하지 않았거나 잠금을 설정했더라도 곧바로 turn = 1로 바꾸면 P1은 임계구역에 진입해 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나온다. P2도 같은 방식으로 임계구역에 진입한다.
- 세 가지 조건을 모두 만족하지만 2개의 프로세스만 사용가능하다는 한계가 있다.
데커 알고리즘
이 알고리즘은 하드웨어의 도움 없이도 임계구역 문제를 해결할 수 있다. 하지만 매우 복잡하고 프로세스가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 더 복잡해진다.
Process P1
lock1 = true; // 공유 변수
while(lock2 == true){
if(turn == 2){ // P2의 차례
lock1 = false;
while(turn == 2); // P2가 작업을 마칠때 까지 기다림
lock1 = true;
}
}
/*
Critical section
*/
turn = 2; // 공유 변수
lock1 = false;Process P2
bool lock2 = true; // 공유 변수
while(lock1 == true){
if(turn == 1){ // P1의 차례
lock2 = false;
while(turn == 1); // P1이 작업을 마칠때 까지 기다림
lock2 = true;
}
}
/*
Critical section
*/
turn = 1; // 공유 변수
lock2 = false;P1은 먼저 잠그고 나서 P2의 잠금이 걸렸는지 확인한다. 만약 P2도 잠겨있다면 누가 먼저인지 (turn) 확인한다. P1의 차례라면 임계구역으로 진입하고, P2의 차례라면 임계구역으로 진입한다. 그리고 P1은 잠금을 풀고 P2가 작업을 마칠 때까지 기다린다. P2가 작업을 마치면 잠금을 걸고 임계구역으로 진입한다.
