Answered step by step

Verified Expert Solution

Link Copied!

Question

1 Approved Answer

Posted on Sep 30, 2024

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

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. 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 first. 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 process this job. For simplicity, we will 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. Also, each process will have a process identification number 1 . . . n, where n is the number of simulated processes created. First, you will complete the implementation of a heap ADT. Then you will use the ADT 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. You will enter 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. Your application will generate a random probability value q between 0 and 1and for q p 2 , two simulated jobs are created for p 2 < q p one is created and for other values of q none is created. You will then set the relevant meta-data fields of the simulated jobs with appropriate values. Each process 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. Your 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 CPUs ready queue is not running, it begins executing the process and updates the start and wait meta-data 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 CPUs ready queue 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. When a process terminates, its process control block (PCB) is removed from the ready queue. If its quantum has not expired, the message CPU k: Process # x is executing should be displayed. The letter x denotes the PID of the process.

3. Your 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, your 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 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. See project files for details on assigned tasks.

Here are the programs I have for this project, including what the output should look like. Only DualCoreSimulator and Heap need to be worked on to where the array is stored in the heap.

_____________________________________________

DualCoreSimulator.java //class

package dualcoresimulator;

import java.util.Random;

public class DualCoreSimulator

{

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

double p = .2;

int pid = 0;

int jid=0;

int n=0;

class job{

int pid;

int length;

int priority;

int start;

int end;

}

;

job[] jobdata = new job[1000];

for ( int i=0; i

jobdata[i]=new job();

}

for(int x=1; x<=1000; x ++){

System.out.println("Cycle #" + x);

{ Random rand = new Random();

double number;

number = rand.nextDouble();

//System.out.println(number);

if( number <= p*p) {System.out.println("Two new jobs this cycle");

for(int y=1; y<=2; y ++) {

jid=jid+1;

jobdata[n].pid=jid;

System.out.println("Job ID = " +jobdata[n].pid);

jobdata[n].length = 1 + (int)(Math.random() * 100);

System.out.println("Length= "+jobdata[n].length);

jobdata[n].start=x;

jobdata[n].end=jobdata[x].start+jobdata[n].length;

System.out.println("Start cycle = " +jobdata[n].start);

System.out.println("End cycle = " +jobdata[n].end);

jobdata[n].priority= -19 + (int) (Math.random()* 20);

System.out.println("Job priority = " +jobdata[n].priority);

n=n+1;}}

else if (number > p*p & number<=p) {System.out.println("One new job this cycle.");

jid=jid+1;

jobdata[n].pid=jid;

System.out.println("Job ID = " +jobdata[n].pid);

jobdata[n].length = 1 + (int)(Math.random() * 100);

System.out.println("Length= "+jobdata[n].length);

jobdata[n].start=x;

jobdata[n].end=jobdata[n].start+jobdata[n].length;

System.out.println("Start cycle = " +jobdata[n].start);

System.out.println("End cycle = " +jobdata[n].end);

jobdata[n].priority= -19 + (int) (Math.random()* 20);

System.out.println("Job priority = " +jobdata[n].priority);

n=n+1;}

else {System.out.println("No new job this cycle.");}

}

//Implement this method

}

_____________________________________________

HeapException.java

package dualcoresimulator;

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 //interface

package dualcoresimulator;

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 //class

package dualcoresimulator;

import java.util.*;

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() { tree=new ArrayList(); }

public boolean isEmpty() { if (tree.size() == 0) { return true; } return false; }

//Still needs work! public void insert(E obj) {

if (isEmpty())

{

tree.add(obj);

}

else

{

tree.add(obj);

int place = tree.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;

}

public E remove() throws HeapException { E root = tree.get(0); tree.set(0 , tree.get(tree.size()-1)); reheapify(0); return root; }

// still needs work public E peek() throws HeapException { if (size() == 0){ throw new HeapException(); } return tree.get(0); }

public int size() { return(tree.size()); // still needs work } /** * 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(place); tree.set(place, tree.get(parent)); tree.set(parent, 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 */ private void reheapify(int root) {

if (((2 * root) + 1) < (size() -1)) { int child = (2 * root) + 1; if (child <= size()) { 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); reheapify(child); } }

}

______________________________________

PCB.java //class

package dualcoresimulator;

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; } }

_____________________________________

What the output should look like

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