|
Project 3 (45 points) |
Programming
Assignment #3 Event Driven Simulation
Abstract
Write a C program that simulates the activity of customers in queues at a bank.
Outcomes
After successfully completing this assignment, you should be able to:
· Develop a C program that uses linked lists
· Write a program that simulates some real-world activity
· Use a random number generators in C
Before Starting
Read Chapters 6 K&R or Chapter 10 of D&D, both pertaining to structures.
Event-driven Simulations
An event-driven simulation is a computer program that mimics the behavior of people or objects in a system in response to events that occur at certain times. The program must maintain a data structure for each person or object (called an actor) and place it in a queue according to the time of its event. It then reads the queue in the order of the events and causes the actors to do certain things, such as join a different queue or leave the system.
In this program, you will simulate people arriving at a bank and joining one of the queues in front of one of the tellers. People arrive at random intervals. Each person waits in his/her selected queue until reaching the head of the queue. When a person reaches the head of the queue, the teller provides service for a random amount of time. After the service is completed, the person leaves the bank. The purpose of the simulation is to measure the average amount of time people spend between arriving at the bank and leaving the bank. Your simulation should compare the performance of a single queue serving all tellers versus separate queues for each teller.
Assume that when there is a separate queue for each teller, a newly arrived person joins the shortest queue (or selects randomly among the set of equally short queues) and stays in that queue until served. That is, no person leaves a queue without being served, and no person moves among queues.
Team or Individual Project
This project may be carried out either individually or in two-person teams. If you wish to work with a partner, both partners must inform the TAs that they are working together. You must do this by 11:59 PM on Tuesday, February 2.
Implementing your program
Your program should be called qSim. It needs to do several things:
· Get and interpret the program parameters from the command line.
· Generate an event struct for each person indicating his/her arrival time at the bank. Arrival times are determined from a random number generator and the input parameters of the simulation. Also generate an event struct for each idle teller, with a random idle time in the range 1-60 seconds. (Be sure that all constants are defined symbolically.)
· Place each struct in the event queue sorted according to the time of its event. That is, the event with the earliest time is at the head of the queue, and the event with the latest time is at the tail of the queue.
· Play out the simulation as follows: take the first event off the queue, advance a simulated clock to the time of that event, do the action required of that event (which may mean queuing something on another queue or queuing another event on the event queue). Continue until the event queue is empty.
· Print out the statistics gathered by the simulation.
For this assignment, you will need to play the simulation twice once for a bank with a single queue and multiple tellers and once for a bank with a separate queue for each teller. Draw some comparison about the average total time required for a person to be served at the bank under each queue regime.
Here are some of the actions that can occur when an event reaches the head of the event queue:
· If the event represents a newly arrived person at the bank, add that person onto the end of a teller queue (i.e., either the common queue, in the case of a single-queued bank or the end of the shortest teller queue).
· If the event represents the end of the idle time of a teller, gather statistics about teller idle time.
If there is no customer waiting in the relevant queue, put the idle teller back into the queue with an additional random idle time of 1-60 seconds.
If there is a customer is waiting, remove the customer from the teller queue, generate a random service time according to the input parameters of the program, and add an event to the event queue, sorted according to the time of completion of the service.
· If the event represents the completion of service by the teller, do two things:
(a) Collect information about the customer, in particular, how long has the customer been in the bank, from first arrival time to completion of teller service. Also collect statistics about teller service time.
(b) Check the relevant teller queue, and if it is not empty, remove the first customer from the teller queue as described above, generate a random service time, and place the teller back in the event queue according to the completion time of that service. If the relevant teller queue is empty, place the teller back in the event queue with a random idle time in the range 1-60 seconds.
Input
The command line of your program should be of the following form:
./qSim #customers #tellers simulationTime averageServiceTime <seed>
The numbers of customers and tellers should be integers, and the simulation and average service times should be floating point numbers in units of minutes. The seed is optional and indicates a fixed seed for starting the random number generator (see below) For example,
./qSim 100 4 60 2.3
should be interpreted to mean that 100 customers and four tellers should be simulated over a period of 60 simulated minutes. The service time for each teller is an average of 2.3 minutes. No random number seed is specified.
Random Number Generation
To generate random numbers, use the function rand(), which is described in §5.10 of Deitel & Deitel or pages 46 and 252 of Kernighan & Ritchie. The function rand() is a pseudo random number generator. That is, it generates a different number each time it is called, and those numbers look like they are random in the range 0 .. RAND_MAX. In reality, however, it can generate the exact same sequence of random numbers repeatedly, to make it possible for you to debug your program. To use rand(), you need to include <stdlib.h>.
Random number generators work by maintaining one or more internal counters and performing a contorted transformation on the most recent number generated to get a new one that appears to be unrelated to the previous one. The random sequence can be initialized by calling srand(seed) at the beginning of your program,[1] where seed is an unsigned integer value. If you did not specify a seed in the command line, use some number that is likely to be truly random, such as the microsecond value returned from gettimeofday().
To generate random arrival times, the following expression is suggested:
float arrTime = simulationTime * rand()/(float)RAND_MAX;
You should generate all of the arrivals at the beginning of the program and put them into the event queue in order of arrival time.
To generate random service times, the following is suggested:
float serviceTime = 2*averageServiceTime*rand()/(float)RAND_MAX;[2]
Queue Management
Remember that the definition of a queue in C is a linked list in which entries are added to the tail and removed from the head. Strictly speaking, the event queue of this simulation is not a queue in that sense, because elements are inserted into the queue in time order, not at the end. However, elements are only removed from the head of the queue. The program should maintain a simulated clock, which indicates the time of the most recent object removed from the head of the queue.
Elements in the event queue should be represented by a struct containing the following fields:
struct event {
event *next;
float eventTime; // fractions of simulated minutes
... //
other fields as necessary
};
This simulation also requires one or more other queues in which customers can wait. These represent the physical queues of people inside the bank. Each is a real queue, in the sense that customers are added to the tail and are removed from the head. Elements of these queues should be structs representing customer for example,
struct person {
person *next;
float arrivalTime; // original arrival time at the bank
... //
other fields as necessary
};
Output
After your simulation has completed for both types of queuing regimes, you should print out a summary with the following information:
· Total number of customers served and total time required to serve all customers
· Number of tellers and type of queuing (one per teller or common)
· Average (i.e., mean) amount of time a customer spent in the bank and the standard deviation
· Maximum wait time from the time a customer arrives to the time he/she is seen by a teller.
· Total amount of teller service time and total amount of teller idle time.
The information that you need to print should determine the statistics that you gather during the simulations.
Deliverables
You must provide the following:
· The .c files and .h file to implement your simulation.
· A makefile to build your program. The executable program must be called qSim.
· At least three different test cases that show the behavior of the bank under both queuing regimes. Show the command line and the output.
· A document called README.txt, README.pdf, or README.doc summarizing your program, how to run it, and detailing any problems that you had. Also, if you borrowed all or part of the algorithm for this assignment, be sure to cite your sources and explain in detail how it works.
From your CCC Linux shell, submit your C program using the following turnin command:
/cs/bin/turnin submit cs2303 PA3 <your
files> README
Programs submitted after 11:59 pm on due date (February 7) will be tagged as late, and will be subject to the late homework policy.
Grading
This assignment is worth forty-five (45) points. Your program must compile without errors in order to receive any credit. It is suggested that before your submit your program, compile it again on a CCC system to be sure that it does not blow up or contain surprising warnings.
· Correct compilation without warnings 2 points
· Correct makefile to build program and individual components and to clean up 3 points
· Correct use of random number generator and seed 5 points
· Correct management of event queue 5 points
· Correct management of teller queues 5 points
· Correct implementation of actions when elements reach the heads of their queues 5 points
· Satisfactory test cases 5 points
· Correct execution with graders test cases 5 points
· Satisfactory README file, including a discussion of the merits of common or per-teller queuing 5 points
· Satisfactory program organization into an understandable set of functions and modules (i.e., .c and .h files) and satisfactory use of symbolic constants 5 points (subjective).