import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;
/*
* 作者：Chensx1020
* 时间：2016-12-11
* 功能：CPU调度算法
* 1)先到先服务调度算法（FCFS）
* 2)最短作业优先调度算法，非抢占式（SJF）
* 3)优先级调度算法（PSA）
* 4)轮转法调度算法（RR）
* 5)最高响应比调度算法（HRR）
* 6)最短作业优先调度算法，抢占式（SJF）
*/
public class CPU {
//排序方法
public static String whichComp="FCFS";
//时间片
public static int timeSlice=4;
//进程类...............................................................
public static class MyProcess implements Comparable<MyProcess> {
private String name; //进程名字
private int arrive; //到达时间
private int work; //区间时间(服务时间)
private int rWork; //还需时间
private int priority; //优先级
private int begin; //开始时间
private double hrr; //响应比
private boolean flag; //标记该进程是否执行
public MyProcess(String name){
this.name = name;
this.flag = false;
}
public void setArrive(int arrive){
this.arrive = arrive;
}
public void setWork(int work){
this.work = work;
}
public void setRwork(int rWork){
this.rWork = rWork;
}
public void setPriority(int priority){
this.priority = priority;
}
public void setBegin(int begin){
this.begin = begin;
}
public void setHrr(){
this.hrr = (this.begin-this.arrive)*1.0/this.work + 1;
}
public void setHrr(double hrr){
this.hrr = hrr;
}
public void setFlag(){
this.flag = true;
}
public String getName(){
return this.name;
}
public int getArrive(){
return this.arrive;
}
public int getWork(){
return this.work;
}
public int getRwork(){
return this.rWork;
}
public int getPriority(){
return this.priority;
}
public int getBegin(){
return this.begin;
}
public double getHrr(){
return this.hrr;
}
public boolean getFlag(){
return this.flag;
}
@Override
public int compareTo(MyProcess o) {
if(whichComp.equals("FCFS")){
if(this.arrive>o.arrive)
return 1;
else if(this.arrive<o.arrive)
return -1;
else
return this.work-o.work;
}
else if(whichComp.equals("SJF")){
if(this.work>o.work)
return 1;
else if(this.work<o.work)
return -1;
else
return this.arrive-o.arrive;
}
else if(whichComp.equals("SJFS")){
if(this.rWork>o.rWork)
return 1;
else if(this.rWork<o.rWork)
return -1;
else
return this.arrive-o.arrive;
}
else if(whichComp.equals("PSA")){
if(this.priority>o.priority)
return 1;
else if(this.priority<o.priority)
return -1;
else
return this.arrive-o.arrive;
}
else if(whichComp.equals("HRR")){
if(this.begin>o.begin)
return 1;
else if(this.begin<o.begin)
return -1;
else{
if(this.hrr < o.hrr)
return 1;
else if(this.hrr > o.hrr)
return -1;
else{
return this.arrive-o.arrive;
// if(this.arrive>o.arrive)
// return 1;
// else if(this.arrive<o.arrive)
// return -1;
// else
// return this.work-o.work;
}
}
}
else{
return 0;
}
}
}
//FCFS类...............................................................
public static class FCFS{
private int count;
private String temp;
public FCFS(MyProcess test[]){
Arrays.sort(test);
count = test[0].getArrive();
temp = "";
int length = test.length;
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("先到先服务调度算法的结果为：");
System.out.println("进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t等待时间\t"
+ "周转时间\t带权周转时间\t");
for(int i=0; i<length-1; ++i){
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+count+"\t"
+(count+test[i].getWork())+"\t"
+(count-test[i].getArrive())+"\t"
+(count-test[i].getArrive()+test[i].getWork())+"\t"
+(count-test[i].getArrive()+test[i].getWork())*1.0/test[i].getWork()+"\t"
);
wait += count-test[i].getArrive();
cycle += count-test[i].getArrive()+test[i].getWork();
count += test[i].getWork();
if(count < test[i+1].getArrive())
count = test[i+1].getArrive();
temp += test[i].getName()+" ";
}
System.out.println(test[length-1].getName()+"\t"
+test[length-1].getArrive()+"\t"
+test[length-1].getWork()+"\t"
+count+"\t"
+(count+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())*1.0/test[length-1].getWork()+"\t"
);
wait += count-test[length-1].getArrive();
cycle += count-test[length-1].getArrive()+test[length-1].getWork();
temp += test[test.length-1].getName()+" ";
System.out.println("\n所以最后先到先服务调度算法执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//SJF类非抢占式...............................................................
public static class SJF{
private int count;
private String temp;
public SJF(MyProcess test[]){
Arrays.sort(test);
count = test[0].getArrive();
temp = "";
int length = test.length;
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("最短作业优先调度算法非抢占式的结果为：");
System.out.println("进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t等待时间\t"
+ "周转时间\t带权周转时间\t");
for(int i=0; i<length-1; ++i){
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+count+"\t"
+(count+test[i].getWork())+"\t"
+(count-test[i].getArrive())+"\t"
+(count-test[i].getArrive()+test[i].getWork())+"\t"
+(count-test[i].getArrive()+test[i].getWork())*1.0/test[i].getWork()+"\t"
);
wait += count-test[i].getArrive();
cycle += count-test[i].getArrive()+test[i].getWork();
count += test[i].getWork();
if(count < test[i+1].getArrive())
count = test[i+1].getArrive();
temp += test[i].getName()+" ";
}
System.out.println(test[length-1].getName()+"\t"
+test[length-1].getArrive()+"\t"
+test[length-1].getWork()+"\t"
+count+"\t"
+(count+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())*1.0/test[length-1].getWork()+"\t"
);
wait += count-test[length-1].getArrive();
cycle += count-test[length-1].getArrive()+test[length-1].getWork();
temp += test[test.length-1].getName()+" ";
System.out.println("\n所以最后最短作业优先调度算法非抢占式执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//SJF类抢占式...............................................................
public static class SJFS{
private int count;
private String temp; //执行的顺序
private int flag = 0; //计数，用于判断是否所有进程执行完毕
public SJFS(MyProcess test[]){
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("最短作业优先调度算法抢占式的结果为：");
System.out.println("进程名字\t到达时间\t区间时长\t开始时间\t结束时间\t剩余服务时间\t等待时间\t"
+ "周转时间\t带权周转时间\t");
int length = test.length; //长度
whichComp="FCFS";
Arrays.sort(test); //按照进程的到达时间排序
count = test[0].getArrive(); //count的值为程序最先到达的进程的到达时间
whichComp="SJFS";
Arrays.sort(test); //所有进程按照剩余服务时间的长短排序
String lastName = ""; //上一次执行的进程的名字
for(int i=0; i<length; ++i){
if(test[i].getArrive()<=count){
lastName = test[i].getName();
System.out.print(test[i].getName() + "\t"
+ test[i].getArrive() + "\t"
+ test[i].getWork() + "\t"
+ count + "\t");
temp = test[i].getName()+" ";
break;
}
}
boolean done = false;
while(true){
done = false;
++count;
for(int j=0; j<length; ++j){
if(test[j].getName().equals(lastName)){
test[j].setRwork(test[j].getRwork()-1); //剩余时间-1
if(test[j].getRwork() == 0){
++flag;
test[j].setRwork(999999999);
System.out.println(count + "\t"
+ "0\t\t"
+ (count-test[j].getWork()-test[j].getArrive()) + "\t" //等待时间
+ (count-test[j].getArrive()) + "\t" //周转时间
+ ((count-test[j].getArrive())*1.0/test[j].getWork()) + "\t" //带权周转
);
wait += count-test[j].getWork()-test[j].getArrive();
cycle += count-test[j].getArrive();
done = true;
}
break;
}
}
if(flag==length){
break;
}
Arrays.sort(test); //所有进程按照剩余服务时间的长短重新排序
for(int i=0; i<length; ++i){
if(test[i].getArrive()<=count){
if(lastName.equals(test[i].getName())){
// System.out.println(test[i].getName());
}
else{
for(int j=0; j<length; ++j){
if(test[j].getName().equals(lastName)){
if(!done){
System.out.println(count + "\t"
+ test[j].getRwork()+ "\t\t"
+ "未执行完\t" + "未执行完\t" + "未执行完\t");
}
}
}
lastName = test[i].getName();
System.out.print(test[i].getName() + "\t"
+ test[i].getArrive() + "\t"
+ test[i].getWork() + "\t"
+ count + "\t");
temp += test[i].getName()+" ";
}
break;
}
}
}
System.out.println("\n所以最后最短作业优先调度算法抢占式执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//PSA类...............................................................
public static class PSA{
private int count;
private String temp;
public PSA(MyProcess test[]){
Arrays.sort(test);
count = test[0].getArrive();
temp = "";
int length = test.length;
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("优先级调度算法的结果为：");
System.out.println("进程名字\t到达时间\t服务时间\t优先级\t开始时间\t结束时间\t等待时间\t"
+ "周转时间\t带权周转时间\t");
for(int i=0; i<length-1; ++i){
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+test[i].getPriority()+"\t"
+count+"\t"
+(count+test[i].getWork())+"\t"
+(count-test[i].getArrive())+"\t"
+(count-test[i].getArrive()+test[i].getWork())+"\t"
+(count-test[i].getArrive()+test[i].getWork())*1.0/test[i].getWork()+"\t"
);
wait += count-test[i].getArrive();
cycle += count-test[i].getArrive()+test[i].getWork();
count += test[i].getWork();
if(count < test[i+1].getArrive())
count = test[i+1].getArrive();
temp += test[i].getName()+" ";
}
System.out.println(test[length-1].getName()+"\t"
+test[length-1].getArrive()+"\t"
+test[length-1].getWork()+"\t"
+test[length-1].getPriority()+"\t"
+count+"\t"
+(count+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())+"\t"
+(count-test[length-1].getArrive()+test[length-1].getWork())*1.0/test[length-1].getWork()+"\t"
);
wait += count-test[length-1].getArrive();
cycle += count-test[length-1].getArrive()+test[length-1].getWork();
temp += test[test.length-1].getName()+" ";
System.out.println("\n所以最后优先级调度算法执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//HRR类...............................................................
public static class HRR{
private int count;
private String temp;
public HRR(MyProcess test[], MyProcess tests[]){
DecimalFormat df = new DecimalFormat("#.###"); //小数保留三位小数
Arrays.sort(tests);
count = tests[0].getBegin();
temp = "";
int length = test.length;
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("最高响应比调度算法的结果为：");
for(int tur = 1; tur<=length; ++tur){
System.out.println("\n正在执行第"+tur+"个进程："+tests[0].getName());
System.out.println("进程名字\t到达时间\t服务时间\t响应比\t开始时间\t结束时间\t等待时间\t"
+ "周转时间\t带权周转时间\t");
for(int i=0; i<length; ++i) {
if(test[i].getFlag()){ //已执行
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+"已执行完\t"
+test[i].getBegin()+"\t"
+(test[i].getBegin()+test[i].getWork())+"\t"
+(test[i].getBegin()-test[i].getArrive())+"\t"
+(test[i].getBegin()-test[i].getArrive()+test[i].getWork())+"\t"
+df.format((test[i].getBegin()-test[i].getArrive()+test[i].getWork())*1.0/test[i].getWork())+"\t"
);
continue;
}
else if(test[i].getArrive()>count){ //未到达
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+"未到达\t"
+"未到达\t"
+"未到达\t"
+"未到达\t"
+"未到达\t"
+"未到达\t"
);
continue;
}
else{
//执行该进程
if(test[i].getName().equals(tests[0].getName())){
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+df.format(test[i].getHrr())+"\t"
+test[i].getBegin()+"\t"
+(test[i].getBegin()+test[i].getWork())+"\t"
+(test[i].getBegin()-test[i].getArrive())+"\t"
+(test[i].getBegin()-test[i].getArrive()+test[i].getWork())+"\t"
+df.format((test[i].getBegin()-test[i].getArrive()+test[i].getWork())*1.0/test[i].getWork())+"\t"
);
wait += test[i].getBegin()-test[i].getArrive();
cycle += test[i].getBegin()-test[i].getArrive()+test[i].getWork();
test[i].setFlag();
tests[0].setFlag();
}
else{
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+df.format(test[i].getHrr())+"\t"
+"未开始\t"
+"未开始\t"
+"未开始\t"
+"未开始\t"
+"未开始\t"
);
}
}
}
int count1=count+tests[0].getWork();
for(int j=tests.length-1; j>=1; --j){
if(tests[j].getFlag()){
;
}
else{
if(count1 >= tests[j].getArrive()){ //进程已到
tests[j].setBegin(count1);
int x;
for(x=0; x<length; ++x){
if(tests[j].getName().equals(test[x].getName()))
break;
}
test[x].setBegin(count1);
tests[j].setHrr();
test[x].setHrr();
count = count1;
}
else{
count = tests[j].getBegin();
}
}
}
temp += tests[0].getName()+" ";
//改变执行过的进程数据，使再次排序时排在未执行数据的后面
tests[0].setArrive(999999999);
tests[0].setBegin(999999999);
tests[0].setHrr(-1.0);
Arrays.sort(tests); //重新排序
}
System.out.println("\n所以最后最高响应比调度算法执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//RR类...............................................................
public static class RR{
private int count;
private String temp;
public RR(MyProcess test[]){
count = 0;
temp = "";
int length = test.length;
int wait = 0; //总等待时间
int cycle = 0; //总周转时间
int tur = 1; //第几趟
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.println("轮转法调度算法的结果为：");
System.out.println("第"+tur+"趟结果\n进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t剩余所需服务时间\t"
+ "等待时间\t周转时间\t带权周转时间\t");
int tempCount=0; //记录是否还有进程未执行完
int i=0;
while(true){
if(test[i].getRwork()>timeSlice){
test[i].setRwork(test[i].getRwork()-timeSlice);
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+count+"\t"
+(count+timeSlice)+"\t"
+test[i].getRwork()+"\t\t"
+"未执行完\t"
+"未执行完\t"
+"未执行完\t"
);
count += timeSlice;
temp += test[i].getName()+" ";
++i;
if(i==length){
i=0;
++tur;
System.out.println("第"+tur+"趟结果\n进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t"
+ "剩余所需服务时间\t等待时间\t周转时间\t带权周转时间\t");
}
}
else if(test[i].getRwork()>0){
System.out.println(test[i].getName()+"\t"
+test[i].getArrive()+"\t"
+test[i].getWork()+"\t"
+count+"\t"
+(count+test[i].getRwork())+"\t"
+"0\t\t"
+(count+test[i].getRwork()-test[i].getWork()-test[i].getArrive())+"\t"
+(count+test[i].getRwork()-test[i].getArrive())+"\t"
+(count+test[i].getRwork()-test[i].getArrive())*1.0/test[i].getWork()+"\t"
);
wait += count+test[i].getRwork()-test[i].getWork()-test[i].getArrive();
cycle += count+test[i].getRwork()-test[i].getArrive();
count += test[i].getRwork();
temp += test[i].getName()+" ";
test[i].setRwork(0);
++i;
if(i==length){
i=0;
++tur;
System.out.println("第"+tur+"趟结果\n进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t"
+ "剩余所需服务时间\t等待时间\t周转时间\t带权周转时间\t");
}
++tempCount;
if(tempCount == length)
break;
}
else{
++i;
if(i==length){
i=0;
++tur;
System.out.println("第"+tur+"趟结果\n进程名字\t到达时间\t服务时间\t开始时间\t结束时间\t"
+ "剩余所需服务时间\t等待时间\t周转时间\t带权周转时间\t");
}
continue;
}
}
System.out.println("\n所以最后轮转法调度算法执行的顺序为：" + temp);
System.out.println("平均等待时间为：" + wait*1.0/length + "，平均周转时间为：" + cycle*1.0/length);
}
}
//主函数................................................................
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
while(true){
int n; //进程数
while(true){
try{
System.out.print("输入进程个数：");
n = input.nextInt();
break;
} catch(Exception e){
System.out.println("输入不合法，请重新输入！");
input.nextLine();
}
}
MyProcess test[] = new MyProcess[n]; //进程数组
MyProcess tests[] = new MyProcess[n]; //临时进程数组（HRR用）
System.out.println("您想执行何种操作：");
System.out.println("1.FCFS(先到先服务调度算法)");
System.out.println("2.SJF(最短作业优先调度算法,非抢占式)");
System.out.println("3.PSA(优先级调度算法)");
System.out.println("4.RR(轮转法调度算法)");
System.out.println("5.HRR(最高响应比调度算法)");
System.out.println("6.SJF(最短作业优先调度算法,抢占式)");
System.out.println("7.退出");
int which;
try{
which = input.nextInt();
} catch(Exception e){
System.out.println("输入不合法，请重新输入！");
input.nextLine();
continue;
}
//FCFS
if(which == 1){
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的到达时间和服务时间:");
test[i].setArrive(input.nextInt());
test[i].setWork(input.nextInt());
}
whichComp = "FCFS";
new FCFS(test);
}
//SJF，非抢占式
else if(which == 2){
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的到达时间和服务时间:");
test[i].setArrive(input.nextInt());
test[i].setWork(input.nextInt());
}
whichComp = "SJF";
new SJF(test);
}
//PSA
else if(which == 3){
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的到达时间和服务时间和优先级:");
test[i].setArrive(input.nextInt());
test[i].setWork(input.nextInt());
test[i].setPriority(input.nextInt());
}
whichComp = "PSA";
new PSA(test);
}
//RR
else if(which == 4){
System.out.print("请输入时间片的大小：");
timeSlice = input.nextInt();
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的服务时间（剩余时间）:");
test[i].setWork(input.nextInt());
test[i].setRwork(test[i].getWork());
}
whichComp = "RR";
new RR(test);
}
//HRR
else if(which == 5){
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
tests[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的到达时间和服务时间:");
int a = input.nextInt();
test[i].setArrive(a);
tests[i].setArrive(a);
int b = input.nextInt();
test[i].setWork(b);
tests[i].setWork(b);
//设置开始时间和响应比
test[i].setBegin(a);
test[i].setHrr();
tests[i].setBegin(a);
tests[i].setHrr();
}
whichComp = "HRR";
new HRR(test,tests);
}
//SJF,抢占式
else if(which == 6){
for(int i=0; i<n; ++i){
test[i] = new MyProcess("P"+(i+1));
System.out.print("请输入P" + (i+1) + "的到达时间和服务时间:");
test[i].setArrive(input.nextInt());
test[i].setWork(input.nextInt());
test[i].setRwork(test[i].getWork()); //设置剩余时间
}
whichComp = "SJFS";
new SJFS(test);
}
else if(which == 7){
System.out.println("程序结束！");
break;
}
else {
System.out.println("输入不合法，请重新输入！");
}
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------");
System.out.print("------------------------------------------------------------------");
System.out.println("------------------------------------------------------------------\n\n");
}
input.close();
}
}
部分运行结果：
相同数据的最高响应比结果为