진지하게 읽지 마세요.
------------------------------
식당에서 주문을 하는 시스템을 관찰한 적이 있었다. 어차피 밥은 매일매일 먹으러 가니까 관찰하는데 일부러 신경써서 뭘 해야 하는건 없다.

여기에 더불어 요즘 컴퓨터과학을 배우다 보니 운영체제가 사용자에게 서비스를 제공하는 방식에 대해서 공부를 하고 있다. 이것은 사실 식당의 발전 체계와 비슷한 것 같다.

초기의 식당은 1명의 식당 주인이 주문 받고, 요리를 하고, 상을 차려서 내주고, 손님이 식사를 마치면 계산을 한다. 가령, 이런 것은 운영체제가 프로그램의 요청을 받아서 자원을 분배하고 회수하는 시스템과 닮아있다. 손님이 그다지 많지 않은 식당에서는 충분히 처리할 수 있다. 손님이 너무 오래 기다린다고 짜증내기 전에 식사를 내 올 수 있다.

식당이 유명해 지게 되면 손님이 점점 많아지는데, 식당 주인은 가게를 확장해야 한다. 가게를 확장하게 되면 받을 수 있는 손님의 수가 많아지므로 더 많은 돈을 벌 수 있다. 그런데, 한번에 많은 수의 손님을 받게 되면 자리에서 대기하고 있는 손님이 많아지고, 결과적으로 손님의 평균 대기시간이 늘어나게 된다. 평균 대기시간이 늘어난다는 것은 맛이야 어떻든간에 서비스의 질적 하락을 나타내므로 좋지 않은 상황이다. 따라서 평균 대기시간을 줄이기 위한 방법을 생각해 봐야 한다.

식당 주인이 쓰는 방법은 여러가지가 있다.
식당 주인이 손님의 요청을 받고, 주문서를 갖다가 주문서 큐(Queue)에 올려두면 요리사가 순서대로 처리하는 방법이 있다. 식당 주인이 손님의 요청을 받는 사이에도 요리사는 요리를 할 수 있고, 주문서 큐를 잠깐만 참고하면 되기 때문에 이 방법은 요리사를 방해하지 않는다. 이런걸 DMA(Direct Memory Access)방법이라고 한다.

요리사가 요리를 하기 전에 냉장고에서 미리 요리 재료를 꺼내서 도마 위에 올려둘 수가 있는데, 이걸 캐싱(Cacheing)이라고 부른다. 냉장고에서 꺼내 오는 것보다 도마 위에서 바로 손질하는 것이 훨씬 빠르기 때문에 잘만 하면 대기시간을 확 줄일 수 있다. 캐싱을 잘 하려면 어떤 요리가 주문될 것인가 예측하는 것이 대단히 중요하다. 예측의 정확도가 높을수록 대기시간이 줄어든다.

한단계 더 나아가서, 납품받은 식재료를 미리 냉장고에 채워넣는 것은 버퍼링이라고 한다. 버퍼링이 없다면, 가령 간장 게장을 시킨 손님은 "아니, 요리사가 게잡으러 동해로 떠났어?"라고 생각하게 될 것이다.

식사가 나오기 전에 밑반찬을 미리 내와서, "뭔가 진행중"이라는 생각을 갖도록 하여 손님을 붙잡아 두는 방법이 있다. 만약, 여기에 밑반찬을 미리 내오는 서빙 알바를 두고 식사를 서빙하는 알바를 둔다면 이것은 2단계 파이프라이닝이 되는 것이다. 물론 여기에서도 병목현상은 일어날 수 있는데, 알바가 1명이라면 손님이 몰려왔을 때 밑반찬 세팅에 대한 대기시간도 늦어질 수가 있다.
처리하는 단계를 좀 더 세분화 해서, 물수건과 물컵과 식기를 세팅하는 알바를 두고, 주문을 받는 알바를 두고, 밑반찬을 내오는 알바를 두고, 식사를 서빙하는 알바를 두고, 계산대에서 식대 정산만 하는 알바를 둔다면 5단계 파이프라이닝이 된다.
3, 4단계 파이프라이닝은 어떻게 하면 되는지 생각해 보자.

