《进程调度》学习与Java简单实现
一、摘要
学习操作系统 FCFS、SJF、HRRF、HPF调度算法，并使用Java语言对四种调度算法进行源码级编程实现，对相关执行案例进行作图分析、逻辑验证。具体代码附在报告最后。
二、量化数值关系
周转时间 = 完成时间 - 到达时间
响应比 = (等待时间 + 执行时间）/ 执行时间
平均周转时间 = 总周转时间 / 作业数
等待时间 = 周转时间 - 执行时间
带权周转时间 = 周转时间 / 服务时间
三、算法描述及案例分析
1.先来先服务(FCFS)
1.1 FCFS算法概述
（1）概念：按照作业/进程进入系统的先后次序进行调度，先进入系统者先调度；即启动等待时间最长的作业/进程。是一种最简单的调度算法，即可用于作业调度，也可用于进程调度。
（2）优缺点
比较有利于长作业（进程），而不利于短作业（进程）。
有利于CPU繁忙型作业（进程） ，而不利于I/O繁忙型作业（进程)。
用于批处理系统，不适于分时系统 。
1.2 FCFS算法实现思路
编写WorkModel类模拟作业，让该类继承Comparable接口，重写compareTo方法，实现依作业到达时间排序。
@Override
public int compareTo(WorkModel o) {
return this.arriveTime - o.arriveTime;
}
核心逻辑部分如下
//依到达时间排序
Collections.sort(workModels);
for (WorkModel t : workModels){
//如果当前时间小于进程到达时间，当前时间推移到到达时间
if (runTime < t.getArriveTime()){
runTime = t.getArriveTime();
}
t.setStartTime(runTime);
runTime += t.getExecuteTime();
t.setFinishTime(runTime);
t.setTurnoverTime();
t.setWaitTime();
waitTime += t.getWaitTime();
t.setPriorityTurn();
this.setNowTime(runTime);
}
this.setAverageWait(waitTime,len);
将作业列表按到达时间排序，遍历作业列表。如果当前时间小于进程到达时间，则当前时间推移到到达时间，然后执行该作业，计算各种量化数值并同步。最后计算平均等待时间，输出结果。
1.3 FCFS案例分析
作业
到达时间
运行时间
开始时间
等待时间
完成时间
周转时间
带权周转时间
A
3
1
5
2
6
3
3
B
1
2
3
2
5
4
2
C
4
2
6
2
8
4
2
D
0
3
0
0
3
3
1
平均等待时间 t=(2+2+2+0)/4=1.5
甘特图
2.作业优先调度算法（SJF）
2.1 SJF算法概述
（1）概念：从队列中选出一个估计运行时间最短的作业优先调度，即可用于作业调度，也可用于进程调度。
（2）优缺点
对长作业不利。严重的是，若一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度——饥饿.
完全未考虑作业(进程)的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
2.2 SJF算法实现思路
编写WorkModel类模拟作业，让该类继承Comparable接口，重写compareTo方法，实现依执行时间排序。设置flag变量来标识是否已执行。
//标识是否已执行
private boolean flag=false;
@Override
public int compareTo(WorkModel o) {
return this.executeTime - o.executeTime;
}
核心部分逻辑如下。
//依执行时间排序
Collections.sort(workModels);
for (int i = 0; i < workModels.size(); i++) {
for (sjf.WorkModel t : workModels){
//获取当前未执行作业中最早到达时间
int temp = 9999;
for (sjf.WorkModel a :workModels){
if ((a.getArriveTime() < temp) && (a.isFlag() == false)){
temp = a.getArriveTime();
}
}
if (runTime < temp){
runTime = temp;
}
//如果当前时间大于作业到达时间，且当前作业未执行，则执行
if ((runTime >= t.getArriveTime()) && t.isFlag() == false){
t.setStartTime(runTime);
runTime += t.getExecuteTime();
t.setFlag(true);
t.setFinishTime(runTime);
t.setTurnoverTime();
t.setWaitTime();
waitTime += t.getWaitTime();
t.setPriorityTurn();
this.setNowTime(runTime);
}
else {
//同步时间并检查下一个作业
this.setNowTime(runTime);
continue;
}
}
}
this.setAverageWait(waitTime,len);
首先把作业列表按照执行时间排序。遍历列表，获取当前未执行作业中最早到达时间，设置当前时间。判断如果当前时间大于作业到达时间，且当前作业未执行，则执行；否则同步时间并检查下一个作业。每个循环中找到按执行时间排序列表中第一个当前时间可执行的作业，如此完成调度。
2.3 SJF案例分析
作业
到达时间
运行时间
开始时间
等待时间
完成时间
周转时间
带权周转时间
A
2
5
4
2
9
7
1.4
B
0
1
0
0
1
1
1
C
0
3
1
1
4
4
1.3
D
5
4
9
4
13
8
2
平均等待时间t=(2+0+1+4)/4=1.75
甘特图
3.最高响应比优先调度算法（HRRF）
3.1 HRRF算法概述
（1）概念：高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：
$$
响应比 =（等待时间+要求服务时间）/ 要求服务时间
$$
（2）优缺点
优点：
等待时间相同的作业，则要求服务的时间愈短，其优先权愈高，对短作业有利。
要求服务的时间相同的作业，则等待时间愈长，其优先权愈高，是先来先服务。
长作业，优先权随等待时间的增加而提高，其等待时间足够长时，其优先权便可升到很高， 从而也可获得处理机——对长作业有利。
是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得不到服务。
缺点：要进行响应比计算，增加了系统开销。
3.2 HRRF算法实现思路
首先比较带权周转时间和响应比的概念。
从公式上来看是一样的，但要注意实际运用时的区别。
带权周转时间是调度算法的性能指标，对于一个作业序列，选定了调度算法，也就确定了带权周转时间。
而高响应比算法是动态选择作业执行序列的算法，每个作业完成后都需要重新计算剩余作业响应比，以确定下一个需要调度的作业。
HRRF作业类中响应比的计算如下，需要实时更新响应比。
public void setPriorityTurn(int runtime) {
int finish = runtime + this.executeTime;
int turn = finish - this.arriveTime;
this.priorityTurn = turn/this.executeTime;
}
HRRF调度算法核心逻辑如下。
for (int i = 0; i < len; i++) {
//获取当前未执行作业中最高响应比
float temp = -1;
int tmpflag = -1;
//更新响应比
for (hrrf.WorkModel w : workModels){
w.setRatio(runTime);
}
int timeflag = 9999;
for (int j = 0; j < len; j++) {
//获取已到达当前最高响应比的未执行作业
if ((workModels.get(j).getPriorityTurn() > temp) && (workModels.get(j).isFlag() == false) && (runTime >= workModels.get(j).getArriveTime())) {
temp = workModels.get(j).getPriorityTurn();
tmpflag = j;
}
}
//当前时间下没有已到达未执行作业
if(tmpflag == -1){
//找到最近即将到达未执行作业
for (int j = 0; j < len; j++) {
if ((timeflag >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
timeflag = workModels.get(j).getArriveTime();
tmpflag = j;
}
}
runTime = timeflag;
//更新响应比
for (hrrf.WorkModel w : workModels){
w.setRatio(runTime);
}
}
for(hrrf.WorkModel t : workModels){
System.out.println(t.getName()+"当前响应比为"+t.getPriorityTurn()+" flag:"+t.isFlag());
}
System.out.println("执行作业"+workModels.get(tmpflag).getName());
System.out.println("----------------");
workModels.get(tmpflag).setStartTime(runTime);
runTime += workModels.get(tmpflag).getExecuteTime();
workModels.get(tmpflag).setFinishTime(runTime);
workModels.get(tmpflag).setTurnoverTime();
workModels.get(tmpflag).setWaitTime();
waitTime += workModels.get(tmpflag).getWaitTime();
workModels.get(tmpflag).setPriorityTurn();
workModels.get(tmpflag).setFlag(true);
this.setNowTime(runTime);
}
this.setAverageWait(waitTime, len);
for (hrrf.WorkModel t : workModels) {
System.out.println(t.toString());
}
System.out.println("Average wait time:" + this.getAverageWait());
}
遍历作业列表长度次，每次处理一个作业。首先更新响应比，然后遍历获取已到达当前最高响应比的未执行作业编号。若此时没有获取符合条件的作业，则找到最近即将到达未执行作业，同步时间并记录其编号，更新响应比。
执行获取的作业，同步量化数据，计算所需数值。
3.3 HRRF案例分析
作业
到达时间
运行时间
开始时间
等待时间
完成时间
周转时间
带权周转时间
A
3
1
5
2
6
7
3
B
1
2
3
2
5
1
2
C
2
2
6
4
8
4
3
D
0
3
0
0
3
8
1
平均等待时间t=(2+2+4+0)/4=2
甘特图
每一轮中找出当前响应比为正数的、flag位是false、响应比最高的作业来执行。
4.高优先级优先调度算法（HPF）
本报告研究静态优先级、非抢占式。
4.1 HPF算法概述
（1）概念：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程。
（2）特点
静态优先权在创建进程时确定，且在进程的整个运行期间保持不变。
进程类型：系统进程的优先权高于一般用户进程。
进程对资源的需求：如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。
用户要求：由用户进程的紧迫程度和用户所付费用的多少来确定优先权。
4.2 HPF算法实现思路
研究静态优先级非抢占式的HPF算法。
在HPF作业类中设置优先级变量，创建作业时需定义。
for (int i = 0; i < len; i++) {
//遍历获取当前未执行的最高优先级作业
int temp = -1;
int tmpflag = -1;
for (int j = 0; j < len; j++) {
if ((temp < workModels.get(j).getPriority()) && (runTime >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
temp = workModels.get(j).getPriority();
tmpflag = j;
}
}
//当前时间下没有已到达未执行作业
int timeflag = 9999;
if (tmpflag == -1){
for (int j = 0; j < len; j++) {
if ((timeflag >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
timeflag = workModels.get(j).getArriveTime();
tmpflag = j;
}
}
runTime = timeflag;
}
workModels.get(tmpflag).setStartTime(runTime);
runTime += workModels.get(tmpflag).getExecuteTime();
workModels.get(tmpflag).setFinishTime(runTime);
workModels.get(tmpflag).setTurnoverTime();
workModels.get(tmpflag).setWaitTime();
workModels.get(tmpflag).setPriorityTurn();
waitTime += workModels.get(tmpflag).getWaitTime();
workModels.get(tmpflag).setFlag(true);
this.setNowTime(runTime);
}
this.setAverageWait(waitTime, len);
for (hpf.WorkModel t : workModels) {
System.out.println(t.toString());
}
System.out.println("Average wait time:" + this.getAverageWait());
遍历作业列表长度次。每次先遍历获取当前未执行的最高优先级作业，如果没有符合条件的作业，找到最近到达的作业时间，并把当前时间推移同步。执行当前符合条件的作业，并计算相关量化数据。
4.3 HPF案例分析
作业
到达时间
运行时间
优先级
开始时间
等待时间
完成时间
周转时间
带权周转时间
A
2
5
3
4
2
9
7
3
B
0
1
6
3
3
4
4
2
C
0
3
7
0
0
3
3
3
D
5
4
5
9
4
13
8
1
平均等待时间t=(2+3+0+4)/4=2.25
甘特图
四、代码附录
1.FCFS代码
FCFS作业类
package fcfs;
public class WorkModel implements Comparable
private String name;
private int arriveTime;
private int executeTime;
private int turnoverTime;
private float priorityTurn;
private int startTime;
private int finishTime;
//等待时间 等待时间=周转-执行
private int waitTime;
public int getStartTime() {
return startTime;
}
public void setStartTime(int startTime) {
this.startTime = startTime;
}
public void setPriorityTurn() {
this.priorityTurn = (float)this.turnoverTime/(float)this.executeTime;
}
public WorkModel(String name, int arriveTime, int executeTime) {
this.name = name;
this.arriveTime = arriveTime;
this.executeTime = executeTime;
}
@Override
public String toString() {
return "WorkModel{" +
"name='" + name + '\'' +
", arriveTime=" + arriveTime +
", executeTime=" + executeTime +
", turnoverTime=" + turnoverTime +
", priorityTurn=" + priorityTurn +
", startTime=" + startTime +
", finishTime=" + finishTime +
", waitTime=" + waitTime +
'}';
}
public int getFinishTime() {
return finishTime;
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
public int getWaitTime() {
return waitTime;
}
public void setWaitTime() {
this.waitTime = this.turnoverTime - this.executeTime;
}
public int getTurnoverTime() {
return turnoverTime;
}
public void setTurnoverTime() {
this.turnoverTime = this.finishTime - this.arriveTime;
}
public int getArriveTime() {
return arriveTime;
}
public int getExecuteTime() {
return executeTime;
}
@Override
public int compareTo(WorkModel o) {
return this.arriveTime - o.arriveTime;
}
}
FCFS类
package fcfs;
//先来先服务算法
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class FCFSmodel {
//平均等待时间
private float averageWait;
private int nowTime;
public float getAverageWait() {
return averageWait;
}
public void setAverageWait(float averageWait,int len) {
this.averageWait = averageWait/len;
}
public int getNowTime() {
return nowTime;
}
public void setNowTime(int nowTime) {
this.nowTime = nowTime;
}
public void executeFCFS(List
int runTime = 0;
int waitTime = 0;
int len = workModels.size();
//依到达时间排序
Collections.sort(workModels);
for (WorkModel t : workModels){
//如果当前时间小于进程到达时间，当前时间推移到到达时间
if (runTime < t.getArriveTime()){
runTime = t.getArriveTime();
}
t.setStartTime(runTime);
runTime += t.getExecuteTime();
t.setFinishTime(runTime);
t.setTurnoverTime();
t.setWaitTime();
waitTime += t.getWaitTime();
t.setPriorityTurn();
this.setNowTime(runTime);
}
this.setAverageWait(waitTime,len);
for (WorkModel t : workModels){
System.out.println(t.toString());
}
System.out.println("Average wait time:"+this.getAverageWait());
}
public static void main(String[] args) {
FCFSmodel fcfsmodel = new FCFSmodel();
List
WorkModel w1 = new WorkModel("A",3,1);
WorkModel w2 = new WorkModel("B",1,2);
WorkModel w3 = new WorkModel("C",4,2);
WorkModel w4 = new WorkModel("D",0,3);
workModels.add(w1);
workModels.add(w2);
workModels.add(w3);
workModels.add(w4);
fcfsmodel.executeFCFS(workModels);
}
}
2.SJF代码
SJF作业类
package sjf;
public class WorkModel implements Comparable
private String name;
private int arriveTime;
private int executeTime;
private int turnoverTime;
private float priorityTurn;
//标识是否已执行
private boolean flag=false;
private int startTime;
public void setFlag(boolean flag) {
this.flag = flag;
}
public boolean isFlag() {
return flag;
}
private int finishTime;
//等待时间 等待时间=周转-执行
private int waitTime;
public int getStartTime() {
return startTime;
}
public void setStartTime(int startTime) {
this.startTime = startTime;
}
public void setPriorityTurn() {
this.priorityTurn = (float)this.turnoverTime/(float)this.executeTime;
}
public WorkModel(String name, int arriveTime, int executeTime) {
this.name = name;
this.arriveTime = arriveTime;
this.executeTime = executeTime;
}
@Override
public String toString() {
return "WorkModel{" +
"name='" + name + '\'' +
", arriveTime=" + arriveTime +
", executeTime=" + executeTime +
", turnoverTime=" + turnoverTime +
", priorityTurn=" + priorityTurn +
", startTime=" + startTime +
", finishTime=" + finishTime +
", waitTime=" + waitTime +
'}';
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
public int getWaitTime() {
return waitTime;
}
public void setWaitTime() {
this.waitTime = this.turnoverTime - this.executeTime;
}
public void setTurnoverTime() {
this.turnoverTime = this.finishTime - this.arriveTime;
}
public int getArriveTime() {
return arriveTime;
}
public int getExecuteTime() {
return executeTime;
}
@Override
public int compareTo(WorkModel o) {
return this.executeTime - o.executeTime;
}
}
SJF类
package sjf;
//短作业优先算法
import fcfs.FCFSmodel;
import fcfs.WorkModel;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SJFmodel {
//平均等待时间
private float averageWait;
private int nowTime;
public float getAverageWait() {
return averageWait;
}
public void setAverageWait(float averageWait,int len) {
this.averageWait = averageWait/len;
}
public int getNowTime() {
return nowTime;
}
public void setNowTime(int nowTime) {
this.nowTime = nowTime;
}
public void executeSJF(List
int runTime = 0;
int waitTime = 0;
int len = workModels.size();
//依执行时间排序
Collections.sort(workModels);
for (int i = 0; i < workModels.size(); i++) {
for (sjf.WorkModel t : workModels){
//获取当前未执行作业中最早到达时间
int temp = 9999;
for (sjf.WorkModel a :workModels){
if ((a.getArriveTime() < temp) && (a.isFlag() == false)){
temp = a.getArriveTime();
}
}
if (runTime < temp){
runTime = temp;
}
//如果当前时间大于作业到达时间，且当前作业未执行，则执行
if ((runTime >= t.getArriveTime()) && t.isFlag() == false){
t.setStartTime(runTime);
runTime += t.getExecuteTime();
t.setFlag(true);
t.setFinishTime(runTime);
t.setTurnoverTime();
t.setWaitTime();
waitTime += t.getWaitTime();
t.setPriorityTurn();
this.setNowTime(runTime);
}
else {
//同步时间并检查下一个作业
this.setNowTime(runTime);
continue;
}
}
}
this.setAverageWait(waitTime,len);
for (sjf.WorkModel t : workModels){
System.out.println(t.toString());
}
System.out.println("Average wait time:"+this.getAverageWait());
}
public static void main(String[] args) {
SJFmodel sjfmodel = new SJFmodel();
List
sjf.WorkModel w1 = new sjf.WorkModel("A",2,5);
sjf.WorkModel w2 = new sjf.WorkModel("B",0,1);
sjf.WorkModel w3 = new sjf.WorkModel("C",0,3);
sjf.WorkModel w4 = new sjf.WorkModel("D",5,4);
workModels.add(w1);
workModels.add(w2);
workModels.add(w3);
workModels.add(w4);
sjfmodel.executeSJF(workModels);
}
}
3.HRRF代码
HRRF作业类
package hrrf;
public class WorkModel{
private String name;
private int arriveTime;
private int executeTime;
private int turnoverTime;
private float priorityTurn;
private int startTime;
private int finishTime=-1;
private int responseRatio;
//等待时间 等待时间=周转-执行
private int waitTime;
public String getName() {
return name;
}
//标识是否已执行
private boolean flag=false;
public void setFlag(boolean flag) {
this.flag = flag;
}
public boolean isFlag() {
return flag;
}
public void setStartTime(int startTime) {
this.startTime = startTime;
}
public float getPriorityTurn() {
return priorityTurn;
}
public void setPriorityTurn() {
this.priorityTurn = (float)this.turnoverTime/(float)this.executeTime;
}
public void setRatio(int runtime) {
int finish = runtime + this.executeTime;
int turn = finish - this.arriveTime;
this.responseRatio = (float)turn/(float)this.executeTime;
}
public float getResponseRatio() {
return responseRatio;
}
public WorkModel(String name, int arriveTime, int executeTime) {
this.name = name;
this.arriveTime = arriveTime;
this.executeTime = executeTime;
}
@Override
public String toString() {
return "WorkModel{" +
"name='" + name + '\'' +
", arriveTime=" + arriveTime +
", executeTime=" + executeTime +
", turnoverTime=" + turnoverTime +
", priorityTurn=" + priorityTurn +
", startTime=" + startTime +
", finishTime=" + finishTime +
", waitTime=" + waitTime +
'}';
}
public int getFinishTime() {
return finishTime;
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
public int getWaitTime() {
return waitTime;
}
public void setWaitTime() {
this.waitTime = this.turnoverTime - this.executeTime;
}
public void setTurnoverTime() {
this.turnoverTime = this.finishTime - this.arriveTime;
}
public int getArriveTime() {
return arriveTime;
}
public int getExecuteTime() {
return executeTime;
}
}
HRRF类
package hrrf;
//高响应比优先算法 Highest Response Ratio First
//响应比=（等待时间+执行时间）/执行时间
import java.util.ArrayList;
import java.util.List;
public class HRRFmodel {
//平均等待时间
private float averageWait;
private int nowTime;
public float getAverageWait() {
return averageWait;
}
public void setAverageWait(float averageWait,int len) {
this.averageWait = averageWait/len;
}
public void setNowTime(int nowTime) {
this.nowTime = nowTime;
}
public void executeHRRF(List
int runTime = 0;
int waitTime = 0;
int len = workModels.size();
for (int i = 0; i < len; i++) {
//获取当前未执行作业中最高响应比
float temp = -1;
int tmpflag = -1;
//更新响应比
for (hrrf.WorkModel w : workModels){
w.setRatio(runTime);
}
int timeflag = 9999;
for (int j = 0; j < len; j++) {
//获取已到达当前最高响应比的未执行作业
if ((workModels.get(j).getResponseRatio() > temp) && (workModels.get(j).isFlag() == false) && (runTime >= workModels.get(j).getArriveTime())) {
temp = workModels.get(j).getResponseRatio();
tmpflag = j;
}
}
//当前时间下没有已到达未执行作业
if(tmpflag == -1){
//找到最近即将到达未执行作业
for (int j = 0; j < len; j++) {
if ((timeflag >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
timeflag = workModels.get(j).getArriveTime();
tmpflag = j;
}
}
runTime = timeflag;
//更新响应比
for (hrrf.WorkModel w : workModels){
w.setRatio(runTime);
}
}
for(hrrf.WorkModel t : workModels){
System.out.println(t.getName()+"当前响应比为"+t.getResponseRatio()+" flag:"+t.isFlag());
}
System.out.println("执行作业"+workModels.get(tmpflag).getName());
System.out.println("----------------");
workModels.get(tmpflag).setStartTime(runTime);
runTime += workModels.get(tmpflag).getExecuteTime();
workModels.get(tmpflag).setFinishTime(runTime);
workModels.get(tmpflag).setTurnoverTime();
workModels.get(tmpflag).setWaitTime();
waitTime += workModels.get(tmpflag).getWaitTime();
workModels.get(tmpflag).setPriorityTurn();
workModels.get(tmpflag).setFlag(true);
this.setNowTime(runTime);
}
this.setAverageWait(waitTime, len);
for (hrrf.WorkModel t : workModels) {
System.out.println(t.toString());
}
System.out.println("Average wait time:" + this.getAverageWait());
}
public static void main(String[] args) {
HRRFmodel hrrfmodel = new HRRFmodel();
List
hrrf.WorkModel w1 = new hrrf.WorkModel("A",3,1);
hrrf.WorkModel w2 = new hrrf.WorkModel("B",1,2);
hrrf.WorkModel w3 = new hrrf.WorkModel("C",2,2);
hrrf.WorkModel w4 = new hrrf.WorkModel("D",0,3);
workModels.add(w1);
workModels.add(w2);
workModels.add(w3);
workModels.add(w4);
hrrfmodel.executeHRRF(workModels);
}
}
4.HPF代码
HPF作业类
package hpf;
public class WorkModel {
private String name;
private int arriveTime;
private int executeTime;
private int turnoverTime;
//带权周转时间
private float priorityTurn;
private int startTime;
private int finishTime=-1;
//等待时间 等待时间=周转-执行
private int waitTime;
//标识是否已执行
private boolean flag = false;
//默认优先级为5
private int priority = 5;
public WorkModel(String name, int arriveTime, int executeTime, int priority) {
this.name = name;
this.arriveTime = arriveTime;
this.executeTime = executeTime;
this.priority = priority;
}
@Override
public String toString() {
return "WorkModel{" +
"name='" + name + '\'' +
", arriveTime=" + arriveTime +
", executeTime=" + executeTime +
", turnoverTime=" + turnoverTime +
", priorityTurn=" + priorityTurn +
", startTime=" + startTime +
", finishTime=" + finishTime +
", waitTime=" + waitTime +
", priority=" + priority +
'}';
}
public void setFlag(boolean flag) {
this.flag = flag;
}
public int getPriority() {
return priority;
}
public boolean isFlag() {
return flag;
}
public void setStartTime(int startTime) {
this.startTime = startTime;
}
public void setPriorityTurn() {
this.priorityTurn = (float)this.turnoverTime/(float)this.executeTime;
}
public void setFinishTime(int finishTime) {
this.finishTime = finishTime;
}
public int getWaitTime() {
return waitTime;
}
public void setWaitTime() {
this.waitTime = this.turnoverTime - this.executeTime;
}
public void setTurnoverTime() {
this.turnoverTime = this.finishTime - this.arriveTime;
}
public int getArriveTime() {
return arriveTime;
}
public int getExecuteTime() {
return executeTime;
}
}
HPF类
package hpf;
import java.util.ArrayList;
import java.util.List;
//最高优先级算法(HPF)
public class HPFmodel {
//平均等待时间
private float averageWait;
private int nowTime;
public float getAverageWait() {
return averageWait;
}
public void setAverageWait(float averageWait,int len) {
this.averageWait = averageWait/len;
}
public void setNowTime(int nowTime) {
this.nowTime = nowTime;
}
public void executeHPF(List
int runTime = 0;
int waitTime = 0;
int len = workModels.size();
for (int i = 0; i < len; i++) {
//遍历获取当前未执行的最高优先级作业
int temp = -1;
int tmpflag = -1;
for (int j = 0; j < len; j++) {
if ((temp < workModels.get(j).getPriority()) && (runTime >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
temp = workModels.get(j).getPriority();
tmpflag = j;
}
}
//当前时间下没有已到达未执行作业
int timeflag = 9999;
if (tmpflag == -1){
for (int j = 0; j < len; j++) {
if ((timeflag >= workModels.get(j).getArriveTime()) && (workModels.get(j).isFlag() == false)){
timeflag = workModels.get(j).getArriveTime();
tmpflag = j;
}
}
runTime = timeflag;
}
workModels.get(tmpflag).setStartTime(runTime);
runTime += workModels.get(tmpflag).getExecuteTime();
workModels.get(tmpflag).setFinishTime(runTime);
workModels.get(tmpflag).setTurnoverTime();
workModels.get(tmpflag).setWaitTime();
workModels.get(tmpflag).setPriorityTurn();
waitTime += workModels.get(tmpflag).getWaitTime();
workModels.get(tmpflag).setFlag(true);
this.setNowTime(runTime);
}
this.setAverageWait(waitTime, len);
for (hpf.WorkModel t : workModels) {
System.out.println(t.toString());
}
System.out.println("Average wait time:" + this.getAverageWait());
}
public static void main(String[] args) {
HPFmodel hpfmodel = new HPFmodel();
List
hpf.WorkModel w1 = new hpf.WorkModel("A",2,5,3);
hpf.WorkModel w2 = new hpf.WorkModel("B",0,1,6);
hpf.WorkModel w3 = new hpf.WorkModel("C",0,3,7);
hpf.WorkModel w4 = new hpf.WorkModel("D",5,4,5);
workModels.add(w1);
workModels.add(w2);
workModels.add(w3);
workModels.add(w4);
hpfmodel.executeHPF(workModels);
}
}