[운영체제] 4. 프로세스 동기화 (2) - 세마포, 뮤텍스, 모니터

Sleep and Wakeup

프로세스를 동기화하여 서로 다른 프로세스가 동시에 임계 구역에 존재하지 못하도록 막는 알고리즘을 '상호 배제' 라고 하였다.

상호 배제를 달성하는 간단한 알고리즘들을 정리하였는데, 이 알고리즘들은 모두 busy waiting 알고리즘으로 계속해서 공유 변수를 체크하면서 자신이 임게 구역에 들어갈 수 있는지 직접 확인해야했다.

 

busy waiting 방식은 CPU 시간을 낭비하고, 우선순위 스케줄링 방식에서 우순선위 역전 문제를 일으키기도 한다.

그래서 그 대안으로 나온 방법이 Sleep and Wakeup 이다.

 

sleep, wakeup 은 모두 시스템 콜이다.

sleep 시스템 콜을 호출하면 다른 프로세스가 wakeup 시스템 콜을 호출할 때까지 호출한 프로세스를 blocked 상태로 만든다.

(suspended 된다고 표현하기도 한다.)

즉, 내가 계속해서 확인하는게 아니라, 나중에 다 쓰면 알려달라고 하고 쉬는 방법이다.

그리고 그 동안에는 해당 임계 구역과 관련 없는 동작을 하는 다른 프로세스가 running 상태로 올라와서 CPU를 사용한다.

 

 

생산자와 소비자 문제

생산자와 소비자 문제(Producer-Consumer problem)는 상호 배제를 위한 동기화 문제에서 매우 고전적인 문제이다.

다른 이름으로는 bounded-buffer problem 이라고도 한다.

 

두 프로세스가 '고정된 크기의' 버퍼를 공유하는 상황에서,

생산자 프로세스는 버퍼에 데이터를 넣으려고 하고, 소비자 프로세스는 버퍼에서 데이터를 꺼내 읽으려고 한다.

 

만약 생산자가 새로운 데이터를 버퍼에 넣으려는데, 버퍼가 가득 찼다면 소비자가 버퍼에서 데이터를 하나라도 꺼낸 뒤 깨울 때까지 잠자기 시작한다.

비슷하게, 소비자가 데이터를 버퍼에서 꺼내려는데, 버퍼가 텅텅 비었다면 생산자가 버퍼에 데이터를 하나라도 넣은 뒤 깨울 때까지 잠자기 시작한다.

 

이때 생산자와 소비자 프로세스 사이에 적절하게 동기화가 이루어지지 않으면 버퍼에 데이터를 올바르게 저장하지 못하는 문제가 발생할 수 있다. (즉, race condition 이 발생할 수 있다)

 

경쟁 상태를 예방하기 위해 sleep and wakeup 방식으로 이 문제에 대한 코드를 작성한다면 다음과 같이 작성할 수 있다.

 

#DEFINE N 100
int count = 0; // 공유 자원, 버퍼에 들어있는 물건 개수

void producer() {

    int item;
    
    while (true) {
        item = produce_item();
        
        if (count == N) { // 버퍼가 가득찬 상황
            sleep();
        }
        
        // 이 코드가 실행된다면 wakeup 시스템 콜 호출에 의해 일어난 것
        insert_item(item);
        count += 1;
        
        if (count == 1) {  // 소비자가 이이템을 꺼낼 수 없었던 상황이므로 잠자고 있을 수 있다.
            wakeup(consumer);
        }
    }
}


void consumer() {
    int item;
    
    while (true) {
        if (count == 0) { // 아이템을 꺼낼 수 없는 상황
            sleep();
        }
        
        item = remove_item();
        count -= 1;
        
        if (count == N-1) { // 꺼내고보니 직전에 가득 차 있었다면 생산자가 잠자고 있을 수 있다.
            wakeup(producer);
        }
    }
}

 

 

하지만 과연 이렇게만 작성하면 아무런 문제 없이 코드가 돌아갈까?

