CMSC 341 Spring 2004
Project 2

Assigned	Monday, Feb 16, 2004
Due	11:59 pm on Sunday March 7, 2004
Update: 17 Feb 04	Fixed minor typo under Description - Job Class: The probability of no Job arrives is thus 1 - p1 - p2. Fixed minor typo under Job Arrival - job creation formula: if p1 < rn <= p1 + p2, create a Large Job
Update: 18 Feb 04	Due date for Project 2 is extended to Sunday, March 7.
Clarification: 3 March 04	1. A simulation will end only when all jobs entered the system before or at simuTime have been served (e.g., SQ is empty and all servers become idled). 2. Servers' idle time will conitue to cumulate until the simulation ends. 3. When a server is given a job, it alone serves this job to its completion. No other server is allowed to serve any part of this job at the same time; and the service shall not be interrupted or preempted when the system switches to dequeue-with-priority mode. Your code must following these clarifications.
Update: 3 March 04	Sample Output can be found here.

Objectives

The List ADT is a fundamental building block for other ADTs such as the stack and queue. The text describes singly-linked lists and provides an implementation. In this project you will learn and use a design technique known as "layering" to implement a ServiceQueue class on top of the author's list code. The ServiceQueue is very much like a queue except an additional dequeue operation, which, when called, removes items according to their priorities. Using one ADT to implement another is an important programming concept. The user of the new data structure does not have to know there's a LinkedList underneath.

You will also learn about event simulation in a service center application where jobs are created randomly and served when there are servers available.

Description

A service center is an abstraction of many real world applications such as those in bank branches, call centers, auto shops, and computer operating systems. A service center has a number of servers to perform services for jobs required by its customers. Jobs are served in the "first come first serve" basis, therefore, queues are an appropriate data structure to use for storing outstanding jobs (arrived yet to be served). However, when too many jobs are waiting on the queue, the center gives smaller jobs a higher priority.

Your main task is to simulate the behavior of such a service center to help determining how many servers to have so that it can ensure there are neither too few servers (causing jobs to wait a long time) nor too many servers (causing them to stand around waiting with no jobs to serve). You will run simulations to collect data, including the job wait time, server idle time, and queue length that categorize the behavior of a service center. The behavior is essentially determined by the job arrival and service rates. These and other simulation parameters are provided in the Simulation Parameter File whose path is provided via the command line. Simulation interval is 1 minute, simulation time can be realized by a simple loop: starting from 1, incrementing by 1 for each minute elapsed.

You are asked to define and implement two classes: Job and Server, and the template class ServiceQueue for storing outstanding Jobs. All Servers are stored in a vector. Details of these are described below.

Job Class:
There are two types of jobs for this service center: Small Job which can be served by a short service time (say 5 minute); and Large Job which takes longer time (say 50 minutes) to serve. It is assumed that in each simulation, service time for each type of Jobs is a constant. Both types of Jobs can be served by any of the servers in the center. Jobs will arrive at the Service Center at random intervals. At each minute during the simulation, the probabilities that a Small Job arrives and Large Job arrives, are p1 and p2, respectively. The probability of no Job arrives is thus 1 - p1 - p2 (See sections Simulation Parameter File, and Job Arrival below for more details).

Server Class:
Each Server needs to accumulate the total amount of idle time. If a Server is currently serving a Job, the remaining service time shall be decreasd by 1 with each minute elapsed. If it is not busy, it may be assigned an outstanding Job to serve. How to schedule servers when more than one is available is up to you.

You will have a vector of Servers. The size of the vector equals the number of Servers used for a simulation, given as a simulation parameter.

ServiceQueue
Outstanding Jobs are stored in the ServiceQueue. When a Job arrives, it will be inserted at the rear of the queue (enqueued). During the normal operation, Job at the front of the queue is removed (dequeued) when a Server is available. However, when the queue size >= swichPoint, the system switches to the policy of dequeue-with-priority. In this mode, the first Small Job on the queue is removed and given to an available Server for service. This requires implementing an iterator to access the queue in searching for the first Small Job. The system returns to the normal dequeue mode when the queue size is reduced to < switchPoint.

