[OS] 임계구역

프로세스 동기화 - 임계구역 문제와 해결방법

Race Condition(경쟁 조건)

두 개 이상의 프로세스가 shared resource(공유 자원)룰 병행적으로 읽거나 쓰는 상황을 Race condition이라고 한다.

다음의 예시를 생각해보자

잔액이라는 전역변수가 있다. 두 사람(프로세스)이 변수 ‘잔액’에 대해 입금을 한다. 프로세스 P1은 잔액에 20만원이 있는 것을 확인하고 10만원을 입금했다. 동시에 ,프로세스 P2도 잔액에 20만원 있는 것을 확인하고 30만원을 입금하였다.
작업이 완료되면 잔액은 총 20+10+30=60만원이어야 한다. 그런데 잔액은 50만원 뿐이다. 두 프로세스가 동시에 잔액이 20만원인 것을 확인한 후 다른프로세스의 작업을 덮어쓰는 바람에 예상과 다른 잔액이 저장된 것이다. 잔액이 60만원이 나오려면 P1이 입금을 마친 후에 P2가 잔액을 확인하고 입금을 하거나 P2가 입금을 마친 후 P1이 입금해야 한다.

이와 같이 공유 자원에 접근하는 경우, 프로세스나 스레드가 수행되는 시점을 조절하는 것을 Synchronization 이라고 한다.


Critical Section(임계구역)

공유 자원 접근 순서에 따라 실행결과가 달라지는 프로그램의 영역을 Critical section이라고 한다.
위의 ‘잔액’ 예시에서는, 하나의 프로세스가 전역변수 ‘잔액’을 사용하는 부분(잔액을 확인하고 입금한 후 저장하는 부분)이 임계구역이다. 임계구역에서는 프로세스들이 동시에 작업하면 안된다. 한 프로세스가 임계구역에 들어가면 다른 프로세스는 그 프로세스가 나와야 임계구역에 들어갈 수 있다.


임계구역 문제 해결 조건

문제를 해결하려면 다음의 3가지 조건을 만족하면 된다.


임계구역 문제 해결 방법

임계구역 문제를 해결하는 단순한 방법은 lock을 사용하는 것이다. 임계구역에 들어갈 때는 잠그고, 나올 때는 잠금을 해제하는 것이다.

bool lock = false;
int balance;

int main(){
  while(lock==true);
  lock = true;
  balance = balance + 10; //임계구역
  lock = false;
}

피터슨 알고리즘

bool lock1 = false;
bool lock2 = false;
int turn = 1;
lock1 = true;
turn = 2;
while(lock2 == true && turn == 2);
//임계구역
lock1 = false;
lock2 = true;
turn = 1;
while(lock1 == true && turn == 1);
//임계구역
lock2 = false;

변수 turn은 두 프로세스가 동시에 lock을 하여 임계구역에 못들어가는 상황에 대비하기 위한 것이다. P2가 lock을 설정했더라도 바로 turn 값을 1로 바꾸면 P1은 임계구역에 들어가 작업을 마친 후 잠금을 해제하고 임계구역을 빠져나온다.
피터슨 알고리즘은 임계구역 해결 조건의 3가지를 모두 만족하지만, 2개의 프로세스만 사용 가능하다는 한계가 있다.

데커 알고리즘

bool lock1 = false;
bool lock2 = false;
int turn = 1;
lock1 = true; // 1. P1의 잠금을 설정함
while(lock2 == true){ //2. P2의 잠금이 걸렸는지 확인함
  if(turn == 2){      //3. P2도 잠금이 걸렸다면 누구 차례인지 확인. P1의 차례라면 임계구역에 진입  
    lock1 = false;    //4-1.P2의 차례라면 잠금을 풀고,
    while(turn == 2); //P2의 작업이 끝날때 까지 기다림
    lock1 = true;     //P2가 작업을 마치면 잠금을 설정하고 임계구역 진입
  }
}
/*임계구역*/           
turn = 2;       
lock1 = false;        
lock2 = true;
while(lock1 == true){
  if(turn == 1){
    lock2 = false;
    while(turn == 1);
    lock2 = true;
  }
}
/*임계구역*/
turn = 1;
lock2 = false;

데커 알고리즘 또한 3가지 조건을 모두 만족하고, 데커 알고리즘과 달리 하드웨어의 도움 없이도 임계구역 문제를 해결할 수 있다. 그러나 프로세스가 늘어나면 전체 알고리즘이 복잡해지기 때문에 바람직하지 않다.

세마포어

세마포어는 임계구역에 진입하기 전 토글 스위치를 ‘사용 중’으로 놓고 임계구역에 들어간다. 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠 때까지 기다린다. 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

Semaphore(n); //RS = n; (RS에는 현재 사용가능한 자원의 수가 저장됨)
P();    //if(RS > 0) RS = RS -1;  (RS 1빼고 임계구역 진입)
        //else block(); (0보다 커질때까지 대기)

/*임계구역*/

V();    //RS = RS + 1;
        //wake_up(); (세마포어에서 기다리는 프로세스에게 임계구역에 진입하라는 신호)

세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어큐에 저장되어 있다가 wake_up 신호를 받으면 임계구역에 진입한다. 따라서 바쁜대기를 하는 프로세스는 없지만, P()나 V() 내부 코드가 실행되는 도중 다른코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못한다. 그러므로 P()와 V() 내부코드는 분리 실행되지 않고 완전히 실행되게 해야 한다.

모니터

세마포어는 단순하고 사용하기 편하지만, 사용자의 잘못된 사용으로 인해 임계구역이 보호받지 못할 수 있다. 공유자원을 사용할 때 모든 프로세스가 세마포어 알고리즘을 따른다면 P()와 V()를 사용할 필요 없이 자동으로 처리하면 되는데, 이것을 구현한 것이 모니터이다.

모니터는 공유자원에 접근하기 위한 인터페이스만 제공하여(내부적으로 숨김) 자원을 보호하고 프로세스 동기화를 시킨다. 모니터는 시스템콜과 같은 개념이다.

운영체제가 관리하는 자원을 사용자가 잘못 사용하게 두면 시스템 자원이 망가질 수 있다. 따라서 운영체제는 시스템 자원을 사용자로부터 숨기면서 요구사항을 처리할 수 있는 인터페이스만 제공하는데, 이것이 바로 시스템콜 이다.

사용자는 잠금이나 세마포어를 사용하지 않고 명령(함수)만 사용한다. 모니터는 모니터 큐에 프로세스의 요청을 넣은 후 순서대로 실행하고 그 결과만 해당 프로세스에 알려준다.

모니터는 내부적으로 상태변수를 사용한다.