這裡記錄一下作業系統的實驗，幾個排程算法的原理很好了解，網上也有很多解釋，這裡不再解釋，直接上代碼。
一、JCB類
public class JCB {
public int id;
/**
* 剩餘服務時間
*/
public int leftTime;
/**
* 要求服務時間
*/
public int serviceTime;
/**
* 到達時間
*/
public int arriveTime;
/**
* 開始時間
*/
public int beginTime;
/**
* 結束時間
*/
public int finishTime;
/**
* 優先權
*/
public float priority;
public JCB(int id, int serviceTime, int arriveTime,float priority) {
this.id = id;
this.leftTime = serviceTime;
this.serviceTime = serviceTime;
this.arriveTime = arriveTime;
beginTime =0;
this.priority=priority;
finishTime=0;
}
@Override
public String toString() {
return "JCB{" +
"id=" + id +
", serviceTime=" + serviceTime +
", arriveTime=" + arriveTime +
", priority=" + priority +
'}';
}
}
二、定義所需資料結構
/**
* 時間片輪轉算法
*
* @author MaoLin Wang
* @date 2019/11/3020:03
*/
public class SchedulingAlgorithm {
/**
* 就緒隊列
*/
LinkedList<JCB> readyQueue = null;
/**
* 結束排程隊列
*/
LinkedList<JCB> finishQueue = null;
/**
* 時間段
*/
private int cpuTime;
/**
* 時間片大小
*/
private int timeSize;
/**
* 作業數
*/
private int jobNum;
private String dispatchName;//排程算法名
/**
* 作業周轉時間
*/
private int[] turnoverTime;
/**
* 作業帶權周轉時間·
*/
private float[] turnoverTimeWithWeight;
/**
* 平均帶權周轉時間
*/
private float ave;
}
三、初始化
這裡将最高響應比的初始化拉了出來，因為要設定響應比
/**
* 初始化
*/
public void init(int jobNum, int timeSize, String dispatchName) {
System.out.println("開始" + dispatchName + "排程");
readyQueue = new LinkedList<>();
finishQueue = new LinkedList<>();
this.turnoverTime = new int[jobNum];
this.turnoverTimeWithWeight = new float[jobNum];
this.cpuTime = 0;
JCB jcb;
for (int i = 1; i <= jobNum; i++) {
jcb = new JCB(i, (int) (Math.random() * 10 + 1), i - 1, 0);
readyQueue.offer(jcb);
}
this.timeSize = timeSize;
this.jobNum = jobNum;
this.dispatchName = dispatchName;
printInitQueue();
}
/**
* 初始化高響應比優先隊列
*
* @param jobNum
* @param timeSize
* @param dispatchName
*/
public void HRNInit(int jobNum, int timeSize, String dispatchName) {
System.out.println("開始" + dispatchName + "排程");
readyQueue = new LinkedList<>();
finishQueue = new LinkedList<>();
this.turnoverTime = new int[jobNum];
this.turnoverTimeWithWeight = new float[jobNum];
this.cpuTime = 0;
JCB jcb;
for (int i = 1; i <= jobNum; i++) {
float v = (float) (Math.random() * 5 + 1);
jcb = new JCB(i, (int) (Math.random() * 10 + 1), i - 1, (float) (Math.random() * 5 + 1));
readyQueue.offer(jcb);
}
this.timeSize = timeSize;
this.jobNum = jobNum;
this.dispatchName = dispatchName;
printInitQueue();
}
作業id預設為序号i，所需服務時間随機生成，到達時間預設從0開始，響應比其他排程算法為0，高響應比算法為随機生成。
四、高響應比優先算法實作
邏輯很簡單，使用遞歸實作，參數初始為0，每次取出對頭作業，因為這裡所有的作業在初始化時資料都初始化好了，是以需判斷作業到達時間是否小于cpu時間片，因為隻有小于時間片，說明其實際是到達的。
如果小于，則設定其開始時間為cpu目前時間，結束時間為開始時間+服務時間，剩餘時間設為0，同時增加cpu時間，将該作業加入已完成隊列中，否則，遞歸調用該算法，參數為index+1，一輪結束後，對作業按響應比排序，繼續遞歸，知道就緒隊列為空。
/**
* 最高響應比優先算法
*/
public void HRNAlgorithm(int index) {
if (readyQueue.size() == 0) {
System.out.println("就緒隊列為空，排程完畢!");
return;
}
JCB head = readyQueue.get(index);
if (head.arriveTime <= cpuTime) {
readyQueue.poll();
System.out.println("-----------------------------------------------------");
System.out.println("時間片: " + cpuTime + "開始排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
head.beginTime = cpuTime;
head.finishTime = head.beginTime + head.serviceTime;
head.leftTime = 0;
cpuTime += head.serviceTime;
finishQueue.offer(head);
System.out.println("時間片: " + cpuTime + "結束排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
} else {
HRNAlgorithm(index++);
}
sortByPriority();
HRNAlgorithm(0);
}
/**
* 根據響應比排序
*/
private void sortByPriority() {
readyQueue.sort((o1, o2) -> o1.priority > o2.priority ? -1 : 1);
}
五、短作業優先排程算法
同高響應比優先類似，隻是按照要求服務時間排序。
/**
* 短作業優先排程算法
*/
public void SJFAlgorithm(int index) {
if (readyQueue.size() == 0) {
System.out.println("就緒隊列為空，排程完畢！");
return;
}
JCB head = readyQueue.get(index);
if (head.arriveTime <= cpuTime) {
readyQueue.poll();
System.out.println("-----------------------------------------------------");
System.out.println("時間片: " + cpuTime + "開始排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
head.beginTime = cpuTime;
head.finishTime = head.beginTime + head.serviceTime;
head.leftTime = 0;
cpuTime += head.serviceTime;
finishQueue.offer(head);
System.out.println("時間片: " + cpuTime + "結束排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
} else {
sortByServiceTime();
SJFAlgorithm(index++);
}
sortByServiceTime();
SJFAlgorithm(0);
}
/**
* 根據要求服務時間從小到大排序
*/
private void sortByServiceTime() {
readyQueue.sort((o1, o2) -> o1.serviceTime < o2.serviceTime ? -1 : 1);
}
六、先來先服務
最簡單的一個算法，直接按順序取出隊頭作業執行。
/**
* 先來先服務排程算法
*/
public void FCFSAlgorithm() {
if (readyQueue.size() == 0) {
System.out.println("就緒隊列為空，排程完畢！");
return;
}
JCB head = readyQueue.poll();
System.out.println("-----------------------------------------------------");
System.out.println("時間片: " + cpuTime + "開始排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
head.beginTime = cpuTime;
head.leftTime = 0;
head.finishTime = head.beginTime + head.serviceTime;
cpuTime += head.serviceTime;
finishQueue.offer(head);
System.out.println("時間片: " + cpuTime + "結束排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
FCFSAlgorithm();
}
七、時間片輪轉算法
這裡需要根據作業剩餘需要服務的時間跟時間片大小做對比，代碼很好了解。
/**
* 時間片輪轉算法
*/
public void RRAlgorithm() {
if (readyQueue.size() == 0) {
System.out.println("就緒隊列為空，排程完畢！");
return;
}
JCB head = readyQueue.poll();
System.out.println("-----------------------------------------------------");
System.out.println("時間片: " + cpuTime + "開始排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
head.beginTime = cpuTime;
if (head.leftTime > timeSize) {
//服務時間大于時間片大小
head.leftTime -= timeSize;
//重新加入到就緒隊列尾部
readyQueue.offer(head);
cpuTime += timeSize;
} else if (head.leftTime == timeSize) {
//服務時間等于時間片大小
cpuTime += timeSize;
head.finishTime = cpuTime;
head.leftTime = 0;
//加入結束隊列
finishQueue.offer(head);
} else {
//服務時間小于時間片大小
head.finishTime = cpuTime + head.leftTime;
head.leftTime = 0;
cpuTime += head.leftTime;
finishQueue.offer(head);
}
System.out.println("時間片: " + cpuTime + "結束排程作業:" + head.id + ", 剩餘服務時間: " + head.leftTime);
RRAlgorithm();
}
八、計算周轉時間和帶權周轉時間
/**
* 計算周轉時間和帶權周轉時間
* @param finishQueue
*/
public void R_Dis(Queue<JCB> finishQueue) {
Queue<JCB>temp=finishQueue;
JCB tempJcb;
float sum = 0;
for (int i = 0; i < jobNum; i++) {
tempJcb=temp.poll();
turnoverTime[i] = tempJcb.finishTime - tempJcb.arriveTime;
turnoverTimeWithWeight[i] =(float) turnoverTime[i] / tempJcb.serviceTime;
sum += turnoverTimeWithWeight[i];
temp.offer(tempJcb);
}
float ave = sum / jobNum;
this.ave = ave;
}
九、列印結果
public void printResult(boolean isHRN) {
R_Dis(this.finishQueue);
System.out.println("=====================" + this.dispatchName + "排程結果為=========================");
if (isHRN) {
System.out.println("程序名\t" + "到達時間\t" + "要求服務時間\t" + "響應比\t" + "開始時間\t" + "完成時間\t" + "周轉時間\t" + "帶權周轉時間\t"+"平均帶權周轉時間\t");
} else {
System.out.println("程序名\t" + "到達時間\t" + "要求服務時間\t" + "開始時間\t" + "完成時間\t" + "周轉時間\t" + "帶權周轉時間\t"+"平均帶權周轉時間\t");
}
int count = 0;
for (JCB jcb : this.finishQueue) {
if (isHRN) {
System.out.println(" " + jcb.id + "\t\t\t" + jcb.arriveTime + "\t\t" + jcb.serviceTime + "\t\t" + jcb.priority + "\t\t" + jcb.beginTime + "\t\t"
+ jcb.finishTime + "\t\t" + turnoverTime[count] + "\t\t" + turnoverTimeWithWeight[count]+"\t\t"+this.ave);
count = count + 1;
} else {
System.out.println(" " + jcb.id + "\t\t\t" + jcb.arriveTime + "\t\t" + jcb.serviceTime + "\t\t" + jcb.beginTime + "\t\t"
+ jcb.finishTime + "\t\t" + turnoverTime[count] + "\t\t" + turnoverTimeWithWeight[count]+"\t\t"+this.ave);
count = count + 1;
}
}
}
/**
* 列印初始化隊列
*/
private void printInitQueue() {
System.out.println("目前就緒隊列為:");
for (JCB jcb2 : readyQueue) {
System.out.println(jcb2);
}
}
測試
public class Test {
public static void main(String[] args) {
SchedulingAlgorithm schedulingAlgorithm = new SchedulingAlgorithm();
schedulingAlgorithm.init(5, 2,"輪轉");
schedulingAlgorithm.RRAlgorithm();
schedulingAlgorithm.printResult(false);
schedulingAlgorithm.init(5,3,"先來先服務");
schedulingAlgorithm.FCFSAlgorithm();
schedulingAlgorithm.printResult(false);
schedulingAlgorithm.init(5,3,"短作業優先服務");
schedulingAlgorithm.SJFAlgorithm(0);
schedulingAlgorithm.printResult(false);
schedulingAlgorithm.HRNInit(5,3,"高響應比優先");
schedulingAlgorithm.HRNAlgorithm(0);
schedulingAlgorithm.printResult(true);
}
}
結果：
開始輪轉排程
目前就緒隊列為:
JCB{id=1, serviceTime=1, arriveTime=0, priority=0.0}
JCB{id=2, serviceTime=5, arriveTime=1, priority=0.0}
JCB{id=3, serviceTime=4, arriveTime=2, priority=0.0}
JCB{id=4, serviceTime=6, arriveTime=3, priority=0.0}
JCB{id=5, serviceTime=6, arriveTime=4, priority=0.0}
-----------------------------------------------------
時間片: 0開始排程作業:1, 剩餘服務時間: 1
時間片: 0結束排程作業:1, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 0開始排程作業:2, 剩餘服務時間: 5
時間片: 2結束排程作業:2, 剩餘服務時間: 3
-----------------------------------------------------
時間片: 2開始排程作業:3, 剩餘服務時間: 4
時間片: 4結束排程作業:3, 剩餘服務時間: 2
-----------------------------------------------------
時間片: 4開始排程作業:4, 剩餘服務時間: 6
時間片: 6結束排程作業:4, 剩餘服務時間: 4
-----------------------------------------------------
時間片: 6開始排程作業:5, 剩餘服務時間: 6
時間片: 8結束排程作業:5, 剩餘服務時間: 4
-----------------------------------------------------
時間片: 8開始排程作業:2, 剩餘服務時間: 3
時間片: 10結束排程作業:2, 剩餘服務時間: 1
-----------------------------------------------------
時間片: 10開始排程作業:3, 剩餘服務時間: 2
時間片: 12結束排程作業:3, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 12開始排程作業:4, 剩餘服務時間: 4
時間片: 14結束排程作業:4, 剩餘服務時間: 2
-----------------------------------------------------
時間片: 14開始排程作業:5, 剩餘服務時間: 4
時間片: 16結束排程作業:5, 剩餘服務時間: 2
-----------------------------------------------------
時間片: 16開始排程作業:2, 剩餘服務時間: 1
時間片: 16結束排程作業:2, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 16開始排程作業:4, 剩餘服務時間: 2
時間片: 18結束排程作業:4, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 18開始排程作業:5, 剩餘服務時間: 2
時間片: 20結束排程作業:5, 剩餘服務時間: 0
就緒隊列為空，排程完畢！
=====================輪轉排程結果為=========================
程序名 到達時間 要求服務時間 開始時間 完成時間 周轉時間 帶權周轉時間 平均帶權周轉時間
1 0 1 0 1 1 1.0 2.3733335
3 2 4 10 12 10 2.5 2.3733335
2 1 5 16 17 16 3.2 2.3733335
4 3 6 16 18 15 2.5 2.3733335
5 4 6 18 20 16 2.6666667 2.3733335
開始先來先服務排程
目前就緒隊列為:
JCB{id=1, serviceTime=3, arriveTime=0, priority=0.0}
JCB{id=2, serviceTime=10, arriveTime=1, priority=0.0}
JCB{id=3, serviceTime=7, arriveTime=2, priority=0.0}
JCB{id=4, serviceTime=1, arriveTime=3, priority=0.0}
JCB{id=5, serviceTime=1, arriveTime=4, priority=0.0}
-----------------------------------------------------
時間片: 0開始排程作業:1, 剩餘服務時間: 3
時間片: 3結束排程作業:1, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 3開始排程作業:2, 剩餘服務時間: 10
時間片: 13結束排程作業:2, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 13開始排程作業:3, 剩餘服務時間: 7
時間片: 20結束排程作業:3, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 20開始排程作業:4, 剩餘服務時間: 1
時間片: 21結束排程作業:4, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 21開始排程作業:5, 剩餘服務時間: 1
時間片: 22結束排程作業:5, 剩餘服務時間: 0
就緒隊列為空，排程完畢！
=====================先來先服務排程結果為=========================
程序名 到達時間 要求服務時間 開始時間 完成時間 周轉時間 帶權周轉時間 平均帶權周轉時間
1 0 3 0 3 3 1.0 8.154286
2 1 10 3 13 12 1.2 8.154286
3 2 7 13 20 18 2.5714285 8.154286
4 3 1 20 21 18 18.0 8.154286
5 4 1 21 22 18 18.0 8.154286
開始短作業優先服務排程
目前就緒隊列為:
JCB{id=1, serviceTime=8, arriveTime=0, priority=0.0}
JCB{id=2, serviceTime=10, arriveTime=1, priority=0.0}
JCB{id=3, serviceTime=1, arriveTime=2, priority=0.0}
JCB{id=4, serviceTime=10, arriveTime=3, priority=0.0}
JCB{id=5, serviceTime=1, arriveTime=4, priority=0.0}
-----------------------------------------------------
時間片: 0開始排程作業:1, 剩餘服務時間: 8
時間片: 8結束排程作業:1, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 8開始排程作業:3, 剩餘服務時間: 1
時間片: 9結束排程作業:3, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 9開始排程作業:5, 剩餘服務時間: 1
時間片: 10結束排程作業:5, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 10開始排程作業:2, 剩餘服務時間: 10
時間片: 20結束排程作業:2, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 20開始排程作業:4, 剩餘服務時間: 10
時間片: 30結束排程作業:4, 剩餘服務時間: 0
就緒隊列為空，排程完畢！
=====================短作業優先服務排程結果為=========================
程序名 到達時間 要求服務時間 開始時間 完成時間 周轉時間 帶權周轉時間 平均帶權周轉時間
1 0 8 0 8 8 1.0 3.72
3 2 1 8 9 7 7.0 3.72
5 4 1 9 10 6 6.0 3.72
2 1 10 10 20 19 1.9 3.72
4 3 10 20 30 27 2.7 3.72
開始高響應比優先排程
目前就緒隊列為:
JCB{id=1, serviceTime=1, arriveTime=0, priority=5.41018}
JCB{id=2, serviceTime=6, arriveTime=1, priority=5.1338425}
JCB{id=3, serviceTime=6, arriveTime=2, priority=3.1670618}
JCB{id=4, serviceTime=6, arriveTime=3, priority=2.0463989}
JCB{id=5, serviceTime=1, arriveTime=4, priority=4.711568}
-----------------------------------------------------
時間片: 0開始排程作業:1, 剩餘服務時間: 1
時間片: 1結束排程作業:1, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 1開始排程作業:2, 剩餘服務時間: 6
時間片: 7結束排程作業:2, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 7開始排程作業:5, 剩餘服務時間: 1
時間片: 8結束排程作業:5, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 8開始排程作業:3, 剩餘服務時間: 6
時間片: 14結束排程作業:3, 剩餘服務時間: 0
-----------------------------------------------------
時間片: 14開始排程作業:4, 剩餘服務時間: 6
時間片: 20結束排程作業:4, 剩餘服務時間: 0
就緒隊列為空，排程完畢!
=====================高響應比優先排程結果為=========================
程序名 到達時間 要求服務時間 響應比 開始時間 完成時間 周轉時間 帶權周轉時間 平均帶權周轉時間
1 0 1 5.41018 0 1 1 1.0 2.1666665
2 1 6 5.1338425 1 7 6 1.0 2.1666665
5 4 1 4.711568 7 8 4 4.0 2.1666665
3 2 6 3.1670618 8 14 12 2.0 2.1666665
4 3 6 2.0463989 14 20 17 2.8333333 2.1666665
![Win10系統怎麼開啟Linux Bash指令行？[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)