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(); } }
部分运行结果:
相同数据的最高响应比结果为