프로세스 스위칭은 코드를 실행하는 중간 언제 어디서든 발생할 수 있음에 주의하자.

 

이 프로그램 초기 상태에 count = 0 일 때 소비자 프로세스가 먼저 실행되었다고 해보자.

그런데 while(true) 를 지나서 if (count == 0) 까지 실행이 되고나서 하필 이때 프로세스 스위칭이 발생한다고 해보자.

 

그러면 이때부터 생산자 프로세스가 돌아간다.

생산자는 아이템을 채운 뒤 count == 1 이 되었으므로 wakeup(consumer)를 호출한다.

하지만 이때 소비자는 자고 있는 상태가 아니었다. 그래서 아무런 의미 없이 wakeup() 호출이 끝나버린다.

 

그러다가 아이템을 계속 채워넣고 count = 100이 되었을 때 당연히 생산자는 소비자가 깨어있을 것이라고 믿고 sleep() 을 호출한 채 잠들어버린다.

하지만 다시 소비자 프로세스로 돌아왔을 때는 소비자는 이제서야 sleep() 을 호출하고 잠들어버리면서 두 프로세스 모두 영원히 잠들어버리는 문제가 발생한다.

 

따라서 위와 같은 코드는 코드의 실행 순서에 따라 결과가 바뀌는, 여전히 레이스 컨디션이 발생하는 코드이다.

이제부터 이 문제를 해결해보자.

 

 

세마포

1965년 다익스트라가 고안한 새로운 variable type 이다.

세마포는 다음과 같이 사용한다.

 

 

그러면 하나의 critical region 에는 하나의 프로세스만 들어갈 수 있다.

 

- Down (P) Operation

만약 세마포 변수가 0 보다 크면, 세마포 변수 값을 감소시키고 critical region 코드를 실행하도록 허용한다.

만약 세마포 변수가 0 이라면, 이 프로세스에 대해 sleep() 시스템 콜을 호출하여 blocked 상태로 만든다.

(혼공운체 책에서는 무한 반복문을 돌면서 함수가 종료되지 않도록 막아 critical region 코드를 실행하지 못하도록 막는다고 하였다. 이 방식은 busy waiting 방식이다.)

 

- Up (V) Operation

만약 기존에 자고 있던 프로세스가 있다면 해당 프로세스를 깨우고 down 오퍼레이션을 마저 실행하도록 한다.

기존에 자고 있던 프로세스가 없다면 세마포 변수의 값을 1 증가시킨다.

(혼공 운체 책에서는 무조건 1 증가시켰다. 역시 busy waiting 방식이기 때문이다.)

 

기존에 자고 있던 프로세스가 있다면 왜 변수를 올리지 않고 down 오퍼레이션을 마저 실행하도록 하는걸까?

그 이유는 간단하다. 그 프로세스가 자게 된 이유는 세마포 변수를 확인했을 때 이미 0이었고, 이 의미는 들어갈 수 있는 임계 구역이 남아있지 않다는 뜻이다.

 

이 상황에서 접근했다가 자게 되었다면, 다른 프로세스가 임계 구역을 나가면서 Up을 호출하자마자 바로 기존에 자던 프로세스가 일어나서 임계구역에 들어가면 똑같이 0으로 유지가 되는 것이나 마찬가지다.

따라서 기존에 잠든 프로세스가 있다면 변수값은 굳이 바꾸지 않는다.

 

그리고 이때 Down, Up 연산은 각 흐름이 더 이상 쪼개질 수 없는 atomic 한 성질을 갖는다.

그래서 보통 이 두 연산을 구현할 때는 각 연산이 실행되는 동안 인터럽트를 무시하는 시스템콜이 호출된다.

 

---

 

이제 Sleep and Wakeup 방식으로 구현된 세마포를 사용하여 소비자, 생산자 문제를 해결해보자.

먼저 기존의 문제는 잠들기 전 변수를 확인하는 과정과 실제 잠드는 과정이 프로세스 스위칭에 의해 쪼개질 수 있는 점이었다.

