고전적인 동기화 문제들

유한 버퍼 문제

유한 버퍼 문제는 동기화 문제의 대표적인 예로서 데이터를 생산하는 생산자 프로세스와

데이터를 소비하는 소비자 프로세스 간에 한정된 공유 버퍼를 사용하는 문제이다.

이 문제에서 소비자와 생산자는 다음과 같은 자료구조를 공유한다.

int n; semaphore mutex = 1; semaphore empty = n; semaphore full = 0;

 

n개의 버퍼들로 구성된 풀이 있으며 각 버퍼들은 한 항목을 저장할 수 있다고 가정한다.

mutex 세마포어는 버퍼 풀을 접근하기 위한 상호 배제 기능을 제공하며 1로 초기화된다.

empty 세마포어는 비어있는 버퍼의 수를 기록하며 n값으로 초기화 된다.

full 세마포어는 꽉 찬 버퍼의 수를 기록하며 0으로 초기화된다.

 

생산자가 counter을 올리는 도중 cpu스케줄링이 발생하여 소비자가 counter을 낮추는 작업을 한다면 count값에 오류가 발생한다.

 

생산자, 소비자 간의 임계구역 문제 해결

 

 

독자 저자 문제

하나의 데이터베이스가 다수의 병행 프로세스들 간에 공유 된다고 가정 한다.

일부 프로세스들은 데이터베이스의 내용을 읽기만 수행하고 어떤 프로세스들은 데이터베이스의 내용을 갱신한다.

 

만약 여러명의 독자가 동시에 공유 데이터에 접근한다고 하여도 문제가 발생하지 않는다.

하지만 하나의 저자와 어떤 다른 프로세스가 동시에 데이터베이스에 접근할 경우 혼란이 야기될 수 있다.

이러한 문제가 발생하지 않도록 보장하기 위해 저자가 쓰기 작업 동안에 공유 데이터에 다른 프로세스들이 접근하지 못하게 막아야 한다.

이 동기화 문제를 독자 저자 문제라고 한다.

 

이 문제에 대한 해결안에서 독자 프로세스는 다음과 같은 자료구조를 공유한다.

semaphore rw_mutex = 1; semaphore mutex = 1; int read count = 0;

 

mutex는 read_count를 갱신할 때 상호배제를 보장하기 위해 사용된다.

rw_mutex는 1로 초기화 되며  임계구역으로 진입하는 첫 번째 독자와 임계구역을 빠져나오는 마지막 독자에 의해서 사용된다.

read_count 변수는 현재 몇 개의 프로세스들이 공유 자원을 읽고 있는지를 나타내 준다.

 

저자 프로세스의 구조

do {     wait(rw_mutex);    // 임계구역에 들어가기 위해 허가가 나기를 기다린다. ... //쓰기 작업 수행 ... signal(rw_mutex);  // 임계구역에서 빠져나왔음을 알린다. }while (true)

 

독자 프로세스의 구조

do{     wait(mutex);         read count++;     // 독자 수 1 증가         if read count = 1                 wait(rw_mutex);   // 쓰고 있는 저자가 없을 때까지 기다린다.     signal(mutex);     ...     읽기 작업 수행     ...     wait(mutex);           read count--;     // 독자 수 1 감소         if  read count = 0                 signal(rw_mutex); // 독자가 없다면 이를 알린다.     signal(mutex); }while (true

 

 

식사하는 철학자들 문제

철학자들은 원형 테이블을 공유하며, 이 테이블은 각각 한 철학자에 속하는 5개의 의자로 둘러 싸여 있다.

테이블 중앙에는 한 사발의 밥이 있고 테이블에는 다섯 개의 젓가락이 놓여 있다.

철학자가 생각할 때는 다른 동료들과 상호 작용 하지 않고 때때로 철학자들이 배가 고파지면 자신에게 가장 가까이 있는 두 개의 젓가락을 잡으려고 시도한다.

철학자들은 한 번에 한 개의 젓가락만 집을 수 있고 이미 옆 사람 손에 들어간 젓가락을 집을 수는 없다.

배고픈 철학자가 동시에 젓가락 두 개를 집으면 젓가락을 놓지 않고 식사를 한다.

식사를 마치면 젓가락 두 개를 모두 놓고 다시 생각하기 시작한다.

 

이러한 경우 동시에 모든 철학자들이 왼쪽 젓가락을 잡을 경우 모두가 오른쪽 젓가락을 영원히 기다리게 된다.

 

해결 방법

첫 번째 방법은 n명이 앉을 수 있는 테이블이면 n-1 명의 철학자만 앉을 수 있게 하는 것이다.

이렇게 되면 무조건 하나 이상의 젓가락은 대기 상태로 있게 되고 어떤 철학자는 무조건 식사를 할 수 있게 된다.

 

두 번째 방법은 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집는 것을 허용하는 것이다.

이러면 모든 철학자들이 차례대로 왼 쪽 젓가락을 잡을 때 마지막 철학자는 두 젓가락을 모두 집을 수 없기 때문에 

젓가락을 집을 수 없게 되어 교착 상태가 발생하지 않게 된다.

 

세 번째 방법은 누군가는 왼쪽 젓가락을 먼저 잡지 않고 오른쪽 젓가락을 먼저 잡게 하는 방법이다.

이런 상황에서는 누군가는 젓가락을 집을 수 없게 되고 교착상태가 방지되게 된다.

 

이 문제를 해결하기 위한 해결안들은 철학자들 중 어느 하나가 굶어 죽지 않게 하도록 해야 한다.

교착상태가 없는 해결안이 기아의 가능성도 제거하는 것은 아니다.