COMP15 Project #9: Discrete event simulation

COMP 15 Project #9: Discrete event simulation

COMP15 Fall 20XX
Due: Thursday, December 9, 11:00PM

Overview

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:

When: The simulated time when the event occurs.
What: The action to perform when the event occurs.
Who: The job (or server) that participates in the event.

The engine generates and schedules future simulated events. Future events are kept by an event list. When the engine is ready for another event, it removes the earliest event from the event list, sets simulated time to the time of the event, and then processes the event. In this way, the simulation makes progress and simulated time is advanced in discrete steps.

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.

Objectives

The objectives for this project are:

To construct a priority queue abstract datatype.
To apply the priority queue abstract datatype to maintain an event list within a discrete event simulation system.
To study a discrete event simulation system in action.

The program components can be modified and reused to study the behavior of other queueing system models.

What needs to be done

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 generator

The 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:

You must use the provided makefile to build your solution.
You should thoroughly and systematically test the program.

Add comments to the source code to describe your approach and solution. Don't forget to fill out any header comments with your name, section and e-mail address.

A little bit about the model

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.

Executables and a quick smoketest

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.

Submitting your work

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 generator

Be 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.

Extra credit

Here are additional requirements that will earn extra credit.

Implement the priority queue with a heap instead of an ordered linked list.
Collect and display descriptive statistics on the length of the waiting line (queue length.)

As usual, all extra credit requirements are above and beyond the call of duty!

Informal specification: EventList API

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