scheduler-simulator

git clone git://git.codymlewis.com/scheduler-simulator.git
Log | Files | Refs | README

commit c70b2ecf64876cb0bfee87411b36c72814c650e0
Author: Cody Lewis <cody@codymlewis.com>
Date:   Wed, 21 Aug 2019 09:55:27 +1000

Added four completed schedulers

Diffstat:
A.gitignore | 45+++++++++++++++++++++++++++++++++++++++++++++
AA1.java | 48++++++++++++++++++++++++++++++++++++++++++++++++
ADispatcher.java | 153+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AFB.java | 146+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AFCFS.java | 76++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AInvalidDataException.java | 6++++++
ANRR.java | 115+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AProcess.java | 140+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ARR.java | 88+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AReport.md | 14++++++++++++++
AScheduler.java | 94+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
ASortbyPid.java | 7+++++++
Areadme.txt | 17+++++++++++++++++
13 files changed, 949 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,45 @@ +### Java ### +# Compiled class file +*.class + +# Log file +*.log + +# BlueJ files +*.ctxt + +# Mobile Tools for Java (J2ME) +.mtj.tmp/ + +# Package Files # +*.jar +*.war +*.nar +*.ear +*.zip +*.tar.gz +*.rar + +# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml +hs_err_pid* + +### Vim ### +# Swap +[._]*.s[a-v][a-z] +[._]*.sw[a-p] +[._]s[a-rt-v][a-z] +[._]ss[a-gi-z] +[._]sw[a-p] + +# Session +Session.vim +Sessionx.vim + +# Temporary +.netrwhist +*~ +# Auto-generated tag files +tags +# Persistent undo +[._]*.un~ +*.pdf diff --git a/A1.java b/A1.java @@ -0,0 +1,48 @@ +/** + * <h1>A1 - Comp2240</h1> + * + * The main interface class for the First Assignment of COMP2240 Operating + * Systems. This simulates and compares a few scheduling algortihms. + * + * + * @author Cody Lewis (c3283349) + * @version 1 + * @since 2019-08-16 + */ + +public class A1 { + public static void main(String args[]) { + if (args.length < 1) { + System.out.println("A1: missing an input file"); + System.out.println("Usage: java A1 INPUT_FILE"); + + System.exit(1); + } + + System.out.println("FCFS:"); + Dispatcher fcfs = new Dispatcher("FCFS", args[0]); + System.out.println(fcfs.run()); + + System.out.println("RR:"); + Dispatcher rr = new Dispatcher("RR", args[0]); + System.out.println(rr.run()); + + System.out.println("FB (constant):"); + Dispatcher fb = new Dispatcher("FB", args[0]); + System.out.println(fb.run()); + + System.out.println("NRR:"); + Dispatcher nrr = new Dispatcher("NRR", args[0]); + 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.exit(0); + } + +} diff --git a/Dispatcher.java b/Dispatcher.java @@ -0,0 +1,153 @@ +import java.util.ArrayList; +import java.util.LinkedList; +import java.util.Map; +import java.util.HashMap; +import java.util.Scanner; +import java.io.File; + +/** + * <h1>Dispatcher - Comp2240A1</h1> + * + * A class for the Dispatcher, it manages the process execution simulation and + * is composed of a scheduler. + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +public class Dispatcher { + private Scheduler scheduler; + private int switchProcessTime; + private Map<Integer, LinkedList<Process>> processes; + + /** + * Default constructor + */ + public Dispatcher() { + } + + /** + * Input constructor + * + * @param schedulerAlgorithm Name of the scheduler algorithm to use + * @param filename Name of the data file + */ + public Dispatcher(String schedulerAlgorithm, String filename) { + this(); + processes = parseDataFile(filename); + scheduler = schedulerFactory(schedulerAlgorithm); + } + + /** + * Read the data file and construct a map between the time of the process + * and the list of processes. + * + * @param filename Name of the file to read + * @return Map between time of process and the list of processes + */ + private Map<Integer, LinkedList<Process>> parseDataFile(String filename) { + Map<Integer, LinkedList<Process>> data = new HashMap<>(); + + try (Scanner fstream = new Scanner(new File(filename))) { + String curLine = fstream.nextLine(); + if (!curLine.contains("BEGIN")) { + throw new InvalidDataException(); + } + fstream.nextLine(); + curLine = fstream.nextLine(); + Scanner sstream = new Scanner(curLine); + if (!sstream.next().contains("DISP:")) { + throw new InvalidDataException(); + } + switchProcessTime = sstream.nextInt(); + if (!fstream.nextLine().contains("END")) { + throw new InvalidDataException(); + } + String pid = ""; + int arrivalTime = 0; + int serviceTime = 0; + while (!(curLine = fstream.nextLine()).contains("EOF")) { + if (curLine.length() > 1) { + sstream = new Scanner(curLine); + switch (sstream.next()) { + case "ID:": + pid = sstream.next(); + break; + case "Arrive:": + arrivalTime = sstream.nextInt(); + break; + case "ExecSize:": + serviceTime = sstream.nextInt(); + break; + case "END": + if (data.get(arrivalTime) == null) { + data.put( + arrivalTime, + new LinkedList<Process>() + ); + } + data.get(arrivalTime).add( + new Process(pid, arrivalTime, serviceTime) + ); + } + } + } + } catch (Exception e) { + e.printStackTrace(); + } + + return data; + } + + /** + * Factory method to choose the appropriate scheduler to compose this + * + * @param algorithm Name of the algorithm + * @return A scheduler running the chosen algorithm + */ + private Scheduler schedulerFactory(String algorithm) { + switch (algorithm) { + case "RR": + return new RR(switchProcessTime); + case "NRR": + return new NRR(switchProcessTime); + case "FB": + return new FB(switchProcessTime); + default: + return new FCFS(switchProcessTime); + } + } + + /** + * Run through the scheduled processes + * + * @return Results of the simulation + */ + public String run() { + int time = 0; + int timeProcessingTo = 0; + + while (processes.size() != 0 || !scheduler.empty()) { + if (processes.get(time) != null) { + for (Process process : processes.get(time)) { + scheduler.add(process); + } + processes.remove(time); + } + scheduler.process(time); + time++; + } + + return scheduler.results(); + } + + /** + * Give summary data of the simulation + * + * @return The average turnaroundTime and average waitingTime + */ + public String summary() { + return scheduler.summary(); + } +} diff --git a/FB.java b/FB.java @@ -0,0 +1,146 @@ +import java.util.ArrayList; +import java.util.Queue; +import java.util.PriorityQueue; +import java.util.Comparator; +import java.util.Collections; + +/** + * <h1>FB - Comp2240A1</h1> + * + * The round robin scheduler + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +public class FB extends Scheduler { + private static final int SLICE_SIZE = 4; + private String prevPid; + + private class FBProcess implements Comparable<FBProcess>, Comparator<FBProcess> { + private Process process; + private Integer priority; + + public FBProcess() { + priority = 0; + } + + public FBProcess(Process process) { + this.process = process; + priority = 0; + } + + public void incrementPriority() { + if (priority < 5) { + priority++; + } + } + + public Process getProcess() { + return process; + } + + public Integer getPriority() { + return priority; + } + + public int compareTo(FBProcess other) { + return priority.compareTo(other.getPriority()); + } + + public int compare(FBProcess a, FBProcess b) { + return a.compareTo(b); + } + + public String toString() { + return String.format("%s: %d", process.toString(), priority); + } + } + + private ArrayList<FBProcess> queue; + private int slice; + + /** + * Default constructor + */ + public FB() { + super(); + queue = new ArrayList<>(); + slice = 0; + prevPid = ""; + } + + public FB(int switchProcessTime) { + super(switchProcessTime); + queue = new ArrayList<>(); + slice = 0; + prevPid = ""; + } + + /** + * Add a process to the tail of the Queue + * + * @param process Process to add to the Queue + */ + @Override + public void add(Process process) { + queue.add(new FBProcess(process)); + // Collections.sort(queue, new FBProcess()); + } + + private void add(FBProcess process) { + queue.add(process); + Collections.sort(queue, new FBProcess()); + } + + /** + * Check whether the queue is empty + * + * @return True if the queue is empy else false + */ + @Override + public boolean empty() { + return queue.isEmpty(); + } + + @Override + public void process(int time) { + FBProcess head = queue.get(0); + if (head != null) { + 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; + } else { + slice = (slice + 1) % SLICE_SIZE; + if (slice == 0 && queue.size() > 1) { + head.incrementPriority(); + add(queue.remove(0)); + newProcess = true; + } + } + } + } + + @Override + protected void switchProcess(int time) { + newProcess = false; + switching = switchProcessTime; + slice = 0; + String curPid = queue.get(0).getProcess().getPid(); + if (!prevPid.equals(curPid)) { + startTimes += String.format( + "T%d: %s\n", + time + 1, + curPid + ); + } + prevPid = curPid; + } +} diff --git a/FCFS.java b/FCFS.java @@ -0,0 +1,76 @@ +import java.util.LinkedList; +import java.util.Queue; + +/** + * <h1>FCFS - Comp2240A1</h1> + * + * The first come fist served scheduler + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +public class FCFS extends Scheduler { + private Queue<Process> queue; + + /** + * Default constructor + */ + public FCFS() { + super(); + queue = new LinkedList<>(); + } + + public FCFS(int switchProcessTime) { + super(switchProcessTime); + queue = new LinkedList<>(); + } + + /** + * Add a process to the tail of the Queue + * + * @param process Process to add to the Queue + */ + @Override + public void add(Process process) { + queue.add(process); + } + + /** + * Check whether the queue is empty + * + * @return True if the queue is empy else false + */ + @Override + public boolean empty() { + return queue.peek() == null; + } + + @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; + } + } + } + + @Override + protected void switchProcess(int time) { + newProcess = false; + switching = switchProcessTime; + startTimes += String.format( + "T%d: %s\n", + time + 1, + queue.peek().getPid() + ); + } +} diff --git a/InvalidDataException.java b/InvalidDataException.java @@ -0,0 +1,6 @@ +public class InvalidDataException extends Exception { + static final long serialVersionUID = 1L; + public InvalidDataException() { + super("The format of the data file is invalid."); + } +} diff --git a/NRR.java b/NRR.java @@ -0,0 +1,115 @@ +import java.util.LinkedList; +import java.util.Queue; + +/** + * <h1>RR - Comp2240A1</h1> + * + * The round robin scheduler + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +public class NRR extends Scheduler { + private class NarrowProcess { + private Process process; + private int sliceSize; + private boolean used; + + public NarrowProcess(Process process) { + this.process = process; + sliceSize = 4; + used = false; + } + + public int getSliceSize() { + return sliceSize; + } + + public void decrementSliceSize() { + if (used) { + sliceSize--; + } else { + used = true; + } + } + + public Process getProcess() { + return process; + } + } + + private Queue<NarrowProcess> queue; + private int slice; + + /** + * Default constructor + */ + public NRR() { + super(); + queue = new LinkedList<>(); + slice = 0; + } + + public NRR(int switchProcessTime) { + super(switchProcessTime); + queue = new LinkedList<>(); + slice = 0; + } + + /** + * Add a process to the tail of the Queue + * + * @param process Process to add to the Queue + */ + @Override + public void add(Process process) { + queue.add(new NarrowProcess(process)); + } + + /** + * Check whether the queue is empty + * + * @return True if the queue is empy else false + */ + @Override + public boolean empty() { + return queue.peek() == null; + } + + @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; + } else { + slice = (slice + 1) % queue.peek().getSliceSize(); + if (slice == 0 && queue.size() > 1) { + queue.add(queue.poll()); + newProcess = true; + } + } + } + } + + @Override + protected void switchProcess(int time) { + newProcess = false; + switching = switchProcessTime; + slice = 0; + queue.peek().decrementSliceSize(); + startTimes += String.format( + "T%d: %s\n", + time + 1, + queue.peek().getProcess().getPid() + ); + } +} diff --git a/Process.java b/Process.java @@ -0,0 +1,140 @@ +/** + * <h1>Process - Comp2240A1</h1> + * + * A simple glorified struct style class for a process. + * + * @author Cody Lewis (c3283349) + * @version 1 + * @since 2019-08-16 + */ + +public class Process { + private String pid; // ID + private Integer arrivalTime; // Arrive + private Integer serviceTime; // ExecSize + private Integer turnaroundTime; + private Integer waitingTime; + private Integer lastProcessedTime; + private Integer startTime; + + /** + * The default constructor + */ + public Process() { + pid = ""; + arrivalTime = 0; + serviceTime = 0; + turnaroundTime = 0; + waitingTime = 0; + lastProcessedTime = 0; + startTime = 0; + } + + /** + * Member setting constructor + * + * @param pid process id + * @param arrivalTime time the the process arrived at the processor + * @param serviceTime time the process takes to execute + */ + public Process(String pid, int arrivalTime, int serviceTime) { + this(); + this.pid = pid; + this.arrivalTime = arrivalTime; + this.serviceTime = serviceTime; + this.lastProcessedTime = arrivalTime; + } + + /** + * Get the process id + * @return process id + */ + public String getPid() { + return pid; + } + + /** + * Get the time that the process arrived at the processor + * @return time that the process arrived at the processor + */ + public Integer getArrivalTime() { + return arrivalTime; + } + + /** + * Get the time that the process takes to execute + * @return time that the process takes to execute + */ + public Integer getServiceTime() { + return serviceTime; + } + + /** + * Set the process id + * @param pid process id + */ + public void setPid(String pid) { + this.pid = pid; + } + + /** + * Set the time that the process arrived at the processor + * @param arrivalTime time that the process arrived at the processor + */ + public void setArrivalTime(Integer arrivalTime) { + this.arrivalTime = arrivalTime; + } + + /** + * Set the time that the process takes to execute + * @param serviceTime time that the process takes to execute + */ + public void setServiceTime(Integer serviceTime) { + this.serviceTime = serviceTime; + } + + public boolean process(int time) { + 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; + } + + /** + * Get the turnaround time + * + * @return Time taken waiting and excuting + */ + public int getTurnaroundTime() { + return turnaroundTime; + } + + /** + * Get the waiting time + * + * @return Time taken waiting + */ + public int getWaitingTime() { + return waitingTime; + } + + /** + * Get the start time + * + * @return time when execution started + */ + public int getStartTime() { + return startTime; + } + + public String toString() { + return pid; + } + +} + diff --git a/RR.java b/RR.java @@ -0,0 +1,88 @@ +import java.util.LinkedList; +import java.util.Queue; + +/** + * <h1>RR - Comp2240A1</h1> + * + * The round robin scheduler + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +public class RR extends Scheduler { + private static final int SLICE_SIZE = 4; + + private Queue<Process> queue; + private int slice; + + /** + * Default constructor + */ + public RR() { + super(); + queue = new LinkedList<>(); + slice = 0; + } + + public RR(int switchProcessTime) { + super(switchProcessTime); + queue = new LinkedList<>(); + slice = 0; + } + + /** + * Add a process to the tail of the Queue + * + * @param process Process to add to the Queue + */ + @Override + public void add(Process process) { + queue.add(process); + } + + /** + * Check whether the queue is empty + * + * @return True if the queue is empy else false + */ + @Override + public boolean empty() { + return queue.peek() == null; + } + + @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; + } else { + slice = (slice + 1) % SLICE_SIZE; + if (slice == 0 && queue.size() > 1) { + queue.add(queue.poll()); + newProcess = true; + } + } + } + } + + @Override + protected void switchProcess(int time) { + newProcess = false; + switching = switchProcessTime; + slice = 0; + startTimes += String.format( + "T%d: %s\n", + time + 1, + queue.peek().getPid() + ); + } +} diff --git a/Report.md b/Report.md @@ -0,0 +1,14 @@ +--- +title: Comp2240 - Assignment 1 +author: Cody Lewis [c3283349@uon.edu.au](mailto:c3283349@uon.edu.au) +date: \today +geometry: margin=2cm +linkcolor: blue +--- + +# Datafile 1 + +The Narrow Round Robin scheduling algorithm was the best performing for the +first data file, and First Come First Served performed the worst. Both Round +Robin and Feedback performed equally in this case. All of the rankings for best +to worst are notably diff --git a/Scheduler.java b/Scheduler.java @@ -0,0 +1,94 @@ +import java.util.Collections; +import java.util.ArrayList; + +/** + * <h1>Scheduler - Comp2240A1</h1> + * + * Interface for the scheduler classes + * + * @author Cody Lewis + * @version 1 + * @since 2019-08-17 + */ + +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; + } + + /** + * Add a process to the scheduler + * + * @param process Process to add to the schedule + */ + public abstract void add(Process process); + + /** + * Check whether the schedule is empty + * + * @return True if schedule is empty else false + */ + public abstract boolean empty(); + + public abstract void process(int time); + + /** + * Give the results of the simulation, such as the times the process was + * execute + * + * @return Results of the simulation + */ + public String results() { + String stats = ""; + Collections.sort(processed, new SortbyPid()); + stats += startTimes; + stats += "\nProcess Turnaround Time Waiting Time\n"; + for (Process process : processed) { + stats += String.format( + "%s %d %d\n", + process.getPid(), + process.getTurnaroundTime(), + process.getWaitingTime() + ); + } + + return stats; + } + + /** + * Give summary data of the simulation + * + * @return The average turnaroundTime and average waitingTime + */ + public String summary() { + double avgTurnaround = 0; + double avgWaiting = 0; + + for (Process process : processed) { + avgTurnaround += process.getTurnaroundTime(); + avgWaiting += process.getWaitingTime(); + } + avgTurnaround /= processed.size(); + avgWaiting /= processed.size(); + + return String.format("%.2f %.2f", avgTurnaround, avgWaiting); + } + + protected abstract void switchProcess(int time); +} diff --git a/SortbyPid.java b/SortbyPid.java @@ -0,0 +1,7 @@ +import java.util.Comparator; + +public class SortbyPid implements Comparator<Process> { + public int compare(Process a, Process b) { + return a.getPid().compareTo(b.getPid()); + } +} diff --git a/readme.txt b/readme.txt @@ -0,0 +1,17 @@ +--- +title: Comp2240 - Assignment 1 +author: Cody Lewis (c3283349) +date: 2019-08-20 +--- + +# Compiling + +``` +javac A1.java +``` + +# Running + +``` +java A1 INPUT_FILE +```