Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 30, 2024

Hello, I'm supposed to write a Java code using NetBeans IDE 8.2 that does A Non-Preemptive Scheduler that implements a priority queue using the heap

Hello, I'm supposed to write a Java code using NetBeans IDE 8.2 that does A Non-Preemptive Scheduler that implements a priority queue using the heap ADT and Manipulates an extensible array.

As a synopsis, CPU scheduling is the basis of multiprogramming such as when 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. The goal is to write a program that schedules simulated CPU jobs, and it should run in a loop, with 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, which is the highest priority, and 19, which is the lowest priority, inclusive. With all the jobs waiting to be processed in a time slice, the CPU must work on a job with the highest priority. Once two jobs have the same priority, the one created earliest will be processed first. Each job comes with a length value in the simulation, which is a random integer between 1 and 100, inclusive, indicating the number of time slices that are needed to process this job. To make is easier to understand, lets assume that the CPU is non-preemptive; that is, once a job is scheduled on the CPU, it runs for the number of time slices equal to its length without being interrupted. With that said, each process will have a process identification number 1 n, where n is the number of simulated processes created.

The first thing that needs to be completed is the implementation of a heap ADT. Then the ADT will be used in writing a simple CPU scheduling simulator for a dual=core processor. At time zero, the ready queue for each processor is empty. The random number generator should be seeded using the current time of day. Then what will be entered as a command line argument p, a value between 0.01 and 1.00 inclusive, and s, the number of time slices the simulator will run. P is the probability that a new process is created during any given cycle. Two simplifying assumptions are that at most two processes may be spawned during a cycle and that process creation is independent and identically distributed. Then the application will generate a random probability value q between 0 and 1and for 1 <= p², two simulated jobs are created for p² < q < <= p one is created and for other values of q none is created. Then the relevant meta-data fields of the simulated jobs with appropriate values will be set. Each control block also has additional meta-data fields to facilitate the 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.

The application should track the following events which occur during each time slice and print these activities:

1. *** Cycle #: c *** at the beginning of each cycle, followed by the number of processes in the ready queue of each processor in the format CPU 1 (n1) CPU 2 (n2).

2. During each cycle, your simulator will examine the status of the ready queues for each core:

(a) Whenever the ready queue for a CPU is empty, your simulator prints CPU k: idle, where k =1 or 2 is the CPU number.

(b) Whenever the ready queue for a CPU is non-empty, your simulator tracks these events:

i. If the process at the head of the CPU is not running, it begins executing the process and updates the startand wait metadata fields of its process control block (PCB). Additionally, variables that are relevant to your analysis are updated.

ii. If the process at the head of the CPU is running, the simulator checks whether the processs quantum has expired. If it has, the message CPU k: Process # x has just terminated. should be displayed. If its quantum has not expired, CPU k: Process # x is executing. The letter x denotes the PID of the process.

3. The simulator should also track process creation and scheduling during each cycle using the following policy.

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

(b) If one new job is created, the message One new job this cycle. should be displayed. If both ready queues have the same length, the process is scheduled on CPU 1. If the ready queues have different lengths, the process is scheduled on the CPU with the shorter ready queue. When the new process is scheduled the message CPU k: Adding job with pid # x and priority p and length t. should be displayed.

(c) If two new jobs are created, the message Two new jobs this cycle. should be displayed. If both ready queues have the same length, one process is scheduled on CPU 1 and the other on CPU2. If the ready queues have different lengths, both processes are scheduled on the CPU with the shorter ready queue. For each new process that is scheduled the message CPU k: Adding job with pid # x and priority p and length t. should be displayed.

At the end of the simulation, the program should also display the average throughput (number of processes executed per cycle) and average wait time per process for each CPU as well as the overall average throughput and average wait time per process.

To run the 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. See project files for details on assigned tasks.

Below are the source codes for HeapException.java (class), HeapAPI.java (interface), Heap.java (class), PCB.java (class) and DualCoreSimulator.java (class). The first thing that needs to be added isDualCoreSimulator.java as a class, and the rest of the names of the source codes can be added as classes except for HeapAPI.java, which should be created as an interface. The only source codes that need modification are the DualCoreSimulator.java and Heap.java, and the rest don't need any modifications.

-----------------------------------------------------------------------------------

DualCoreSimulator.java (first thing that needs to be created as a class, and needs modifications.)

package dualcoresimulator;

import java.util.Random;

public class DualCoreSimulator

{

public static void main(String []args) throws HeapException

{

//Implement this method

}

----------------------------------------------------------------------------

HeapException.java (create as a class, and DO NOT alter the code.)

package dualcoresimulator;

/**

* This class reports Heap exceptions.

public 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);

}

----------------------------------------------------------------------------

HeapAPI.java (create as an interface and DO NOT alter the code)

package dualcoresimulator;

/**

* Describes the basic operations of a max heap

* @param

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();

}

----------------------------------------------------------------------------

Heap.java (create as class, and the code needs modifications.)

package dualcoresimulator;

import java.util.*;

/**

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

* HeapAPI interface. The array holds objects that implement the

* parameterized Comparable interface.

* @param the heap element type

public class Heap> implements HeapAPI

{

/**

* A complete tree stored in an array list representing this

* binary heap

private ArrayList tree;

/**

* Constructs an empty heap

public Heap()

{

//implement this method

}

public boolean isEmpty()

{

// implement this method

}

public void insert(E obj)

{

//implement this method

}

public E remove() throws HeapException

{

//implement this method

}

public E peek() throws HeapException

{

//implement this method

}

public int size()

{

//implement this method

}

/**

* 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)

{

//implement this method

}

/**

* 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

private void reheapify(int root)

{

//implement this method

}

----------------------------------------------------------------------------

PCB.java (create as class, and DO NOT make any modifications to it.)

package dualcoresimulator;

/**

* Models a process control block.

public class PCB implements Comparable

{

/**

* this process ID

private int pid;

/**

* the nice (priority) value of this process

private int priority;

/**

* running status 0=idle 1=running

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 = 19;

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 (running > another.running)

return 1;

if (running < another.running)

return -1;

if (priority < another.priority)

return 1;

if (priority > another.priority)

return -1;

if (arrived < another.arrived)

return 1;

if (arrived > another.arrived)

return -1;

return 0;

}

___________________

Sample Output:

run:

*** Cycle #: 1

CPU 1 (0) CPU 2 (0)

CPU 1: idle.

CPU 2: idle.

One new job this cycle.

CPU 1: Adding job with pid #1 and priority 19 and length 99.

*** Cycle #: 2

CPU 1 (1) CPU 2 (0)