Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

In JAVA, please code the following non-preemptive priority scheduler. 3 java classes and 1 interface is provided after the information below, ONLY singlecorescheduler.java WILL BE

In JAVA, please code the following non-preemptive priority scheduler.

3 java classes and 1 interface is provided after the information below, ONLY singlecorescheduler.java WILL BE MODIFIED.

CPU scheduling is the basis of multiprogramming. Whenever a computer CPU becomes idle, the operating system must select a process in the ready queue to be executed. One application of priority queues in operating systems is scheduling jobs on a CPU. In this project, you will write a program that schedules simulated CPU jobs on a single-core processor. Your program should run in a loop, each iteration of which corresponds to a time slice, one CPU cycle. Each job is assigned a priority, which is a random integer 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 a job with the highest priority. When two jobs have the same priority the one created earliest will be processed. In this simulation each job comes with a length value, which is a random integer between 1 and 100, inclusive, indicating the number of time slices that are needed to complete this job. For simplicity, we will assume that the CPU is non-preemptive; that is, once a job is scheduled on the CPU, a job runs for a number of time slices equal to its length without being interrupted. Also, each process will have a process identification number 1 ...n, where n is the number of simulated processes created.

Modes of Operations of the Simulator

The simulator runs in two modes: random, denoted by the command line argument -r or -R, or file, denoted by the command line argument -f or -F. In either mode, the simulator runs with three command line arguments. In either mode, the first command argument is a positive integer representing the number of CPU cycles for the simulation. In random mode the remaining command line arguments are the -r or -R flag followed a positive real number less than or equal to 1.0 representing the probability that a process is created during a CPU cycle. In file mode the remaining command line arguments are the -f or -F flag followed by the file name of the file containing information about the simulated jobs.

Activities During a Cycle in Pseudocode:

A. if (readyq is empty)

print idle CPU message

else if (readyQ head process is not running)

execute the head process

endif

if (readyQ head process is finished exeuting)

terminate the process print process termination message

else

print process running message

endif

endif

B. if (process is created) add the process to the readyQ

print process created message

else

print no process created message

endif

First, you will implement a priority queue ADT. Then you will use the ADT in writing a simple CPU scheduling simulator. At time zero the ready queue is empty. As described above, to run the simulator in random mode you will enter as a third command line argument p, a value between 0.01 and 1.00 inclusive. Your application will generate a random probability value q between 0 and 1 and for q p a simulated job will be created. You will then set the relevant instance fields of the simulated jobs with appropriate values. Each process control block also has additional fields to facilitate your analysis: A PCB has an arrived field, the time slice during which the process was created, start, the time slice when the process begins running, wait, the length of time from the process creation to when it begins running, and running, which is 0 if the process is waiting and 1 if the process is executing. Similarly, to run the simulator in file mode you will enter as a third command line argument representing the name of a text file containing information about the simulated jobs. Each line of this file will contain four integers. The first integer is the process identification number. The second number is an integer in [19,20], the priority value of this process. The smaller this number, the higher the priority. The third number is an integer in [1, c], where c is the number of cycles that the simulator will run. The last number is a positive integer that represents the number of cycles required to execute the process. These values are used to set the relevant fields of the simulated jobs. In either mode, a simplifying assumption is that only one simulated job may be created during a cycle.

Your application should trace these activities during each time slice:

1. *** Cycle #: c *** at the beginning of each cycle.

2. If the ready queue is empty, the message The CPU is idle should be displayed.

3. Whenever a process is finished executing, the message Process # pidhas just terminated should be displayed.

4. If a process is still executing, the message Process # pid is executing.should be displayed.

5. Whenever a new process is created the message Adding job with pid # x and priority p and length t. should be displayed.

6. If no new process is created during a cycle, the message No new job this cycle. should be displayed.

At the end of the simulation, your program should also display the average throughput, number of processes completed per CPU cycle. It should also display the average wait time per process. The wait time of a process is the number of cycles from its creation to when it begins executing.

To run your simulation for 1000 time slices (cycles) where the probability that a new process is created during each cycle is 0.2, your program will be executed with these values as command line tokens. Be sure to seed the random number generator using time of day. Do so at the beginning of the main. I have also provided a sample input file, simulatedjobs.txt and its corresponding output. When you run the simulator in file mode using this file, the simulator should display the output shown in simulatedjobsoutput.txton the screen. See starter code that I have provided for additional details. Modify the code only where indicated.

----------STARTER CODE----------

singlecorescheduler.java

package singlecorescheduler;

