Data structures and algorithm
Bee_wake
assg-11.pdf
Assg 11: Priority Queues and Queue Applications
COSC 2336 Spring 2019
March 13, 2019
Dates:
Due: Sunday March 31, by Midnight
Objectives
� Extend queue ADT to add a priority queue type
� Use queue ADT for a job scheduling simulation
� Practice with manipulating linked list data structures
� Practice with inheritance and class abstractions
� Practice with operator overloading
� Practice using queue data types for applications and simulations
� Introduction to some concepts in scienti�c simulations an programming
Description
In this assignment, we will be building a simulation of a job scheduling and processing system. The purpose of the simulation is to be able to run simulations in order to compare their performance, when they use di�erent queuing disciplines in order to schedule and run jobs in the system as they arrive. We will only be building a simulator that will compare a basic queuing discipline (�rst-come-�rst-serve) with a priority queuing discipline. In the system being simulated, jobs will have a priority level assigned to them. It is more costly to keep high priority jobs waiting. Thus we will de�ne an execution cost of a job as
1
cost = priority×waitTime (1)
In this simulation, higher numbers will represent higher priority jobs. Thus in the formula to compute cost, if a high priority job ends up having a long wait time before it is executed and �nishes, then the cost will be high. This is not so much of an issue if a low priority task ends up waiting a long time, or if a high priority task is executed immediately without waiting.
In general, we want to run simulations of jobs arriving, and being man- aged, dispatched and run, using di�erent queuing disciplines. As already mentioned, we will only compare a basic �rst-come-�rst-serve queue with a priority queue, but the basic framework you will create and see in this assignment is useful for many kinds of simulation system problems.
In this assignment, you are going to be given quite a bit of starting code. We will be using the basic Queue data type that was developed in the videos for this weeks content about Queues ("Queue.hpp" and "Queue.cpp"). You will also be given �les called "JobSimulator.[hpp|cpp]" which contain de�- nitions already for a Job class, and for a JobSchedulerSimulator class. A Job class/object represents a single job being managed and run in a sim- ulation. The basic characteristics of a Job for our assignment is that it is created or arrives in a system at some startTime. The simulator will simu- late the creation/arrival of new jobs. New jobs are also randomly assigned a priority level and a serviceTime upon arrival (again by the simulator). The serviceTime is the amount of system time that the Job needs in or- der to complete its work, or in other words it is the amount of resources or time that the system will need to allocate to and be busy with in order to complete the work of the Job.
The JobSchedulerSimulator runs a simulation of jobs arriving, being put on a waiting jobQueue, and being dispatched and run when the system is ready to run the next Job. Di�erent types of queues will e�ect the perfor- mance of the system and how well it does in reducing the overall and average cost of running jobs on the system. The simulator will simulate time using discrete time steps, starting at time 1, 2, . . . up to the simulationTime that is speci�ed as one of the simulation parameters. Other parameters of a simulation, besides the type of queuing discipline to use, is the min and max priority range to randomly assign when new jobs arrive, and the min and max amount of serviceTime that newly created jobs will need from the system.
You basically have to perform two di�erent parts to complete the sim- ulator you have been given. You have to implement a PriorityQueue
2
class (derived from the given LQueue linked list based queue class), in or- der to have a PriorityQueue we can use for the simulator. And the main runSimulation() method has not been implemented in the JobSchedulerSimulator class, you will need to create it according to the description below.
For this assignment you need to perform the following tasks.
1. Create a PriorityQueue class and implement a new enqueue() method to implement a priority queuing discipline. For e�ciency, priority queues are often implemented using a heap, so that both insertion and removal of items can be done in O(log n) time. However, we are going to use a simple naive method and simply insert new items into a link list that we keep sorted by priority. Doing this means that the insertion (enqueue()) operation becomes O(log n), but since for a pri- ority queue we always want the next item with the highest priority for a dequeue(), dequeue() is still O(1) constant time, since we will keep items order by priority and the highest priority item in the queue should always be at the front of the list.
This may sound like a lot, but there is really not too much to do to get a basic priority queue working. You need to perform the following steps
(a) Create a new class called PriorityQueue that inherits (using pub- lic inheritance) and derives from the LQueue class. This class still needs to be a template class, as it needs to be able to handle queues of di�erent types of objects. I have set the member vari- ables of the LQueue class to be protected, which means that your PriorityQueue class methods will be able to access and refer to the queueFront and queueBack member variables. You should insert your class de�nition for your PriorityQueue at the end of the "Queue.hpp" �le.
The only method you need to implement/override is the enqueue() method. All other methods should work correctly using the LQueue() implementations you will inherit. But since you are overriding enqueue() you do need to put a new declaration for this function in your PriorityQueue class declaration, but this will be the only function or variable (re)de�ned in the PriorityQueue.
(b) Once you have the declaration working, you will need to create your implementation of the enqueue() method for the PriorityQueue. As we already mentioned, instead of always just inserting the new
3
item/node at the back of the queue, you instead need to some some extra work and insert the new node into the linked list at the proper position so that the link list is ordered by priority. You can assume that the objects inserted into a PriorityQueue are over- loaded so that boolean comparisons (like operator<, operator<=, operator>, etc.) are de�ned to order object by their priority. The Job class that you will be managing with your PriorityQueue has had this operators de�ned to order jobs by their priority level. The pseudo-code for the algorithm your enqueue() function needs to perform is as follow:
0. Create a new Node dynamically, and assign the
newItem as its item. You may need to set link
to NULL and don't forget to update the numitems
variable of the LQueue parent as well.
1. Case 1, if the queue is empty, then the new node
becomes both the queueFront and the queueBack.
You don't have to do anything else, because a
list of only 1 item is already sorted.
2. Case 2, if the priority of the newItem is bigger
than the priority of the queueFront, then simply
make the newNode the new queueFront (and don't
forget to link the newNode back to the old front
item).
3. Case 3, if the newNode priority is less than or
equal to the front node, then it is going to end
up somewhere in the middle (or end) of the
linked list. Here you need a loop to search for
the correct position. You need to keep following
links until the current node is greater or equal
in priority to the newNode, and the node it links
to is smaller priority.
a. Once you have found that position, you need
to link the newNode between the two nodes, in
the correct position to keep the list sorted.
4
b. You may or may not need to do something special
to detect if you are linking as the last node,
so it becomes the new queueBack. For the
priority queue, you don't need the queueBack
pointer anymore, since you aren't inserting on
the end, so you can safely ignore the queueBack
member variable for your priority queue. But
you do need to make sure if your newNode ends up
being the last node, that its link is properly
NULL terminated.
You should try and implement the cases in order, and uncomment out the individual tests of the PriorityQueue given one by one to test them.
(c) Once you have your PriorityQueue working, and it is passing all of the tests given for it, you should then try and implement the runSimulation() class method. This is a member of the JobSchedulerSimulator class. You need to add the function prototype for this function in the "JobSimulator.hpp" �le, and add the implementation of the function at the end of the "Job- Simulator.cpp" �le.
There are 2 examples of how this function should be called in the tests give to you. The runSimulation() method takes a Queue<Job>, a queue class derived from the Queue base class, that is parameterized to hold objects of type Job, as its �rst pa- rameter. The second parameter to the function is a simple string description of the simulation type/queue that will be run, for display purposes. You should assign the class member variable this value of the passed in description as one of the things you din in the runSimulation() method.
We already brie�y described the runSimulation() method. Here is the pseudo-code of what you need to implement in this method:
for time in range 1..simulanTime
do
// 1. process new job creation, use jobArrived()
// to check this
if job arrived
do
- generate a random priority
5
(using generateRandomPriority() )
- generate a random serviceTime
(generateRandomServiceTime() )
- create a new instance of a Job
- enqueue the job on the job queue
passed in to this function
done
// 2. dispatch jobs to run on system
if no job is running and job queue is not empty
do
- dequeue the next job from the job queue
- set remaining time for this job to its service time
done
// 3. If job is currently running, update remaining time
if job running
do
- decrement the jobs remaining time
// handle when job has finished here
if job is now finished
do
- update stats on number of jobs completed
- update totalWaitTime
- update totalCost
done
done
done
The order of execution of the 3 steps is important in the simula- tion. If no job is running at the start of the time step, it should be possible for a new job to enter at that time step, it be immedi- ately dispatched, and it executes for 1 simulated time step. Thus you have to check the arrival, dispatch and update in that order.
After you main loop simulating the system time steps, you may have to do some more things to calculate your �nal statistics, which is not shown. For example, when a job completes, you
6
should keep track of the number of jobs that have completed so far, and keep track of the total wait time and total cost. You need these sums so you can calculate the average wait time and the average cost after the simulation ends. These averages should be calculated only for the jobs that successfully completed be- fore the simulation ended. There is also a parameter named numJobsUnfinished in the simulator, which is the number of jobs still on the job queue when the simulation ends that you should �ll in as well.
In this assignment you will only be given 5 �les in total. The "assg- 11.cpp" �le contains tests of the PriorityQueue you are to create, and exam- ples of creating a JobSchedulerSimulator, and how your runSimulation() method should be called. In addition, as mentioned, there are the "Queue.[hpp|cpp]" �les, that you will modify to add the PriorityQueue class implementa- tion. And the �les "JobSimulator.[hpp|cpp]" contain both the Job class and the JobSchedulerSimulator class. You need to only add the single runSimulation() member method to the JobSchedulerSimulator class in these �les.
Here is an example of the output you should get if your code is passing all of the tests and is able to run the simulation. You may not get the exact same statistics for the runSimulation() output, as the simulation is generating random numbers, but you should see similar values.
--------------- testing basic Queue ----------------------------
<LQueue> basic test of the base LQueue using linked list
Front: 5 7 9 11 :Back
--------------- testing PriorityQueue<int> ----------------------
<PriorityQueue<int> Test case 1 insertion into empty priority queue
Front: 5 :Back
<PriorityQueue<int> Test case 2 new node is highest priority and
needs to go on front
Front: 10 5 :Back
<PriorityQueue<int> Test case new node is lowest priority and
7
ends up on back
Front: 10 5 2 :Back
<PriorityQueue<int> Test case new node is lowest priority and
ends up on back
Front: 10 5 2 1 :Back
<PriorityQueue<int> Test case 3 insertion in between
Front: 10 5 3 2 1 :Back
<PriorityQueue<int> Test case 3 insertion of equal valued priority
(can't see if correct or not with ints)
Front: 10 5 3 2 2 1 :Back
--------------- testing PriorityQueue<Job> ----------------------
<PriorityQueue<Job> Test case 1 insertion into empty priority queue
Front: [id: 1 priority: 5] :Back
<PriorityQueue<Job> Test case 2 new node is highest priority and
needs to go on front
Front: [id: 2 priority: 10] [id: 1 priority: 5] :Back
<PriorityQueue<Job> Test case new node is lowest priority and ends
up on back
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2] :Back
<PriorityQueue<Job> Test case new node is lowest priority and ends
up on back
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 3 priority: 2]
[id: 4 priority: 1] :Back
8
<PriorityQueue<Job> Test case 3 insertion in between
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]
[id: 3 priority: 2] [id: 4 priority: 1] :Back
<PriorityQueue<Job> Test case 3 insertion of equal valued
Front: [id: 2 priority: 10] [id: 1 priority: 5] [id: 5 priority: 3]
[id: 3 priority: 2] [id: 6 priority: 2] [id: 4 priority: 1] :Back
----------- testing jobSchedulerSimulator() --------------------
Job Scheduler Simulation Results
--------------------------------
Simulation Parameters
--------------------------
Description : Normal (non-prioirity based) Queueing discipline
Simulation Time : 10000
Job Arrival Probability : 0.1
Priority (min,max) : (1, 10)
Service Time (min,max) : (5, 15)
Simulation Results
--------------------------
Number of jobs started : 990
Number of jobs completed : 956
Number of jobs unfinished: 33
Total Wait Time : 165051
Total Cost : 906378
Average Wait Time : 172.6475
Average Cost : 948.0941
Job Scheduler Simulation Results
--------------------------------
Simulation Parameters
--------------------------
Description : Priority Queueing discipline
Simulation Time : 10000
9
Job Arrival Probability : 0.1
Priority (min,max) : (1, 10)
Service Time (min,max) : (5, 15)
Simulation Results
--------------------------
Number of jobs started : 990
Number of jobs completed : 956
Number of jobs unfinished: 34
Total Wait Time : 113251
Total Cost : 204155
Average Wait Time : 118.4634
Average Cost : 213.5513
Assignment Submission
A MyLeoOnline submission folder has been created for this assignment. You should attach and upload your completed "Queue.[hpp|cpp]" and "JobSim- ulator.[hpp|cpp]" source �les to the submission folder to complete this as- signment. You do not need to submit your "assg-11.cpp" �le with test. But please only submit the asked for source code �les, I do not need your build projects, executables, project �les, etc.
Requirements and Grading Rubrics
Program Execution, Output and Functional Requirements
1. Your program must compile, run and produce some sort of output to be graded. 0 if not satis�ed.
2. (50 pts.) PriorityQueue is implemented correctly.
� Correctly derived class from LQueue base class.
� Class is still a template class
� Correctly specify prototype to override enqueue() method of base class.
� enqueue() implementation works for the empty list case
� enqueue() works to insert node at front when it is highest priority
� enqueue() works to insert node in list in correct order by priority
10
� enqueue() works when inserting node with lowest priority at back of list
3. (50 pts.) runSimulation() function is implemented correctly.
� Correctly creating new jobs and assigning random priority and service time on Poisson random arrival.
� Correctly dispatching jobs from queue when no job is running
� Correctly simulating job running, keeping track of remaining
� Correctly update statistics when jobs �nish.
� All simulation steps and statistics look correctly calculated.
Program Style
Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.
1. Most importantly, make sure you �gure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from �les, and only 2 spaces used for indentation.
2. A function header must be present for member functions you de�ne. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.
3. You should have a document header for your class. The class header document should give a description of the class. Also you should doc- ument all private member variables that the class manages in the class document header.
4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is speci�c to a single operating system, such as the system("pause") which is Microsoft Windows speci�c.
11
