[운영체제] 동기화 관련 여러 문제(The Bounded-Buffer Problem, The Reader-Writer Problem)

1. The Bounded-Buffer Problem

여기에서는 두 종류의 프로세스가 있는데, 하나는 Producer 프로세스, 또 다른 하나는 Consumer 프로세스이다. 즉, 이는 생산자-소비자 문제(Producer-Consumer Problem)이라고도 불린다. Producer 프로세스는 데이터를 만들어 버퍼에 삽입하고, Consumer 프로세스는 버퍼에서 데이터를 꺼내는 역할을 수행한다.

여기서 발생할 수 있는 문제점은 어느 생산자 프로세스가 버퍼 중 빈 곳에 데이터를 쓰려고 할때, Interrupt가 발생하여 다른 프로세스한테 공유자원이 넘어가서 다른 프로세스가 해당하는 빈 곳에 데이터를 쓸 때 나타날 수 있다. 그렇게 되면 둘 중에 한 프로세스의 데이터가 유실될 수 있을 가능성이 농후하기 때문이다. 그리하여 해당 공유 버퍼에 접근시 lock을 걸어 비어있는 위치에 데이터를 넣고, 그 다음 비어있는 위치를 다른 위리로 바꾸는 일을 한 후에 lock을 해제해야 한다.

소비자 프로세스의 경우 역시 살펴보면, 어떤 프로세스가 특정 데이터를 꺼내가려고 했는데 Interrupt가 발생하여 공유 자원이 다른 프로세스에 넘어갔다고 가정해보자. 그러면 실제로 데이터는 하나이지만 두 프로세스가 하나의 데이터를 가져가는 문제가 발생할 수 있다. 따라서 이를 막기 위해 공유 버퍼에 lock을 걸고 데이터를 꺼내간 뒤에, 내용이 들어있는 버퍼 위치를 찾아 다음 위치로 이동 후 lock을 풀어주어야 한다.

이를 나타내는 코드는 다음과 같다.

 

Producer process 코드

// 총 버퍼의 개수를 n이라고 가정
// 바이너리 세마포어는 mutex, 카운팅 세마포어는 empty, full. 
// mutex는 mutual exclusion 보장 위해 만들어진 세마포어, empty와 full은 버퍼의 총 수 n과 관련 있는 세마포어
int n;
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

while(true) {
    // 새로운 item을 하나 생성

    wait(empty); // 초기값 n은 n-1이 된다. 버퍼에 새 item을 넣으니 비어있는 n개 버퍼가 n-1개로 바뀐다는 의미이다.
    wait(mutex); // mutual exclusion을 만족시키기 위해 바이너리 세마포어의 wait 함수를 사용하고 임계 구역에 진입한다.

    //버퍼에 새로 생성된 item을 추가

    signal(mutex); // 버퍼에 item을 추가했으면, 바이너리 세마포어의 signal 함수 호출해 임계 구역 탈출을 알린다.
    signal(full); // signal(full)을 호출해 0의 초기값을 count++를 통해 1로 만들어준다. 
                  // 버퍼의 공간이 하나도 없었는데 자신이 하나 채웠으니 1이 된 것이다.
}

여기에서 Producer가 n+1번 실행되면 wait(empty) 조건에 의해 그 producer는 block된다. 이는 n이 -1이 되고, 이는 버퍼가 꽉 차있으니 새로 생성한 item을 넣은 공간이 없어서 block 된다는 의미이다.

 

Consumer process 코드

// Producer가 생성한 item을 Consumer가 소비하는 형태
while(true) {
    wait(full);  // 데이터 꺼내기 위해 full자원을 얻는다. 버퍼에 item이 한 번도 안 들어갔다면 0은 -1이 되어 block에 걸린다.
    wait(mutex); // full 자원이 있다면 lock을 걸기 위해 mutex를 실행한다.

     // 해당 버퍼에서 item을 빼냄

     signal(mutex); // item을 빼온 이후 signal 함수를 호출하여 임계 구역 탈출을 알린다.
     signal(empty); // signal(empty)를 호출해 데이터가 채워져 있는 버퍼의 공간 개수 하나를 뺀다.

     // item을 소비함
}

The Readers-Writers Problem

Reader와 Writer는 하나의 공유하는 데이터베이스를 지니고 있다. 여기서 Writer는 데이터베이스를 수정하는 역할을 하고, Reader는 데이터베이스를 읽어들이는 역할을 한다. Writer가 임계 구역에 있을 때 다른 Writer와 Reader가 접근하는 것을 막아야 한다. 반면, Reader는 공유 자원을 읽어 들이기만 하면 되기 때문에 다른 Reader가 함께 공유 자원을 읽는 것을 허락한다. 물론 Writer가 접근하여 데이터 수정하면 안되니 Writer는 접근하지 못하게 막는다.

이를 위해 아래와 같은 변수들을 만든다.

semaphore rw_mutex = 1; //binary
semaphore mutex = 1; //binary
int read_count = 0;

Writer와 Reader의 코드들은 아래와 같은 형식으로 구성한다.

 

Writer process 코드

while(true) {
    // Writer는 공유 자원에 접근하면 다른 모든 프로세스들의 접근을 차단함
    // 바이너리 세마포어로 다른 프로세스들의 임계 구역 진입 일체 차단함
    wait(rw_mutex); 

    //writing 수행

    signal(rw_mutex);
}

 

Reader process 코드

while(true) {
    // Reader에서는 Writer의 접근만 막을 뿐, Reader가 몇 명이 접근하는지는 신경 안씀

    wait(mutex); // read_count에 대한 mutual exclusion 보장하기 위한 설정
    read_count++; // read_count가 0이라면 1로 증가시킨다.

    if(read_count == 1) // 만약 read_count가 1이라면 wait(rw_mutex)를 실행, 이를 통해 Writer는 임계 구역에 진입 못한다.
        wait(rw_mutex); // 한편 reader는 read_count를 증가시킬 뿐 wait(rw_mutex)를 호출하지 않으므로 임계 구역에 그냥 진입한다.
    signal(mutex); // read_count에 대한 mutual exclusion 보장하기 위한 설정

    //reading 수행

    wait(mutex);
    read_count--; // reading 수행 이후 read_count를 1 감소시킨다.
    if(read_count == 0) // 임계 구역에 머물러 있는 Reader가 하나도 없을 경우에 signal(rw_mutex)를 호출한다.
        signal(rw_mutex); // 이로써 writer가 공유 자원에 접근 가능한다.
    signal(mutex); 
}

이 구조는 Writer에 Starvation 문제를 초래하게 되는데, 현재 Writer가 임계 구역에 진입하는데 매우 불리한 구조이다.

 

 

참고 자료

https://blog.naver.com/PostView.nhn?blogId=and_lamyland&logNo=221192481544 

[대딩의 운영체제, OS 14] 동기화 문제(Bounded Buffer, Readers Writers, Dining Philosophers Problem)와 모니터 Moni

 

https://higunnew.tistory.com/45

7-3강. 동기화 문제(Deadlock) 해결 방안