3. (20 points) Phase 3: Write an application based on the MPQ to simulate the scheduling of computer processes (jobs) to run on a single CPU (see also Problem P-8.7, page 366 in the textbook).

(a) The simulation of CPU running is done by using a loop where one iteration corresponds to the unit of the CPU time called a time slice. The value of the loop index is the current CPU time, and it goes from 1 to a certain integer limit (say, the number of jobs to run). The CPU selects a job with the highest priority (see the denition of the highest priority below) and run it. (b) The jobs to run the CPU are read from a le called cpu-jobs.txt where each line represents a job. The format of each line consists of 3 integers: job ID, length n, priority p.

i. Job IDs are unique positive integers (they do not need to be consecutive numbers).

ii. Assume that the job length n is measured in time slices and is an integer between 1 and 10, inclusive.

iii. A job priority p is represented also by an integer between 20 (highest priority is negative 20) and 19 (lowest priority is 19), inclusive as well. Jobs are scheduled based on their priorities: highest priority jobs will be scheduled rst. Pay attention to the fact that the higher priority means lower numerical value (therefore we can use Minimum PQ). If two or more jobs have the same priority value, break ties by job IDs: a job with a lower ID is scheduled rst.

File input format:

job ID length priority

281 5 12

825 2 2

111 10 19

382 3 7

(c) For simplicity, we assume that jobs cannot be interrupted once a job is scheduled on the CPU, it runs for a number of time slices equal to its length.

(d) Your program should create an output le cpu-jobs-output.txt. For each time slice, print one line to this le containing job ID of the job currently running the CPU, its priority, and the remaining time to run (in time slices). With every loop iteration the length of the job running the CPU is decreased by 1. The format of the output line is as follows: Job [job ID here] with length n and priority p. For example: Job 382 with length 3 and priority -7 Job 382 with length 2 and priority -7 Job 382 with length 1 and priority -7 Job 825 with length 2 and priority 2 Job 825 with length 1 and priority 2 ...

(e) If there are no jobs to run, the program issues the output: no more jobs waiting, and stops.

Phase One: https://www.chegg.com/homework-help/questions-and-answers/objectives-implementation-minimum-priority-queue-mpq-adt-testing-mpq-operations-using-bina-q25269724

Phase Two: https://www.chegg.com/homework-help/questions-and-answers/2-20-points-phase-2-implement-minimum-priority-queue-adt-operations-removemin-isempty-inse-q25269740

Page 366:

366 Chapter8. eups and Priority Queues resulting data structure for various values of k, by inserting and removing a large numher of randomly generated keys into each data structure. P-8.2 Give a C++ implementation of a priority queue hased on an unsorted list. P 8.3 Develop a C++implementation of a priority queue that is based on a heap heap-surt algurilhm Conare ils running time P-8.5 Implement a heap-basod priority queue that supports the following addi- and supports the locator-based functions. with that of the standard heap-sort that uses an external beap. tional operation in lincar time: P-8.4 Implement the i-pla replaceComparatorfc): Replace the current comparator with c. After changing the comparator, the heap will need to he restructured. Hint: Utilize the bottom-up heap construction algorithm.) P-8.6 Write a program that can process a sequence of stock buy and sell orders us described in Exercise C-8. P8.7 One of the main applications of priority queues is in operating systems for scheduling jobs on a CPU. In this project you are to build a program that schodules simulated CPU jos. Your program should run in a loop. each iteration of which corresponds to a time slice for the CPU. Each job is assigned a prioriy, which is an inleger between-20 (highest priority) and 19 (lowest priority) inclusive. From among all jobs waiting to be processed in a time slice, the CPU must work on the job with highest priority. In this simulation, each job will also oe with a length value, which is an integer between 1 and 100, inclusive, indicating the number of time slices that are needed assume jobs cannot be interupted once it is scheduled on the CPU, a job runs for a number of time slices oqual to its length. Your simulalor must output the name of the job running on the CPU in each time slice and must process a sequence of commands, one per time slice, each of which is of the form "add jobnme with length n and priority"or "no new job this lice." to process this job. For simplicity, you may Chapter Notes Knuth's hook on sorting and searching [57) describes the motivation and history for the seloction-sor, insertion-sort, and heap-sort algorithm. The heap-sort algorithm is due to Williams [103], and the linear-time beap construction algorithm is due to Floyd [33]. Additional algorithms and analytes for heaps and heap-sort variatiocan be found in papers by Bentley [12], Carisson [20, Gonnet and Munro [381, McDiarmid and Reed 70, and SchalTer and Sedgewick 881. The design pattern of using location-aware entrics (also described in [39]), appears to be new 366 Chapter8. eups and Priority Queues resulting data structure for various values of k, by inserting and removing a large numher of randomly generated keys into each data structure. P-8.2 Give a C++ implementation of a priority queue hased on an unsorted list. P 8.3 Develop a C++implementation of a priority queue that is based on a heap heap-surt algurilhm Conare ils running time P-8.5 Implement a heap-basod priority queue that supports the following addi- and supports the locator-based functions. with that of the standard heap-sort that uses an external beap. tional operation in lincar time: P-8.4 Implement the i-pla replaceComparatorfc): Replace the current comparator with c. After changing the comparator, the heap will need to he restructured. Hint: Utilize the bottom-up heap construction algorithm.) P-8.6 Write a program that can process a sequence of stock buy and sell orders us described in Exercise C-8. P8.7 One of the main applications of priority queues is in operating systems for scheduling jobs on a CPU. In this project you are to build a program that schodules simulated CPU jos. Your program should run in a loop. each iteration of which corresponds to a time slice for the CPU. Each job is assigned a prioriy, which is an inleger between-20 (highest priority) and 19 (lowest priority) inclusive. From among all jobs waiting to be processed in a time slice, the CPU must work on the job with highest priority. In this simulation, each job will also oe with a length value, which is an integer between 1 and 100, inclusive, indicating the number of time slices that are needed assume jobs cannot be interupted once it is scheduled on the CPU, a job runs for a number of time slices oqual to its length. Your simulalor must output the name of the job running on the CPU in each time slice and must process a sequence of commands, one per time slice, each of which is of the form "add jobnme with length n and priority"or "no new job this lice." to process this job. For simplicity, you may Chapter Notes Knuth's hook on sorting and searching [57) describes the motivation and history for the seloction-sor, insertion-sort, and heap-sort algorithm. The heap-sort algorithm is due to Williams [103], and the linear-time beap construction algorithm is due to Floyd [33]. Additional algorithms and analytes for heaps and heap-sort variatiocan be found in papers by Bentley [12], Carisson [20, Gonnet and Munro [381, McDiarmid and Reed 70, and SchalTer and Sedgewick 881. The design pattern of using location-aware entrics (also described in [39]), appears to be new