进程调度的两种算法JAVA实现----FCFS(先来先服务)和SJF(最短作业优先)

来源:互联网 时间:1970-01-01

(SJF分为preemptive shortest job first(抢占式)和non-preemptive shortest job first(非抢占式),本位涉及的是后者,前者比后者复杂)

 

FCFS核心代码如下:

 1 package me.ares.algorithms; 2 3 import java.util.List; 4 import me.ares.domain.Process; 5 import me.ares.utils.ProcessUtil; 6 7 public class FCFS { 8 private List<Process> processes; 9 10 public FCFS(String fileString){11 processes = ProcessUtil.readProcesses(fileString);12 }13 14 public void execute(){15 ProcessUtil.sortByArrivalTime(processes);16 int currentTime = 0;17 for (int i = 0; i < processes.size(); i++) {18 System.out.println("时刻"+currentTime+": 进程"+processes.get(i).getProcessID()+"启动");19 if(processes.get(i).getArrivalTime()>=currentTime){20 processes.get(i).setStartingTime(processes.get(i).getArrivalTime());21 processes.get(i).setFinishingTime(processes.get(i).getStartingTime()+processes.get(i).getServiceTime());22 processes.get(i).setTurnAroundTime(processes.get(i).getFinishingTime()-processes.get(i).getArrivalTime());23 processes.get(i).setAverageTAT((double)processes.get(i).getTurnAroundTime() / processes.get(i).getServiceTime());24 }else {25 processes.get(i).setStartingTime(currentTime);26 processes.get(i).setFinishingTime(processes.get(i).getStartingTime()+processes.get(i).getServiceTime());27 processes.get(i).setTurnAroundTime(processes.get(i).getFinishingTime()-processes.get(i).getArrivalTime());28 processes.get(i).setAverageTAT((double)processes.get(i).getTurnAroundTime() / processes.get(i).getServiceTime());29 }30 currentTime = processes.get(i).getFinishingTime();31 }32 33 System.out.println("---------------------------------------------------------------------");34 35 ProcessUtil.sortByID(processes);36 for(Process p : processes){37 System.out.println(p);38 }39 }40 }

 

