프로세스 동기화 - 고전적인 문제들

카테고리 없음

2019. 5. 10. 20:59

동기화와 관련된 고전적인 문제들에 대해 알아보자. 이 문제들은 프로그래머가 프로세스 간 공유자원을 필요로 하는 애플리케이션을 설계할 때 해결해야 하는 문제들과 많은 공통부분을 가지게 될 확률이 높다.

 

Bounded Buffer Problem

 

소비자와 생산자가 유한 개의 원소를 가지는 버퍼자원을 공유하는 상황에서, 다음의 두 가지 문제를 해결하여야 한다.

- 소비자와 생산자가 버퍼에 상호배타적으로 접근

- 소비자는 버퍼에 하나 이상의 원소가 존재할 때 원소를 소비해야 하고, 생산자는 버퍼에 빈 공간이 존재할 때 원소를 생산해야 한다.

 

위의 두 가지 문제를 해결하기 위해서 세 종류를 사용한다.

- 상호배타적 접근문제를 해결하기 위한 mutex(이진 세마포어)

- 버퍼의 빈 공간의 개수를 나타내는 empty 세마포어

- 버퍼의 찬 공간의 개수를 나타내는 full 세마포어

/*
    producer
*/
do {
    ... // produce item
    
    wait(empty);
    wait(mutex);
    
    ... // add item to buffer
    
    signal(mutex);
    signal(full);
} while(TRUE);

/*
    consumer
*/
do {
    wait(full);
    wait(mutex);
    
    ... // remove item
    
    signal(mutex);
    signal(empty);
    
    ... // consume item
} while(TRUE);

생산자는 원소를 생성하고 버퍼에 빈 공간이 생길때까지 기다리다가 빈 공간이 생기면 또다시 mutex를 기다리고 mutex를 획득하면 버퍼에 원소를 추가한다. 버퍼에 원소를 추가하고 나면 mutex를 놓아주고 버퍼에 존재하는 원소의 개수를 의미하는 full 세마포어를 증가시킨다.(놓아준다)

소비자는 생산자와 반대로 동작한다. 

 

Readers-Writers Problem

 

reader는 공유데이터를 읽기만 하고 writer는 공유데이터를 갱신할 수도 있는 상황에서, 여러 개의reader만 공유데이터에 접근하는 경우 세마포어를 사용하지 않고도 데이터의 일관성을 유지할 수 있는 반면, 하나 이상의 writer가 개입하는 경우 데이터의 일관성이 무너질 수 있다. 이에 의해 발생하는 다음의 두 가지 문제를 해결하여야 한다.

- writer가 아직 공유데이터에 대한 접근할 준비가 되지 않았다면 reader들이 기다리는 시간을 길게해서는 안된다. 이는 프로세서의 자원을 낭비하는 것이기 때문이다.

- writer가 준비가 되었다면 곧바로 writer가 쓰도록 해 주어야 한다.

 

위의 두 가지 문제들 중 첫 번째 문제를 해결하기 위해서 다음 세 가지의 자료를 사용한다.

- 읽기와 쓰기 공통 뮤텍스(이진 세마포어) rw_mutex, 1로 초기화

- 읽고있는 reader의 수를 나타내는 정수 read_count, 0으로 초기화

- reader들 사이에서 read_count로의 상호배타적 접근을 위한 rc_mutex

/*
    writer
*/
do {
    wait(rw_mutex);
    
    ... // writing
    
    signal(rw_mutex);
} while(TRUE);

/*
    reader
*/
do {
    wait(rc_mutex);
    read_count++;
    if(read_count == 1) // 읽기동작을 수행하는 첫 번째 reader인 경우
        wait(rw_mutex); // rw_mutex를 기다린다.
    signal(rc_mutex);
    
    ... // reading
    
    wait(rc_mutex);
    read_count--;
    if(read_count == 0) // 읽기동작을 끝낸 마지막 reader인 경우
        signal(rw_mutex); // rw_mutex를 놓아준다.
    signal(rc_mutex);
} while(TRUE);

 

위와 같이 writer와 reader를 구현하면 한 개 이상의 reader가 읽기를 수행중일 때는 writer의 개입을 배제함으로써 reader들이 기다리지 않고 읽기 동작의 수행이 가능하도록 할 수 있다. 하지만 이는 writer측면에서의 starvation을 야기시킬 수도 있다.

 

The Dining-Philosophers Problem

 

철학자 5명이 테이블에 앉아 있다. 각각의 철할자들은 식사하기 위해서 두 개의 젓가락을 필요로 하며, 자신의 왼쪽과 오른쪽 젓가락을 집어들 수 있다. 또한 철학자는 한 번에 하나의 젓가락만 집어들 수 있다. 철학자는 식사하지 않는 동안에는 생각을 하는데, 생각을 하는 동안에는 다른 철학자들과 교류하지 않는다.

철학자 5명이 식사 대기중

식사하는 철학자들 문제는 Deadlock과 Starvation을 발생시키지 않으면서 각 철학자들이 식사할 수 있도록 하는 것이다. 여기서 세마포어는 5개의 젓가락이다.

semaphore chopstick[5];

위의 세마포어 5개를 가지고 일반적인 알고리즘을 구현해 보자.

/*
    process of Pi
*/
do {
    wait(chopstick[i]);
    wait(chopstick[(i+1) % 5]);
    
    ... // 맛잇게 식사
    
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    
    ... // 생각
} while(TRUE);

위의 알고리즘은 인접한 두 명의 철학자가 동시에 식사하지 않는것은 보장하지만, 각각의 철학자가 동시에 자신의 왼쪽에 있는 젓가락을 집어드는 경우 Deadlock이 발생할 수 있다. 따라서 이 알고리즘은 사용하면 안된다.

 

이러한 문제를 해결하기 위해서 다음의 세 가지 해결방안이 존재한다.

- 5개의 자리 중 동시에 네 명의 철학자만 앉을 수 있도록 한다.

- 철학자 양쪽에 젓가락이 존재할 때만 임계구역 내에서 젓가락을 집도록 한다.

- 짝수 번째 철학자들은 자신의 왼쪽에 있는 젓가락부터, 홀수 번째 철학자들은 자신의 오른쪽에 있는 젓가락부터 집어들도록 한다.

 

참조

 

ABRAHAM SILBERSCHATZ, PETER BAER GALVIN, GREG GAGNE / 운영체제 / (주)교보문고 / 2018년

 

티스토리툴바