(이 문제를 가리켜 lost-wakeup problem 이라고 한다. 깨울 사람이 없는데 깨우는, wakeup 동작을 잃어버린 것이다.)

 

이 문제를 해결하기 위해서는 2가지 문제를 해결해야 한다.

첫 번째는 공유 버퍼에 여러 프로세스가 동시에 접근하는 상황을 막아야 한다. (상호 배제)

따라서 공유 버퍼에 대해 상호 배제를 보장하기 위해서 mutex 라는 이름의 공유 변수를 사용한다.

특히 이때의 뮤텍스는 'binary mutex' 로 동작한다. 초기값을 1로 가지며, 2개 이상의 프로세스에 대해 임계구역에 들어갈 수 있는 프로세스를 최대 1개로 제한하는 것이다. (꼭 바이너리일 필요는 없다. 만약 임계 구역의 개수가 많다면 그 개수만큼 초기값을 설정할 수 있다.)

 

두 번째는 생산자 프로세스는 버퍼가 가득차면 멈추고, 소비자 프로세스는 버퍼가 비면 멈추는 동작을 맞춰서 수행해야 한다.

즉, 생산자는 소비자가 자원을 소비한 이후에 생산해야 하고, 소비자는 생산자가 자원을 생산한 이후에 소비해야 한다.

따라서 이 실행 순서의 동기화를 위해 full, empty 변수를 사용한다.

full 변수는 버퍼가 가득 차있는 수의 개수를 세고, empty 는 버퍼가 비어있는 수의 개수를 센다.

 

각 변수에 대해  세마포를 적용한 코드는 아래와 같다.

 

#DEFINE N 100
// count 변수는 사용하지 않는다.
// int count = 0; // 공유 자원, 버퍼에 들어있는 물건 개수
// 

semaphore mutex = 1;
semaphore full = 0;
semaphore empty = N;

void producer() {

    int item;
    
    while (true) {
        item = produce_item();
        
        // insert_item 이라는 critical region 에 접근하기 전에 세마포 down 연산 수행
        down(&empty);  // empty 를 감소시킨다. 만약 이미 0이라면 sleep()
        down(&mutex);  // mutex 를 감소시킨다. 만약 이미 0이라면 sleep()
        
        insert_item(item);

		up(&mutex);    // mutex 변수 down에 의해 자고 있는 프로세스는 깨우고, 없으면 값 증가
        up(&full);     // full 변수 down에 의해 자고 있는 프로세스는 깨우고, 없으면 값 증가 
    }
}


void consumer() {
    int item;
    
    while (true) {
    
        down($full);   // full 감소. 이미 0이라면 sleep() (삭제할 데이터가 없으므로)
        down($mutex);  // 임계 구역 설정. 이미 0이라면 sleep()
        
        item = remove_item();
        
        up($mutex);   // 임계 구역 탈출. 자고 있는 프로세스를 깨우거나 값 증가
        up($empty);   // 자고 있는 프로세스를 깨우거나 empty값 증가
    }
}

 

 

기존의 count 변수와 관련된 코드 대신 세마포 기능을 3개 변수에 적용하여 활용한다.

(현재 공유데이터는 mutex, full, empty 이다. 세마포는 특별한 변수 타입임을 기억하자!)

 

초기에 아무런 아이템이 없는 상태에서 consumer 가 먼저 호출되는 경우,

down($full) 에 의해 full 변수의 값을 먼저 감소시켜야 하는데, 초기값이 0이므로 소비자는 sleep() 한다.

이때 down() 은 세마포 연산으로서 쪼개질 수 없으므로 lost-wakeup 문제는 발생하지 않는다.

(이때 뮤텍스가 먼저 호출되면 안된다!! 뮤텍스는 두 프로세스 모두 full / empty 안쪽 범위에서 호출되어야 한다.)

 

다음으로 생산자 프로세스가 실행되면 생산자 프로세스 역시 처음으로는 down($empty) 를 먼저 호출한다.

