[운영체제] 고전적 동기화 문제-1 : 유한 버퍼 문제(The Bounded-Buffer Problem)

참고도서: Operating System Concepts (10/E) Abraham Silberschatz, Peter B. Galvin, Greg Gagne

다시 찾아온 생산자-소비자 문제

이전에 공부했던 생산자 소비자 문제가 다시 찾아왔다. 생산자-소비자 문제 혹은 유한 버퍼 문제는 어떤 버퍼에 생산자는 계속해서 자원을 넣으려고 하고, 소비자는 계속해서 자원을 빼내려고 할 때, 효과적으로 이 둘의 행동을 제어하는 문제이다. 세마포어를 통해 생산자 소비자 문제를 해결하기 위해 우리에겐 다음과 같은 자료구조가 필요하다

int n;
semaphore mutex = 1;  // 사호배제를 위한 임계구역 진입여부 표시
semaphore empty = N;  // 비어있는 버퍼의 자리 개수
semaphore full = 0;   // 차있는 버퍼의 자리 개수

우리가 가지고 있는 유한한 버퍼의 크기가 N일 때, 소비자는 버퍼에서 한번의 하나의 자원을 획득해간다. 이때 empty semaphore는 빈자리가 하나 늘어났기 때문에 1 증가하고, full semaphore는 차 있던 버퍼 한 자리가 비워졌기 때문에 1 감소한다.

세마포어로 유한 버퍼 문제를 구현해보자

생산자(Producer)

do {
    /* 자원 생성 */

    wait(empty); // 빈자리가 생길 때까지 대기한다
    wait(mutex); // 임계구역 진입이 획득될 때까지 대기한다

    /* 버퍼에 자원 넣기 */

    signal(mutex); // 임계구역 진입 lock을 푼다
    signal(full);  // 버퍼에 새로 들어간 자원이 있다는 것을 알린다.

} while(true);

Producer의 역할을 자원을 버퍼에 넣는 것이다. 이런 맥락에서 위 코드를 해석해보면 Producer가 하는 일의 과정은 다음과 같다.

1. 버퍼에 넣을 자원 정하기
2. 버퍼에 빈자리가 있는지 확인, 빈자리가 없다면 대기
3. 빈자리가 생기면 lock 획득 후 임계구역 진입
4. 임계구역 내에서 버퍼에 자원 넣기
5. 임계구역 탈출
6. 임계구역을 빠져나오면서 lock 해제 및 full signal 실행

결국 생산자가 하는 역할은 빈자리가 생겼을 때 넣을 자원을 준비해두고 빈자리가 생길때까지 대기하다가 빈자리가 생기는 순간에 임계구역으로 진입해서 빈자리에 자원을 넣어주는 것이다.

소비자(Consumer)

do {
    wait(full);  // 자원 대기
    wait(mutex); // lock 획득
    ...
    /* 버퍼에서 자원 하나 가져오기. 해당 버퍼는 비워진다. */
    ...
    signal(mutex); // lock 해제
    signal(empty); // 자원을 하나 가져갔기 때문에 버퍼에 빈자리가 생겼다는 것을 알린다.

    /* 가져온 자원을 사용한다 */

} while(true);

Consumer 의 역할은 버퍼에 남아있는 자원이 있다면, 해당자원을 버퍼에서 꺼내 가져오는 것이다. 이 맥락에서 위 코드를 읽어보면 Consumer의 작업은 다음과 같은 과정으로 이루어진다.

1. full semaphore를 읽어서 버퍼에 자원이 있는지 확인
2. 자원이 있다면 계속 진행, 자원이 없다면 대기
3. 자원이 있으면 lock을 획득하고 임계구역으로 진입해서 자원을 하나 소비
4. 임계구역 탈출
5. 임계구역을 빠져나오면서 lock 해제 및 empty signal 실행

위와 같이 소비자를 구성하게 되면, 소비자는 버퍼가 오나전히 비워져있지 않다면 버퍼에 접근해서 자원을 하나 가져오게되고, 자원이 빠져나갔다는 것을 signal을 통해 알리게 된다.

lock 을 함께 사용하는 이유

위 자료구조에서 세마포어가 총 세 개가 사용된다. 비어있는 버퍼의 갯수를 나타내는 empty, 차 있는 버퍼의 갯수를 나타내는 full 그리고 프로세스간 상호 배제를 위해 사용하는 mutex이다. 세마포어 변수의 이름이 mutex 로 지어져서 헷갈릴 수도 있지만, 이 변수는 binary semaphore이지 mutex lock은 아니다. 근데 왜 굳이 lock 역할을 하는 세마포어가 또 필요할끼?

문제는 full 과 empty의 signal 과 wait 연산에 있다. 두 연산은 그 자체로는 전혀 atomic 한 연산이 아니다. 내부적으로 값도 증가시켜주어야 하고, 대기를 시킬 때는 리스트에 PCB를 연결해주는 것 까지 해야한다. 따라서 signal 에 의해 동시에 여러 프로세스들이 임계구역 진입에 대한 조건을 만족하게 되면, 저마다 대기 큐에서 빠져나오려고 할 텐데, 이 때 binary semaphore를 사용해서 단 하나의 프로세스에게만 진입을 허용한다면, 동시에 여러 프로세스가 임계구역으로 진입하는 문제를 막을 수 있을 것이다.