차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

생산자_소비자_문제 [2011/06/28 09:42]
raychani 새로 만듦
생산자_소비자_문제 [2011/06/28 10:50] (현재)
raychani
줄 3: 줄 3:
 **[[wk>​생산자-소비자 문제|생산자 소비자 문제]]**는 동기화 문제를 일으키지 않고 한정된 크기의 공유자원(버퍼)에 접근하는 방법을 어떻게 해결할 것인가를 나타낸다. 멀티스레드 프로그래밍에서 어떤 스레드는 주로 데이터를 생산하고,​ 다른 스레드는 생산한 데이터를 이용하여 다른 작업을 하는 경우가 많다. 예를 들어, 인터넷에서 스트리밍 방식 동영상을 재생하는 경우, 인터넷에서 자료를 가져오는(생산하는) 스레드와 가져온 자료를 이용하여 재생하는(소비하는) 스레드로 이루어질 수 있다.((물론 엄청나가 단순화 시킨 예다.)) **[[wk>​생산자-소비자 문제|생산자 소비자 문제]]**는 동기화 문제를 일으키지 않고 한정된 크기의 공유자원(버퍼)에 접근하는 방법을 어떻게 해결할 것인가를 나타낸다. 멀티스레드 프로그래밍에서 어떤 스레드는 주로 데이터를 생산하고,​ 다른 스레드는 생산한 데이터를 이용하여 다른 작업을 하는 경우가 많다. 예를 들어, 인터넷에서 스트리밍 방식 동영상을 재생하는 경우, 인터넷에서 자료를 가져오는(생산하는) 스레드와 가져온 자료를 이용하여 재생하는(소비하는) 스레드로 이루어질 수 있다.((물론 엄청나가 단순화 시킨 예다.))
  
 +이 문서에서는 세마포어를 이용한 알고리즘과 예제 코드를 소개한다.
 ===== 알고리즘 ===== ===== 알고리즘 =====
 +세마포어를 이용해 문제를 해결하는 알고리즘이다. 공유자원 접근 문제는 물론 버퍼 언더플로우,​ 오버플로우 문제도 해결해 줘서 사용하기 편하다.
 +
 굉장히 오래전 자료를 참고하여 만든 것을 이제와서 다시 정리하는 것이라 원본 데이터가 너무 희미하다. 하지만 알고리즘 자체는 명확히 맞으므로 그대로 예전 자료를 참조한다. 굉장히 오래전 자료를 참고하여 만든 것을 이제와서 다시 정리하는 것이라 원본 데이터가 너무 희미하다. 하지만 알고리즘 자체는 명확히 맞으므로 그대로 예전 자료를 참조한다.
 +
 +:!:이 알고리즘은 현재 [[wk>​생산자-소비자 문제|한국어 위키]]에서 불완전한 방법으로 소개하고 있다. 그러나 [[wp>​Producer-consumer problem|영문 위키]]에서 불완전한 방법(Inadequate implementation)으로 소개하고 있는 것은 이 알고리즘과 다르다. 좀 더 공부하고 확실하면 수정할 예정이다.
 +
 +한국어 위키에서 불완전한 방법으로 소개한 것은 알고리즘에 해당하고,​ 영문 위키에서 불완전한 방법으로 소개하는 것은 엄밀히 해석해서 불완전한 **구현**이다.
 +
 +영문 위키에서 **Using semaphores**에서 완전한 방법으로 소개하고 있는 코드를 보면 이 문서에서 소개하고 있는 알고리즘과 동일함을 알 수 있다.
 ==== 공유 변수 ==== ==== 공유 변수 ====
   * int maxSize   * int maxSize
줄 118: 줄 126:
 ===== 예제: 구현 ===== ===== 예제: 구현 =====
 예제를 상속받아서 0~9 사이의 숫자를 만들고(생산자) 출력하는(소비자) 간단한 예제이다. 아무 생각없이 만들었는데,​ 생산자와 소비자가 각각 1개인 경우 뿐만아니라 각각이 여러개인 경우에도 잘 동작한다. 물론 이렇게 쓰는 경우는 없을거다. 예제를 상속받아서 0~9 사이의 숫자를 만들고(생산자) 출력하는(소비자) 간단한 예제이다. 아무 생각없이 만들었는데,​ 생산자와 소비자가 각각 1개인 경우 뿐만아니라 각각이 여러개인 경우에도 잘 동작한다. 물론 이렇게 쓰는 경우는 없을거다.
 +
 +C# 코드지만 사실 이걸 C# 코드라고 말하기 어렵다. Mutex를 사용한 부분은 lock라는 키워드로 대체하는 것이 더 적절할 것이다. 다만 알고리즘을 소개하는 문서이니만큼 최초 알고리즘을 존중하여 **Semaphore s**로 시작하였다가 Mutex로만 바꾸었다.
  
 좀 더 그럴듯하게 만드려면 while(true) 대신에 적절하게 스레드를 탈출하는 코드로 바꾸면 된다. 단지 그런 코드는 콘솔 어플리케이션에서는 처리하기 어렵고 GUI 프로그램을 이용해야 한다. 자세한 것은 [[멀티스레딩]] 문서를 참조하자. 좀 더 그럴듯하게 만드려면 while(true) 대신에 적절하게 스레드를 탈출하는 코드로 바꾸면 된다. 단지 그런 코드는 콘솔 어플리케이션에서는 처리하기 어렵고 GUI 프로그램을 이용해야 한다. 자세한 것은 [[멀티스레딩]] 문서를 참조하자.
