ADT

Assignment 10: Priority Queues and Queue Applications

COSC 2336: Data Structures and Algorithms

Fall 2020

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 scientific 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 different 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 (first-come-first-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 define an execution cost of a job as

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 finishes, 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 managed, dispatched and run, using different queuing disciplines. As already mentioned, we will only compare a basic first-come-first-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 files called “JobSimulator.[hpp|cpp]” which contain definitions already for a Job class, and for a JobSchedulerSimulator class. A Job class/object represents a single job being managed and run in a simulation. 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 simulate 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 order 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. Different types of queues will effect the performance 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

1

specified 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 different parts to complete the simulator you have been given. You have to implement a PriorityQueue class (derived from the given LQueue linked list based queue class), in order 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.

NOTE You are to use the Queue ADT abstraction give to you for this assignment. If you are familiar with STL queue adapter containers, you are not to use them for this assignment. Part of the assignment is to look over and learn the Stack ADT implementation we give you here based on our textbook Stack examples.

Setup For this assignment you will be given the following files:

File Name Description assg10-tests.cpp Unit tests for the member functions and queue

functions you are to write. JobSimulator.hpp Header file for a JobSimulator class that uses

queues and priority queues to simulate processing jobs from queues.

JobSimulator.cpp Implementation file, the implementation of the runSimulation() function you are to complete goes here in this file.

Queue.hpp Header file defining a Queue ADT for use in implementing the functions for this assignment.

Queue.cpp Implementation file for the Queue ADT template class.

Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class.

The general approach you should take for this assignment, and all assignment is:

1. Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing.

2. For this project, start by uncommenting the first TEST_CASE in the assg10-tests.cpp file. These are the unit tests to test the functionality of your PriorityQueue enqueue() function, the class and overridden member function you are to implement.

3. Add the PriorityQueue class to the Queue.hpp header file. The class should inherit from LQueue and override the enqueue() method as described in more detail below.

4. Add a stub for your enqueue() member function to the assg07-stackfun.cpp implementation file. You could start by doing nothing, or by copying the code of the enqueue() function from the LQueue class.

5. Your code should compile and run now. Make sure after adding the class and your stub method your code compiles and runs. However, your unit tests will be failing initially.

6. Incrementally implement the functionality of your enqueue() member function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach.

7. Once you have the enqueue() member function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some functions use previous ones in this assignment, so do them in the order given for you in the tasks below.

2

Tasks You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment:

1. Create a PriorityQueue class and implement a new enqueue() method to implement a priority queuing discipline. For efficiency, 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(n), but since for a priority 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 ordered 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

1. Create a new class called PriorityQueue that inherits (using public 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 different types of objects. I have set the member variables 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 definition for your PriorityQueue at the end of the “Queue.hpp” file.

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)defined in the PriorityQueue.

2. 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 item/node at the back of the queue, you instead need to do some some extra work and insert the new node into the linked list at the proper position so that the linked list is ordered by priority. You can assume that the objects inserted into a PriorityQueue are overloaded so that boolean comparisons (like operator<, operator<=, operator>, etc.) are defined to order object by their priority. The Job class that you will be managing with your PriorityQueue has had these operators defined 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

3

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.

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.

3. This task is for 25 points of extra credit. It is not required, but if you have time and would like a chance to make up some missed points you can attempt.

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” file, and add the implementation of the function at the end of the “JobSimulator.cpp” file.

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 first parameter. 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 briefly 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 then

- generate a random priority (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 endif

// 2. dispatch jobs to run on system if no job is running and job queue is not empty then

- dequeue the next job from the job queue - set remaining time for this job to its service time

endif

4

// 3. If job is currently running, update remaining time if job running then

- decrement the jobs remaining time

// handle when job has finished here if job is now finished then

- update stats on number of jobs completed - update totalWaitTime - update totalCost

endif endif

done

The order of execution of the 3 steps is important in the simulation. 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 immediately dispatched, and it executes for 1 simulated time step. Thus you have to check the arrival, dispatch and update in that order.

After your main loop simulating the system time steps, you may have to do some more things to calculate your final statistics, which is not shown. For example, when a job completes, you 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 before 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 fill in as well.

Example Output Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output.

$ ./test =============================================================================== All tests passed (251 assertions in 4 test cases)

$ ./test -s

------------------------------------------------------------------------------- test is a Catch v2.7.2 host application. Run with -? for options

------------------------------------------------------------------------------- <basic Queue> test basic Queue functionality ------------------------------------------------------------------------------- assg10-tests.cpp:30 ...............................................................................

assg10-tests.cpp:38: PASSED: CHECK( ilq.isEmpty() )

5

with expansion: true

... output snipped ...

=============================================================================== All tests passed (251 assertions in 4 test cases)

If you attempt the extra credit, an example of testing your runSimulation() method is given in the assg10-main.cpp file. Uncomment that example, and use the debug target to test calling and running your function. Example output for how your results should look if you implement the function correctly should look like this:

$ ./debug Job Scheduler Simulation Results -------------------------------- Simulation Parameters -------------------------- Description : Normal (non-priority 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: 34 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 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

6

Assignment Submission A MyLeoOnline submission folder has been created for this assignment. There is a target named submit that will create a tared and gziped file named assg02.tar.gz. You should do a make submit when finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment.

$ make submit tar cvfz assg10.tar.gz assg10-tests.cpp assg10-main.cpp

Queue.hpp Queue.cpp JobSimulator.hpp JobSimulator.cpp assg10-tests.cpp assg10-main.cpp Queue.hpp Queue.cpp JobSimulator.hpp JobSimulator.cpp

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 satisfied. 2. (100 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 • enqueue() works when inserting node with lowest priority at back of list

3. (25 bouns 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 finish. • 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 figure 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 files, and only 2 spaces used for indentation.

2. A function header must be present for member functions you define. 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 document 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 specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.

7