[운영체제] 동시성 제어의 고전적 문제들

1. Bounded - Buffer 문제 (생산자 소비자 문제)

유한한 개수의 데이터를 보관하는 Buffer에 여러 명의 생산자들과 소비자들이 접근한다. 생산자의 경우 데이터를 생성하면 Buffer에 저장하는데 이 때 저장할 Buffer 공간이 없을 수 있는 문제가 발생 할 수 있다.

소비자의 경우 데이터가 필요 할 때 Buffer에서 데이터를 가져오는데 , 이 때 가져올 데이터가 Buffer에 없는 문제가 발생 할 수 있다.

해결방법은 생산자-소비자 협동으로 세마포어를 사용하여 버퍼를 동기화 시키는 것이다.

• 이 때 각 변수는 아래와 같다.

int n;
semaphore empty = n; // 버퍼 내에 저장할 공간이 있는지 
semaphore full = 0 // 버퍼 내에 소비 할 데이터가 있는지 
semaphore mutex = 1 // 버퍼에 대한 접근을 통제하여 동기화를 충족시켜주는 세마포어 

• 생산자 프로세스

while(true){
    // Data 생산 
   wait(empty); // 버퍼에 빈 공간이 생길 때 까지 기다린다.
   wait(mutex); // 임계 영역에 진입 하기 전까지 기다린다.
   
   // 데이터를 버퍼에 추가 
   signal(mutex); // 임계 영역을 빠져나왔다고 알려준다.
   signal(full); // 버퍼에 데이터가 있다고 알려준다. 
}

• 소비자 프로세스

while(true){
    wait(full); // 버퍼에 데이터가 들어올 때 까지 기다린다. 
    wait(mutex); // 임계 영역에 진입 하기 전까지 기다린다. 
    
    // 버퍼로부터 데이터를 가져온다. 
    signal(mutex);
    signal(empty); // 버퍼에 빈 공간이 생겼다고 알려준다. 
}

2. Readers-Writers 문제

여러 명의 독자(Readers)와 저자(Writers)들이 하나의 저장 공간 (Buffer) 을 공유하며 이를 접근 할 때 발생하는 문제이다.

• 독자 : Buffer에서 데이터를 읽어온다. 여러명의 독자가 동시에 데이터 읽어오기 가능
• 저자 : Buffer에 데이터를 쓴다. 한 저자가 Buffer에 데이터를 쓰고 있는 동안에는 그 저자만 접근 가능 (독자와 다른 저자들 접근 불가)

이 때, 독자와 저자 사이의 기아문제가 발생 할 수 있다. ( 독자의 수가 압도적으로 많고, 저자는 계속해서 기다리는 상황이 발생 가능 vice versa)

해결 방법은 세마포어를 사용하는 것이다.

• 이 때 각 변수는 아래와 같다.

int readcount = 0  //현재 Buffer에 접근 중인 독자의 수 
    // 독자 수가 0 일 경우 저자가 임계 영역에 접근 가능 
semaphore rw_mutex = 1 //저자와 독자 사이 동기화 
semaphore mutex = 1  // 상호 배제를 보장하기 위해 사용 

• 저자 프로세스

while(true){
    wait(rw_mutex); // 임계 영역에 들어가기 위해 기다리는 중
	// 쓰기 작업 수행
	signal(rw_mutex); // 임계 영역에서 빠져나옴 
}

• 독자 프로세스

while(true){
    wait(mutex);
    readcount++; // 독자수 1 증가
    if(readcount = 1 ) 
        wait(wrt) // 쓰고 있는 저자가 없을 때 까지 기다리기
    signal(mutex);

    // 읽기 작업 수행

    wait(mutex);
    readcount--; // 독자수 1 감소
    if(readcount = 0) 
        signal(rw_mutex); // 독자가 없다면 알려줘서 기다리고 있는 독자/저자를 끼운다.
    signal(mutex);
}

3. 철학자들의 저녁식사 문제

철학자들은 서로 대화 할 수 없으며, 양쪽에 있는 포크를 모두 쥐어야지 식사를 할 수 있다.

세마포어를 통한 상호배제 충족

각 포크에 세마포어를 상호배제 세마포어를 걸어준다. 철학자가 포크를 집을 때, wait 연산을 하고, 포크를 내려놓을 때 signal 연산을 하는 것이다.

while(true){
    // 포크 양쪽 가져오기
    wait(포크[i]);
    wait(포크[(i+1)%5]);
    
    // 냠냠 먹는다.
    
    // 포크 양쪽 놓기 
    signal(포크[i]);
    signal(포크[(i+1)%5]);
    
    // 철학적인 생각한다..
}

이렇게 구현 할 시, 상호배제는 충조갛지만 교착상태와 기아현상이 발생한다.

교착상태 (DeadLocks)

이 때 만약 이 때 모든 철학자들이 오른쪽에 놓여있는 포크를 집는다면 , 왼쪽의 포크는 이미 사라진 상태이기 때문에 모든 철학자들이 서로가 포크를 내려놓기를 무한정 대기하는 문제가 생긴다.

해결방법

1. 식탁에 한 자리를 비워둔다.
2. 양쪽 포크를 모두 사용 가능 할 때에만 포크를 잡도록 한다.
3. 홀수 번째의 철학자는 왼쪽 포크 집고-> 오른쪽 포크 집고 / 짝수 번째의 철학자는 오른쪽 포크 집고- 왼쪽포크 집고

기아 문제

몇몇 철학자들만 양손 포크를 쥐어서 식사를 하는 경우가 발생 할 수 있다.

모니터 해결 방법

철학자들의 상태를 thinking hungry 그리고 eating으로 나눈다.

• 철학자가 자신의 상태를 hungry -> eating으로 바꿀 수 있는데 , 이 때 양쪽에 있는 철학자들이 eating상태가 아닐 때만 바꿀 수 있다.

그럼에도 불구하고 기아현상은 발생 할 수 있다.

참고 / 이미지 출처

• 위키피디아 - 독자 저자 문제
• 위키피디아 - 식사하는 철학자들 문제
• 인프런 운영체제 공룡책 강의