[Data Structure] #3-4 큐를 이용한 Server가 하나인 은행 시뮬레이션

Queue를 이용한 은행 시뮬레이션 프로그램

 Queue를 공부하면서 시뮬레이션이 안나올리가 없다고 생각한 순간 나왔다. ㅎㄷㄷ. 산업공학과에서 굉장히 자주 하는 짓이다. 여기서는 Server가 1개라고 가정한다. 아마 이 말을 잘 이해하지 못하는 분이 계실텐데(왜냐하면 내가 그랬으니까 ㅜㅜ)... 간단하게 말해서 은행에 갔더니 업무를 처리하는 은행원이 1명밖에 없는 그런 상황이다. 이런 상황에서는 한 명의 고객의 업무가 모두 끝날때까지 나머지 고객은 무조건 기다려야 한다. Server가 하나인 것은 main에서 service_time 변수가 하나인 것으로 표현된다.

 또한 여기서는 Queue가 하나뿐이다. 즉, 은행에서 고객들은 오직 1줄로만 기다린다. 여러 줄이 아니다. 여러 줄이 되는 순간 Queue 또한 여러 개가 되어야 한다. 아래의 코드에서 보면 전역 변수로 Queue 구조체 하나가 선언된 것을 볼 수 있다.

 코드에 주석을 달아놨으니 참고하시길..

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define FALSE 0
#define TRUE 1
#define MAX_QUEUE_SIZE 100

typedef struct {
    int id; // 고객 고유 번호. 들어오는 순서대로 번호표를 받는다고 생각하면 된다.
    int arrival_time; // 고객 도착 시간
    int service_time; // 고객에게 걸리는 서비스 시간
} element;

typedef struct {
    element queue[MAX_QUEUE_SIZE];
    int front;
    int rear;
} QueueType;

QueueType q; // 전역 변수로 설정

void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init(QueueType *q){
    q->front = 0;
    q->rear = 0;
}

int is_empty(QueueType *q){
    return q->front == q->rear;
}

int is_full(QueueType *q){
    return (q->rear+1) % MAX_QUEUE_SIZE == q->front;
}

void enqueue(QueueType *q, element item){
    if (is_full(q)) error("q is full");
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

element dequeue(QueueType *q){
    if (is_empty(q)) error("q is empty");
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

element peek(QueueType *q){
    if (is_empty(q)) error("q is empty");
    return q->queue[q->front];
}

double q_random(){
    // 0 <= rand() <= maximum integer(=rand_max)
    // rand()함수가 낼 수 있는 최대값(RAND_MAX)로 나누었으므로
    // 0 <= return value <= 1이 된다
    return rand() / (double) RAND_MAX;
}

// variables for simulation : 시뮬레이션용 변수들
int duration = 10; // simulation time : 총 시뮬레이션 시간
double arrival_prob = 0.7; // probability of customer arrival : 고객 도착 확률
int max_serv_time = 5; // max service time per a customer : 최대 서비스 시간
int q_clock; // current simulation time

// result variables
int customers; // number of all customers
int served_customers; // number of serviced customers
int waited_time; // waiting time of all of customers

// 0.7의 확률로 고객 생산
int is_customer_arrived(){
    if (q_random() < arrival_prob) {
        return TRUE;
    }
    return FALSE;
}

void insert_customer(int arrival_time){
    element customer;
    customer.id = customers++;
    customer.arrival_time = arrival_time;
    // 서비스 시간 = 1,2,3,4,5 중에 하나가 선택된다
    customer.service_time = (int)(max_serv_time * q_random()) + 1;
    enqueue(&q, customer);
    printf("고객번호 [%d]이 %d분에 도착했습니다. 서비스 시간은 %d분입니다.",
           customer.id,
           customer.arrival_time,
           customer.service_time);
}

// 대기 중인 고객을 한명 꺼내서 서비스를 실행한다
int remove_customer(){
    element customer;
    int service_time;
    
    if (is_empty(&q)) return 0; // 기다리는 고객이 없다
    customer = dequeue(&q);
    service_time = customer.service_time - 1; // ?
    served_customers++;
    
    waited_time += q_clock - customer.arrival_time; // 현재시간 - 도착시간
    printf("고객번호 [%d]이 %d분에 서비스를 시작합니다. 대기시간은 %d분이었습니다.\n",
           customer.id, q_clock, q_clock-customer.arrival_time);
    
    return service_time;
}

void print_stat(){
    printf("서비스 받은 고객 수 = %d\n",served_customers);
    printf("전체 대기 시간 = %d분",waited_time);
    printf("1인당 평균 대기 시간 = %f분\n",(double)waited_time/served_customers);
    printf("서비스를 받지 못하고 대기 중인 고객 수 = %d\n",customers-served_customers);
}

int main(){
    int service_time = 0;
    q_clock = 0;
    
    while (q_clock < duration) {
        q_clock++;
        printf("현재 시각=%d\n",q_clock);
        if (is_customer_arrived())
            insert_customer(q_clock);
        if (service_time > 0) // server가 하나임을 의미한다
            service_time--;   // 한명의 고객이 모두 처리될 때까지 다른 고객을 받지 않는다
        else
            service_time = remove_customer();
    }
    
    print_stat();
    return 0;
}

산업공학도로서 참 부끄럽게도 main안에 있는 service_time이 왜 존재하는지 한참 생각했다. (그렇게 배워놓고는 ㅠㅠ) 맨 위에서도 설명했지만 server가 하나이기 때문이다!
오늘은 여기까지!