/* Simulation of the Pancake Manor example in CPSC 531 */ /* */ /* Warning! This is not fully working yet!!!! */ /* Slightly better than it was during class though. */ /* */ /* Written by Carey Williamson, University of Calgary */ /* */ /* Usage: cc -o pancakes pancakes.c -lm */ /* ./pancakes */ #include #include #include /* use man 3 log for the math functions */ /* Event types */ #define NULL_EVENT 0 #define ARRIVAL 1 #define SEATING 2 #define ORDERING 3 #define COOKING 4 #define EATING 5 #define PAYING 6 #define DEPARTURE 7 #define STOP 8 /* State of different entities */ #define IDLE 0 #define BUSY 1 #define TABLE_IDLE 0 /* not yet implemented */ #define TABLE_BUSY 1 /* not yet implemented */ #define HOST_IDLE 0 #define HOST_BUSY 1 #define SERVER_IDLE 0 #define SERVER_BUSY 1 #define COOK_IDLE 0 #define COOK_BUSY 1 #define CASHIER_IDLE 0 #define CASHIER_BUSY 1 /* seems buggy still */ /* Model parameters */ #define LAMBDA 0.2 /* Arrival rate of new customers */ #define HOST_RATE 0.5 /* Service rate for host/hostess */ #define SERVER_RATE 0.4 /* Service rate for waiter/waitress */ #define COOK_RATE 0.3 /* Service rate for cook */ #define EATING_RATE 0.1 /* Service rate for cook */ #define CASHIER_RATE 0.5 /* Service rate for cashier */ /* More model parameters */ #define MAX_CUSTOMERS 100 #define MAX_QUEUE 10 #define MAX_EVENTS 20 #define END_OF_TIME 1000.0 #define NUM_TABLES 4 /* not yet implemented */ #define MEAN_GROUP_SIZE 3 /* not yet implemented */ /* Debugging output */ /* #define DEBUG 1 */ /* #define DEBUG2 1 /* event list sorting */ /* #define DEBUG3 1 /* event list shifting */ /* #define DEBUG4 1 /* event list copying */ /* Event list global variables */ struct { int type; int idnum; float time; } eventlist[MAX_EVENTS]; int head, tail, events; float now; struct { int groupsize; float arrivaltime; float seatingtime; float orderingtime; float cookingtime; float eatingtime; float payingtime; float waitingtime; float departuretime; float sojourntime; } customerlist[MAX_CUSTOMERS]; int tables[NUM_TABLES]; /***********************************************************************/ /* RANDOM NUMBER GENERATION STUFF */ /***********************************************************************/ /* Parameters for random number generation. */ #define MAX_INT 2147483647 /* Maximum positive integer 2^31 - 1 */ /* Generate a random floating point value uniformly distributed in [0,1] */ float Uniform01() { float randnum; /* get a random positive integer from random() */ randnum = (float) 1.0 * random(); /* divide by max int to get something in 0..1 */ randnum = (float) randnum / (1.0 * MAX_INT); return( randnum ); } /* Generate a random floating point number from an exponential */ /* distribution with mean mu. */ float Exponential(mu) float mu; { float randnum, ans; randnum = Uniform01(); ans = -(mu) * log(randnum); return( ans ); } /***********************************************************************/ /* EVENT LIST MANAGEMENT STUFF */ /***********************************************************************/ void PrintEventList() { int i; #ifdef DEBUG printf(" Event list at time %8.6f currently has %d events: head %d tail %d\n", now, events, head, tail); #endif for( i = head; i <= tail; i++ ) { int who, what; float when; char whatchar; what = eventlist[i].type; who = eventlist[i].idnum; when = eventlist[i].time; if( what == ARRIVAL ) whatchar = 'A'; else if( what == SEATING ) whatchar = 'S'; else if( what == ORDERING ) whatchar = 'O'; else if( what == COOKING ) whatchar = 'C'; else if( what == EATING ) whatchar = 'E'; else if( what == PAYING ) whatchar = 'P'; else if( what == DEPARTURE ) whatchar = 'D'; else if( what == NULL_EVENT ) whatchar = 'N'; else if( what == STOP ) whatchar = 'X'; else whatchar = '?'; printf(" eventlist[%d]: %c, %d, %8.6f\n", i, whatchar, when, who); } } void ShiftEventList() { int i, j; #ifdef DEBUG3 printf(" Event list BEFORE shifting: \n"); PrintEventList(); #endif for( i = 0, j = head; i < events; i++, j++ ) { eventlist[i].type = eventlist[j].type; eventlist[i].idnum = eventlist[j].idnum; eventlist[i].time = eventlist[j].time; } head = 0; tail = events - 1; #ifdef DEBUG3 printf(" Event list AFTER shifting: \n"); PrintEventList(); #endif } void SortEventList() { int i, j, spot, index; float smallest; #ifdef DEBUG2 printf(" Event list BEFORE sorting: \n"); PrintEventList(); #endif for( i = 0; i < events; i++ ) { /* find the smallest timestamp */ smallest = eventlist[i].time; spot = i; for( j = i+1; j < events; j++ ) { if( eventlist[j].time < smallest ) { smallest = eventlist[j].time; spot = j; } } #ifdef DEBUG4 printf("Copying event from spot %d to position %d\n", spot, i); #endif /* copy that event to position i if needed */ if( i != spot ) { int temptype, tempidnum; float temptime; temptype = eventlist[i].type; tempidnum = eventlist[i].idnum; temptime = eventlist[i].time; eventlist[i].type = eventlist[spot].type; eventlist[i].idnum = eventlist[spot].idnum; eventlist[i].time = eventlist[spot].time; eventlist[spot].type = temptype; eventlist[spot].idnum = tempidnum; eventlist[spot].time = temptime; } } #ifdef DEBUG2 printf(" Event list AFTER sorting: \n"); PrintEventList(); #endif } /***********************************************************************/ /* MAIN PROGRAM */ /***********************************************************************/ int main() { int i, index, eventtype, who; int arrivals, departures, active; float when; int hoststate, serverstate, cookstate, cashierstate; int hostqsize, serverqsize, cookqsize, cashierqsize; int maxhostq, maxserverq, maxcookq, maxcashierq; float hostbusytime, hoststartbusy; float serverbusytime, serverstartbusy; float cookbusytime, cookstartbusy; float cashierbusytime, cashierstartbusy; /* Initialization */ hoststate = HOST_IDLE; serverstate = SERVER_IDLE; cookstate = COOK_IDLE; cashierstate = CASHIER_IDLE; hostqsize = 0; serverqsize = 0; cookqsize = 0; cashierqsize = 0; maxhostq = 0; maxserverq = 0; maxcookq = 0; maxcashierq = 0; active = 0; arrivals = 0; departures = 0; hostbusytime = 0.0; serverbusytime = 0.0; cookbusytime = 0.0; cashierbusytime = 0.0; now = 0.0; for( i = 0; i < MAX_EVENTS; i++ ) { eventlist[i].type = NULL_EVENT; eventlist[i].idnum = -1; eventlist[i].time = END_OF_TIME; } for( i = 0; i < NUM_TABLES; i++ ) { tables[i] = TABLE_IDLE; } /* Enqueue two initial seed events */ events = 0; index = 0; eventlist[index].type = ARRIVAL; eventlist[index].idnum = arrivals; eventlist[index].time = now + Exponential(1.0 / LAMBDA); events++; index++; eventlist[index].type = STOP; eventlist[index].idnum = -1; eventlist[index].time = END_OF_TIME; events++; head = 0; tail = index; index++; #ifdef DEBUG PrintEventList(); #endif /* Extract first event */ eventtype = eventlist[head].type; #ifdef DEBUG printf("Extracting event %d of type %d from head of event list\n", head, eventtype); #endif /* Main simulation loop */ while( eventtype != STOP ) { /* Extract relevant info about event */ who = eventlist[head].idnum; when = eventlist[head].time; /* Remove event */ eventlist[head].type = NULL_EVENT; eventlist[head].idnum = -1; eventlist[head].time = END_OF_TIME; head++; events--; /* Determine event type to handle */ if( eventtype == ARRIVAL ) { #ifdef DEBUG printf("Event is arrival of customer %d at time %8.6f\n", who, when); #endif now = when; customerlist[arrivals].arrivaltime = now; arrivals++; active++; /* Update system state */ if( hoststate == HOST_IDLE ) { hoststate = HOST_BUSY; hoststartbusy = now; #ifdef DEBUG printf("Host becomes BUSY at time %8.6f\n", now); #endif /* Schedule the seating event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = SEATING; eventlist[index].idnum = who; customerlist[who].seatingtime = Exponential(1.0 / HOST_RATE); when = now + customerlist[who].seatingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the seating of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } } else /* host is already BUSY */ { if( hostqsize < MAX_QUEUE ) { hostqsize++; #ifdef DEBUG printf("Arrival queue now has %d customers!\n", hostqsize); #endif if( hostqsize > maxhostq ) maxhostq = hostqsize; } else { fprintf(stderr, "Too many to fit in queue! Time %8.6f Customer %d qsize %d\n", now, who, hostqsize); exit(-1); } } /* Schedule next arrival event (if any) */ if( arrivals < MAX_CUSTOMERS ) { index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = ARRIVAL; eventlist[index].idnum = arrivals; when = now + Exponential(1.0 / LAMBDA); eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the arrival of customer %d at time %8.6f\n", arrivals, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is full!\n"); exit(-1); } } else printf("No more customers at this point!\n"); } else if( eventtype == SEATING ) { /* seat the customers; start ordering if server available */ /* Update system state */ if( serverstate == SERVER_IDLE ) { serverstate = SERVER_BUSY; serverstartbusy = now; #ifdef DEBUG printf("Server becomes BUSY at time %8.6f\n", now); #endif /* Schedule the ordering event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = ORDERING; eventlist[index].idnum = who; customerlist[who].orderingtime = Exponential(1.0 / SERVER_RATE); when = now + customerlist[who].orderingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the ordering of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } } else /* server is already BUSY */ { if( serverqsize < MAX_QUEUE ) { serverqsize++; #ifdef DEBUG printf("Server's queue now has %d customers!\n", serverqsize); #endif if( serverqsize > maxserverq ) maxserverq = serverqsize; } else { fprintf(stderr, "Too many to fit in server queue! Time %8.6f Customer %d qsize %d\n", now, who, serverqsize); exit(-1); } } /* See if anybody else is waiting at the door */ if( hostqsize > 0 ) { /* Find the next customer and schedule their seating */ who++; index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = SEATING; eventlist[index].idnum = who; customerlist[who].seatingtime = Exponential(1.0 / HOST_RATE); when = now + customerlist[who].seatingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Host staying busy! Next scheduled seating is customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is totally full!\n"); exit(-1); } hostqsize--; } else { hoststate = HOST_IDLE; hostbusytime += now - hoststartbusy; #ifdef DEBUG printf("Nobody else waiting. Host becoming IDLE at time %8.6f...\n", now); #endif } } else if( eventtype == ORDERING ) { /* Update system state */ if( cookstate == COOK_IDLE ) { cookstate = COOK_BUSY; cookstartbusy = now; #ifdef DEBUG printf("Cook becomes BUSY at time %8.6f\n", now); #endif /* Schedule the cooking event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = COOKING; eventlist[index].idnum = who; customerlist[who].cookingtime = Exponential(1.0 / COOK_RATE); when = now + customerlist[who].cookingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the cooking of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } } else /* cook is already BUSY */ { if( cookqsize < MAX_QUEUE ) { cookqsize++; #ifdef DEBUG printf("Cook's queue now has %d customers!\n", cookqsize); #endif if( cookqsize > maxcookq ) maxcookq = cookqsize; } else { fprintf(stderr, "Too many to fit in cooking queue! Time %8.6f Customer %d qsize %d\n", now, who, cookqsize); exit(-1); } } /* See if anybody else is waiting to order */ if( serverqsize > 0 ) { /* Find the next customer and schedule their ordering */ who++; index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = ORDERING; eventlist[index].idnum = who; customerlist[who].orderingtime = Exponential(1.0 / SERVER_RATE); when = now + customerlist[who].orderingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Server staying busy! Next scheduled ordering is customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is totally full!\n"); exit(-1); } serverqsize--; } else { serverstate = SERVER_IDLE; serverbusytime += now - serverstartbusy; #ifdef DEBUG printf("Nobody else waiting. Server becoming IDLE at time %8.6f...\n", now); #endif } } else if( eventtype == COOKING ) { /* Schedule the eating event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = EATING; eventlist[index].idnum = who; customerlist[who].eatingtime = Exponential(1.0 / EATING_RATE); when = now + customerlist[who].eatingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the eating of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } /* See if anybody else is waiting for the cookr */ if( cookqsize > 0 ) { /* Find the next customer and start cooking their order */ who++; index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = COOKING; eventlist[index].idnum = who; customerlist[who].cookingtime = Exponential(1.0 / COOK_RATE); when = now + customerlist[who].cookingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Cook staying busy! Next scheduled order to cook is customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is totally full!\n"); exit(-1); } cookqsize--; } else { cookstate = COOK_IDLE; cookbusytime += now - cookstartbusy; #ifdef DEBUG printf("Nobody else waiting. Cook becoming IDLE at time %8.6f...\n", now); #endif } } else if( eventtype == EATING ) { /* Schedule the paying event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = PAYING; eventlist[index].idnum = who; customerlist[who].payingtime = Exponential(1.0 / CASHIER_RATE); when = now + customerlist[who].payingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the paying of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } } else if( eventtype == PAYING ) { /* Update system state */ if( cashierstate == CASHIER_IDLE ) { cashierstate = CASHIER_BUSY; cashierstartbusy = now; #ifdef DEBUG printf("Cashier becomes BUSY at time %8.6f\n", now); #endif /* Schedule the departure event for this customer */ index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = DEPARTURE; eventlist[index].idnum = who; customerlist[who].waitingtime = Exponential(1.0 / SERVER_RATE); when = now + customerlist[who].waitingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Scheduled the departure of customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is already full!\n"); exit(-1); } } else /* cashier is already BUSY */ { if( cashierqsize < MAX_QUEUE ) { cashierqsize++; #ifdef DEBUG printf("Cashier's queue now has %d customers!\n", cashierqsize); #endif if( cashierqsize > maxcashierq ) maxcashierq = cashierqsize; } else { fprintf(stderr, "Too many to fit in cashier queue! Time %8.6f Customer %d qsize %d\n", now, who, cashierqsize); exit(-1); } } } else if( eventtype == DEPARTURE ) { #ifdef DEBUG printf("Event is departure of customer %d at time %8.6f\n", who, when); #endif now = when; customerlist[who].departuretime = now; customerlist[who].sojourntime = now - customerlist[who].arrivaltime; departures++; active--; } else { fprintf(stderr, "Unknown event type %d!!!\n", eventtype); exit(-1); } /* See if anybody else is waiting to pay */ if( cashierqsize > 0 ) { /* Find the next customer and let them pay */ who++; index = tail; index++; if( index < MAX_EVENTS ) { /* Create the event */ eventlist[index].type = PAYING; eventlist[index].idnum = who; customerlist[who].payingtime = Exponential(1.0 / CASHIER_RATE); when = now + customerlist[who].payingtime; eventlist[index].time = when; events++; tail++; #ifdef DEBUG printf("Cashier staying busy! Next scheduled paying is customer %d at time %8.6f\n", who, when); #endif /* Put it in the correct position */ if( head > 0 ) ShiftEventList(); SortEventList(); } else { printf("Yikes!! Event list is totally full!\n"); exit(-1); } cashierqsize--; } else { cashierstate = CASHIER_IDLE; cashierbusytime += now - cashierstartbusy; #ifdef DEBUG printf("Nobody else waiting. Cashier becoming IDLE at time %8.6f...\n", now); #endif } /* Extract front event */ eventtype = eventlist[head].type; #ifdef DEBUG printf("Extracting event %d of type %d from head of event list\n", head, eventtype); #endif } /* Record end time of stop event */ now = eventlist[head].time; if( hoststate == HOST_BUSY ) hostbusytime += now - hoststartbusy; if( serverstate == SERVER_BUSY ) serverbusytime += now - serverstartbusy; if( cookstate == COOK_BUSY ) cookbusytime += now - cookstartbusy; if( cashierstate == CASHIER_BUSY ) cashierbusytime += now - cashierstartbusy; /* Final output after STOP event is seen */ printf("\n"); printf("Pancake Manor Simulation: LAMBDA %3.2f MAX_QUEUE %d\n", LAMBDA, MAX_QUEUE); printf("Time: %8.6f Arrivals: %d Departures: %d In system: %d\n", now, arrivals, departures, active); printf("Cust Arr Seat Order Cook Eat Pay Wait Total Depart\n"); for( i = 0; i < departures; i++ ) { printf(" %d %5.1f %5.1f %5.1f %5.1f %5.1f %5.1f %5.1f %5.1f %5.1f\n", i, customerlist[i].arrivaltime, customerlist[i].seatingtime, customerlist[i].orderingtime, customerlist[i].cookingtime, customerlist[i].eatingtime, customerlist[i].payingtime, customerlist[i].waitingtime, customerlist[i].sojourntime, customerlist[i].departuretime); } printf("Host busy time: %8.6f Utilization: %8.6f\n", hostbusytime, hostbusytime/now); printf("Maximum host queue size observed: %d\n", maxhostq); printf("Server busy time: %8.6f Utilization: %8.6f\n", serverbusytime, serverbusytime/now); printf("Maximum server queue size observed: %d\n", maxserverq); printf("Cook busy time: %8.6f Utilization: %8.6f\n", cookbusytime, cookbusytime/now); printf("Maximum cook queue size observed: %d\n", maxcookq); printf("Cashier busy time: %8.6f Utilization: %8.6f <--- wrong!!!\n", cashierbusytime, cashierbusytime/now); printf("Maximum cashier queue size observed: %d\n", maxcashierq); }