운영체제 5.4 세마포어 (생산자/소비자 문제)
생산자/소비자 (Producer/Consumer)문제에 대해 생각해보자.
하나 이상의 생산자는 데이터를 생성하고, 버퍼에 저장한다.
소비자는 한번에 하나씩 버퍼에서 데이터를 꺼내 소비한다.
이 문제의 요구조건은 버퍼접근이 중첩되어서는 안된다는 것이다.
즉, 한 시점에 버퍼에 하나만 접근할 수 있도록 해야한다. 버퍼가 가득 차면 Producer는 더이상 버퍼에 데이터를 추가할 수 없고, 버퍼가 비어있으면, Consumer는 꺼내갈 수 없도록 제어해야한다.
(버퍼는 무한하고 원소들이 linear하게 배열되어있다고 가정하자.)
Producer
데이터를 생성하고 버퍼에 저장한다.
in이라는 곳에 저장된다고 생각하고, 저장하게 되면 in 은 ++ 된다.
Consumer
버퍼에서 데이터를 꺼내어 소비한다. 꺼내는 위치는 out이라는 이름의 인덱스고, 꺼내고 out은 ++된다.
빈 공간에서 데이터를 꺼내지 않도록 주의해야 한다.
다시말해, consumer 는 버퍼에서 데이터를 읽기 전에 producer가 앞서가고 있는지 체크해야한다.
변수 n을 이용해 인덱스 in, out을 관리할 수 있고,(n= in-out). s를 상호 배제를 보장하기 위해 사용된다.
int n;
binary_semaphore s =1; delay=0;
void producer()
{
while(true){
produce()
semWaitB(s);
append();
n++;
if(n==1) semSignalB(delay);
semSignalB(s);
}
}
void consumer()
{semWaitB(delay);
while(true){
semWaitB(s);
take();
n--;
semSingalB(s);
comsume();
if(n==0) semWaitB(delay);
...
producer는 데이터를 자유롭게 버퍼에 추가할 수 있다. 하지만 추가하기 전에, mutual exclusion을 보장하기 위해 semWaitB(s)를 호출하고 추가한 후에 semSignalB(s)를 호출하면 된다.
이것이 버퍼에 데이터를 추가할때 consumer or different producer가 버퍼를 사용하는 것을 방지하기 위함이다.
그리고 producer는 critical section에 있는 동안 n의 값을 증가시킨다.
증가했을 때 n=1이 되면, (증가 이전에 n=0)이라면, 데이터를 버퍼에 추가하기 직전에는 버퍼가 비어있었다는 것을 뜻한다.
따라서 producer는 consumer에게 버퍼에 데이터가 채워졌습니다! 말해야한다. ->semsignalB(delay)를 호출한다.
그러면 consumer는 critical section 으로 진입해 데이터를 꺼내고, n을 감소시킨다.
만약 producer가 consumer에 비해 먼저 수행될 수 있다면,(일반적인 경우) n이 대부분양수이기 때문에, consumer 가 semaphore delay에서 블록되는 경우는 매우 드물다. -> 원활하게 수행되는 경우가 잦다.
하지만 이 프로그램은 결함이 있따.
만약 소비자가 버퍼의 데이터를 모두 사용하였따면? producer가 새로 데이터를 생산 할때까지 세마포어 delay에 대기해야한다.
프로그램에서 if(n==0) semWaitB(delay) 문장이 이 역할을 담당함.
n이 -인것은 소비자가 버퍼에서 존재하지 않는 데이터를 소비했다는것을 뜻한다. 이 문제를 해결하기 위해 조건문을 consumer의 임계영역으로 옮기는 것을 고려할 수 있지만 deadlock을 발생시킬 수 있다.
semWait(n)과 semWait(s)연산의 순서가 바뀌었다고 생각해봐자.
그렇게 되면 s에 의해 보호되는 임계영역 내부에서 세마포어n에 대한 semWait을 수행하게 된다.
버퍼가 비어있으면 소비자가 임계영역에 들어가면서 세마포어 s를 확보한 채 세마포어 n에서 블록된다. 하지만 생산자는 세마포어 s에 대한 허가를 얻을 수 없어 버퍼에 데이터를 추가하기 위한 임계영역에 진입하지 못한다.
버퍼의 크기는 무한하지 않지만 지금까진 무한하다고 가정했다.
버퍼가 유한하려면 어떻게 해야할까?
환형 큐로 된 버퍼 구조가 된다.(고리모양)