동기화 문제 (Problems of Synchronization)
동기화에는 다음과 같은 고전적인 문제들이 있습니다.
- Bounded-buffer (Producer-Consumer) Problem
- The Readers-Writers Problem
- 식사하는 철학자 문제(The Dining-Philosophers Problem)
이번에는 세마포어를 사용하여 고전적인 문제들을 해결방법에 대해서 알아보도록 하겠습니다.
Bounded-buffer (producer-consumer) problem
생산자 소비자 문제라고도 하는 경계 버퍼 문제는 동기화의 고전적인 문제 중 하나입니다.
문제 설명
n개의 슬롯의 버퍼가 있으며 각 슬롯은 하나의 데이터를 저장할 수 있습니다.
실행 중인 두 개의 프로세스, 즉 생산자(in)와 소비자(out)가 버퍼에서 작동합니다.
생산자가 버퍼의 빈 슬롯에 데이터를 삽입하려고 합니다. 소비자는 채워진 슬롯에서 데이터를 제거하려고 합니다.
이 두 프로세스는 동시에 실행되는 경우 예상치 못한 문제가 발생할 수 있습니다.
해결방안
이 문제를 해결하기 위해 세 가지 세마포어를 사용합니다.
- mutex : 잠금을 획득하고 해제하는 데 사용되는 이진 세마포어입니다. (초기값 = 1)
- empty : 빈 슬롯의 수를 나타내는 세마포어 (초기값 = n)
- full : 버퍼에서 점유된 슬롯의 수를 나타내는 세마포어 (초기값 = 0)
생산자 구현
생산자는 다음과 같이 구현됩니다.
Producer Process:
do {
...
// produce an item in nextp
...
wait(empty); // empty > 0 까지 기다린 다음 'empty' 감소
wait (mutex); // 잠금 획득
// add nextp to buffer
signal(mutex); // 잠금 해제
signal(full); // 'full' 증가
} while (TRUE);- 생산자에 대한 위의 코드를 보면 생산자가 빈 슬롯이 하나 이상 있을 때까지 먼저 대기하는 것을 볼 수 있습니다.
- 그런 다음 생산자가 해당 슬롯 중 하나에 데이터를 삽입할 것이기 때문에 빈 세마포어를 감소시킵니다.
- 그런 다음 버퍼에 대한 잠금을 획득하여 생산자가 작업을 완료할 때까지 소비자가 버퍼에 액세스 할 수 없도록 합니다.
- 삽입 작업을 수행한 후 잠금이 해제되고 생산자가 버퍼의 슬롯을 방금 채웠기 때문에 full 값 이 증가합니다.
소비자 구현
소비자는 다음과 같이 구현됩니다.
do {
wait(full); // full > 0 까지 기다린 다음 'full' 감소
wait(mutex); // 잠금 획득
...
// remove an item from buffer to nextc
...
signal(mutex); // 잠금 해제
signal(empty); // 'empty' 증가
...
// comsume the item in nextc
...
} while(TRUE);- 소비자는 버퍼에 가득 찬 슬롯이 하나 이상 있을 때까지 기다립니다.
- 그런 다음 소비자가 작업을 완료한 후 점유된 슬롯 수가 1만큼 감소하므로 전체 세마포어를 감소시킵니다.
- 그 후 소비자는 버퍼에 대한 잠금을 획득합니다.
- 그 후 소비자는 전체 슬롯 중 하나의 데이터가 제거되도록 제거 작업을 완료합니다.
- 그런 다음 소비자가 잠금을 해제합니다.
- 마지막으로, 소비자가 점유된 슬롯에서 데이터를 제거하여 빈 상태로 만들기 때문에 빈 세마포어가 1씩 증가합니다.
The Readers-Writers Problem
독자-저자 문제(Readers-Writers Problem)란 여러 명의 독자와 저자들이 하나의 저장 공간(버퍼)을 공유하며 이를 접근할 때 발생하는 문제입니다.
문제 설명
Readers-Writers 문제에서는 다음과 같이 두 가지 유형의 프로세스가 있습니다.
- Reader : 공유 데이터만 읽고 변경하지 않는 프로세스
- Writer : 공유 데이터를 추가 또는 변경할 수 있는 프로세스
여러 reader가 공유 데이터를 동시에 읽을 수 있지만 한 명의 writer만 공유 데이터에 쓸 수 있습니다.
writer가 공유 데이터를 쓸 때는 다른 프로세스는 접근할 수 없습니다.
해결방안
Reader 또는 Writer에게 우선권을 부여하여 해결합니다.
- Reader에게 우선권 부여
- reader가 데이터 접근에 대한 우선권을 가지고 있습니다. 계속해서 reader에 대한 접근 요청이 일어나면 writer에 기아 상태(starvation)가 발생할 수 있습니다.
- Writer에게 우선권 부여
- writer가 데이터 접근에 대한 우선권을 가지고 있습니다. 계속해서 writer에 대한 접근 요청이 일어나면 reader에 기아 상태(starvation)가 발생할 수 있습니다.
누구에게 우선권을 부여하느냐에 따라 구현이 달라지게 됩니다.
여기서는 reader에게 우선권을 부여하여 문제를 해결하는 경우를 보겠습니다.
이 문제를 해결하기 다음과 같은 변수 및 세마포어를 사용합니다.
- readcount : 현재 버퍼에 접근 중인 독자의 수를 나타냅니다. (초기값 = 0)
- wrt : 저자를 차단하고 해제하기 위해 사용하는 세마포어입니다. (초기값 = 1)
- mutex : 독자가 readcount와 wrt에 접근하는 것을 원자적으로 하기 위해 사용하는 뮤텍스(이진세마포어)입니다. (초기값 = 1)
Writer 프로세스 구현
do {
wait(wrt); // 읽고 있는 독자가 없을 때까지 기다림.
...
// 쓰기 작업 수행
...
signal(wrt);
} while (TRUE);- writer는 리소스에 reader가 없을 때까지 대기를 합니다.
- 쓰기 작업을 수행한 후 signal 함수 호출로 wrt가 증가하며 다음 writer가 리소스에 액세스 할 수 있습니다.
Reader 프로세스 구현
do {
wait(mutex);
readcount ++; // 독자 수 1 증가.
if (readcount == 1)
wait(wrt); // 쓰고 있는 저자가 없을 때까지 기다림.
signal(mutex);
...
// 읽기 작업 수행
...
wait(mutex);
readcount --; // 독자 수 1 감소
if (redcount == 0)
signal(wrt); // 독자가 없다면 이를 저자에게 알림.
signal(mutex);
} while (TRUE);- reader는 readcount를 업데이트할 때마다 잠금을 획득합니다.
- reader가 임계 구역에 접근하려면 먼저 readcount를 증가시킨 다음 접근하고 이후 readcount를 감소시키고 나옵니다.
- 세마포어 wrt는 임계 구역에 들어가는 첫 번째 reader와 임계 구역을 나가는 마지막 reader에서 사용됩니다.
- 그 이유는 첫 번째 reader가 임계 구역에 들어가면 writer는 차단되기 때문입니다. 이제 새로운 reader만 임계 구역에 진입할 수 있습니다.
- 마찬가지로 마지막 reader가 임계 구역을 나오면 현재 readcount가 0개이고 writer가 임계 구역에 접근할 수 있는 기회를 가질 수 있으므로 signal(wrt)를 사용하여 writer에게 신호를 보냅니다.
The Dining-Philosophers Problem
식사하는 철학자 문제(The Dining-Philosophers Problem)는 여러 프로세스에게 제한된 리소스를 할당하는 상황에서 발생할 수 있는 문제입니다.
문제 설명
아래 그림과 같이 다섯 명의 철학자가 원탁에 앉아 있고, 각자의 앞에는 음식과 양옆에 포크가 하나씩 있습니다.
- 이 철학자들은 먹고 생각하는 두 가지 활동을 번갈아 합니다.
- 철학자는 먹고 싶을 때는 양 옆의 두 개의 젓가락을 사용해야 합니다.
- 젓가락은 인접한 철학자만 사용할 수 있으며 동시에 두 명이 사용할 수 없습니다.
- 철학자는 식사를 마치고 두 젓가락을 원래 위치에 내려놓은 뒤 생각에 잠깁니다.
해결 방안
간단한 해결 방안은 세마포어를 사용하여 젓가락을 나타내는 것입니다.
wait() 함수를 호출하여 젓가락을 집어 들고 signal() 함수를 호출하여 젓가락을 내려놓습니다.
구현
젓가락 구조는 다음과 같습니다.
semaphore chopstick[5];처음에는 젓가락을 사용하지 않기 때문에 젓가락들은 1로 초기화합니다.
철학자 구조는 다음과 같습니다.
do {
wait( chopstick[i] ); // 왼쪽 젓가락을 집어듬.
wait( chopstick[ (i+i) % 5] ); // 오른쪽 젓가락을 집어듬.
...
// eat
...
signal( chopstick[i] ); // 왼쪽 젓가락을 내려놓음.
signal( chopstick[ (i+1) % 5] ); // 오른쪽 젓가락을 내려놓음.
...
// think
...
} while(TURE);- 철학자는 왼쪽 젓가락 (chopsticks[i])과 오른쪽 젓가락 (chopsticks[i+1)%5) 순으로 집어 든 뒤 식사를 합니다.
- 식사를 마치고 두 젓가락을 내려놓은 뒤 생각을 하게 합니다.
위 해결책은 두 명의 이웃 철학자가 동시에 먹을 수 없도록 합니다.
그러나 모든 철학자가 동시에 왼쪽 젓가락을 집는다면 누구도 먹을 수 없는 교착상태가 발생하게 됩니다.
교착상태에 대한 해결책은 다음과 같은 방법들이 있습니다.
- 4명의 철학자만 테이블에 동시에 앉을 수 있도록 합니다.
- 왼쪽과 오른쪽 젓가락을 모두 사용할 수 있는 경우에만 젓가락을 집을 수 있게 합니다.
- 짝수 번째 철학자들은 자신의 왼쪽에 있는 젓가락부터, 홀수 번째 철학자들은 자신의 오른쪽에 있는 젓가락부터 집어 들도록 합니다.