/** * A application to simulate a non-preemptive scheduler for a single-core CPU * using a heap-based implementation of a priority queue * @see Heap.java, PCB.java * File:SingleCoreScheduler.java */

import java.io.FileReader; import java.io.IOException; import java.util.Comparator; import java.util.Random; import java.util.Scanner;

public class SingleCoreScheduler { /** * Single-core processor with non-preemptive scheduling simulator * @param args an array of strings containing command line arguments * args[0] - number of cyles to run the simulation * args[1] - the mode: -r or -R for random mode and -f or -F for file mode * args[2] - if the mode is random, this entry contains the probability that * a process is created per cycle and if the simulator is running in * file mode, this entry contains the name of the file containing the * the simulated jobs. In file mode, each line of the input file is * in this format: *

} }

Heap.java

package singlecorescheduler;

import java.util.ArrayList;

import java.util.Comparator;

/**

* This class models an array-list-based min binary heap that implements the

* HeapAPI interface. The array holds objects that implement the

* parameterized Comparable interface. *

* @param the heap element type.

* @since 99-99-9999 *

*/

public class Heap> implements HeapAPI {

/**

* A complete tree stored in an array list representing this

* binary heap

*/

private ArrayList tree;

/**

* A comparator lambda function that compares two elements of this

* heap when rebuilding it; cmp.compare(x,y) gives 1. negative when x less than y

* 2. positive when x greater than y 3. 0 when x equal y

*/

private Comparator cmp;

/**

* Constructs an empty heap using the compareTo method of its data type as the

* comparator

*/

public Heap() {

tree = new ArrayList();

cmp = (object1, object2) -> object1.compareTo(object2);

}

/** * A parameterized constructor that uses an externally defined comparator

* * @param fn - a trichotomous integer value comparator function

*/

public Heap(Comparator fn) {

// implement this method

tree = new ArrayList<>();

fn = cmp;

}

@Override

public boolean isEmpty() {

return tree.isEmpty();

}

@Override

public void insert(E obj) {

tree.add(obj);

int place = size() - 1;

int parent = (place - 1) / 2;

while (parent >= 0 && tree.get(place).compareTo(tree.get(parent)) > 0) {

swap(place, parent);

place = parent;

parent = (place - 1) / 2;

}

}

@Override

public E remove() throws HeapException {

if (isEmpty())

throw new HeapException("Heap is empty");

E temp = tree.get(0);

tree.set(0, tree.get(size() - 1));

tree.remove(size() - 1);

rebuild(0, size());

return temp;

}

@Override

public E peek() throws HeapException {

if (isEmpty())

throw new HeapException("Heap is empty");

return tree.get(0);

}

@Override

public int size() {

return tree.size();

}

/**

* Swaps a parent and child elements of this heap at the specified indices

*

* @param place

* an index of the child element on this heap

* @param parent

* an index of the parent element on this heap

*/

private void swap(int place, int parent) {

E temp = tree.get(parent);

tree.set(parent, tree.get(place));

tree.set(place, temp);

}

/**

* Rebuilds the heap to ensure that the heap property of the tree is

* preserved.

*

* @param root

* the root index of the subtree to be rebuilt

* @param eSize

* the size of this tree

*/

private void rebuild(int root, int eSize) {

if (root > 1) {

int child = 2 * root + 1;

if (2 * root + 2 < eSize - 1) {

if (tree.get(child + 1).compareTo(tree.get(child)) > 0) {

child = child + 1;

}

}

if (tree.get(root).compareTo(tree.get(child)) < 0) {

swap(root, child);

rebuild(child, eSize);

}

}

}

}

HeapAPI.java (interface)-- DO NOT MODIFY THIS FILE!

package singlecorescheduler;

/** * This class reports Heap exceptions. * Note: DO NOT MODIFY THIS FILE */

class HeapException extends Exception { /** * Creates a new instance of HeapException without detail * message. */ public HeapException() { }

/** * Constructs an instance of HeapException with the specified * detail message. * @param msg the detail message. */ public HeapException(String msg) { super(msg); } }

/** * Describes the basic operations of a heap * @author Duncan * @param * @since 99-99-9999 */ public interface HeapAPI> { /** * Determine whether the Heap is empty. * @return this method returns true if the heap is empty; * otherwise, it returns false if the heap contains at least one item. */ boolean isEmpty();

/** * Inserts an item into the Heap. * @param item the value to be inserted. */ void insert(E item);

/** * An exception is generated if this method is invoked * by an empty heap. The maximum/minimum value is removed * from the heap if the heap is not empty and its effective * size is reduced by 1. * @return the maximum (in the case of a maxheap) or the * minimum (in the case of a minheap) on the heap. * @throws HeapException when the heap is empty */ E remove() throws HeapException;

/** * An exception is generated if this method is invoked * by an empty heap * @return the maximum (in the case of a maxheap) or the * minimum (in the case of a minheap) on the heap. * @throws HeapException when the heap is empty */ E peek() throws HeapException;

/** * Gives the size of this heap * @return the size of the heap; the effective size of the * heap. */ int size(); }

PCB.java -- DO NOT MODIFY THIS FILE!

package singlecorescheduler;

import java.util.logging.Level; import java.util.logging.Logger;

/** * Models a process control block. * Note: DO NOT MODIFY THIS FILE */ public class PCB implements Comparable {

/** * the process ID */ private int pid; /** * the priority value of this process */ final private int priority; /** * running status */ private int running; /** * cycle during which this process was created */ private int arrived; /** * length of time this process will take to execute */ private int length; /** * cycle during which this process begins executing */ private int start; /** * how long the process waits before it begins executing */ private int wait; /** * Creates a simulated job with default values for its parameters. */ public PCB() { priority = 20; running = 0; arrived = 0; length = 0; } /** * Creates a simulated job with the specified parameters. * @param iD the process id * @param pVal the priority value * @param run the running status * @param arr the arrival time * @param len the number of cycles this process takes to execute */ public PCB(int iD, int pVal, int run, int arr, int len) { pid = iD; priority = pVal; running = run; arrived = arr; length = len; } /** * Gives the ID of this job. * @return the process ID */ public int getPid() { return pid; } /** * Gives the priority value of this process. * @return the priority value of this process */ public int getPriority() { return priority; }

/** * Indicates whether this process is executing.. * @return the execution status of this process */ public boolean isExecuting() { return running == 1; } /** * Sets the running status of this job. */ public void execute() { running = 1; } /** * Gives the cycle during which this process was creates * @return the cycle during which this process was created. */ public int getArrival() { return arrived; } /** * Gives the number of cycles required to execute this process. * @return the number of cycles required to execute this process */ public int getLength() { return length; } /** * Gives the cycle during which this process began executing. * @return the cycle during which this process began executing */ public int getStart() { return start; }

/** * Sets the cycle during which the process begins executing. * @param startCycle the cycle during which this process begins executing. */ public void setStart(int startCycle) { start = startCycle; } /** * Gives the number of cycles this process waited before executing. * @return the number of cycles from the process creation to its execution */ public int getWait() { return wait; }

/** * Sets the wait time for this process * @param waitTime the number of cycles that this process waited */ public void setWait(int waitTime) { wait = waitTime; }

/** * Compares this simulated job with the specified simulated job. * @param another a simulated process * @return 0 when this simulated job is the same as the specified * simulated job; -1 if this job will be executed after; otherwise 1. */ public int compareTo(PCB another) { if (priority < another.priority) return 1; if (priority > another.priority) return -1; return 0; } }

The sample INPUT file, simulatedjobs.txt :

1 -16 10 52 2 -13 13 31 3 13 21 50 4 18 39 30 5 4 48 27 6 10 50 61 7 17 64 25 8 -8 83 64 9 -1 100 32 10 16 104 80 11 -5 107 63 12 -8 124 21 13 -9 136 53 14 -17 154 56 15 -13 155 62 16 -16 159 19 17 -9 170 56 18 -2 183 41 19 -6 191 88 20 13 192 46 21 14 193 96 22 -5 201 100 23 -19 209 31 24 20 210 87 25 -3 230 8 26 15 232 29 27 -14 239 20 28 10 241 2 29 -16 265 46 30 -8 267 97 31 17 274 61 32 12 283 89 33 -4 296 30 34 15 298 89 35 18 302 65 36 -7 304 12 37 -16 321 60 38 -14 326 49 39 13 337 50 40 -11 343 68 41 19 346 93 42 9 347 19 43 1 382 30 44 -1 395 36 45 12 399 5 46 -6 422 12 47 1 428 33 48 -3 439 5 49 2 451 25 50 -8 455 5 51 15 478 83 52 14 480 98 53 -13 497 12 54 -3 506 69 55 -16 525 68 56 -14 539 26 57 16 540 77 58 3 545 80 59 -17 549 64 60 5 561 46 61 -2 565 51 62 14 575 54 63 19 587 39 64 17 613 60 65 9 616 97 66 10 642 9 67 20 648 71 68 11 683 14 69 -7 692 30 70 19 700 18 71 1 742 29 72 -7 756 14 73 18 761 64 74 -1 772 84 75 18 778 78 76 6 790 10 77 -6 801 39 78 18 822 68 79 9 824 93 80 14 830 68 81 10 837 17 82 -1 839 24 83 20 841 56 84 -18 850 71 85 -4 858 77 86 -17 863 93 87 5 884 25 88 -2 890 43 89 14 898 58 90 -10 915 40 91 -14 920 17 92 -19 923 35 93 -8 925 60 94 5 957 36 95 -16 967 37 96 12 981 100 97 3 991 43

Sample OUTPUT file, simulatedjobsoutput.txt (1-1000 cycles):

*** Cycle #: 0 *** The CPU is idle. No new job this cycle. *** Cycle #: 1 *** The CPU is idle. No new job this cycle. *** Cycle #: 2 *** The CPU is idle. No new job this cycle. *** Cycle #: 3 *** The CPU is idle. No new job this cycle. *** Cycle #: 4 *** The CPU is idle. No new job this cycle. *** Cycle #: 5 *** The CPU is idle. No new job this cycle. *** Cycle #: 6 *** The CPU is idle. No new job this cycle. *** Cycle #: 7 *** The CPU is idle. No new job this cycle. *** Cycle #: 8 *** The CPU is idle. No new job this cycle. *** Cycle #: 9 *** The CPU is idle. No new job this cycle. *** Cycle #: 10 *** The CPU is idle. Adding job with pid #1 and priority -16 and length 52. *** Cycle #: 11 *** Process #1 is executing. No new job this cycle. *** Cycle #: 12 *** Process #1 is executing. No new job this cycle. *** Cycle #: 13 *** Process #1 is executing. Adding job with pid #2 and priority -13 and length 31. *** Cycle #: 14 *** Process #1 is executing. No new job this cycle. *** Cycle #: 15 *** Process #1 is executing. No new job this cycle. *** Cycle #: 16 *** Process #1 is executing. No new job this cycle. *** Cycle #: 17 *** Process #1 is executing. No new job this cycle. *** Cycle #: 18 *** Process #1 is executing. No new job this cycle. *** Cycle #: 19 *** Process #1 is executing. No new job this cycle. *** Cycle #: 20 *** Process #1 is executing. No new job this cycle. *** Cycle #: 21 *** Process #1 is executing. Adding job with pid #3 and priority 13 and length 50. *** Cycle #: 22 *** Process #1 is executing. No new job this cycle. *** Cycle #: 23 *** Process #1 is executing. No new job this cycle. *** Cycle #: 24 *** Process #1 is executing. No new job this cycle. *** Cycle #: 25 *** Process #1 is executing. No new job this cycle. *** Cycle #: 26 *** Process #1 is executing. No new job this cycle. *** Cycle #: 27 *** Process #1 is executing. No new job this cycle. *** Cycle #: 28 *** Process #1 is executing. No new job this cycle. *** Cycle #: 29 *** Process #1 is executing. No new job this cycle. *** Cycle #: 30 *** Process #1 is executing. No new job this cycle. *** Cycle #: 31 *** Process #1 is executing. No new job this cycle. *** Cycle #: 32 *** Process #1 is executing. No new job this cycle. *** Cycle #: 33 *** Process #1 is executing. No new job this cycle. *** Cycle #: 34 *** Process #1 is executing. No new job this cycle. *** Cycle #: 35 *** Process #1 is executing. No new job this cycle. *** Cycle #: 36 *** Process #1 is executing. No new job this cycle. *** Cycle #: 37 *** Process #1 is executing. No new job this cycle. *** Cycle #: 38 *** Process #1 is executing. No new job this cycle. *** Cycle #: 39 *** Process #1 is executing. Adding job with pid #4 and priority 18 and length 30. *** Cycle #: 40 *** Process #1 is executing. No new job this cycle. *** Cycle #: 41 *** Process #1 is executing. No new job this cycle. *** Cycle #: 42 *** Process #1 is executing. No new job this cycle. *** Cycle #: 43 *** Process #1 is executing. No new job this cycle. *** Cycle #: 44 *** Process #1 is executing. No new job this cycle. *** Cycle #: 45 *** Process #1 is executing. No new job this cycle. *** Cycle #: 46 *** Process #1 is executing. No new job this cycle. *** Cycle #: 47 *** Process #1 is executing. No new job this cycle. *** Cycle #: 48 *** Process #1 is executing. Adding job with pid #5 and priority 4 and length 27. *** Cycle #: 49 *** Process #1 is executing. No new job this cycle. *** Cycle #: 50 *** Process #1 is executing. Adding job with pid #6 and priority 10 and length 61. *** Cycle #: 51 *** Process #1 is executing. No new job this cycle. *** Cycle #: 52 *** Process #1 is executing. No new job this cycle. *** Cycle #: 53 *** Process #1 is executing. No new job this cycle. *** Cycle #: 54 *** Process #1 is executing. No new job this cycle. *** Cycle #: 55 *** Process #1 is executing. No new job this cycle. *** Cycle #: 56 *** Process #1 is executing. No new job this cycle. *** Cycle #: 57 *** Process #1 is executing. No new job this cycle. *** Cycle #: 58 *** Process #1 is executing. No new job this cycle. *** Cycle #: 59 *** Process #1 is executing. No new job this cycle. *** Cycle #: 60 *** Process #1 is executing. No new job this cycle. *** Cycle #: 61 *** Process #1 is executing. No new job this cycle. *** Cycle #: 62 *** Process #1 is executing. No new job this cycle. *** Cycle #: 63 *** Process #1 has just terminated. No new job this cycle. *** Cycle #: 64 *** Process #2 is executing. Adding job with pid #7 and priority 17 and length 25. *** Cycle #: 65 *** Process #2 is executing. No new job this cycle. *** Cycle #: 66 *** Process #2 is executing. No new job this cycle. *** Cycle #: 67 *** Process #2 is executing. No new job this cycle. *** Cycle #: 68 *** Process #2 is executing. No new job this cycle. *** Cycle #: 69 *** Process #2 is executing. No new job this cycle. *** Cycle #: 70 *** Process #2 is executing. No new job this cycle. *** Cycle #: 71 *** Process #2 is executing. No new job this cycle. .

.

.

.

*** Cycle #: 971 *** Process #92 is executing. No new job this cycle. *** Cycle #: 972 *** Process #92 is executing. No new job this cycle. *** Cycle #: 973 *** Process #92 has just terminated. No new job this cycle. *** Cycle #: 974 *** Process #86 is executing. No new job this cycle. *** Cycle #: 975 *** Process #86 is executing. No new job this cycle. *** Cycle #: 976 *** Process #86 is executing. No new job this cycle. *** Cycle #: 977 *** Process #86 is executing. No new job this cycle. *** Cycle #: 978 *** Process #86 is executing. No new job this cycle. *** Cycle #: 979 *** Process #86 is executing. No new job this cycle. *** Cycle #: 980 *** Process #86 is executing. No new job this cycle. *** Cycle #: 981 *** Process #86 is executing. Adding job with pid #96 and priority 12 and length 100. *** Cycle #: 982 *** Process #86 is executing. No new job this cycle. *** Cycle #: 983 *** Process #86 is executing. No new job this cycle. *** Cycle #: 984 *** Process #86 is executing. No new job this cycle. *** Cycle #: 985 *** Process #86 is executing. No new job this cycle. *** Cycle #: 986 *** Process #86 is executing. No new job this cycle. *** Cycle #: 987 *** Process #86 is executing. No new job this cycle. *** Cycle #: 988 *** Process #86 is executing. No new job this cycle. *** Cycle #: 989 *** Process #86 is executing. No new job this cycle. *** Cycle #: 990 *** Process #86 is executing. No new job this cycle. *** Cycle #: 991 *** Process #86 is executing. Adding job with pid #97 and priority 3 and length 43. *** Cycle #: 992 *** Process #86 is executing. No new job this cycle. *** Cycle #: 993 *** Process #86 is executing. No new job this cycle. *** Cycle #: 994 *** Process #86 is executing. No new job this cycle. *** Cycle #: 995 *** Process #86 is executing. No new job this cycle. *** Cycle #: 996 *** Process #86 is executing. No new job this cycle. *** Cycle #: 997 *** Process #86 is executing. No new job this cycle. *** Cycle #: 998 *** Process #86 is executing. No new job this cycle. *** Cycle #: 999 *** Process #86 is executing. No new job this cycle. *** Cycle #: 1000 *** Process #86 is executing. No new job this cycle. The average throughput is 0.01998 per cycle. The average wait time is 130.2.

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

SQL Server T-SQL Recipes

Authors: David Dye, Jason Brimhall

4th Edition

1484200616, 9781484200612

More Books

Students also viewed these Databases questions

Question

How do Dimensional Database Models differ from Relational Models?

Answered: 1 week ago

Question

What type of processing do Relational Databases support?

Answered: 1 week ago

Question

Describe several aggregation operators.

Answered: 1 week ago