commit facc3d081a1b0be5c6faf81fd4cc72ddf1967e9f
parent c70b2ecf64876cb0bfee87411b36c72814c650e0
Author: Cody Lewis <cody@codymlewis.com>
Date: Thu, 22 Aug 2019 11:06:45 +1000
Migrated to discrete time event simulation
Diffstat:
| M | A1.java | | | 10 | +++++----- |
| M | Dispatcher.java | | | 19 | +++++++++++++++---- |
| M | FB.java | | | 33 | +++++++++++++++------------------ |
| M | FCFS.java | | | 20 | +++++++++++--------- |
| M | NRR.java | | | 84 | +++++++++++++++++++++++++++++++++++++++++++++++++++++-------------------------- |
| M | Process.java | | | 20 | ++++++++++++++------ |
| M | RR.java | | | 105 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------ |
| M | Scheduler.java | | | 11 | ++++------- |
8 files changed, 202 insertions(+), 100 deletions(-)
diff --git a/A1.java b/A1.java
@@ -36,11 +36,11 @@ public class A1 {
System.out.println(nrr.run());
System.out.println("Summary");
- System.out.println("Algorithm Average Turnaround Time Average Waiting Time");
- System.out.format("FCFS %s\n", fcfs.summary());
- System.out.format("RR %s\n", rr.summary());
- System.out.format("FB (constant) %s\n", fb.summary());
- System.out.format("NRR %s\n", nrr.summary());
+ System.out.println("Algorithm\tAverage Turnaround Time\tAverage Waiting Time");
+ System.out.format("FCFS\t\t%s\n", fcfs.summary());
+ System.out.format("RR\t\t%s\n", rr.summary());
+ System.out.format("FB (constant)\t%s\n", fb.summary());
+ System.out.format("NRR\t\t%s\n", nrr.summary());
System.exit(0);
}
diff --git a/Dispatcher.java b/Dispatcher.java
@@ -1,8 +1,8 @@
-import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;
import java.util.Scanner;
+import java.util.PriorityQueue;
import java.io.File;
/**
@@ -127,16 +127,27 @@ public class Dispatcher {
public String run() {
int time = 0;
int timeProcessingTo = 0;
+ PriorityQueue<Integer> eventTimes = new PriorityQueue<>();
- while (processes.size() != 0 || !scheduler.empty()) {
+ for (int eventTime: processes.keySet()) {
+ eventTimes.add(eventTime);
+ }
+
+ while (!eventTimes.isEmpty()) {
+ time = eventTimes.poll();
if (processes.get(time) != null) {
for (Process process : processes.get(time)) {
scheduler.add(process);
}
processes.remove(time);
}
- scheduler.process(time);
- time++;
+ if (time >= timeProcessingTo) {
+ int processingTime = scheduler.process(time);
+ if (processingTime != 0) {
+ eventTimes.add(time + processingTime);
+ timeProcessingTo = time + processingTime;
+ }
+ }
}
return scheduler.results();
diff --git a/FB.java b/FB.java
@@ -1,6 +1,4 @@
import java.util.ArrayList;
-import java.util.Queue;
-import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Collections;
@@ -86,7 +84,6 @@ public class FB extends Scheduler {
@Override
public void add(Process process) {
queue.add(new FBProcess(process));
- // Collections.sort(queue, new FBProcess());
}
private void add(FBProcess process) {
@@ -105,33 +102,32 @@ public class FB extends Scheduler {
}
@Override
- public void process(int time) {
- FBProcess head = queue.get(0);
- if (head != null) {
+ public int process(int time) {
+ if (!queue.isEmpty()) {
+ FBProcess head = queue.get(0);
if (newProcess) {
- switching--;
- if (switching == 0) {
- Collections.sort(queue, new FBProcess());
- switchProcess(time);
- }
- } else if (head.getProcess().process(time)) {
- processed.add(queue.remove(0).getProcess());
- newProcess = true;
+ Collections.sort(queue, new FBProcess());
+ return switchProcess(time);
} else {
- slice = (slice + 1) % SLICE_SIZE;
- if (slice == 0 && queue.size() > 1) {
+ int processingTime = head.getProcess()
+ .process(time, SLICE_SIZE);
+ if (head.getProcess().finished()) {
+ processed.add(queue.remove(0).getProcess());
+ newProcess = true;
+ } else {
head.incrementPriority();
add(queue.remove(0));
newProcess = true;
}
+ return processingTime;
}
}
+ return 0;
}
@Override
- protected void switchProcess(int time) {
+ protected int switchProcess(int time) {
newProcess = false;
- switching = switchProcessTime;
slice = 0;
String curPid = queue.get(0).getProcess().getPid();
if (!prevPid.equals(curPid)) {
@@ -142,5 +138,6 @@ public class FB extends Scheduler {
);
}
prevPid = curPid;
+ return switchProcessTime;
}
}
diff --git a/FCFS.java b/FCFS.java
@@ -48,29 +48,31 @@ public class FCFS extends Scheduler {
}
@Override
- public void process(int time) {
+ public int process(int time) {
Process head = queue.peek();
if (head != null) {
if (newProcess) {
- switching--;
- if (switching == 0) {
- switchProcess(time);
+ return switchProcess(time);
+ } else {
+ int processingTime = head.process(time, 0);
+ if (head.finished()) {
+ processed.add(queue.poll());
+ newProcess = true;
}
- } else if (head.process(time)) {
- processed.add(queue.poll());
- newProcess = true;
+ return processingTime;
}
}
+ return 0;
}
@Override
- protected void switchProcess(int time) {
+ protected int switchProcess(int time) {
newProcess = false;
- switching = switchProcessTime;
startTimes += String.format(
"T%d: %s\n",
time + 1,
queue.peek().getPid()
);
+ return switchProcessTime;
}
}
diff --git a/NRR.java b/NRR.java
@@ -1,5 +1,6 @@
-import java.util.LinkedList;
-import java.util.Queue;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Collections;
/**
* <h1>RR - Comp2240A1</h1>
@@ -12,21 +13,35 @@ import java.util.Queue;
*/
public class NRR extends Scheduler {
- private class NarrowProcess {
+ String prevPid;
+
+ private class NarrowProcess implements Comparable<NarrowProcess>,
+ Comparator<NarrowProcess> {
private Process process;
private int sliceSize;
private boolean used;
+ private Integer time;
- public NarrowProcess(Process process) {
+ public NarrowProcess(Process process, int time) {
this.process = process;
sliceSize = 4;
used = false;
+ this.time = time;
}
public int getSliceSize() {
return sliceSize;
}
+
+ public Integer getTime() {
+ return time;
+ }
+
+ public void setTime(int time) {
+ this.time = time;
+ }
+
public void decrementSliceSize() {
if (used) {
sliceSize--;
@@ -38,9 +53,19 @@ public class NRR extends Scheduler {
public Process getProcess() {
return process;
}
+
+ @Override
+ public int compareTo(NarrowProcess other) {
+ return time.compareTo(other.getTime());
+ }
+
+ @Override
+ public int compare(NarrowProcess a, NarrowProcess b) {
+ return a.compareTo(b);
+ }
}
- private Queue<NarrowProcess> queue;
+ private ArrayList<NarrowProcess> queue;
private int slice;
/**
@@ -48,14 +73,16 @@ public class NRR extends Scheduler {
*/
public NRR() {
super();
- queue = new LinkedList<>();
+ queue = new ArrayList<>();
slice = 0;
+ prevPid = "";
}
public NRR(int switchProcessTime) {
super(switchProcessTime);
- queue = new LinkedList<>();
+ queue = new ArrayList<>();
slice = 0;
+ prevPid = "";
}
/**
@@ -65,7 +92,8 @@ public class NRR extends Scheduler {
*/
@Override
public void add(Process process) {
- queue.add(new NarrowProcess(process));
+ queue.add(new NarrowProcess(process, process.getArrivalTime()));
+ Collections.sort(queue);
}
/**
@@ -75,41 +103,43 @@ public class NRR extends Scheduler {
*/
@Override
public boolean empty() {
- return queue.peek() == null;
+ return queue.isEmpty();
}
@Override
- public void process(int time) {
- NarrowProcess head = queue.peek();
- if (head != null) {
- if (newProcess) {
- switching--;
- if (switching == 0) {
- switchProcess(time);
- }
- } else if (head.getProcess().process(time)) {
- processed.add(queue.poll().getProcess());
- newProcess = true;
+ public int process(int time) {
+ if (!queue.isEmpty()) {
+ NarrowProcess head = queue.get(0);
+ if (newProcess && !prevPid.equals(head.getProcess().getPid())) {
+ return switchProcess(time);
} else {
- slice = (slice + 1) % queue.peek().getSliceSize();
- if (slice == 0 && queue.size() > 1) {
- queue.add(queue.poll());
+ int processingTime = head.getProcess().process(time, head.getSliceSize());
+ prevPid = head.getProcess().getPid();
+ if (head.getProcess().finished()) {
+ processed.add(queue.remove(0).getProcess());
+ newProcess = true;
+ } else {
+ queue.remove(0);
+ head.setTime(time + processingTime);
+ queue.add(head);
newProcess = true;
}
+ return processingTime;
}
}
+ return 0;
}
@Override
- protected void switchProcess(int time) {
+ protected int switchProcess(int time) {
newProcess = false;
- switching = switchProcessTime;
slice = 0;
- queue.peek().decrementSliceSize();
+ queue.get(0).decrementSliceSize();
startTimes += String.format(
"T%d: %s\n",
time + 1,
- queue.peek().getProcess().getPid()
+ queue.get(0).getProcess().getPid()
);
+ return switchProcessTime;
}
}
diff --git a/Process.java b/Process.java
@@ -93,16 +93,20 @@ public class Process {
this.serviceTime = serviceTime;
}
- public boolean process(int time) {
+ public int process(int time, int slice) {
if (lastProcessedTime == arrivalTime) {
startTime = time;
}
waitingTime += (time - lastProcessedTime);
- turnaroundTime += (time - lastProcessedTime + 1);
- serviceTime--;
- lastProcessedTime = time + 1;
- // System.out.format("%s, wt: %d, tt: %d, st: %d, lpt: %d\n", pid, waitingTime, turnaroundTime, serviceTime, lastProcessedTime);
- return serviceTime == 0;
+ if (slice == 0) {
+ slice = serviceTime;
+ } else {
+ slice = Integer.min(slice, serviceTime);
+ }
+ turnaroundTime += (time - lastProcessedTime + slice);
+ serviceTime -= slice;
+ lastProcessedTime = time + slice;
+ return slice;
}
/**
@@ -132,6 +136,10 @@ public class Process {
return startTime;
}
+ public boolean finished() {
+ return serviceTime == 0;
+ }
+
public String toString() {
return pid;
}
diff --git a/RR.java b/RR.java
@@ -1,5 +1,6 @@
-import java.util.LinkedList;
-import java.util.Queue;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.Collections;
/**
* <h1>RR - Comp2240A1</h1>
@@ -12,9 +13,59 @@ import java.util.Queue;
*/
public class RR extends Scheduler {
+ String prevPid;
private static final int SLICE_SIZE = 4;
- private Queue<Process> queue;
+ private class RRProcess implements Comparable<RRProcess>, Comparator<RRProcess> {
+ private Process process;
+ private int sliceSize;
+ private boolean used;
+ private Integer time;
+
+ public RRProcess(Process process, int time) {
+ this.process = process;
+ sliceSize = 4;
+ used = false;
+ this.time = time;
+ }
+
+ public int getSliceSize() {
+ return sliceSize;
+ }
+
+
+ public Integer getTime() {
+ return time;
+ }
+
+ public void setTime(int time) {
+ this.time = time;
+ }
+
+ public void decrementSliceSize() {
+ if (used) {
+ sliceSize--;
+ } else {
+ used = true;
+ }
+ }
+
+ public Process getProcess() {
+ return process;
+ }
+
+ @Override
+ public int compareTo(RRProcess other) {
+ return time.compareTo(other.getTime());
+ }
+
+ @Override
+ public int compare(RRProcess a, RRProcess b) {
+ return a.compareTo(b);
+ }
+ }
+
+ private ArrayList<RRProcess> queue;
private int slice;
/**
@@ -22,14 +73,16 @@ public class RR extends Scheduler {
*/
public RR() {
super();
- queue = new LinkedList<>();
+ queue = new ArrayList<>();
slice = 0;
+ prevPid = "";
}
public RR(int switchProcessTime) {
super(switchProcessTime);
- queue = new LinkedList<>();
+ queue = new ArrayList<>();
slice = 0;
+ prevPid = "";
}
/**
@@ -39,7 +92,8 @@ public class RR extends Scheduler {
*/
@Override
public void add(Process process) {
- queue.add(process);
+ queue.add(new RRProcess(process, process.getArrivalTime()));
+ Collections.sort(queue);
}
/**
@@ -49,40 +103,43 @@ public class RR extends Scheduler {
*/
@Override
public boolean empty() {
- return queue.peek() == null;
+ return queue.isEmpty();
}
@Override
- public void process(int time) {
- Process head = queue.peek();
- if (head != null) {
- if (newProcess) {
- switching--;
- if (switching == 0) {
- switchProcess(time);
- }
- } else if (head.process(time)) {
- processed.add(queue.poll());
- newProcess = true;
+ public int process(int time) {
+ if (!queue.isEmpty()) {
+ RRProcess head = queue.get(0);
+ if (newProcess && !prevPid.equals(head.getProcess().getPid())) {
+ return switchProcess(time);
} else {
- slice = (slice + 1) % SLICE_SIZE;
- if (slice == 0 && queue.size() > 1) {
- queue.add(queue.poll());
+ int processingTime = head.getProcess().process(time, SLICE_SIZE);
+ prevPid = head.getProcess().getPid();
+ if (head.getProcess().finished()) {
+ processed.add(queue.remove(0).getProcess());
+ newProcess = true;
+ } else {
+ queue.remove(0);
+ head.setTime(time + processingTime);
+ queue.add(head);
newProcess = true;
}
+ return processingTime;
}
}
+ return 0;
}
@Override
- protected void switchProcess(int time) {
+ protected int switchProcess(int time) {
newProcess = false;
- switching = switchProcessTime;
slice = 0;
+ queue.get(0).decrementSliceSize();
startTimes += String.format(
"T%d: %s\n",
time + 1,
- queue.peek().getPid()
+ queue.get(0).getProcess().getPid()
);
+ return switchProcessTime;
}
}
diff --git a/Scheduler.java b/Scheduler.java
@@ -15,21 +15,18 @@ public abstract class Scheduler {
protected ArrayList<Process> processed;
protected Integer switchProcessTime;
protected boolean newProcess;
- protected Integer switching;
protected String startTimes;
protected Scheduler() {
processed = new ArrayList<>();
switchProcessTime = 0;
newProcess = true;
- switching = switchProcessTime;
startTimes = "";
}
protected Scheduler(int switchProcessTime) {
this();
this.switchProcessTime = switchProcessTime;
- switching = switchProcessTime;
}
/**
@@ -46,7 +43,7 @@ public abstract class Scheduler {
*/
public abstract boolean empty();
- public abstract void process(int time);
+ public abstract int process(int time);
/**
* Give the results of the simulation, such as the times the process was
@@ -61,7 +58,7 @@ public abstract class Scheduler {
stats += "\nProcess Turnaround Time Waiting Time\n";
for (Process process : processed) {
stats += String.format(
- "%s %d %d\n",
+ "%s\t%d\t\t%d\n",
process.getPid(),
process.getTurnaroundTime(),
process.getWaitingTime()
@@ -87,8 +84,8 @@ public abstract class Scheduler {
avgTurnaround /= processed.size();
avgWaiting /= processed.size();
- return String.format("%.2f %.2f", avgTurnaround, avgWaiting);
+ return String.format("%.2f\t\t\t%.2f", avgTurnaround, avgWaiting);
}
- protected abstract void switchProcess(int time);
+ protected abstract int switchProcess(int time);
}
