進程調度的兩種算法JAVA實現----FCFS(先來先服務)和SJF(最短作業優先)

2019-11-14 15:21:46

字體：大中小

來源：轉載

供稿：網友

(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();    }}