Assigned |
|
Due |
|
May 5: Correction |
In the sample output (line 3),
the right child of job 6, before it is removed, should be 4, not 5. |
This project is an exercise on priority queues and their implementation as binary heaps. It also gives you exposure to discrete event simulation. In this description, terms of “queue” and “heap” are used interchangeably.
A job server (e.g., a printer) continuously receives and processes arrived job requests one at a time. The server puts jobs arrived but not yet served in a queue according to jobs’ priorities determined by certain rules. In addition to simulating the proper order in which these jobs are served, we are also interested in the time each job stays in the system (waiting time plus service time), which requires simulation of time that is updated with the occurrences of events (e.g., arrival of a job, service to a job is completed, etc.). Specifics of this project are given below.
Requests
to
the server
The types of requests a user can submit
to the
server are listed below. The meaning of each type of request and its
parameters
are briefly explained.
The job submitted in the request will be inserted into the queue.
The server will remove the job from the queue if it is still there. It does nothing if the job is not in the queue.
The server will move the job up in the queue according to the modified priority. It does nothing if the job is not in the queue.
For this project, instead of writing a program to generate arrivals of requests, you are asked to read a sequence of requests of mixed types from an input file. You can assume that in this input file, 1) requests are listed in the order of their submission time stamps; and 2) requests of WithdrawJob and IncreasePrice will only be issued for jobs already submitted. However, it is possible that these jobs have been served and removed from the queue before these requests are made.
Job
priorities
Priorities among outstanding (submitted but not yet completed) jobs
are
determined as follows:
Otherwise, they will be served in the order determined by heap update procedure.
Simulating server's system time
Since all requests in the input file are
time stamped,
your program needs to know when each request should be read in and
processed.
For example, if the first two jobs can be served before the submission
time of
the third one, then the request for the third job should not be read
and
processed until the first two are processed. Also, you are required to
report
the time a job stays in the system, which starts at the time the job is
submitted and ends at the time its service is completed by he server.
Instead
of using a real clock, we simulate the system time as follows. Let T
be
the system time.
Program output
After completion of each job, print the following for this job
ID, size, total payment, time in system, and its left and
right
children right before it is removed.
Here, again,
total payment = size * final unitPrice; and
time in
system = T
- job submission time.
After all requests in the input file are processed, report the
following: among
all job that have been served
The job with shortest time in system
The job with longest time in system
The average time in system over all jobs.
/afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj5/341-Spring05-p5_questions.txt
These questions are worth 10% of the project grade.
The input file may look like this:
SubmitJob
1 150 4 0
SubmitJob 2
100
4 0
SubmitJob
3 100 5 0
SubmitJob
4
120 3 100
SubmitJob 5
20
2 100
SubmitJob
6 200 7 200
IncreasePrice 4 5
300
WithdrawJob 1 300
The output for this example input file should look like this:
PROJECT 5:
PRIORITY QUEUES
The following
jobs have been
processed
ID
SIZE
TOTAL TIME IN
LEFT
RIGHT
PAYMENT SYSTEM CHILD
CHILD
3
100
500
100 1
2
2
100 400
200 1
4
6
200 1400
200 1
4
4
120 960
420 5
NULL
5
20 40
440 NULL NULL
JOB 3 HAS THE
SHORTEST TIME
STAYING IN SYSTEM OF 100
JOB 5 HAS THE
LONGEST TIME
STAYING IN SYSTEM OF 440
THE AVERAGE TIME
JOBS
STAYING IN SYSTEM IS 272
Note:
1. Do not report jobs that have been withdrawn from the queue before been served. They should not be included when computing the average.
2. For average time in system, only print its integer part.
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