줄 214: 줄 224:
 Add: 10 Id: 4 Add: 10 Id: 4
 Pro: 8  Id: 4 Pro: 8  Id: 4
 +</​code>​
 +
 +===== 다른 방법 =====
 +MS에서는 C#언어를 이용한 [[http://​msdn.microsoft.com/​ko-kr/​library/​yy12yx1f(v=vs.80).aspx|생산자와 소비자 스레드 동기화]]라는 방법을 소개하고 있다. 알고리즘 자체는 이 문서와 유사한 것으로 보인다. 다만 언어 자체에서 지원하는 방법을 최대한 사용하여 구현 방법이 다를 뿐이다. 구현 측면에서 눈에 보이 차이점을 분석해 보면 다음과 같다.
 +
 +:!: 분석이 맞다고 보장은 못 하겠다.
 +
 +  * Producer와 Consumer 클래스 분리
 +    * Producer, Consumer 분리에 따라 각 클래스의 생성 시 공유자원,​ 동기화 객체 지정
 +    * public Producer(Queue<​int>​ q, SyncEvents e)
 +    * public Consumer(Queue<​int>​ q, SyncEvents e)
 +  * 스레드 종료 방법 추가
 +
 +알고리즘 측면에서도 조금 다른 지 모르겠다. lock의 범위로 볼 때 버퍼에 추가하는 부분만 최소화하여 s로 보호하던 것을 여러개를 추가하도록 바꾼 것 같은데... 효율을 높히기 위해 이렇게 바꾼 것인지, 언어 자체에서 지원을 해주어서 이렇게 한 것인지는 모르겠다. 컨텍스트 스위칭이 더 줄어 전체 시스템 자원 낭비는 줄겠지만... 버퍼를 너무 오래 붙잡고 있는게 아닌지... 효율을 위해서 이렇게 했다면, produce에 시간이 오래 걸리는 경우 좀 안좋은 결과가 생길 것도 같다.
 +
 +처음에 소개한 스트리밍 동영상의 예를 보자. 인터넷 상태가 잠시 안 좋아서 버퍼가 비어있다가 인터넷이 복구되었다. 이 문서의 방식에서는 일단 데이터를 1개라도 가져오면 버퍼에 넣어서 바로 재생을 시작한다. MS방식은 데이터를 최대한 가져와서 다 채운 이후에야((버퍼링 100%)) 재생을 시작한다. 인터넷 상태가 이후로 계속 좋은 경우는 조금이라도 빨리 재생을 시작하는 이 문서의 방법이 좋을 것 같다. 다만 상태가 안 좋으면 조금 나오고 바로 끊기고를 반복할 것이다. 반면에 MS의 방식은 인터넷이 좋은 경우 재생을 더 느리게 시작하겠지만,​ 이후로도 좋지 않은 경우는 그래도 어느 정도 나오고 끊기고를 반복할 것이다. 이 쯤 되면 알고리즘의 좋고 나쁘고를 떠나서 개발 정책의 문제다. 자신의 환경에 맞는 방법을 찾아보자.
 +
 +이 문서의 알고리즘. 일단 생산하고 버퍼를 독점한 후에 버퍼에 1개만 넣고 버퍼를 놓아준다.
 +<​code>​
 +        data = produce(); // 데이터 생산
 +        wait(e); ​         // 버퍼의 빈 공간 확인(대기)
 +        wait(s); ​         // 버퍼에 단독 접근 확인(대기)
 +        append(data); ​    // 버퍼에 데이터 추가
 +        signal(s); ​       // 버퍼에 단독 접근 해제
 +        signal(n); ​       // 버퍼에 데이터 추가 알림(해제) ​
 +</​code>​
 +
 +MS의 방식을 이 문서와 유사하게 표현한 알고리즘. 버퍼를 독점한 후에 버퍼가 다 찰 때까지 생산-추가를 반복하고 버퍼를 놓아준다.
 +<​code>​
 +        wait(e); ​         // 버퍼의 빈 공간 확인(대기)
 +        wait(s); ​         // 버퍼에 단독 접근 확인(대기)
 +        while(numberOfData < maxBufferSize)
 +            data = produce(); // 데이터 생산
 +            append(data); ​    // 버퍼에 데이터 추가
 +            signal(n); ​       // 버퍼에 데이터 추가 알림(해제) ​
 +        signal(s); ​       // 버퍼에 단독 접근 해제
 +
 +</​code>​
 +
 +
 +이 문서의 코드를 다음과 같이 Mutex를 lock로 바꾸는 정도가 무난하지 않을까?
 +<​code>​
 +    T t = Produce();
 +    e.WaitOne();​
 +    lock(list)
 +    {
 +        Append(t);
 +    }    ​
 +    s.ReleaseMutex();​
 +    n.Release();​
 </​code>​ </​code>​
 ~~LINKBACK~~ ~~LINKBACK~~
 ~~DISCUSSION~~ ~~DISCUSSION~~