(뮤텍스는 그 다음이다. 감소시킬 수 있는지 체크하고, 실제로 remove_item 을 수행할 때 뮤텍스로 락을 걸어둔다.)

초기값으로는 emtpy = N 이므로 아이템을 생산해서 넣을 수 있기에 empty 값을 1 감소시키고 다음 코드를 실행한다.

 

아이템을 생산하고 버퍼에 넣기 위해 임계 구역에 진입하며 down($mutex) 를 호출한다.

초기값으로 mutex = 1 이므로 크리티컬 리전에 들어가며 mutex 변수 값을 감소시킨다.

다음으로 insert_item() 함수를 호출하고, 임계 구역 코드가 종료된다.

따라서 up($mutex) 를 통해 mutex 변수값을 되돌린다. (mutex 변수와 관련되어 자고 있는 프로세스가 없으므로)

다음으로는 up($full) 을 호출하는데, 이때 full 변수와 관련되어 소비자 프로세스가 자고 있으므로 깨운다.

 

깨어난 소비자 프로세스는 down($full) 함수를 통과하여 (변수값은 조정하지 않는다) down($mutex) 를 호출하고 정상적으로 아이템을 소비한다. 아이템 소비가 끝나면 up($mutex) 를 호출하여 락을 풀어두고, up($empty) 를 호출한다.

이때 자고있는 프로세스는 없으므로 실제 empty 변수값이 1 증가한다.

 

 

세마포와 같은 공유 자료구조는 보통 '커널 영역'에 존재하며, 시스템 콜에 의해서만 접근할 수 있다.

대부분의 현대 운영체제에서는 프로세스들이 자신의 address space 를 다른 프로세스와 공유할 수 있는 방법을 제공한다.

(하지만 이런 방법이 없더라도 file을 공유해서 같은 효과를 달성할 수 있기는 하다.)

 

---

뮤텍스 (Mutex)

이 뮤텍스는 위에 세마포에서 변수명으로 등장한 '뮤텍스' 와는 다르다.

(세마포에서는 그냥 변수 이름을 뮤텍스로 지은 것 뿐이다. 관련성이 아예 없지는 않지만..)

뮤텍스는 상호 배제를 위한 또 다른 알고리즘으로, 세마포의 단순화된 버전이다.

 

뮤텍스는 Locked, Unlocked 2가지 상태를 갖는 변수이다.

이때 Unlocked 상태는 0이고, Locked 상태는 0이 아닌 값을 갖는다.

(세마포에서 0이 아닌 값이면 1 감소시키면서 임계구역에 들여보냈던 것과 동일하다)

 

뮤텍스를 사용할 때는 세마포와 비슷하게 다음과 같은 흐름으로 사용한다.

 

 

 

이러면 역시 critical region 에 들어갈 때는 하나의 프로세스만 들어갈 수 있게 된다.

뮤텍스는 TSL instruction 을 사용하여 다음과 같이 구현할 수 있다.

 

mutex_lock:
    TSL REGISTER, MUTEX
    CMP REGISTER, #0
    JZE ok
    CALL thread_yield
    JMP mutex_lock

ok:
    RET


mutex_unlock:
    MOVE MUTEX, #0
    RET

 

 

TSL 명령어는 test and set lock 의 줄임말로, mutex 변수의 값을 register 에 복사하고, mutex 변수의 값을 1로 설정한다.

만약 기존에 mutex 변수에 저장되었었던 값이 0 이었다면, 이번에 막 0에서 1로 세팅된 상태이므로 ok 로 점프하고 함수가 종료된다.

(JZE = Jump if Zero Equal)

따라서 mutex_lock 코드를 빠져나가므로 critical region 에 들어갈 수 있다.

 

만약 mutex_lock 코드를 실행했을 때 기존의 MUTEX 변수의 값이 1로 설정되어 있었다면, thread_yield 함수가 실행된다.

