操作系统中的调度算法FCFS、SJF、RR算法（Java实现）

Proce类： package five;

public class Process { public String name;// 进程名称 public int arrivalTime;// 到达时间 public int serviceTime;// 服务时间 public int finishTime;// 完成时间 public int startTime;// 开始时间 public int WholeTime;// 周转时间 public double weightWholeTime;// 带权周转时间 private int remainServiceTime; // 还需要服务的时间

Process(int arrivalTime, int serviceTime, String name) { this.arrivalTime = arrivalTime; this.serviceTime = serviceTime; this.remainServiceTime = serviceTime; this.name = name; }

//name的set()和get() public String getName() { return name; }

public void setName(String name) { this.name = name; }

//arrivalTime public int getArrivalTime() { return arrivalTime; }

public void setArrivalTime(int arrivalTime) { this.arrivalTime = arrivalTime; }

//ServiceTime public int getServiceTime() { return serviceTime; }

public void setServiceTime(int serviceTime) { this.serviceTime = serviceTime; }

//finishTime public int getFinishTime() { return finishTime; }

public void setFinishTime(int finishTime) { this.finishTime = finishTime; }

//startTime public int getStartTime() { return startTime; }

public void setStartTime(int startTime) { this.startTime = startTime; } public int getWholeTime() { return WholeTime; } public void setWholeTime(int wholeTime) { WholeTime = wholeTime; } public double getWeightWholeTime() { return weightWholeTime; } public void setWeightWholeTime(double weightWholeTime) { this.weightWholeTime = weightWholeTime; } public int getRemainServiceTime() { return remainServiceTime; } public void setRemainServiceTime(int remainServiceTime) { this.remainServiceTime = remainServiceTime; } @Override public String toString() { return "名称：" + name + " 到达时间：" + arrivalTime + " 服务时间：" + serviceTime; }

}

RR算法的类： 4 package five;

import java.util.LinkedList; import java.util.Queue; import java.util.concurrent.LinkedBlockingQueue;

