Monday, Feb 16, 2004
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.|
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.
3 March 04
|Sample Output can be found here.|
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.
A service center is an abstraction of many real
applications such as those in bank branches, call centers, auto shops,
computer operating systems. A service center has a number of servers to
perform services for jobs required by its customers. Jobs are served in
"first come first serve" basis, therefore, queues are an appropriate
data structure to use for storing outstanding jobs (arrived yet to be
However, when too many jobs are waiting on the queue, the center gives
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.
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).
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.
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
You should implement a queue iterator class for scanning the queue and retrieving Jobs from the queue.
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
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:
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.
Each line in the file consists of a sequence of 8 numbers in the following order, specifying the simulation parameters for one simulation:
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
Random Job arrival can be simulated by using pseudo random numbers according to its probability distribution p1 and p2 as follows:
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:
Be sure to include <cstdlib>.
Submit any files which you have written -- source code and makefile. Your files MUST be named as listed below.
Submit the files using the procedure given to you for your section
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.
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/
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
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
cleans up the directory after making the project (removes .o and
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).
Your project will be tested using a variety of
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
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.