현재 스레드에서 임계 구역에 들어가려고 보니 이미 누군가 다른 스레드가 들어갔기 때문에 자신은 더 이상 아무 행동도 할 수 없으니 자신은 쉬고 다른 스레드에게 차례를 양보하는 것이다. 그러면 스레드 단위에서 자신은 ready 상태로 빠지고 다른 스레드를 running 으로 올리게 되어 sleep, wakeup이 자연스럽게 발생한다. 그리고 다른 스레드가 실행되고 다시 자신의 실행 차례로 돌아오면 mutex_lock 코드를 다시 실행한다.

(그런데 엄밀하게는 wakeup 이 임계 구역에 들어갔던 스레드가 호출하는게 아니라, 스케줄링에 의해 호출되는 것이므로 busy waiting 방식에 조금 더 가깝지 않을까? 싶기도 한데, '자기 차례가 왔을 때' 기준으로는 한번만 체크하고 잠들어버리니까 sleep이 맞는 것 같기도 하다. => 나중에 설명해주실 때는 일단 busy waiting 방식은 아니라고 하셨다.)

 

임계 구역에서 할 일을 다 마쳤다면 mutex_unlock 코드를 실행하여 MUTEX 변수 값을 원래대로 되돌린다. (0으로 초기화)

(혼공운체 책에서는 뮤텍스 락을 acquire(), release() 함수로 구분하고, 바쁜 대기 방식으로 구현하였다.)

 

 

---

모니터 (Monitors)

세마포 방식은 사용하기가 복잡한 단점이 있다.

 

 

위와 같은 코드에서 down() 오퍼레이션의 순서가 바뀌는 경우 문제가 발생하므로 순서를 정확히 지켜서 사용해주어야 하기 때문이다.

순서가 바뀌는 경우, 아무 아이템이 없는 상태에서 소비자 -> 생산자 순서로 호출된다고 생각해보자.

소비자가 일단 뮤텍스 락을 걸고 소비를 하려고 보니 소비할 물건이 없어서 잠들어버렸다. 이 상황에서 생산자 코드가 실행되면, 뮤텍스를 소비자가 걸어둔 상태라서 생산자도 뮤텍스가 풀릴 때까지 잠에 빠지면서 두 프로세스 모두 잠들어버리는 문제가 발생한다.

 

이렇게 사용하기 어려운 문제를 해결하는 방법으로서 '모니터'가 등장했다.

모니터는 하나의 모듈이나 패키지로서, 그 내부에 자료구조를 만들어두고 프로세스가 직접 접근하지 못하도록 막아둔다.

대신 프로세스가 자료구조에 값을 읽고 쓸 수 있도록하는 방법을 제공해준다.

(그래서 보통 언어, 컴파일러 레벨에서 모니터를 제공해준다. 대표적인 언어가 자바)

 

모니터 역시 프로세스 동기화를 위해 상호 배제를 제공하므로, 특정 시점에는 모니터 내에서 하나의 프로세스만 활성화 될 수 있다.

모니터를 사용한 상호 배제 방법을 구체적으로 정리해보자.

 

 

모니터는 'Condition Varaible (조건 변수)' 를 가지며, 이 변수에 대해 2가지 기능을 제공한다.

 

1. wait()

wait() 기능은 이 기능을 호출한 프로세스를 조건 변수에 대해 Blocked 상태로 만들고, 다른 프로세스가 모니터에 들어올 수 있도록 한다.

 

2. signal()

이 조건 변수에 대해 Blocked 상태로 빠져있던 프로세스를 깨운다.

 

 

구체적으로 모니터 방식을 사용하여 생산자-소비자 문제를 해결하는 코드를 살펴보자.

 

코드를 살펴보면, 먼저 full, empty 라는 condition variable 을 설정한다.

(마치 세마포에서 세마포 타입의 full, empty 변수를 선언한 것과 같다.)

그리고 count 변수는 interger 타입으로 선언한다.

 

모니터는 insert, remove 메서드를 제공한다.