요리사를 여러명 고용해서 한번에 여러개의 요리를 만들도록 하는 것도 방법이 될 수 있다. 이것은 요즘 유행하고 있는 다중 CPU 병렬 처리가 된다. 이 경우에는 어느 요리사에게 어떤 주문을 넣어주느냐를 분배하는 방법을 잘 고려해야 한다. MPI나 openMP같은 라이브러리를 알려주면 좋겠지만, 식품 공학과 컴퓨터 공학 사이에는 언어의 장벽이 있다. 아무튼 식당 주인은 주문을 받아서 잘 넣어주면 된다.

요리사를 여러명 고용하다 보면 주방이 좁아지는 경우를 피할 수 없는데, 아예 다른 식당과 연합하여 한쪽으로 주문이 몰릴 때 다른 식당에서 요리를 해서 갖다 주는 방식을 생각해 볼 수 있다. 이 경우, 식당과 식당 사이에서 주문을 전달하고 요리를 받아오는 속도가 관건이 된다. 이것은 서버 다중화 기술에 해당한다.

아예 손님이 주문 받는 창구를 단일화 해버리고, 주문은 한곳에서 받고 식사는 각각 적당한 곳에 배정해서 요리를 내오도록 하는 곳도 있다. 백화점 푸드코트에서 쓰는 방식인데, 이런 것을 클라우드 컴퓨팅이라고 한다. 좀 더 확장된 의미의 클라우드 컴퓨팅에서는 아무데서나 주문해도 적당한 곳에서 요리가 나오는 것이 가능하다. 요즘 각광받고 있다.

한명의 요리사를 쓰더라도, 여러개의 요리를 동시에 처리하도록 할 수도 있는데, 가령 어떤 요리가 10분동안 물을 끓여야 하는 과정이 필요하다면 그 사이에 다른 요리의 다른 과정을 수행할 수 있는 것이다. 이 경우, 요리사의 지능이 높아야 한다는 제약조건이 필요하지만 어쨌든 평균 대기시간을 줄이는데 한몫 할 수 있다. 이것은 시분할 다중처리에 해당한다. 만약 한명의 요리사가 가스렌지를 쓰면서 전자렌지를 돌리고 도마에 양파를 다지면서 오븐에 닭을 굽고 있다면 이것은 하이퍼스레딩이 된다. 하이퍼스레딩이란 하나의 CPU를 두개 이상의 CPU처럼 보이게 하는 기술이다. 근데 손님이 적을 때는 하이퍼스레딩을 안하는 것이 더 빠르게 처리된다.

손님 중에 변태끼가 있는 사람이 있어서 중국집에 가서 꽃등심 스테이크를 주문하는 사람이 있다면, 일반적으로 그런 손님은 욕먹으면서 내쫒기게 된다. 하지만 기왕에 온 손님을 내칠 수는 없다며 시장 확대를 위해 몸부림 치는 식당 주인이라면 에뮬레이션과 가상화를 고려하게 된다. 중국집 요리사보고 꽃등심 스테이크를 배워서 내놓으라고 한다. 이런 경우에는 중국집 요리사가 꽃등심 스테이크 만드는 법을 요리책을 보면서 해야 하기 때문에 주문이 느리게 처리될 것이다. 이것을 에뮬레이션이라고 부른다. 돈을 많이 받는 유명 중국집 요리사들은 아예 양식 요리사를 고용할 수도 있는데, 이것은 가상화가 된다. 물론, 진짜 변태스런 손님은 중국집에 가서 양식 요리사보고 탕수육을 만들어 오라고 할 수도 있다. 이 경우, 중국집 식당 주인이 융통성을 발휘해서 양식 요리사 대신에 원래 데리고 있던 중국음식 요리사에게 탕수육을 만들어서 양식 요리사보고 갖다 주라고 할 수도 있는데, 서비스 품질도 좋고 더 빨리 처리된다. 이것을 하드웨어 수준에서 지원하는 가상화라고 한다.

