보고서 #1(제출기한: 09/16) 문제 #1 교재에 제시된 아이스크림 가게 시뮬레이션 프로그램(프로그램 8.5, pp.328) 코드를 이해하고, 다음과 같이 수정하라. a. 프로그램에서는 3가지 이벤트, arrival, order, leave를 발생시키고, 이벤트 발생 시점이 빠른 순서대로 이벤트를 처리한다. 이를 위해서 이벤트를 최소 히프 트리로 구성한다. 프로그램에서는 이벤트 발생시에, arrival 이벤트를 먼저 5개 발생하고, 이러한 이벤트 처리과정에서 order, leave 이벤트만이 발생된다. 즉, 새로 들어오는 고객이 없다고 가정한다. 이는 현실적이지 못하다. 프로그램을 다음과 같이 수정하라: order, leave 이벤트가 처리되는 과정에도 arrival 이벤트가 발생되게 하라. b. 프로그램은 이벤트가 존재하지 않을 때까지 시뮬레이션을 수정한다. 그러나 arrival 이벤트가 계속 발생되면 프로그램은 무한정으로 실행될 수 있게 된다. 프로그램을 다음과 같이 수정하라: 시뮬레이션 수행 시간을 설정(가령 10시간)하고, 이러한 시간이 종료될 때까지 시뮬레이션이 진행되게 하라. c. 프로그램은 손님이 도착했을 때, 자리가 가능한 경우에만 주문 이벤트를 발생시키고, 그렇지 않으면 손님이 즉시 가게를 떠나버린다.고 가정한다. 다음과 같이 프로그램을 수정하라: 손님이 도착했을 때, 자리가 없으면 wait 이벤트를 발생시키고, 이를 히프 트리에 추가한다. 이때 중요한 것은 기다리는 사람이 먼저 서빙을 받을 수 있게 새로 도착하는 사람보다 우선 순위를 높게 해야 한다. 여러분은 시뮬레이션이 종료되었을 때, 손님이 대기하는 평균시간을 출력해야 한다.
Solution: 보고서 #1(1) #define SIM_TIME 100 Int current_t = 0; // current time int main() { HeapType heap; element e; while(t <= SIM_TIME) { // until the simulation time is expired // simTime은 설정된 모의실험 시간 // 난수를 발생시켜서 확률적으로 new arrival event 를 발생시키든지 다른 이벤트를 처리 if (new arrival event is chosen) { // new arrival event 처리 // arrival event를 생성하여 힢 트리에 삽입 e.type = ARRIVAL; // 이벤트 생성 current_t += random(6); // 현재 시간 변경 e.key = current_t; // 현재 시간에 기준하여 새로운 이벤트의 도착 시간 설정 e.number = 1+ random(4); insert_min_heap(&heap, event); } else if (!is_empty(heap)) { // 힙 트리에 포함된 이벤트 순서대로 처리 event <- delete_min_heap(heap); process_event(&heap, event); } return 0;
Solution: 보고서 #1 (2) process_event(HeapType *heap, element e) { element new_event; int tmp; switch(e.type) { case ARRIVAL: case WAIT: if (is_seat_available(e.number)) { // 자리가 있으면 new_event.type = ORDER; new_event.key = e.key + 1 + random(4); new_event.number = e.number; insert_min_heap(heap, event); } else { // 자리가 없으면 new_event.type = WAIT; tmp = e.key + α; // 현재 시간 변경: 적절한 α 값 설정이 중요 if (tmp > current_t) // 새로 들어온 사람 current_t = tmp; // 보다 대기자에 우선순위 부여: 현재 시간 변경 new_event.key = tmp; insert_min_heap(heap, new_event); } case ORDER: // 다른 이벤트 처리 ... new_event.type = LEAVE; new_event.key = e.key + 1 + random(10); … 힢 트리상에 이미 존재하는 arrival event를 고려하는가? 이 경우에 그러한 이벤트보다 먼저 처리되게 하려면?