insert() 메서드는 버퍼가 가득 차있다면 full 변수에 대해 wait() 를 호출하고,

처음 아이템을 생성해서 넣었다면 empty 변수에 대해 signal() 을 호출한다.

remove() 메서드는 버퍼가 비어있다면 empty 변수에 대해 wait() 를 호출하고,

가득 찬 상태에서 아이템을 처음 뺐다면 full 변수에 대해 signal() 을 호출한다.

 

기존에 세마포 변수는 full, empty 도 결국 정수값을 갖는 변수로서, 그 자체가 의미있는 중요한 데이터였지만,

모니터에서 full, empty 는 그저 '조건' 상태를 나타낼 뿐이다.

 

wait(full) 은 full 변수에 대해 어떤 증감도 없이 그저 full 상태가 되었으니 signal(full) 이 발생할 때까지 Blocked 상태가 되어 기다리라는 것이고,

wait(empty) 는 empty 변수에 대해 어떤 증감도 없이 그저 empty 상태가 되었으니 signal(empty) 가 발생할 때까지 Blocked 상태가  되어 기다리라는 것과 같다.

 

 

이 상태에서 생산자, 소비자 프로시저를 보면, 각 프로시저는 그저 무한 반복을 돌면서 아이템을 만들어서 넣고, 아이템을 꺼낸뒤 소비하는 것만을 반복한다.

 

세마포와 비교해보면 mutex 변수가 없는 것만 제외하면 동일한데 과연 어떻게 뮤텍스 변수 없이 상호 배제를 달성할까?

모니터는 그 자체로 기본적으로 상호 배제가 깔려있는 상태라고 보면 된다.

 

위 코드에서 두 프로세스는 동시에 무한 루프를 돌면서 모니터에 있는 프로시저와 함수를 실행하려고 할 것이다.

이때 ProducerConsumer.remove, ProducerConsumer.insert 를 호출한다는 것은 곧 모니터 안에 들어오겠다는 것과 같으며, 두 프로세스가 동시에 돌면서 각각 remove, insert 를 호출하더라도, 둘 중 하나의 프로세스만 들어올 수 있고 나머지는 들어올 수 없도록 막힌다. 그리고 그렇게 막힌 프로세스는 모니터 내부에서 wait() 을 호출할 때 비로소 들어올 수 있게 된다.

 

이번에도 한번 아무것도 없는 초기상태에서부터 소비자 코드가 실행되는 상황을 생각해보자.

count = 0 이므로 wait(empty) 가 호출되어 소비자 프로세스는 blocked 상태에 빠진다.

그리고 이때는 기존의 소비자 코드가 여전히 모니터에 들어있음에도 불구하고, 다른 프로세스가 모니터에 들어오는 것을 허용해준다.

(세마포에서는 full = 0 이므로 잠들었었다.)

 

따라서 프로세스 스위칭이 발생하면서 생산자 코드가 실행되었을 때, 생산자 프로세스 역시 모니터에 들어와서 코드를 실행할 수 있다.

생산자는 아이템을 넣고 카운트를 증가시킨 뒤, count = 1 이므로 signal(empty) 를 호출하여 잠자던 소비자 프로세스를 깨운다.

 

그러면 이 순간, 모니터에는 2개의 프로세스가 active 한 상태로 남아있게 되는데, 이 문제를 해결하기 위해 '호어' 라는 학자가 제시한 방법은 깨어난 소비자 프로세스가 이어서 진행을 하고, 깨워준 생산자 프로세스는 blocked 상태로 빠진다.

 

또는 다른 방법으로는 위 코드처럼 무조건 signal() 함수를 함수의 마지막에 호출하도록 제한하는 방법도 있다.

이 경우 함수가 종료되고 생산자 프로세스가 모니터를 빠져나온 상태에서 다시 insert 메서드를 호출하고 모니터에 들어가기를 기다린다.

(소비자가 아직 모니터에 남아있으므로 들어갈 수 없다.)