memory-and-process-scheduler

git clone git://git.codymlewis.com/memory-and-process-scheduler.git
Log | Files | Refs | README

commit ab5c14aa23252d3414c76bc122ac2d6d3522b8ee
Author: Cody Lewis <cody@codymlewis.com>
Date:   Tue, 15 Oct 2019 10:23:31 +1100

Initial commit

Diffstat:
A.gitignore | 3+++
AA3.java | 46++++++++++++++++++++++++++++++++++++++++++++++
AClock.java | 52++++++++++++++++++++++++++++++++++++++++++++++++++++
AFrameBuffer.java | 49+++++++++++++++++++++++++++++++++++++++++++++++++
ALRU.java | 66++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AMakefile | 14++++++++++++++
AMemory.java | 24++++++++++++++++++++++++
AProcess.java | 91+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
AReport.md | 20++++++++++++++++++++
AScheduler.java | 125+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Areadme.txt | 13+++++++++++++
11 files changed, 503 insertions(+), 0 deletions(-)

diff --git a/.gitignore b/.gitignore @@ -0,0 +1,3 @@ +*.class +*.pdf +Session.vim diff --git a/A3.java b/A3.java @@ -0,0 +1,46 @@ +import java.util.LinkedList; +import java.util.ArrayList; +import java.util.Arrays; + +public class A3 { + public static void main(String args[]) { + if (args.length < 3) { + System.err.println("Error: Not enough arguments supplied."); + System.err.println("Usage: java A3 <F> <Q> <INPUT_FILES>"); + System.exit(1); + } + try { + A3 runner = new A3(); + System.exit( + runner.run( + Integer.parseInt(args[0]), + Integer.parseInt(args[1]), + new ArrayList<String>(Arrays.asList(Arrays.copyOfRange(args, 2, args.length))) + ) + ); + } catch (Exception e) { + e.printStackTrace(); + } + } + + public int run(int frames, int quantum, ArrayList<String> processFiles) throws Exception { + int framesPerProcess = (int) Math.floor(frames / processFiles.size()); + runWithPolicy(framesPerProcess, quantum, processFiles, "LRU"); + System.out.println("------------------------------------------------------------"); + System.out.println(); + runWithPolicy(framesPerProcess, quantum, processFiles, "Clock"); + return 0; + } + + public void runWithPolicy(int framesPerProcess, int quantum, + ArrayList<String> processFiles, String fbname) throws Exception { + LinkedList<Process> processes = new LinkedList<Process>(); + for(int i = 0; i < processFiles.size(); ++i) { + processes.add(new Process(i + 1, processFiles.get(i), framesPerProcess, fbname)); + } + Scheduler scheduler = new Scheduler(processes, quantum); + scheduler.run(); + System.out.format("%s - Fixed\n", fbname); + System.out.println(scheduler.summary()); + } +} diff --git a/Clock.java b/Clock.java @@ -0,0 +1,52 @@ +import java.util.ArrayList; + +/** + * Clock - COMP2240A3 + * Clock memory management policy + * + * @author Cody Lewis (c3283349) + */ + +public class Clock extends FrameBuffer { + private ArrayList<Boolean> useFlags; + private int current; + + /** + * Input constructor + * + * @param totalFrames Total amount of frames that can be used for the process + */ + public Clock(int totalFrames) { + super(totalFrames); + useFlags = new ArrayList<>(totalFrames); + for (int i = 0; i < totalFrames; ++i) { + useFlags.add(false); + } + current = 0; + } + + /** + * Replace a page according to the policy + * + * @param newPage The page the needs to be loaded + */ + @Override + public void replace(Integer newPage) { + while (useFlags.get(current)) { + useFlags.set(current, false); + incrementCurrent(); + } + loadedPages.remove(buffer.get(current)); + buffer.set(current, newPage); + loadedPages.put(buffer.get(current), current); + useFlags.set(current, true); + incrementCurrent(); + } + + /** + * Increment the frame that that this current points to + */ + private void incrementCurrent() { + current = (current + 1) % totalFrames; + } +} diff --git a/FrameBuffer.java b/FrameBuffer.java @@ -0,0 +1,49 @@ +import java.util.HashMap; +import java.util.Map; +import java.util.ArrayList; + +/** + * FrameBuffer - COMP2240A3 + * Abstract implementation of a buffer of frames for a process. + * + * @author Cody Lewis (c3283349) + */ + +public abstract class FrameBuffer { + protected Map<Integer, Integer> loadedPages; + protected int totalFrames; + protected ArrayList<Integer> buffer; + + /** + * Input constructor + * + * @param totalFrames Total amount of frames that can be used for the process + */ + public FrameBuffer(int totalFrames) { + loadedPages = new HashMap<>(); + this.totalFrames = totalFrames; + buffer = new ArrayList<>(totalFrames); + for (int i = 0; i < totalFrames; ++i) { + buffer.add(0); + } + } + + /** + * Replace a page according to the policy + * + * @param newPage The page the needs to be loaded + */ + public abstract void replace(Integer newPage); + + /** + * Use a page + */ + public void use(int page) {} + + /** + * Check whether a page is loaded + */ + public boolean isLoaded(Integer pageid) { + return loadedPages.containsKey(pageid); + } +} diff --git a/LRU.java b/LRU.java @@ -0,0 +1,66 @@ +import java.util.LinkedList; +import java.util.ArrayList; +import java.util.Collections; + +public class LRU extends FrameBuffer { + private class LRUPage implements Comparable<LRUPage> { + Integer time; + int id; + + public LRUPage(int id, int time) { + this.id = id; + this.time = time; + } + + public void use(int time) { + this.time = time; + } + + public int getId() { + return id; + } + + public Integer getTime() { + return time; + } + + public int compareTo(LRUPage other) { + return time.compareTo(other.getTime()); + } + + public String toString() { + return String.format("{id: %d, time: %d}", id, time); + } + } + + private ArrayList<LRUPage> lrubuffer; + private int counter; // Counts time relativistically + + + public LRU(int totalFrames) { + super(totalFrames); + lrubuffer = new ArrayList<>(); + counter = 0; + } + + @Override + public void replace(Integer newPage) { + int replaceFrameNum; + if (lrubuffer.size() == totalFrames) { + replaceFrameNum = loadedPages.get(Collections.min(lrubuffer).getId()); + loadedPages.remove(buffer.get(replaceFrameNum)); + lrubuffer.set(replaceFrameNum, new LRUPage(newPage, counter)); + } else { + replaceFrameNum = lrubuffer.size(); + lrubuffer.add(new LRUPage(newPage, counter)); + } + buffer.set(replaceFrameNum, newPage); + loadedPages.put(buffer.get(replaceFrameNum), replaceFrameNum); + } + + @Override + public void use(int page) { + counter++; + lrubuffer.get(loadedPages.get(page)).use(counter); + } +} diff --git a/Makefile b/Makefile @@ -0,0 +1,14 @@ +all: clean compile run + +clean: + $(RM) *.class + +compile: + javac A3.java + +run: + java A3 30 3 ../SampleInputOutput/S1/process1.txt ../SampleInputOutput/S1/process2.txt ../SampleInputOutput/S1/process3.txt ../SampleInputOutput/S1/process4.txt;\ + java A3 30 3 ../SampleInputOutput/S2/process1.txt ../SampleInputOutput/S2/process2.txt ../SampleInputOutput/S2/process3.txt + +report: + pandoc Report.md -s --highlight-style=pygments -o Report.pdf diff --git a/Memory.java b/Memory.java @@ -0,0 +1,24 @@ +import java.util.ArrayList; +import java.util.Map; +import java.util.HashMap; + +public class Memory { + private class Page { + int id; + + public Page(int id) { + this.id = id; + } + } + + ArrayList<Page> frames; + int maxFrames; + Map<Integer, Integer> pageMap; + FrameBuffer fbuffer; + + public Memory(int numberFrames) { + maxFrames = numberFrames; + frames = new ArrayList<>(numberFrames); + pageMap = new HashMap<>(); + } +} diff --git a/Process.java b/Process.java @@ -0,0 +1,91 @@ +import java.util.Queue; +import java.util.LinkedList; +import java.util.Scanner; +import java.io.File; +import java.io.FileNotFoundException; + +/** + * Process - COMP2240A3 + * A process class + * + * @author Cody Lewis (c3283349) + */ + +public class Process { + // The Integer specifies the page request + private Queue<Integer> instructions; + private String name; + private int pid; + private FrameBuffer fbuffer; + private int timeBlockedTo; + private LinkedList<Integer> faultTimes; + + public Process(int pid, String filename, int maxFrames, String fbname) throws FileNotFoundException { + name = filename; + this.pid = pid; + faultTimes = new LinkedList<>(); + instructions = readInstructionFile(filename); + fbuffer = FBFactory(fbname, maxFrames); + timeBlockedTo = -1; + } + + private Queue<Integer> readInstructionFile(String filename) throws FileNotFoundException { + Scanner fstream = new Scanner(new File(filename)); + Queue<Integer> result = new LinkedList<Integer>(); + // TODO: Add some errors for incorrect file format + String line = fstream.nextLine(); + while (!(line = fstream.nextLine()).equals("end")) { + result.offer(Integer.parseInt(line)); + } + return result; + } + + private FrameBuffer FBFactory(String fbname, int maxFrames) { + switch(fbname) { + case "Clock": + return new Clock(maxFrames); + default: + return new LRU(maxFrames); + } + } + + public boolean isReady(int time) { + int nextInstruction = instructions.peek(); + if (!fbuffer.isLoaded(nextInstruction)) { + fbuffer.replace(nextInstruction); + timeBlockedTo = time + 5; + faultTimes.add(time); + } + return timeBlockedTo < time; + } + + public int run() { + int page = instructions.poll(); + fbuffer.use(page); + return 1; + } + + public boolean isFinished() { + return instructions.isEmpty(); + } + + public String getName() { + return name; + } + + public Integer getPid() { + return pid; + } + + public int getNumberFaults() { + return faultTimes.size(); + } + + public String getFaultTimes() { + return faultTimes.toString().replace("[", "{").replace("]", "}"); + } + + public String toString() { + return String.format("{pid: %d, instructions_left: %d}", pid, instructions.size()); + } +} diff --git a/Report.md b/Report.md @@ -0,0 +1,20 @@ +--- +title: COMP2240 Assignment 3 +author: Cody Lewis [mailto:c3283349@uon.edu.au](c3283349@uon.edu.au) +date: \today +linkcolor: blue +geometry: margin=2cm +--- + +\begin{equation} + \#_{frames_{process}} = \left \lfloor \frac{F}{\#_{processes}} \right \rfloor +\end{equation} + +# Least Recently Used + +I used a binary tree to sort the frames by time of use as I found that to be the +least complex to use and update, $\mathcal{O}(\log n)$, as opposed to a list, which +would be $\mathcal{O}(n\log n)$ on every update. Although, a list or queue would +have faster add and remove operations, $\mathcal{O}(1)$, the update is likely a +more common operation in the case of a sheduler, and the combined complexity +of the operations, make the tree better. diff --git a/Scheduler.java b/Scheduler.java @@ -0,0 +1,125 @@ +import java.util.LinkedList; +import java.util.ArrayList; +import java.util.Iterator; +import java.util.Collections; + +/** + * Scheduler - COMP2240A3 + * The round robin Scheduler + * + * @author Cody Lewis (c3283349) + */ + +public class Scheduler { + private class ScheduledProcess implements Comparable<ScheduledProcess> { + private Process process; + private int slicePoint; + private int turnaroundTime; + + public ScheduledProcess(Process process, int slicePoint) { + this.process = process; + this.slicePoint = slicePoint; + turnaroundTime = 0; + } + + public Process getProcess() { + return process; + } + + public void setSlice(int slicePoint) { + this.slicePoint = slicePoint; + } + + public int getCurSlice() { + return slicePoint; + } + + public void decrementSlice() { + slicePoint--; + } + + public void finish(int time) { + turnaroundTime = time; + } + + public String summary() { + return String.format( + "%d\t%s\t%d\t%d\t%s", + process.getPid(), + process.getName(), + turnaroundTime, + process.getNumberFaults(), + process.getFaultTimes() + ); + } + + @Override + public int compareTo(ScheduledProcess other) { + return process.getPid().compareTo(other.getProcess().getPid()); + } + + public String toString() { + return String.format("{process: %s, slice: %d}", process.toString(), slicePoint); + } + } + + private LinkedList<ScheduledProcess> processes; + private int quantum; + private int time; + private LinkedList<ScheduledProcess> finishedProcesses; + + public Scheduler(LinkedList<Process> processes, int quantum) { + this.processes = new LinkedList<>(); + finishedProcesses = new LinkedList<>(); + processes.stream().forEach(p -> this.processes.add(new ScheduledProcess(p, quantum))); + this.quantum = quantum; + time = 0; + } + + public void run() { + while (!processes.isEmpty()) { + Iterator<ScheduledProcess> it = processes.iterator(); + ScheduledProcess current = null; + while (it.hasNext()) { + current = it.next(); + if (current.getProcess().isReady(time)) { + break; + } else { + current = null; + } + } + if (current == null) { + time++; + } else { + while (!current.getProcess().isFinished() && + current.getProcess().isReady(time) && + current.getCurSlice() > 0) { + current.getProcess().run(); + time++; + current.decrementSlice(); + } + if (current.getProcess().isFinished() || + current.getProcess().isReady(time) || + current.getCurSlice() == 0) { + it.remove(); + if (!current.getProcess().isFinished()) { + current.setSlice(quantum); + processes.add(current); + } else { + current.finish(time); + finishedProcesses.add(current); + } + } + } + } + } + + public String summary() { + String result = "PID\tProcess Name\tTurnaround Time\t# Faults\tFault Times\n"; + Collections.sort(finishedProcesses); + for (ScheduledProcess finishedProcess : finishedProcesses) { + result += finishedProcess.summary() + "\n"; + } + return result; + } +} diff --git a/readme.txt b/readme.txt @@ -0,0 +1,13 @@ +# COMP2240 Assignment 3 + +## Compile + +``` +javac A3.java +``` + +## Run + +``` +java A3 <F> <Q> <PROCESS_FILES> +```