멀티 프로세싱 케케묵은 문제들 - 병렬 처리 관련 문제

Java Blocking Queue 관련 공부 중에 Producer-Consumer Problem(생산자-소비자 문제) 에 대해서 리마인드 해보고자 찾다가 다른 재미난 문제들을 함께 찾게되었다.

대학교를 졸업한지 그리 오래되지 않았지만 공부를 잘 하지않아 잊혀졌던 개념도 있고, 처음들어본 문제도 있어 흥미로웠지만

역시 케케묵은 문제라고 표현하고 있듯, 고전적인 냄새가 많이 난다.

시간이 난다면 꼭 OS 개념에 대해서 한번 더 훑어봐야겠다.

케케묵은 문제들

오래된 문제들이지만 현재 우리가 사용하는 컴퓨터의 기반 알고리즘을 설계하는데 결정적인 역할을 했던 문제들이다. 병렬 처리와 관련된 문제들로서 이를 제대로 파악하지 않으면 자신이 만든 코드가 왜 문제를 발생시키는지 알기 어렵다.

• Producer-Consumer : 하나 이상의 생산자가 정보를 생성해서 Buffer나 Queue에 넣는다. 하나 이상의 소비자가 대기열에서 정보를 가져와서 사용한다.
• 생산자는 대기열에 빈공간이 있을 때까지 정보를 채운다. 빈공간이 없으면 소비자가 Wake Up 해줄 때가지 기다린다.
• 소비자는 대기열에 정보가 없을 때까지 정보를 읽는다. 더이상 읽을 정보가 없으면 생산자가 Wake Up 해줄 때까지 기다린다.
• 문제 상황 - 생산자 스레드와 소비자 스레드 둘 다 서로 상대방에게 Wake Up 되기를 기다리면서 Starvation에 빠질 수 있다.
• 해결책 - Semaphore, Mutual Exclusion, 모니터 패턴
• Readers-Writers : 공유 자원을 읽는 스레드와 공유 자원에 갱신을 일으키는 스레드가 있다. 
• 쓰기 스레드가 버퍼를 갱신하는 동안 읽기 스레드는 버퍼를 읽지 않아야 하고,  읽기 스레드가 버퍼를 읽는 동안 쓰기 스레드는 버퍼를 갱신하지 않아야 한다.
• 처리율을 강조하여 읽기 스레드가 있으면 쓰기 스레드가 대기하도록 구성하면 지속적으로 읽기 스레드가 발생하는 경우에 Starvation 이 발생하기 쉽다. 
• 반대로 갱신을 허용하여 쓰기 스레드에 우선권을 주면 읽기 처리율에 영향을 미친다. 
• Dining Philosophers : 둥근 식탁에 철학자 한 무리가 있다. 각 철학자 왼쪽에 포크가 놓여 있고, 식탁 가운데에는 스파게티 한 접시가 있다. 철학자들은 보통은 생각하며 시간을 보내지만 배가 고프면 양손에 포크를 쥐고 음식을 먹는다. 
• 문제 상황 - 왼쪽이나 오른쪽 철학자가 식사를 하고 있을 때에는 포크를 양손에 쥘 수 없어서 식사를 할 수 없다. 즉, 양쪽 자원이 모두 허용 가능할 때까지 기다려야 한다. 
• Sleeping barber problem : 이발소에는 하나의 머리깍는 의자가 있고, 대기실에는 몇개의 의자가 있어서 손님이 기다릴 수 있다. 이발사는 손님의 머리를 깍고 대기실에 손님이 있으면 손님을 모시고 의자에 앉힌 후 머리를 깎는다. 손님이 대기실에 없으면 쉬러간다. 손님은 이발소에 들어올 때 이발사가 머리를 깍고 있는지 살핀다. 이발사가 머리를 깍고 있지 않으면 바로 의자에 앉은 후 쉬고 있는 이발사를 호출한다. 이발사가 이발을 하고 있지 않으면 바로 대기실에 들어간다. 
• 문제 상황 - 대기실에 손님이 들어가기 전에 이발사가 머리를 다 깍은 경우에 아직 손님은 대기실에 도착하기 전이므로 이발사는 쉬러가는 상황이 발생한다. 
• Cigarette Smokers Problem : 테이블에 3명의 흡연자가 있고 흡연을 위해 필요한 자원 (담뱃잎, 종이, 성냥) 중 1가지를 무한정 공급받고 있다. Agent가 하나 있어서 임의로 두 아이템을 꺼내서 테이블에 놓는다. 두 아이템 이외에 나머지 하나를 가진 흡연자만 담배를 피울 수 있다. 이 실행에서 조정자는 OS이고 흡연자는 프로세스를 의미한다. 
• 문제 상황 : Agent는 한명이 흡연중인 상태에서 다른 흡연자가 담배를 피울 수 있도록 해줄 수 있어야 한다.
  

출처 : http://www.softfactory.org/language/gongtong/multithread