CMSC 341 Spring 2005
Project 5

Assigned	Monday, May 02, 2005
Due	11:59 pm on Sunday May 15, 2005
May 5: Correction	In the sample output (line 3), the right child of job 6, before it is removed, should be 4, not 5.

Objectives

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.

Description

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.

SubmitJob(ID, size, unitPrice, time). A request to serve a job. All four parameters are integers. ID is the (unique) identification number of this job. The size of the job is measured by units of time the server takes to complete this job. The unitPrice gives the price the user (the requester) is to pay for each unit of service time for the job. If the job is completed by the server, the server shall receive a total payment of size * unitPrice. The last parameter (time) gives the time the request is submitted. This is also the time the job enters the system.

The job submitted in the request will be inserted into the queue.

WithdrawJob(ID, time). A request to withdraw the job with the given ID previously requested for service. The second parameter (time) gives the time the request is submitted.

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.

IncreasePrice(ID, amount, time). A request to increase the unit price for the job with given ID by the given amount. The second parameter (time) gives the time the request is submitted. As will be seen shortly, the user can use this request to increases the priority of a job it submitted before.

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:

jobs with higher unit price have higher priority;
among those with equal unit price, the ones with smaller size have higher priority.

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.

When the queue is empty, T is set to the submission time of the next request read from the input file. For example, at the beginning, if the first request is SubmitJob(123, 10, 5, 4), then T is set to 4. The queue may also becomes empty when there is a gap between the submission of two requests during which all jobs in the queue have been served.
At time T, the system reads in from the input file all requests whose submission time is less than or equal to T. For SubmitJob requests, the new jobs are inserted into the queue. For other types of requests, each is processed as soon as it is read in, possibly causing the heap to change.
When there is no request in the input file with submission time less than or equal to T, the first job in the queue (the one with the highest priority) is removed from the queue and considered served. T advances by the amount of the size of the job.

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.

Your Tasks

Modify the author's code (BinaryHeap.h and BinaryHeap.cpp) as you feel necessary for this project. The author's code can be found at /afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj5.
Write your main( ) that drives and controls the experiment.
Write any other classes or auxiliary code you feel are necessary for this project
Write a makefile for this project.
Answer the questions found in the file

/afs/umbc.edu/users/y/p/ypeng/pub/CMSC341/Proj5/341-Spring05-p5_questions.txt

These questions are worth 10% of the project grade.

Command Line and Input File

Project 5 will be invoked with a command line that consists of one argument - the name of an input file that contains a sequence of requests as defined earlier in this description. Note that the name of each request is case sensitive, and the parameters are all integers.

Your program should validate the command line, ensure that the specified file can be opened, then read and process each of the requests in the file.

Example Input File and Sample Out put

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.

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 2005 Project 5