손님이 주문을 한 순서대로 요리를 내가는 방법을 FIFO(First in First out)라고 한다. 이것은 Queue를 써서 주문을 처리하는데, 대부분의 소규모 식당에서 사용한다. 하지만 어떤 손님이 시간이 엄청 걸리는 요리를 주문했는데, 요리사가 한명 뿐이라면 다른 손님들의 평균 대기시간이 너무 길어질 것이다. 그래서 식당 주인들은 잔머리를 굴려서 주문에 우선순위를 주고 평균적으로 대기시간을 줄여서 몇명은 화를 내더라도 전체적으로는 만족스러운 주문 처리를 하는 방법을 개발해 냈다. 우선 한가지 알아두어야 하는 것은, 요리사한테 요리를 하다가 말고 다른 요리부터 먼저 하라고 시키는 방법을 선점형이라고 부르고, 하나 시작했으면 끝까지 마친 다음에 다른 요리를 시키는 방법을 비선점형이라고 한다.

SJF(Shortest Job First)라는 방법이 있다. 이건 비선점형으로, 일단 시작한 요리는 완성한다. 그리고 나서 그 다음에 들어온 주문 중에, 가장 요리 시간이 짧을 것 같은 주문을 먼저 처리한다. 이 방법의 단점은, 요리시간이 짧은 주문이 계속 들어오면 상대적으로 시간이 길게 걸리는 주문은 무한정 기다릴 수 있다는 것이다. 그리고 요리시간에 대한 요리사의 추측이 틀리면 GG

SRT(Shortest Remaining Time)방법은 SJF를 조금 바꾼 선점형 방법이다. 일단 요리를 시작하는데, 만약 지금 하고 있는 요리를 완성하는데 걸리는 시간보다 더 빨리 완성할 수 있는 요리의 주문이 들어오면 그걸 먼저 처리한다. 이건 SJF방법보다 요리사가 좀 더 부담스러운데, 계속해서 만드는 요리를 바꿔야 할 수 있기 때문에 머리털 쥐어 뜯게 만들 수 있다는 점이다.

RR(Round Robin) 방법은 완전 잔머리 굴린 선점형 방법인데, 요리사가 일정 시간마다 계속해서 처리중인 요리를 바꾼다. 일정 시간이 지나면 순서대로 요리를 바꿔가면서 한다. 문제는, 재수없으면 모든 손님이 오래 기다릴 수 있다는 점이다. 그리고 마찬가지로 요리사가 머리가 좋아야 한다는 제약조건이 발생한다.

그외에도 몇가지 방법이 더 있지만 생략한다.

손님들의 주문이 몰려오다 보면 주방이 마비되는 일도 가끔 발생한다. 탕수육을 만들려면 가스렌지 위에 솥을 놓고 기름을 부어서 고기를 튀겨야 하는데, 밥을 하려면 가스렌지 위에 솥을 놓고 물을 끓여서 쌀을 익혀야 한다. 요리사 여러명이 하나의 솥을 놓고 쓰는데, 어떤 요리사가 솥에 기름을 넣고 가스렌지에서 기름을 데우면서 고기를 썰고 있는 사이에, 다른 요리사가 밥을 하겠다고 솥에 있는 기름을 버리고 물을 끓였다. 앞의 요리사가 고기를 썰어서 솥에 넣었더니 탕수육이 아니라 그냥 수육이 되어버렸다. 두 요리사가 싸우게 되고 손님은 무한정 기다리게 되는데, 이런 상황을 교착상태(Deadlock)라고 부른다. 식당 주인으로서는 제발 피하고 싶은 사태이다. 심정적으로는 눈물이 날 것이다.

