병행 프로세스 - 생산자/소비자 문제(Producer/consumer Problem)

<생산자/소비자 문제(Producer/consumer Problem)>

생산자는 데이터를 만들어 버퍼에 저장하고(채워나가고), 소비자는 버퍼에 있는 데이터를 꺼내 소비하는(비우는) 프로세스

버퍼는 공유 자원이므로 버퍼에 대한 접근 즉, 저장하고 꺼내는 일들이 상호배제 되어야 함

버퍼가 비어 있을 때는 소비자가, 버퍼가 꽉 차있을 때는 (더 이상 저장할 공간이 없으므로) 생산자가 기다려야 하는 동기화도 자연스럽게 포함되어 있다. 버퍼의 크기는 저장 공간이 하나인것부터 무한개까지 설정 가능하다.

 

 

위 코드에서 in은 버퍼에서 채워 넣을 위치를 말하고, out은 꺼낼 위치를 나타내며, 초기 값은 각각 0이고, 버퍼가 차있거나 비어 있을 경우 중간의 while문을 맴돌게 된다.

n개의 공간을 가지는 유한 크기의 원형 버퍼를 가정한 알고리즘을 보자.

다음 그림에서 흰 블록은 비어있는 buffer를 나타내고, 검은색 블록은 내용이 들어있는 buffer를 나타낸다.

위의 원형 버퍼를 가지고 다음 코드를 해석해보자.

왼쪽은 생산자 코드이고, 오른쪽은 소비자 코드이다.

Occupied는 세마포어로 초깃값이 0이다. 이유는 맨 처음 원형 버퍼에는 단 한개의 값도 저장되어 있지 않기 때문이다.

Empty는 세마포어로 초깃값이 n이다. 이유는 맨 처음 원형 버퍼에는 n개의 빈칸이 있기 때문이다.

[생산자 코드]

P(Empty)에서 받은 Empty값이 0보다 큰 정수이면 하나를 뺀다. 즉, 원형 버퍼 안에 빈 칸이 있으면 그 값에서 -1을 시킨다. (빈 칸이 하나 없어지는 셈이니...)

만약 비어있는 버퍼라면 j번째에 있는 버퍼 블록에 저장한다.(생성자)

그 후, 다음 저장할 인덱스로 자리를 이동시키기 위해 +1을 해준다. mod n을 해주는 이유는 n mod n = 0이기 때문인데, 원형 버퍼 인 것을 기억하자.

마지막으로 V(Occupied)는 대기중인 프로세스들이 존재하면 실행 상태로 만들고, 그렇지 않다면 +1을 해준다. +1을 해주는 이유는 생성자가 하나 저장했기 때문에 채워진 버퍼 블록(위 그림에서 검은색 블록)이 하나 증가함.

[소비자 코드]

P(Occupied)에서 받은 Occupied 값이 0보다 큰 정수이면 하나를 뺀다. 즉, 원형 버퍼 안에 채워진 슬롯들이 있으면 그 값에서 -1을 시킨다. (채워진 슬롯을 하나 읽어오는 셈이니...)

만약 차있는 버퍼라면 i번째에 있는 버퍼 슬롯을 읽어온다.(소비자)

그 후, 다음 읽어갈 인덱스로 자리를 이동시키기 위해 +1을 해준다. mod n을 해주는 이유는 n mod n = 0이기 때문인데, 원형 버퍼 인 것을 기억하자.

마지막으로 V(Empty)는 대기중인 프로세스들이 존재하면 실행 상태로 만들고, 그렇지 않다면 +1을 해준다. +1을 해주는 이유는 소비자가 하나 읽었기 때문에 비워진 버퍼 블록(위 그림에서 흰색 블록)이 하나 증가함.

<모니터>

공유 데이터들과 이 들에 대한 임계영역들을 관리하는 소프트웨어 프로시저를 포함하는 병행성 구조(concurrency construct)로 자료 추상화(data abstraction)의 개념을 기초로 하고 있다.

모니터는 프로그래밍 언어 수준에서 제공되는 모듈로서 공유 데이터를 위한 변수들과 초기화 루틴, 임계영역을 코딩한 프로시저들로 이루어진 일종의 함(box)으로 이해. 모니터 내의 변수들은 프로시저들을 통해서만 접근이 가능하므로, 프로세스들은 모니터의 프로시저를 호출, 실행하여 모니터 안으로 진입한 후 원하는 공유 데이터에 대한 접근을 하게 된다. 중요한 점은 언제나 모니터의 진입을 한 프로세스로 제한함으로써 즉, 한 번에 하나 이하의 프로세스만이 모니터 내에 있게 함으로써 상호배제를 자연스럽게 실현한다는 것이다.

모니터에서는 조건변수(Condition Variable)를 선언하고, 조건의 대기를위해 wait(C)를, 대기에서 깨어나기 위해 signal(C)을 제공한다. 조건변수는 모니터에서만 선언하고 사용하는 것으로 wait()와 signal()에 의해서만 접근 된다. wait(c)는 이 연산을 호출한 프로세스를 조건 c의 큐에 대기시키고 다른 프로세스의 모니터 진입을 가능하게 한다. signal(c)는 wait(c)에 의해 대기되었던 프로세스를 재개시키고 자신은 신호자 대기 큐로 비켜준다. 만일 wait(c)로 대기 중인 프로세스가 많다면 그 중에 하나를 고를 것이고, 없다면 단순히 다음 문의 실행을 계속하면 된다.

 

 

위 코드를 분석해보자.

buffer[n]은 n개의 buffer를 갖는 배열을 만든다. (원형 버퍼)

nextin은 원형 버퍼에 다음 빈 슬롯에 추가하는 인덱스이다.

nextout은 원형 버퍼에 다음 저장된 슬롯에서 읽어오는 인덱스이다.

count는 저장되어 있는 슬롯의 개수이다.

cond notfull, notempty는 조건 변수로 각각 슬롯이 full이 아닌 상태와 슬롯이 empty가 아닌 상태를 말한다.

void append(char x)에서

if (count == n) 만약 저장되어 있는 슬롯의 개수가 n이면, 꽉찬 상태이면...

cwait(notfull); 슬롯이 full이 아닌 상태가 될 때까지 기다린다. 그래야 빈 슬롯에 저장할 수 있으니까...

buffer[nextint] = x; 그렇지 않다면 다음 비어있는 슬롯(인덱스)에 x값을 저장해라.

nextin = (nextin + 1) % n; 그다음 인덱스값을 다음으로 옮겨준다. %n을 하는 이유는 원형 버퍼를 기억하자!

count++; 값이 하나 저장되었으므로, count값이 하나 증가

csignal(notempty); 대기되었던 프로세스를 재개시키고 자신은 신호자 대기큐로 비켜준다.

void take(char x)에서

if(count == 0) 만약 저장되어 있는 슬롯의 개수가 0이면, 빈 상태이면...

cwait(notempty); 슬롯이 empty가 아닌 상태가 될 때까지 기다린다. 그래야 저장되어 있는 슬롯으로부터 읽어 올 수 있으니까...

x = buffer[nextout]; 그렇지 않다면 다음 슬롯을 읽어서 x에 저장한다.

nextout = (nextout + 1) % n; 다음 인덱스 값으로 옮겨준다.

count--; 값을 하나 읽어 왔으므로, count값이 하나 감소

csignal(notfull);

 

 

Copyrightⓒ2014 By 휴먼사이언스