Write a program in Java that could be used to schedule jobs based on the “shorte
ID: 3583488 • Letter: W
Question
Write a program in Java that could be used to schedule jobs based on the “shortest job” algorithm, and compare the running of the programs to using a queue.
Use the data from the given table to calculate the “turnaround” time for each job (time a job is completed – time a job enters the system), and the average waiting time for the jobs ((total turnaround time – total “running” time)/number of jobs)
a) using a queue
b) using a heap based on “expected run time” (CPU burst)
Which method gives the lower average waiting time?
Explanation / Answer
import java.util.Random;
public class SJF {
static class Process {
public int Timearrival;
public int Timestart;
public int Timeburst;
public Process(int t) { Timeburst=t; }
}
static class PQueue {
class Node {
Process data;
Node next = null;
Node(Process p, Node n) { data=p; next=n; }
Node(Process p) { data=p; }
}
Node tail;
public PQueue() {
tail = null;
}
public boolean isEmpty() {
return tail==null;
}
public void enqueue(Process x, float Timeburst) {
if ( tail==null ) {
tail = new Node(x); tail.next=tail;
}
else tail = (tail.next = new Node(x,tail.next));
}
public Process dequeue() {
if ( tail==null ) return null;
else { Node p = tail.next;
if ( p!=tail ) tail.next = p.next;
else tail = null;
return p.data;
}
}
}
public static void main(String[] args) {
int T = 0;
int N = 0;
int Number_Of_Processes = 100;
int Qqued_Processes = 0;
int Total_time = 0;
int TurnaroundTime = 0;
Process CurrentProcess = null;
int LastProcess = 0;
Random r0 = new Random();
Random r1 = new Random();
Random r2 = new Random();
PQueue q = new PQueue();
while ( N < Number_Of_Processes ) {
int newProcessArrival = r0.nextInt(1801);
double u, v, x;
do {
u = 1.-r1.nextDouble();
v = 1.-r2.nextDouble();
x = Math.sqrt (-2.*Math.log(u))*Math.cos(2.*Math.PI*v) + 2.0;
} while ( x<0 );
int newProcessDuration = (int) Math.round (x*1000);
Process p = new Process(newProcessDuration);
LastProcess += newProcessArrival;
if ( LastProcess < T ) LastProcess = T;
p.Timearrival = LastProcess;
if ( CurrentProcess == null ) {
CurrentProcess = p;
T = p.Timestart = p.Timearrival;
}
else { q.enqueue(p, p.Timeburst); Qqued_Processes++; }
do {
if ( T + CurrentProcess.Timeburst > LastProcess ) break;
Total_time += CurrentProcess.Timeburst;
T += CurrentProcess.Timeburst;
int turnaroundTime = T - CurrentProcess.Timearrival;
TurnaroundTime += turnaroundTime;
System.out.printf ("Process %d terminated. Turnaround time: %.2f milliseconds. ",
++N, (double) turnaroundTime/1000);
System.out.printf (" (arrival %.2f, begin %.2f, end %.2f, duration %.2f) ",
(double) CurrentProcess.Timearrival/1000, (double) CurrentProcess.Timestart/1000,
(double) (CurrentProcess.Timestart+CurrentProcess.Timeburst)/1000,
(double) CurrentProcess.Timeburst/1000);
if ( N >= Number_Of_Processes ) break;
if ( q.isEmpty( ) ) { CurrentProcess = null; break; }
else {
CurrentProcess = q.dequeue( ); Qqued_Processes--;
if ( CurrentProcess.Timearrival <= T ) CurrentProcess.Timestart = T;
else CurrentProcess.Timestart = T = CurrentProcess.Timearrival;
}
} while(true);
}
System.out.printf (" Simulation time: %.2f milliseconds ", (double) T/1000);
System.out.printf ("Average turnaround time: %.2f milliseconds ",
(double) TurnaroundTime/Number_Of_Processes/1000);
System.out.printf ("Average process duration: %.2f milliseconds ",
(double) Total_time/Number_Of_Processes/1000);
System.out.printf ("Throughput: %.2f processes per second ", (double) Number_Of_Processes/T * 1000000);
System.out.println ("Processes in the queue at the end of the simulation: " + Qqued_Processes);
}
}
======================================================================
akshay@akshay-Inspiron-3537:~/Chegg$ javac SJF.java
akshay@akshay-Inspiron-3537:~/Chegg$ java S
ShortestJobFirst SJF SubsetSum
SieveOfEratosthenes Snippet SubSetSum
akshay@akshay-Inspiron-3537:~/Chegg$ java SJF
Process 1 terminated. Turnaround time: 0.62 milliseconds.
(arrival 0.53, begin 0.53, end 1.15, duration 0.62)
Process 2 terminated. Turnaround time: 1.98 milliseconds.
(arrival 0.65, begin 1.15, end 2.64, duration 1.49)
Process 3 terminated. Turnaround time: 1.92 milliseconds.
(arrival 1.21, begin 2.64, end 3.12, duration 0.49)
Process 4 terminated. Turnaround time: 1.67 milliseconds.
(arrival 2.92, begin 3.12, end 4.59, duration 1.47)
Process 5 terminated. Turnaround time: 0.85 milliseconds.
(arrival 4.56, begin 4.59, end 5.41, duration 0.81)
Process 6 terminated. Turnaround time: 2.15 milliseconds.
(arrival 5.83, begin 5.83, end 7.98, duration 2.15)
Process 7 terminated. Turnaround time: 2.91 milliseconds.
(arrival 6.65, begin 7.98, end 9.56, duration 1.58)
Process 8 terminated. Turnaround time: 2.94 milliseconds.
(arrival 7.67, begin 9.56, end 10.61, duration 1.05)
Process 9 terminated. Turnaround time: 4.10 milliseconds.
(arrival 8.96, begin 10.61, end 13.06, duration 2.45)
Process 10 terminated. Turnaround time: 6.02 milliseconds.
(arrival 9.54, begin 13.06, end 15.56, duration 2.49)
Process 11 terminated. Turnaround time: 7.44 milliseconds.
(arrival 10.14, begin 15.56, end 17.58, duration 2.03)
Process 12 terminated. Turnaround time: 7.81 milliseconds.
(arrival 11.58, begin 17.58, end 19.39, duration 1.81)
Process 13 terminated. Turnaround time: 9.26 milliseconds.
(arrival 12.38, begin 19.39, end 21.64, duration 2.26)
Process 14 terminated. Turnaround time: 11.44 milliseconds.
(arrival 13.44, begin 21.64, end 24.88, duration 3.24)
Process 15 terminated. Turnaround time: 13.12 milliseconds.
(arrival 13.96, begin 24.88, end 27.08, duration 2.20)
Process 16 terminated. Turnaround time: 12.95 milliseconds.
(arrival 15.28, begin 27.08, end 28.23, duration 1.15)
Process 17 terminated. Turnaround time: 13.68 milliseconds.
(arrival 15.54, begin 28.23, end 29.23, duration 1.00)
Process 18 terminated. Turnaround time: 16.04 milliseconds.
(arrival 16.06, begin 29.23, end 32.09, duration 2.87)
Process 19 terminated. Turnaround time: 15.42 milliseconds.
(arrival 17.79, begin 32.09, end 33.21, duration 1.12)
Process 20 terminated. Turnaround time: 15.83 milliseconds.
(arrival 18.51, begin 33.21, end 34.35, duration 1.13)
Process 21 terminated. Turnaround time: 15.47 milliseconds.
(arrival 19.28, begin 34.35, end 34.75, duration 0.41)
Process 22 terminated. Turnaround time: 16.08 milliseconds.
(arrival 20.55, begin 34.75, end 36.63, duration 1.87)
Process 23 terminated. Turnaround time: 16.98 milliseconds.
(arrival 20.99, begin 36.63, end 37.97, duration 1.34)
Process 24 terminated. Turnaround time: 17.49 milliseconds.
(arrival 21.45, begin 37.97, end 38.93, duration 0.97)
Process 25 terminated. Turnaround time: 19.31 milliseconds.
(arrival 22.41, begin 38.93, end 41.72, duration 2.79)
Process 26 terminated. Turnaround time: 21.66 milliseconds.
(arrival 22.91, begin 41.72, end 44.57, duration 2.85)
Process 27 terminated. Turnaround time: 23.28 milliseconds.
(arrival 23.10, begin 44.57, end 46.38, duration 1.81)
Process 28 terminated. Turnaround time: 25.77 milliseconds.
(arrival 23.13, begin 46.38, end 48.91, duration 2.53)
Process 29 terminated. Turnaround time: 26.99 milliseconds.
(arrival 23.88, begin 48.91, end 50.88, duration 1.97)
Process 30 terminated. Turnaround time: 29.46 milliseconds.
(arrival 25.57, begin 50.88, end 55.03, duration 4.15)
Process 31 terminated. Turnaround time: 30.19 milliseconds.
(arrival 27.36, begin 55.03, end 57.54, duration 2.51)
Process 32 terminated. Turnaround time: 31.10 milliseconds.
(arrival 28.69, begin 57.54, end 59.79, duration 2.25)
Process 33 terminated. Turnaround time: 32.56 milliseconds.
(arrival 29.38, begin 59.79, end 61.94, duration 2.15)
Process 34 terminated. Turnaround time: 33.70 milliseconds.
(arrival 29.45, begin 61.94, end 63.15, duration 1.20)
Process 35 terminated. Turnaround time: 35.98 milliseconds.
(arrival 29.97, begin 63.15, end 65.94, duration 2.80)
Process 36 terminated. Turnaround time: 38.49 milliseconds.
(arrival 30.91, begin 65.94, end 69.40, duration 3.46)
Process 37 terminated. Turnaround time: 38.96 milliseconds.
(arrival 32.35, begin 69.40, end 71.30, duration 1.90)
Process 38 terminated. Turnaround time: 40.19 milliseconds.
(arrival 33.73, begin 71.30, end 73.92, duration 2.62)
Process 39 terminated. Turnaround time: 40.11 milliseconds.
(arrival 35.06, begin 73.92, end 75.16, duration 1.24)
Process 40 terminated. Turnaround time: 41.66 milliseconds.
(arrival 35.34, begin 75.16, end 77.00, duration 1.84)
Process 41 terminated. Turnaround time: 46.02 milliseconds.
(arrival 35.60, begin 77.00, end 81.62, duration 4.62)
Process 42 terminated. Turnaround time: 46.53 milliseconds.
(arrival 35.78, begin 81.62, end 82.31, duration 0.70)
Process 43 terminated. Turnaround time: 47.51 milliseconds.
(arrival 37.52, begin 82.31, end 85.03, duration 2.72)
Process 44 terminated. Turnaround time: 49.03 milliseconds.
(arrival 39.25, begin 85.03, end 88.28, duration 3.24)
Process 45 terminated. Turnaround time: 50.15 milliseconds.
(arrival 40.50, begin 88.28, end 90.65, duration 2.37)
Process 46 terminated. Turnaround time: 51.74 milliseconds.
(arrival 41.61, begin 90.65, end 93.35, duration 2.70)
Process 47 terminated. Turnaround time: 52.98 milliseconds.
(arrival 42.94, begin 93.35, end 95.92, duration 2.57)
Process 48 terminated. Turnaround time: 56.79 milliseconds.
(arrival 43.14, begin 95.92, end 99.93, duration 4.02)
Process 49 terminated. Turnaround time: 56.75 milliseconds.
(arrival 44.18, begin 99.93, end 100.93, duration 1.00)
Process 50 terminated. Turnaround time: 58.71 milliseconds.
(arrival 44.49, begin 100.93, end 103.20, duration 2.27)
Process 51 terminated. Turnaround time: 60.24 milliseconds.
(arrival 46.05, begin 103.20, end 106.29, duration 3.09)
Process 52 terminated. Turnaround time: 60.92 milliseconds.
(arrival 46.66, begin 106.29, end 107.58, duration 1.29)
Process 53 terminated. Turnaround time: 59.60 milliseconds.
(arrival 48.43, begin 107.58, end 108.03, duration 0.45)
Process 54 terminated. Turnaround time: 60.05 milliseconds.
(arrival 49.59, begin 108.03, end 109.65, duration 1.62)
Process 55 terminated. Turnaround time: 61.37 milliseconds.
(arrival 51.17, begin 109.65, end 112.55, duration 2.90)
Process 56 terminated. Turnaround time: 62.75 milliseconds.
(arrival 52.81, begin 112.55, end 115.56, duration 3.02)
Process 57 terminated. Turnaround time: 63.48 milliseconds.
(arrival 54.54, begin 115.56, end 118.02, duration 2.46)
Process 58 terminated. Turnaround time: 63.39 milliseconds.
(arrival 56.01, begin 118.02, end 119.40, duration 1.38)
Process 59 terminated. Turnaround time: 64.78 milliseconds.
(arrival 57.05, begin 119.40, end 121.83, duration 2.43)
Process 60 terminated. Turnaround time: 65.61 milliseconds.
(arrival 57.56, begin 121.83, end 123.17, duration 1.34)
Process 61 terminated. Turnaround time: 65.05 milliseconds.
(arrival 59.04, begin 123.17, end 124.09, duration 0.92)
Process 62 terminated. Turnaround time: 67.54 milliseconds.
(arrival 59.79, begin 124.09, end 127.33, duration 3.24)
Process 63 terminated. Turnaround time: 68.75 milliseconds.
(arrival 61.27, begin 127.33, end 130.02, duration 2.69)
Process 64 terminated. Turnaround time: 68.94 milliseconds.
(arrival 62.72, begin 130.02, end 131.66, duration 1.64)
Process 65 terminated. Turnaround time: 69.82 milliseconds.
(arrival 63.60, begin 131.66, end 133.42, duration 1.76)
Process 66 terminated. Turnaround time: 70.80 milliseconds.
(arrival 63.73, begin 133.42, end 134.52, duration 1.10)
Process 67 terminated. Turnaround time: 72.36 milliseconds.
(arrival 64.87, begin 134.52, end 137.23, duration 2.71)
Process 68 terminated. Turnaround time: 72.90 milliseconds.
(arrival 66.16, begin 137.23, end 139.07, duration 1.83)
Process 69 terminated. Turnaround time: 71.98 milliseconds.
(arrival 67.60, begin 139.07, end 139.57, duration 0.51)
Process 70 terminated. Turnaround time: 74.17 milliseconds.
(arrival 67.67, begin 139.57, end 141.84, duration 2.27)
Process 71 terminated. Turnaround time: 74.02 milliseconds.
(arrival 68.57, begin 141.84, end 142.59, duration 0.75)
Process 72 terminated. Turnaround time: 75.32 milliseconds.
(arrival 70.05, begin 142.59, end 145.37, duration 2.78)
Process 73 terminated. Turnaround time: 75.87 milliseconds.
(arrival 71.54, begin 145.37, end 147.41, duration 2.05)
Process 74 terminated. Turnaround time: 77.65 milliseconds.
(arrival 72.87, begin 147.41, end 150.52, duration 3.11)
Process 75 terminated. Turnaround time: 77.79 milliseconds.
(arrival 74.42, begin 150.52, end 152.21, duration 1.69)
Process 76 terminated. Turnaround time: 79.72 milliseconds.
(arrival 75.48, begin 152.21, end 155.20, duration 3.00)
Process 77 terminated. Turnaround time: 80.48 milliseconds.
(arrival 76.18, begin 155.20, end 156.66, duration 1.46)
Process 78 terminated. Turnaround time: 81.67 milliseconds.
(arrival 77.59, begin 156.66, end 159.27, duration 2.61)
Process 79 terminated. Turnaround time: 82.01 milliseconds.
(arrival 77.68, begin 159.27, end 159.69, duration 0.42)
Process 80 terminated. Turnaround time: 83.18 milliseconds.
(arrival 77.89, begin 159.69, end 161.07, duration 1.38)
Process 81 terminated. Turnaround time: 84.06 milliseconds.
(arrival 78.39, begin 161.07, end 162.45, duration 1.39)
Process 82 terminated. Turnaround time: 84.45 milliseconds.
(arrival 78.62, begin 162.45, end 163.06, duration 0.61)
Process 83 terminated. Turnaround time: 87.50 milliseconds.
(arrival 78.67, begin 163.06, end 166.17, duration 3.10)
Process 84 terminated. Turnaround time: 88.28 milliseconds.
(arrival 79.39, begin 166.17, end 167.67, duration 1.50)
Process 85 terminated. Turnaround time: 88.28 milliseconds.
(arrival 81.14, begin 167.67, end 169.42, duration 1.75)
Process 86 terminated. Turnaround time: 89.81 milliseconds.
(arrival 82.04, begin 169.42, end 171.84, duration 2.42)
Process 87 terminated. Turnaround time: 92.83 milliseconds.
(arrival 82.43, begin 171.84, end 175.26, duration 3.42)
Process 88 terminated. Turnaround time: 92.24 milliseconds.
(arrival 84.15, begin 175.26, end 176.39, duration 1.13)
Process 89 terminated. Turnaround time: 92.99 milliseconds.
(arrival 85.69, begin 176.39, end 178.68, duration 2.29)
Process 90 terminated. Turnaround time: 93.51 milliseconds.
(arrival 86.16, begin 178.68, end 179.66, duration 0.98)
Process 91 terminated. Turnaround time: 94.61 milliseconds.
(arrival 87.93, begin 179.66, end 182.54, duration 2.87)
Process 92 terminated. Turnaround time: 96.60 milliseconds.
(arrival 88.13, begin 182.54, end 184.73, duration 2.20)
Process 93 terminated. Turnaround time: 99.28 milliseconds.
(arrival 88.34, begin 184.73, end 187.62, duration 2.89)
Process 94 terminated. Turnaround time: 100.03 milliseconds.
(arrival 88.52, begin 187.62, end 188.55, duration 0.93)
Process 95 terminated. Turnaround time: 100.27 milliseconds.
(arrival 90.07, begin 188.55, end 190.34, duration 1.79)
Process 96 terminated. Turnaround time: 100.94 milliseconds.
(arrival 91.75, begin 190.34, end 192.69, duration 2.34)
Process 97 terminated. Turnaround time: 100.36 milliseconds.
(arrival 93.05, begin 192.69, end 193.41, duration 0.73)
Process 98 terminated. Turnaround time: 102.40 milliseconds.
(arrival 93.46, begin 193.41, end 195.86, duration 2.45)
Process 99 terminated. Turnaround time: 103.73 milliseconds.
(arrival 94.43, begin 195.86, end 198.17, duration 2.30)
Process 100 terminated. Turnaround time: 104.25 milliseconds.
(arrival 94.60, begin 198.17, end 198.85, duration 0.68)
Simulation time: 198.85 milliseconds
Average turnaround time: 52.48 milliseconds
Average process duration: 1.98 milliseconds
Throughput: 502.90 processes per second
Processes in the queue at the end of the simulation: 110
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.