public class RR { private int ProcessCount; // 进程数 private Queue ReadyQueue; // 就绪队列，存放“待运行的进程 private Queue UnreachQueue; // 存放可执行的进程 private int TimeSlice; // 时间片

private Queue<Process> ExecutedQueue; // 执行完毕的进程队列 private double mTotalWholeTime = 0.0; private double mTotalWeightWholeTime = 0.0; public RR(int processCount, Queue<Process> processQueue, int timeSlice) { this.ProcessCount = processCount; this.UnreachQueue = processQueue; ReadyQueue = new LinkedBlockingQueue<>(); this.TimeSlice = timeSlice; ExecutedQueue = new LinkedList<>(); } private int executeProcess(Process currProcess, int currTime) { if (currProcess.getRemainServiceTime() - TimeSlice <= 0) { // 当前进程在这个时间片内能执行完毕 showExecuteMessage(currTime, currTime += currProcess.getRemainServiceTime(), currProcess.getName()); currProcess.setFinishTime(currTime); currProcess.setRemainServiceTime(0); // 对周转时间等进行计算 calculeteWholeTime(currProcess); calculateWeightWholeTime(currProcess); mTotalWholeTime += currProcess.getWholeTime(); mTotalWeightWholeTime += currProcess.getWeightWholeTime(); ExecutedQueue.add(currProcess);// 加入完成队列 } else { // 不能执行完毕 showExecuteMessage(currTime, currTime += TimeSlice, currProcess.getName()); currProcess.setRemainServiceTime(currProcess.getRemainServiceTime() - TimeSlice);// 更新该进程的剩余时间 } return currTime; } /** * RR 算法实现 */ public void RRAlgorithm() { ReadyQueue.add(UnreachQueue.poll()); Process currProcess = ReadyQueue.poll(); // 第一个进程执行 int currTime = executeProcess(currProcess, 0);// 更新时间 while (!ReadyQueue.isEmpty() || !UnreachQueue.isEmpty()) { // 把所有“到达时间”达到的进程加入运行队列头部 while (!UnreachQueue.isEmpty()) { if (UnreachQueue.peek().getArrivalTime() <= currTime) {// 取队列头，比较是否到达 ReadyQueue.add(UnreachQueue.poll());// 将可执行队列头部的元素移除并加到就绪队列 } else { break; } } if (currProcess.getRemainServiceTime() > 0)// 未执行完毕，将该进程添加到队列尾 ReadyQueue.add(currProcess); // 运行队列不为空时,继续操作下一个进程 if (!ReadyQueue.isEmpty()) { currProcess = ReadyQueue.poll(); currTime = executeProcess(currProcess, currTime); } else { // 当前没有进程执行，但还有进程未到达，时间直接跳转到到达时间 currTime = UnreachQueue.peek().getArrivalTime(); } } } /** * 计算周转时间 * * @param process */ private void calculeteWholeTime(Process process) { process.setWholeTime(process.getFinishTime() - process.getArrivalTime()); } /** * 计算带权周转时间 * * @param process */ private void calculateWeightWholeTime(Process process) { process.setWeightWholeTime(process.getWholeTime() / (double) process.getServiceTime()); } private void showExecuteMessage(int startTime, int endTime, String name) { System.out.println(startTime + "～" + endTime + "：【进程" + name + "】运行"); } public void showResult() { System.out.print("进程名\t\t"); System.out.print("完成时间\t\t"); System.out.print("周转时间\t\t"); System.out.println("带权周转时间\t"); Process process; while (!ExecutedQueue.isEmpty()) { process = ExecutedQueue.poll(); System.out.print("进程" + process.getName() + "\t"); System.out.print("\t" + process.getFinishTime() + "\t"); System.out.print("\t" + process.getWholeTime() + "\t"); System.out.println("\t" + process.getWeightWholeTime() + "\t"); } System.out.println("平均周转时间：" + mTotalWholeTime / (double) ProcessCount); System.out.println("平均带权周转时间：" + mTotalWeightWholeTime / (double) ProcessCount); } public static void printAll(Queue<Process> queue) { System.out.print("进程名\t\t"); System.out.print("到达时间\t\t"); System.out.println("服务时间\t"); Process process = null; while (!queue.isEmpty()) { process = queue.poll(); System.out.print("进程" + process.getName() + "\t"); System.out.print("\t" + process.getArrivalTime() + "\t"); System.out.println("\t" + process.getServiceTime() + "\t"); } }

} 主函数： package five;

import java.text.DecimalFormat; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.concurrent.LinkedBlockingQueue;