교착상태는 요리사가 여러명일 뿐만 아니라, 요리사가 한명이더라도 손님의 주문이 이상한 경우에 발생할 수 있다. 손님이 낙지 볶음과 돌솥 비빔밥을 주문했다고 하자. 돌솥 비빔밥을 만들려면 밥을 돌솥에 담고 야채와 고기를 넣고 고추장을 넣으면 된다. 근데, 요리사가 야채와 고기를 돌솥에 담아놓고 전기밥솥이 밥을 하는 사이에 요리사가 낙지를 볶았는데 고추장을 다 써 버렸다. 문제는 돌솥에 야채를 다 써버려서 낙지볶음을 완성시킬 수 없다는 것. 게다가 고추장을 다 써버렸으니 돌솥 비빔밥이라고 제대로 만들 수도 없다. 물론 이럴 때 현실의 요리사라면 낙지덮밥을 내놓는 비장의 수를 쓸 수 있겠지만 어쨌거나 주문대로 요리가 나오지 않았으니 고객 만족도는 떨어질 수밖에 없다.

교착상태를 막으려면, 저런식으로 사용량이 제한된 자원은 계속 보충을 해줘야 한다. 또한, 만약 돌솥 비빔밥의 주문이 들어왔다면 돌솥 비빔밥을 만드는데 필요한 자원을 모두 모아놓고 다른데 쓰지 않는 전략이 필요하다. 이런식으로 일을 했다면 위의 요리사는 최소한 돌솥 비빔밥은 내갈 수 있었을 것이다.

by snowall 2009.12.13 03:12
  • ... 2009.12.13 03:44 ADDR EDIT/DEL REPLY

    이건 os관련 문제라기 보다는 os에서 queueing theory를 빌려다 쓰는거 아닌가요?
    주로 식당에서 쓰이는 모델은 M/M/1 (http://en.wikipedia.org/wiki/M/M/1_model) 모델이나 M/M/S 등에서 손님이 도착하는 시간을 poisson process로 보고 그거에 맞게 기다리는 시간 등을 예측하고 하는데

    • snowall 2009.12.13 09:15 신고 EDIT/DEL

      그냥 둘 사이의 유사점을 찾아보자는 거죠. 진지하게 읽진 마세요 --;

  • starrynight 2009.12.13 19:12 신고 ADDR EDIT/DEL REPLY

    고퀼의 유머이군요;;;

    • snowall 2009.12.13 20:37 신고 EDIT/DEL

      네. 개그인데 말입니다. ㅋㅋㅋ

  • dbskzh 2009.12.13 20:16 ADDR EDIT/DEL REPLY

    ㅋㅋㅋ
    '3가지맛 립톤 아이스티'에 이은 명작이네요./

    잘 읽었어요^^

    • snowall 2009.12.13 20:38 신고 EDIT/DEL

      공부하다보니 쉽게 외우려구요
      이런거 하나 찾아내면 쉽게 외워집니다 ㅋㅋㅋ

  • goldenbug 2009.12.13 21:33 ADDR EDIT/DEL REPLY

    정보처리기사 시험 볼 때 생각나네요. 이론에서... 컴퓨터 cpu 이론인가에서 나오는..

    • snowall 2009.12.13 21:48 신고 EDIT/DEL

      아마 그거 1급인가 합격하면 졸업논문이 면제였던가 할거예요;;
      아닌가...-_-; 뭔가 자격증이 면제 조건에 있었어요.

    • goldenbug 2009.12.13 22:37 EDIT/DEL

      졸업논문이 면제될 정도로 어려운 자격증은 아니에요.
      개도 새도 보는 시험인데...^^;

    • snowall 2009.12.13 22:38 신고 EDIT/DEL

      그럼 다른 시험이겠군요. -_-;
      뭐더라...;;;

  • rangshu 2010.03.22 13:05 ADDR EDIT/DEL REPLY

    정말 좋은 글이네요.
    감사합니다.~