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. |
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
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
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
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:
Note:
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>.
/afs/umbc.edu/users/d/e/dennis/pub/CMSC341
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
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.
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).
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.