public class FiveMain { public static void main(String[] args) {

Process[] p = new Process[5]; p[0] = new Process(0, 4, "A"); p[1] = new Process(1, 3, "B"); p[2] = new Process(2, 5, "C"); p[3] = new Process(3, 2, "D"); p[4] = new Process(4, 4, "E"); Queue<Process> queue = new LinkedBlockingQueue<>(); for (int i = 0; i < p.length; i++) { queue.add(p[i]); } Scanner in = new Scanner(System.in); while (true) { System.out.println("1：FCFS 2:SJF 3.RR 0:退出"); switch (in.nextInt()) { case 1: System.out.println("******************* FCFS *****************"); System.out.println("初始化5个进程ABCDE："); for (int i = 0; i < p.length; i++) { System.out.println(p[i].toString()); } FCFS(p); print(p); break; case 2: System.out.println("******************* SJF *****************"); System.out.println("初始化5个进程ABCDE："); for (int i = 0; i < p.length; i++) { System.out.println(p[i].toString()); } Process[] processes = SJF(p); print(processes); break; case 3: System.out.println("******************* RR *****************"); System.out.println("初始化5个进程ABCDE："); for (int i = 0; i < p.length; i++) { System.out.println(p[i].toString()); } RR rr = new RR(5, queue, 1); System.out.println("******************运行过程*****************"); rr.RRAlgorithm(); System.out.println("*******************运行结果*****************"); rr.showResult(); break; case 0: // 退出 System.exit(0); break; default: System.out.println("输入错误，请重新输入！"); break; } } } // 插入排序 public static void InsertSort(Process[] array) { int i, j; int n = array.length; Process target; for (i = 1; i < n; i++) { j = i; target = array[i]; while (j > 0 && target.arrivalTime < array[j - 1].arrivalTime) { array[j] = array[j - 1]; j--; } array[j] = target; } } // FCFS算法 public static void FCFS(Process[] p) { InsertSort(p); for (int i = 0; i < p.length; i++) { if (i == 0) { p[i].finishTime = p[i].arrivalTime + p[i].serviceTime; p[i].startTime = p[i].arrivalTime; } else { if (p[i].arrivalTime > p[i - 1].finishTime) { p[i].finishTime = p[i].arrivalTime + p[i].serviceTime; p[i].startTime = p[i].arrivalTime; } else { p[i].finishTime = p[i - 1].finishTime + p[i].serviceTime; p[i].startTime = p[i - 1].finishTime; } } // 计算周转时间和带权周转时间 p[i].WholeTime = p[i].finishTime - p[i].arrivalTime; p[i].weightWholeTime = (float) p[i].WholeTime / p[i].serviceTime; } } // 找出下一个处理的进程 public static Process FindNextPro(LinkedList<Process> list, int now) { Process process = list.get(0); int index = 0; for (int i = 1; i < list.size(); i++) { if (list.get(i).serviceTime < process.serviceTime && list.get(i).arrivalTime < now) {// 判断条件找到服务时间最短的进程并且已经到达 process = list.get(i); index = i; } } list.remove(index); return process; }

//SJF算法 public static Process[] SJF(Process[] p) { // 待处理 LinkedList list = new LinkedList<>(); // 结果 LinkedList result = new LinkedList<>(); // 当前时间 int now = 0; // 按到达时间排序 InsertSort§; // 对第一个进程操作 p[0].finishTime = p[0].arrivalTime + p[0].serviceTime; p[0].WholeTime = p[0].finishTime - p[0].arrivalTime; p[0].weightWholeTime = (float) p[0].WholeTime / p[0].serviceTime; // 添加到结果 result.add(p[0]); // 更新时间 now = p[0].finishTime; // 将剩余添加到待处理 for (int i = 1; i < p.length; i++) { list.add(p[i]);

} while (list.size() != 0) { Process next = FindNextPro(list, now);// 找到当前队列中服务时间最短的进程 if (next.arrivalTime > now) {// 未到 next.finishTime = next.arrivalTime + next.serviceTime; next.startTime = next.arrivalTime; } else {// 到达 next.finishTime = now + next.serviceTime; next.startTime = now; } now = next.finishTime;// 更新时间 next.WholeTime = next.finishTime - next.arrivalTime; next.weightWholeTime = (float) next.WholeTime / next.serviceTime; result.add(next);// 添加到结果队列 } Process[] res = new Process[result.size()]; return result.toArray(res); } public static void print(Process[] p) { DecimalFormat df = new DecimalFormat("#.00"); float sumWT = 0; float sumWWT = 0; float AverageWT; float AverageWWT; for (int i = 0; i < p.length; i++) { System.out.println("时刻" + p[i].startTime + ": 进程" + p[i].name + "开始运行 完成时间为:" + p[i].finishTime + " 周转时间为：" + p[i].WholeTime + " 带权周转时间为：" + df.format(p[i].weightWholeTime)); sumWT += p[i].WholeTime; sumWWT += p[i].weightWholeTime; } AverageWT = sumWT / p.length; AverageWWT = sumWWT / p.length; System.out.println("平均周转时间为：" + df.format(AverageWT)); System.out.println("平均带权周转时间为：" + df.format(AverageWWT)); System.out.println("---------------------------------------------------------"); }

}