ServiceQueue class should be layered on top of the LinkedList template class. The author's code on LinkedList shall not be modified and not submitted as part of your submittals. There is no limit on the size of the queue. However, you want to have it not larger than the simulation time limit (simuTime) because at most one Job can be created for each minute. Public methods for ServiceQueue class should include

IsEmpty: checks if the queue is empty;
Enqueue: inserts a Job at the rear of the queue;
Dequeue: removes the Job from the front of the queue;
DequeuePr: removes the first Small Job from the queue (dequeue-with-priority);
Getsize: returns the current size of the queue.

You should implement a queue iterator class for scanning the queue and retrieving Jobs from the queue.

Simulation
You are required to run a number of simulations, each with a different set of simulation parameters. For each simulation, create a ServiceQueue and a vector of Servers. At the end of each simulation, report the results in a well formatted output. The report should start with the simulation parameters (echoing what is read from the Simulation Parameter File), followed by the following

The total number of Small Jobs served;
The total number of Large Jobs served;
The average wait time over all Small Jobs;
The average wait time over all Large Jobs;
The longest waiting time among all Jobs;
The maximum queue size during the simulation;
The average idle time over all Servers.

All these values should be integers, except those for average, which should be printed with 2 decimal digits. The wait time for a Job is the time interval from the time it arrives (when enqueued) to the time it is selected for service (when dequeued).

At each minute, the simulation does the following three tasks:

Task 1: Job Creation. Attempt to randomly create a Job according to the given Job arrival rate. If a Job is created, enqueue this Job.
Task 2: Job Service. Update each Server

If it is currently idle, increment the total idle time for that Server by 1;
If it is currently busy, decrement the remaining service time by 1, and if the remaining service time become 0, change the status to idle.

Task 3: Service Assignment. While the ServiceQueue is not empty and there are Server available

Remove a Job using either the normal dequeue method or the dequeue-with-priority method, according to current size of the queue;
Assign this Job to an available Server (one that is idle at the beginning of this minute), and update that Server.

Note:

Task 1 runs from minute 1 to the given simulation time limit since no new Job is allowed to enter the system when the time limit is reached.
Tasks 2 and 3 should be allowed to continue after the time limit as long as the queue is not empty so that all Jobs already entered the system can be served.
It may be more efficient to implement Tasks 2 and 3 in a single loop over the Server vector. Care must be taken to ensure they are done correctly. Also make sure not to create 1 minute idle time when the simulation begins (at time = 1). This can be done by simply initializing the idleTime to -1 for each Server.
At each iteration you also need to update other variables such as queue size, total numbers of Small Jobs and Large Job, and their wait times, etc.

The Command Line

Project 2 will be invoked with a command line that consists of a single argument -- the name of the Simulation Parameter File to read. As usual, you should check the validity of all command line arguments.

The Simulation Parameter File

Each line in the file consists of a sequence of 8 numbers in the following order, specifying the simulation parameters for one simulation:

seed: a value as the seed for random number generation, to be used for creating Jobs;
serverNo: number of servers;
p1: probability for Small Jobs arrival;
p2: probability for Large Jobs arrival;
smallService: service time for a Small Job;
largeService: service time for a Large Job;
switchPoint: the size of the queue that determines whether the operation should switch to dequeue-with -priority mode;
simuTime: the simulation time limit (beyond which no Job is allowed to enter).

p1 and p2 are double, seed is unsigned, and all others are int. You can assume that the format of the file is correct and the data in the file is the appropriate type.

Below is an example of a simulation parameter file.
12345 4 0.4 0.1 5 50 10 120

Job Arrival

Random Job arrival can be simulated by using pseudo random numbers according to its probability distribution p1 and p2 as follows:

generate a random number rn (between 0 and 1);
if rn <= p1, create a Small Job, if p1 < rn <= p1 + p2, create a Large Job, otherwise, no Job is created.

There are many functions for random number generation in the Standard Library. In this project you MUST use functions srand and rand. Function srand sets the seed for the random number generator rand. rand generates one random number r between 0 and RAND_MAX, each time when it is called. You can use the following procedure to generate rn:

Call srand(seed) only once at the beginning of each simulation, where seed is taken from the parameter file;
Call rand at each minute and convert the random number between 0 and 1 by rn = rand()/RAND_MAX.

Be sure to include <cstdlib>.

Your Tasks

Read and understand the author's code for his LinkedList class and his implementations. The author's code is found in Mr. Frey's directory

/afs/umbc.edu/users/d/e/dennis/pub/CMSC341

Define and implement Job and Server classes.
Define and implement ServiceQueue on top of author's LinkedList class.
Design and implement any C++ class you feel is necessary for this project, if any.
Write a program (Proj2.cpp) that models the simulation described above.
Write a makefile for this project. Any code supplied by the author should be referenced within the makefile.
Conduct the simulations and output the report.
Answer the questions posed in 341-Springl04-proj2_questions.txt. Copy the file
/afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj2/341-Spring04-p2_questions.txt
to your own directory and edit it to provide your answers to the questions. Don't forget to submit the edited file; it is 10% of this project's grade.

Program Requirements

Your code must follow all project guidelines established for this course. See the project organization and project policies web pages.
To be consistent with CMSC202, please follow the naming conventions found in 202 Coding Standards web page.
Your main program file must be named Proj2.cpp
Your executable must be named Proj2
You may use any of the author's code (LinkedList.H and LinkedList.C), but may not modify it.
Any C++ class you implement must include the "Big-4".
Your code must handle (try/throw/catch) any exceptions thrown by the author's code or by your own classes.

Files To Be Submitted

Submit any files which you have written -- source code and makefile. Your files MUST be named as listed below.

Proj2.cpp -- contains your main( )
Your makefile which must be named makefile or Makefile.
Header and implementation files for your classes.

Submit the files using the procedure given to you for your section of the course.
If your makefile is set up correctly, you should be able to execute the command make submit.

DO NOT submit author's LinkedList.H and LinkedList.C and any files that you didn't write. These files should be referenced by your makefile.

Submission Tools

There are a number of tools available to you to check on your submittal. It is your responsibility to ensure that the submittal is correct and will result in a successful compilation of your project. Do not wait till the last minute to submit your files. Give yourself enough time to check that your submittal is correct.

If you don't submit a project correctly, you will not get credit for it. Why throw away all that hard work you did to write the project? Check your submittals. Make sure they work. Do this before the due date.

Documentation for the submit program is on the web at http://www.gl.umbc.edu/submit/ . One of the tools provided by the submit program is
submitls. It lists the names of the files you have submitted.

Additionally, there are two programs for use only by CMSC-341 students (not part of the UCS submit program). They are in the directory
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341/ and are named submitmake and submitrun. You can use these programs to make or run your submitted projects.

The syntax is similar to that for submit:

submitmake <class> <project>

Example: submitmake cs341 Proj2

This makes the project, and shows you the report from the make utility. It cleans up the directory after making the project (removes .o and ii_files), but leaves the
executable in place.

submitrun <class> <project>

Example: submitrun cs341 Proj2

This runs the project, assuming there is an executable (i.e. submitmake was run successfully).

Grading and Academic Integrity

Your project will be tested using a variety of command lines, some of which will be invalid.
Your project will also be tested using a variety of command files which will test various conditions which your code should handle.

Project grading is described in the Project Policy handout.
Cheating in any form will not be tolerated. Please re-read the Project Policy handout for further details on honesty in doing projects for this course.

Remember, the due date is firm. Submittals made after midnight of the due date will not be accepted. Do not submit any files after that time.

CMSC 341 Spring 2004 Project 2