Chapter 07. 큐의 활용

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조입니다. 그리고 '큐잉 이론'이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션'하게 되는데, 이때에도 큐는 중요한 역할을 담당합니다. 따라서 우리도 시뮬레이션이라는 주제를 통해서 큐가 활용되는 형태를 적절한 범위 내에서 확인하고자 합니다.

---

시뮬레이션을 구현해 보기 위해 이와 관련한 상황을 예로 들겠습니다.

 

어느 햄버거 가게의 점장은 주문된 음식이 포장돼 나오기를 기다리는 손님들을 위해 대기실을 만들려고 합니다. 하지만 대기실이 몇 명까지 수용할 수 있어야 하는지 판단하기가 쉽지 않습니다. 모든 손님들이 대기실을 이용할 수 있도록 크게 만들자니 돈이 너무 많이 들고, 그렇다고 대기실을 작게 하자니 대기실을 이용하지 못하는 손님들이 오히려 많아 불만을 살지도 모릅니다. 대기실이 항상 넉넉해야 하는 것은 아니고, 때때로 대기실이 가득 차서 대기실을 이용하지 못하는 손님들이 몇몇 생겨도 괜찮습니다. 점장은 일반적인 경우에 손님들을 대부분 수용할 수 있는 대기실을 만들고 싶어 합니다.

 

점장은 우리에게 대기실의 수용인원을 어떻게 정하면 좋을지 도움을 청해왔습니다. 우리는 이 문제를 시뮬레이션을 통해 해결할 수 있습니다. 시뮬레이션을 하기 위해서는 몇 가지 정보가 필요합니다. 점장은 손님이 가장 많이 몰리는 점심시간을 기준으로 다음과 같은 정보를 전해주었습니다.

• 점심시간 1시간 동안에는 고객이 15초당 1명씩 주문을 한다.
• 종류별 햄버거를 만드는 데 걸리는 시간은 다음과 같다.
  • 치즈버거 12초, 불고기버거 15초, 더블버거 24초

 

위 조건을 바탕으로 우리는 시뮬레이션 프로그램을 작성하여 다음과 같은 내용의 보고서를 제시하려고 합니다.

수용인원 (명)	안정적으로 고객을 수용할 확률 (%)
30	50
50	70
100	90
200	100

위에서 안정적으로 고객을 수용할 확률이 50%라는 것은 10회 시뮬레이션을 진행한 결과, 대기하는 고객 전부를 수용하는 것이 불가능한 상황이 5회, 즉 50%의 비율로 발생했다는 의미입니다.

---

실제 현상에 근접한 형태로 시뮬레이션을 하기 위해서는 고려해야 할 사항이 매우 많습니다. 그러나 큐가 시뮬레이션의 도구가 될 수 있음을 경험하는 것이 우리의 목적인 만큼, 그 목적에 부합하는 정도의 예제를 작성하고자 합니다. 다음은 시뮬레이션을 위한 몇 가지 조건을 정리한 것입니다.

• 점심시간은 1시간이고, 그동안 고객은 15초에 1명씩 주문을 하는 것으로 간주한다.
• 한 명의 고객은 하나의 버거만을 주문한다고 가정한다.
• 주문하는 메뉴에는 가중치를 두지 않는다. 모든 고객은 무작위로 메뉴를 선택한다.
• 햄버거를 만드는 사람은 1명이다. 그리고 동시에 둘 이상의 버거가 만들어지지 않는다.
• 본인이 주문한 햄버거의 제작이 시작되면 대기실에서 나온다.

 

고객이 주문하는 메뉴를 랜덤으로 정하기 위해 다음의 난수 생성 함수를 사용하겠습니다.

int rand(void);

난수 생성과 관련해서는 C언어 기본서에서 참조할 수 있기 때문에 위 함수에 대해 알고 있다고 간주합니다. 이어서 시뮬레이션 예제입니다.

//main.c 소스 파일로 저장
#include "LBQueue.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define CUS_COME_TERM 15    //고객의 주문 간격, 초 단위

#define CHE_BUR 0    //치즈버거 상수
#define BUL_BUR 1    //불고기버거 상수
#define DUB_BUR 2    //더블버거 상수

#define CHE_TERM 12    //치즈버거 제작 시간, 초 단위
#define BUL_TERM 15    //불고기버거 제작 시간, 초 단위
#define DUB_TERM 24    //더블버거 제작 시간, 초 단위

#define REPEAT 2000    //시뮬레이션 반복 횟수
#define SEAT 20        //대기실 수용 인원

int main(void)
{
	int makeProc;    //햄버거 제작 시간
	int wait;        //대기인원

	Queue que;
	QueueInit(&que);   

	srand((unsigned int)time(NULL));    //난수 생성을 위한 seed 입력, time(NULL)은 1970년 01월 01일 00시 00분 00초로부터 현재까지 걸린 시간, 초 단위

	int success = 0, fail = 0;

	int i;
	for (i = 0; i < REPEAT; i++)    //시뮬레이션 반복
	{
		makeProc = 0;    
		wait = 0;

		//아래 for문의 1회 회전은 1초의 시간 흐름을 의미함
		int sec;
		for (sec = 0; sec < 3600; sec++)
		{
			makeProc--;    //햄버거 제작 시간 카운트

			if (sec % CUS_COME_TERM == 0)
			{
				wait++;
				switch (rand() % 3)    //0 ~ 2 의 난수 생성
				{
				case CHE_BUR:
					Enqueue(&que, CHE_TERM);
					break;

				case BUL_BUR:
					Enqueue(&que, BUL_TERM);
					break;

				case DUB_BUR:
					Enqueue(&que, DUB_TERM);
					break;
				}
			}

			if (makeProc <= 0 && !QIsEmpty(&que))
			{
				makeProc = Dequeue(&que);    //햄버거 제작 시작
				wait--;
			}

			if (wait > SEAT) break;
		}

		(wait > SEAT) ? fail++ : success++;

		while (!QIsEmpty(&que))    //다음 시뮬레이션을 위해 큐 비우기
		{
			Dequeue(&que);
		}
	}

	printf("Simulation Report! \n");
	printf("Waiting room size : %d \n", SEAT);
	printf("Success : %d, fail : %d, Percentage : %d", success, fail, success * 100 / REPEAT);
	putchar('%');
	printf("\n");
	
	return 0;
}

/*
실행결과

Simulation Report!
Waiting room size : 20
Success : 45, fail : 1955, Percentage : 2%

*/

 

그다지 어려운 코드는 아니기 때문에 코드만 봐도 이해할 것으로 생각됩니다. 시뮬레이션 반복 횟수는 2000회로 했습니다. 대기 인원이 대기실 수용 인원보다 많아지면 fail, 그렇지 않고 시뮬레이션이 끝나면 success입니다.

 

처음 시뮬레이션은 대기실 수용인원을 20명으로 설정하고 수행했습니다. 그리고 결과는 안정적으로 손님들을 수용할 확률이 2%밖에 되지 않았습니다. 이에 수용인원을 30명으로 수정하고 다시 시뮬레이션을 수행했습니다.

/*
실행결과

Simulation Report!
Waiting room size : 30
Success : 1313, fail : 687, Percentage : 65%

*/

수용인원을 30명으로 수정하자 안정적으로 손님들을 수용할 확률이 65%로 증가했습니다. 다시 수용인원을 34명으로 증가시키고 시뮬레이션해보겠습니다.

/*
실행결과

Simulation Report!
Waiting room size : 34
Success : 1801, fail : 199, Percentage : 90%

*/

그러자 안정적으로 손님들을 수용할 확률이 90%가 되었습니다.