COMP15 Fall 20XX
Due: Thursday, December 9, 11:00PM
Simulation is an important tool for engineering analysis. Many real-world systems can be modelled as a queueing system consisting of jobs, servers and queues. Jobs arrive into the system, receive service from one or more servers, and depart the system when finished. When all servers are busy, jobs await service in the queues. Queueing system behavior is simulated in order to measure the behavior of the system over a period of simulated time. Observations are analyzed and the structure of the system is changed to perform "what-if" experiments with the goal of improving customer service, reducing the number of servers, etc.
Simulation is controlled by a simple "engine" that generates new jobs, routes jobs to queues and servers, and removes completed jobs. These major simulated steps in queueing system behavior are represented as discrete events. An event has three essential characteristics:
The goal of this project is to develop a priority queue abstract datatype (ADT) to maintain the event list for a discrete event simulation engine.
The objectives for this project are:
Several classes are provided as a foundation for your program. The following files are provided:
makefile Makefile to build the programs event.h Class declaration for event/event list event.cpp Implementation of event/event list engine.cpp Simulation engine clerk.h Simulated clerk API (server) clerk.cpp Implementation of clerk customer.h Simulated customer API (job) customer.cpp Implementation of customer waiting_line.h Waiting line API (queue) waiting_line.cpp Implementation of waiting line stats.h Descriptive statistics API stats.cpp Implementation of statistics module rng.h Pseudo-random number generator API rng.cpp Implementation of random number generatorThe files are available in the directory /g/15/class/project9. You will need to copy these files to your own working directory and use them as a starting point for development.
You will need to complete the implementation of the Event and EventList classes in event.h and event.cpp. These classes implement the priority queue that maintains the event list for the simulation engine. The standard approach is to keep the events in order from the earliest scheduled event to the latest scheduled event. An informal specification of the event API is given below.
Here are some additional requirements to be satisfied:
The source module engine.cpp contains the simulation engine. It implements a simple queueing model consisting of bank customers, a single clerk (a teller) and a single waiting line. Customers arrive, wait in line when the clerk is busy, receive service from the clerk, and depart after being served. Descriptive statistics are tallied for customer waiting time (how long a customer waits in line) and transaction time (how long it takes for the clerk to provide service to a customer.)
Customers arrivals are independent and random, thus, an exponential distribution is used to generate arrival events. Transaction times are independent and random. An exponential distribution is used to generate service (transaction) times.
The engine keeps track of the number of generated events and the number of dispatched events (i.e., the number of events actually processed by the engine.) The number of dispatched events should only be slightly less than the number of generated events. If the difference is more than a few events, then the event list priority queue is losing events and has a bug.
The rules in the makefile produce two executables: eventtest and simtest. The program eventtest is a stand-alone test that performs a very quick check of the EventList API. The program simtest is the actual simulation program itself. It simulates the operation of the queueing system and displays some descriptive statistics about the behavior of the system.
Take a look at the rule for building eventtest and the test driver code at the end of event.cpp. The -DTESTING compile option causes the main function at the end of event.cpp to be compiled. It provides the test driver for eventtest. This is a simple way to implement a unit test for a specific module that is part of a larger system.
Use the provide system to submit your finished program:
provide comp15 a9 makefile event.h event.cpp engine.cpp ...The files to be submitted are:
makefile Makefile to build the programs event.h Class declaration for event/event list event.cpp Implementation of event/event list engine.cpp Simulation engine clerk.h Simulated clerk API (server) clerk.cpp Implementation of clerk customer.h Simulated customer API (job) customer.cpp Implementation of customer waiting_line.h Waiting line API (queue) waiting_line.cpp Implementation of waiting line stats.h Descriptive statistics API stats.cpp Implementation of statistics module rng.h Pseudo-random number generator API rng.cpp Implementation of random number generatorBe sure to build and test your program on comp15.cs.tufts.edu before submitting your work. This system is the target build and test platform for all course projects.
Here are additional requirements that will earn extra credit.
Function: Event Purpose: Constructor; Initialize a new event Parameters: None Returns: Nothing Function: Event Purpose: Constructor; Initialize a new event with the specified characteristics Parameters: what: Type of event to be created when: Time when the event will occur customer: Customer participating in the event Returns: Nothing Function: EventList Purpose: Constructor; Initialize event list to the empty state Parameters: None Returns: Nothing Function: isEmpty Purpose: Test for an empty event list Parameters: None Returns: True if the event list is empty; otherwise, false Function: print Purpose: Display the events in the event list Parameters: None Returns: Nothing Function: remove Purpose: Remove the earliest event from the event list and return a pointer to the event Parameters: None Returns: Pointer to the next event, now removed from the list Function: add Purpose: Create and add a new event to the event list Parameters: what: Kind of event when: Time when the event will happen customer: Pointer to customer participating in event Returns: Nothing
Copyright © 2004-2013 Paul J. Drongowski