동기화의 고전적인 문제
Producer-Consumer Problem
두가지의 프로세스 타입이 있다.
- 생산자
내부 함수생산을 실행함으로써 이 프로세스들은 소비자에게 보내져야 할 데이터를 생산한다. - 소비자
데이터를 받으면 이 프로세스들은 내부 함수소비에서 계산을 수행한다.
버퍼없이 생성시간, 소비시간이 같은 것을 동기화가 되어있다고 하는데, 기본적으로는 동작속도가 달라서 비동기화 되어있다. 그래서 버퍼를 쓴다.(생성시간 > 소비시간)
Infinite Buffers
무한버퍼. 무한크기의 버퍼
in_ptr이 버퍼에 있는 요소의 개수를 세고, out_ptr이 제거된 요소의 개수를 센다.
Semaphore invariant = #E = 0 + in_ptr - out_ptr > 0 이 항상 유지되어야한다.
생산자-소비자 문제, 특히 소비자가 필요로 하는 동기화는 버퍼의 요소 수를 나타내는 세마포 요소를 사용하여 해결할 수 있다.
생산자는 넣었다고 알려줄 것이 필요하고 소비자는 비었는지 체크하기만 하면 된다.
코드로 나타내면 다음과 같다.
Producer 함수에서 버퍼가 다 찼는지 if문으로 확인할 필요가 없다.
Bounded(or finite) Buffers
유한버퍼. 버퍼의 크기가 유한이다.
생산자는 공간이 존재하는가, 소비자는 읽어갈 요소가 있는가를 확인해야할 필요가 있다. 원형 버퍼를 사용한다. 생산, 소비의 순서를 맞추기 위해 세마포를 사용한다.
코드로 나타내면 다음과 같다.
int array[N];
int in_ptr, out_ptr = 0; //각각 포인터는 0
semaphore elements = 0; //읽어갈 요소는 처음에 0
semaphore spaces = N; //집어넣을 공간은 빈공간.
Producer(int i)
{
while(TRUE) {
Produce(i);
P(spaces);
B[in_ptr] = i;
in_ptr = (in_ptr + 1) mod N ;
V(elements); /* signal to consumer */ }
}
Consumer(int i)
{
while(TRUE) {
P(elements) ; /*Wait until in_ptr>out_ptr */;
i = B[out_ptr];
out_ptr = (out_ptr + 1) mod N ;
V(spaces);
Consume(i); }
}Readers-Writers Problem
상호배제보다 더 복잡하다. 여러명이 읽고 1명이 쓴다. 여러명 쓰기는 문제가 발생한다. 이 문제를 해결하는 방법은 상대적 우선순위에 대해 추정하는 것이다.
writer가 쓰는 것을 요청할 때 모든 현재 reader들은 읽기를 끝내고 모든 읽기 요청은 기다려야한다.
독자가 가능한 한 최신 정보를 읽는 것이 중요할 때 적절한 방법이다.
세마포는 프로세스가 block이 필요한 상황을 관리한다.
Dining-Philosophers Problems
식사하는 철학자 문제
철학자는 원형 탁자에서 식사를 하며,
- 철학자는 두개의 포크가 있을 때 먹을 수 있다.
- 어떤 두 철학자도 동시에 같은 포크를 들 수 없다.
- 데드락이 발생하면 안된다.
- 기아현상이 발생하면 안된다.
각 포크는 세마포로써 역할을 하며 각 철학자는 식사하기 전에 반드시 오른쪽과 왼쪽의 두 포크를 기다려야만 한다.
Semaphore Fork[5]; //5개의 포크가 세마포이다.
Philosopher(int i)
{
while(TRUE) {
P(Fork(i)) ; //포크를 쓸 수 없으면 기다린다.
P(Fork(i+1) mod 5) ; // 모듈러 연산을 한다. 5개를 넘어가면 안되므로.
Eat ; // 먹는다.
V(Fork(i)) ;
V(Fork(i+1) mod 5) ;
Think;
}
}식사하는 철학자 문제는 이러한 문제가 발생할 수 있다.
- 먹으려면 옆의 철학자가 다 먹기를 기다려야 한다. -->포크 사용 시간을 정해 놓고 사용한다.
- 모두가 하나의 포크를 각각 들고 있다면 어떤 한 사람이 놔야 식사를 하는데, 그럴 수 없으므로 데드락이 발생한다.--> 한명이 두 포크를 모두 사용하도록 하여 데드락을 예방한다.
또다른 예방법은 원형 식탁이 아니라 사각 식탁에서 식사하는방법이 있다.
증가와 감소를 경쟁하는 2개의 프로세스
증가와 감소를 경쟁하는 A, B프로세스가 있다. Mutex를 세마포로 사여 P,V operation을 사용하고 있고, 변수 i를 테스트하는 동작은 atomic하다고 한다.
Process A
{
i = 0;
mutex = 1;
while(i < 10)
{
P(mutex);
i++;
V(mutex);
}
printf("A is a winner! \n");
}
Process B
{
i = 0;
mutex = 1;
while(i > -10)
{
P(mutex);
i--;
V(mutex);
}
printf("B is a winner! \n");
}A와 B중 winner가 되는 프로세스를 말하라 하면, 모른다. 스케쥴러에 의해 프로세스 실행이 결정되지 때문에 먼저 끝나는 프로세스는 알 수 없다.
