임계 영역

와! 오늘 개강!

교착 상태(Dead Lock)

교착 상태는 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원(공유 자원)을 서로 기다릴 때 무한 대기에 빠지는 상황입니다. 이런 공유 자원이 속해 있어 교착 상태가 발생할 수 있는 영역을 임계 영역이라고 합니다.

공유 자원(Shared Resource)

시스템 안에서 각 프로세스, 쓰레드가 함께 접근할 수 있는 자원이나 변수 등을 의미합니다.
이 공유 자원을 2개 이상의 프로세스가 동시에 읽거나 쓰려하는 상황을 경쟁 상태(Race Condition)이라고 합니다. 경쟁 상태는 동시에 접근을 시도할 때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태입니다.

임계 영역(Critical Section)

임계 영역은 한 순간에 반드시 하나의 프로세스만 진입해야 하는데, 프로그램에서 임계 자원을 이용하는 부분으로 공유 자원의 독점 사용을 보장하는 코드 영역입니다. 공유되는 자원, 즉 동시 접근하려고 하는 자원에서 문제가 발생하지 않게 독점을 보장해줘야 하는 영역입니다.

임계 영역을 해결하기 위한 방법

세마포어, 뮤텍스 등이 있습니다. 여러 프로세스나 쓰레드가 공유 자원에 접근하는 것을 제어하기 위한 방법입니다. 병행 처리를 위한 프로세스 동기화 기법이기도 합니다.
이들은 모두 상호 배제, 한정 대기, 융통성이라는 조건을 만족합니다.

• 상호 배제 : 한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없습니다.
• 한정 대기 : 특정 프로세스가 영원이 임계 영역에 들어가지 못하면 안됩니다.
• 융통성 : 임계 영역에 들어간 프로세스가 없는 상태에서 여러 프로세스가 진입을 시도한다면, 어느 것이 들어갈지를 적절히 결정해주어야 합니다.

세마포어(Semaphore)

세마포어는 정수 값을 가지는 변수로 볼 수 있습니다. 그 정수 값은 접근할 수 있는 최대 허용치 만큼 동시에 사용자 접근을 할 수 있게 합니다.

• semWait 연산 : 세마포어 값을 감소시킵니다. 만일 값이 음수가 되면 semWait을 호출한 프로세스는 block됩니다. 음수가 아니라면 프로세스는 계속 수행될 수 있습니다.
• semSignal 연산 : 세마포어 값을 증가시킵니다. 만약 값이 양수가 아닌 0이나 음수일 경우 semWait 연산에 의해 blocked된 프로세스들을 깨웁니다.

struct semaphore{
    int count;
    queueType queue;
};

void semWait(semaphore s){
    s.count--;
    if(s.count < 0){
        // 이 구역으로 들어왔다는 것은 현재 프로세스(혹은 쓰레드)가 공유 자원에 접근할 수 없다는 것을 의미
    	// 요청한 프로세스를 s.queue에 연결
        // 요청한 프로세스를 블록 상태로 전이 시킴
    }
}

void semSignal(semaphore s){
    s.count++;
    if(s.count <= 0){
        if (s.count <= 0){
            // count가 0보다 작거나 같다는 것은 대기하고 있는 프로세스(또는 스레드)가 존재한다는 것을 의미
            // s.queue에 연결되어 있는 프로세스를 큐에서 제거
            // 프로세스의 상태를 실행 가능으로 전이시키고 ready list에 연결
        }
    }
}

// 구현부
const int n = /*프로세스 개수*/;
semaphore s = 1;

void P(int i){
    while(true){
        semWait(s);

        // 임계 영역(Critical Section)

        semSignal(s);

        // 임계 영역 이후의 코드
    }
}

int main(){
    parbegin(P(1), P(2), ..., P(n));

    return 0;
}

세마포어는 유지할 수 있는 값의 범위에 따라 이진 세마포어와 범용 세마포어(카운팅 세마포어)로 구분됩니다. 예시 코드의 세마포어는 범용 세마포어(General Semaphore) 또는 카운팅 세마포어(Counting Semaphore)로 불리며, 세마포어의 초기값이 0 이상의 수입니다.
이진 세마포어(Binary Semaphore)는 세마포어의 초기 값으로 0 또는 1만 가질 수 있는 세마포어입니다. 이때, 이진 세마포어는 후술할 뮤텍스와 비슷합니다.

뮤텍스(Mutax)

뮤텍스는 이진 세마포어와 같이 초기값을 0과 1로 가집니다. 임계 영역에 들어갈 때 lock을 걸어 다른 프로세스나 쓰레드가 임계 영역에 접근하지 못하도록 막고, 작업이 끝나 임계 영역에서 나올 때는 해당 lock을 unlock합니다.

int mutex = 1;

void lock(){
    while(mutex != 1){
        // mutex 값이 1이 될 때까지 기다린다
    }

    // 이 구역에 도착했다는 것은 mutex 값이 1이라는 의미이므로, 이제 mutex 값을 0으로 만들어 다른 프로세스나 쓰레드가 접근하지 못하도록 막아야 함
    mutex = 0; // lock
}

void unlock(){
    // 임계 구역에서 나온 프로세스는 다른 프로세스가 접근할 수 있도록 lock을 해제한다
    mutex = 1;
}

• 세마포어는 공유 자원에 세마포어 변수만큼의 프로세스나 쓰레드가 접근할 수 있지만, 뮤텍스는 오직 1개만의 프로세스나 쓰레드만 접근할 수 있습니다.
  
• 세마포어는 현재 수행 중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있지만, 뮤텍스는 lock을 건 프로세스가 반드시 그 lock을 해제해야 합니다.

참고

• 임계 영역
• 세마포어와 뮤텍스

• cs
• muk