SJF核心代码如下

 

 1 package me.ares.algorithms; 2 3 import java.util.List; 4 import me.ares.domain.Process; 5 import me.ares.utils.ProcessUtil; 6 7 public class SJF { 8 private List<Process> processes; 9 10 // 从文件读入模拟进程11 public SJF(String fileString) {12 processes = ProcessUtil.readProcesses(fileString);13 }14 15 public void execute() {16 ProcessUtil.sortByServiceTime(processes);17 int currentTime = 0; //起始时刻18 int next;19 while((next=nextVisit(currentTime))!=-1){20 System.out.println("时刻"+currentTime+": 进程"+processes.get(next).getProcessID()+"启动");21 processes.get(next).setStartingTime(currentTime);22 processes.get(next).setFinishingTime(processes.get(next).getServiceTime()+processes.get(next).getStartingTime());23 processes.get(next).setTurnAroundTime(processes.get(next).getFinishingTime()-processes.get(next).getArrivalTime());24 processes.get(next).setAverageTAT((double)processes.get(next).getTurnAroundTime() / processes.get(next).getServiceTime());25 currentTime = processes.get(next).getFinishingTime();26 }27 System.out.println("---------------------------------------------------------------------");28 ProcessUtil.sortByID(processes);29 for(Process p : processes){30 System.out.println(p);31 }32 }33 34 private int nextVisit(int currentTime) {35 for (int i = 0; i < processes.size(); i++) {36 if (processes.get(i).isVisited() == false && processes.get(i).getArrivalTime() < currentTime) {37 processes.get(i).setVisited(true);38 return i;39 }40 }41 return ProcessUtil.findFirstArrival(processes); //先到达先执行;42 }43 }

 

模拟Process的对象模型

 1 package me.ares.domain; 2 3 public class Process { 4 private char processID; 5 private int arrivalTime; //到达时间 6 private int serviceTime; //服务时间 7 private int startingTime; //开始时间 8 private int finishingTime; //完成时间 9 private int turnAroundTime; //周转时间10 private double averageTAT; //带权周转时间11 private boolean visited = false; 12 13 public Process(char processID, int arrivalTime, int serviceTime) {14 super();15 this.processID = processID;16 this.arrivalTime = arrivalTime;17 this.serviceTime = serviceTime;18 }19 20 public char getProcessID() {21 return processID;22 }23 24 public void setProcessID(char processID) {25 this.processID = processID;26 }27 28 public int getArrivalTime() {29 return arrivalTime;30 }31 public void setArrivalTime(int arrivalTime) {32 this.arrivalTime = arrivalTime;33 }34 public int getServiceTime() {35 return serviceTime;36 }37 public void setServiceTime(int serviceTime) {38 this.serviceTime = serviceTime;39 }40 public int getStartingTime() {41 return startingTime;42 }43 public void setStartingTime(int startingTime) {44 this.startingTime = startingTime;45 }46 public int getFinishingTime() {47 return finishingTime;48 }49 public void setFinishingTime(int finishingTime) {50 this.finishingTime = finishingTime;51 }52 public int getTurnAroundTime() {53 return turnAroundTime;54 }55 public void setTurnAroundTime(int turnAroundTime) {56 this.turnAroundTime = turnAroundTime;57 }58 public double getAverageTAT() {59 return averageTAT;60 }61 public void setAverageTAT(double averageTAT) {62 this.averageTAT = averageTAT;63 }64 65 public boolean isVisited() {66 return visited;67 }68 69 public void setVisited(boolean visited) {70 this.visited = visited;71 }72 73 @Override74 public String toString() {75 return "Process [processID=" + processID + ", arrivalTime="76 + arrivalTime + ", serviceTime=" + serviceTime77 + ", startingTime=" + startingTime + ", finishingTime="78 + finishingTime + ", turnAroundTime=" + turnAroundTime79 + ", averageTAT=" + averageTAT 80 + "]";81 }82 83 }

 

操作Process的便捷工具类

 1 package me.ares.utils; 2 3 import java.io.File; 4 import java.io.FileNotFoundException; 5 import java.util.ArrayList; 6 import java.util.Comparator; 7 import java.util.List; 8 import java.util.Scanner; 9 10 import me.ares.domain.Process;11 12 public class ProcessUtil {13 14 public static List<Process> readProcesses(String fileString){15 List<Process> processes = new ArrayList<Process>();16 Scanner scanner = null;17 try {18 scanner = new Scanner(new File(fileString));19 while (scanner.hasNext()) {20 char processID = scanner.next().charAt(0);21 int arrivalTime = scanner.nextInt();22 int serviceTime = scanner.nextInt();23 processes.add(new Process(processID, arrivalTime, serviceTime));24 }25 } catch (FileNotFoundException e) {26 e.printStackTrace();27 }28 scanner.close();29 return processes;30 }31 32 public static void sortByServiceTime(List<Process> processes) {33 processes.sort(new Comparator<Process>() {34 public int compare(Process o1, Process o2) {35 if (o1.getServiceTime() > o2.getServiceTime()) {36 return 1;37 } else if (o1.getServiceTime() == o2.getServiceTime()) {38 return 0;39 } else {40 return -1;41 }42 }43 });44 }45 46 public static void sortByID(List<Process> processes) {47 processes.sort(new Comparator<Process>(){48 49 @Override50 public int compare(Process o1, Process o2) {51 if (o1.getProcessID()>o2.getProcessID()) {52 return 1;53 }else if (o1.getProcessID() == o2.getProcessID()) {54 return 0;55 }else{56 return -1;57 }58 }59 60 });61 }62 63 public static void sortByArrivalTime(List<Process> processes){64 processes.sort(new Comparator<Process>() {65 66 @Override67 public int compare(Process o1, Process o2) {68 if(o1.getArrivalTime()>o2.getArrivalTime()) return 1;69 else if (o1.getArrivalTime()==o2.getArrivalTime()) return 0; 70 else return -1;71 }72 });73 }74 75 public static int findFirstArrival(List<Process> processes) {76 int firstArrival = Integer.MAX_VALUE;77 int index = -1;78 for (int i = 0; i < processes.size(); i++) {79 if (processes.get(i).isVisited() == false80 && processes.get(i).getArrivalTime() < firstArrival) {81 firstArrival = processes.get(i).getArrivalTime();82 index = i;83 }84 }85 if (index != -1)86 processes.get(index).setVisited(true); // index值改变代表进程被找到,设置进程visited值87 return index;88 }89 90 }

//---------------------------------------------------------测    试    如    下(Junit单元测试)----------------------------------------------------------------------------------------------------

 1 package me.ares.junittest; 2 3 import me.ares.algorithms.FCFS; 4 import org.junit.Test; 5 6 public class FCFS_Test { 7 8 FCFS fcfs = new FCFS("test.txt"); 9 10 @Test11 public void testExecute() {12 fcfs.execute();13 }14 15 }
package me.ares.junittest;import me.ares.algorithms.SJF;import org.junit.Test;public class SJF_Test { SJF sjf = new SJF("test.txt"); @Test public void testExecute() { sjf.execute(); }}

----------------------------------如有疑惑请留言噢--------------------------

相关阅读:
Top