操作系统常见的进程调度算法

1.先来先服务

       (FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的其他因素。FCFS算法简单易行，是一种非抢占式策略，但性能却不大好。只考虑他的到达时间来决定他的执行顺序。

private void FCFS() {

//        按提交时间排序得到新的序列
        float[] arr = new float[size];
        Processcourse[] tmp = new Processcourse[size];
        for (int i = 0; i < size ; i++) {
            arr[i] = work[i].submitTime;
        }
        Arrays.sort(arr);
        for (int i = 0; i < size ; i++) {
            for (int j = 0; j < size ; j++) {
                if(arr[i] == work[j].submitTime){
                    tmp[i] = work[j];
                }
            }
        }
        work = tmp;


        //得到第一个的任务的全部时间
        work[0].startTime = work[0].submitTime;
        work[0].finishTime = work[0].submitTime + work[0].runTime;
       //求出每个的开始时间和结束时间
        for (int j = 1; j < this.size; j++) {
            if(work[j].submitTime <= work[j-1].finishTime){//判断后面进程是否到来
            work[j].startTime = work[j-1].finishTime;
            work[j].finishTime = work[j].startTime+work[j].runTime;
            }else{
                work[j].startTime = work[j].submitTime;
                work[j].finishTime = work[j].startTime+work[j].runTime;
            }
        }
        //求出周转时间和带权周转时间
        for (int j = 0; j < this.size; j++) {
            work[j].turnoverTime = work[j].finishTime - work[j].submitTime;
            work[j].wtTime = work[j].turnoverTime/work[j].runTime;
        }
        System.out.println("运行顺序：");
        for (int i = 0; i < this.size; i++) {
            System.out.print(work[i].workName+" ");
        }
        System.out.println();
        System.out.println("作业"+"	"+"提交时间"+"	"+"运行时间"+"	"+"开始时间"+"	"+"结束/完成时间"+"	"+"周转时间"+"	"+"带权周转时间");
        for (int i = 0; i < this.size; i++) {
            //小数点后保留一位，并且四舍五入
            System.out.println(work[i].workName+"    "+work[i].submitTime+"      "+work[i].runTime+"      "+work[i].startTime+"      "
                    +work[i].finishTime+"      "+(float)(Math.round(work[i].turnoverTime*10))/10+"      "+(float)(Math.round(work[i].wtTime*10))/10);
        }

        float sumturnTime = 0;
        float sumwtfTime = 0;
        for (int i = 0; i < this.size; i++) {
            sumturnTime+= work[i].turnoverTime;
            sumwtfTime+= work[i].wtTime;
        }
        System.out.println("平均周转时间："+(float)(Math.round((sumturnTime/size)*100))/100+" "+"平均带权周转时间："+(float)(Math.round((sumwtfTime/size)*100))/100);

    }

　　测试用例：

1  8.5  0.5  1
2  8.0  1.0  1
3  9.0  0.2  2
4  9.1  0.1  3

运行结果：

2.短作业优先

      （SJF, Shortest Job First），对预计执行时间短的作业（进程）优先分派处理机。 再不考虑抢占的前提下，判断进程到达时间是否小于上一个进程的完成时间，进入等待序列，然后找到等待序列的完成所要时间最短的进程。

    private void SJF() {

        //按提交时间排序得到新的序列
        float[] arr = new float[size];
        Processcourse[] tmpArr = new Processcourse[size];
        for (int i = 0; i < size ; i++) {
            arr[i] = work[i].submitTime;
        }
        //排序提交时间
        Arrays.sort(arr);
        //重新赋值
        for (int i = 0; i < size ; i++) {
            for (int j = 0; j < size ; j++) {
                if(arr[i] == work[j].submitTime){
                    tmpArr[i] = work[j];
                }
            }
        }
        work = tmpArr;

        //得到第一个的任务的开始时间和完成时间
        work[0].startTime = work[0].submitTime;
        work[0].finishTime = work[0].submitTime + work[0].runTime;

        //存入第一个进程完成时间
        float tmpfinshTime = work[0].finishTime;

        //等待序列
        Processcourse[] wait = new Processcourse[this.size];
        //运行完成序列
        Processcourse[] finish  = new Processcourse[this.size];
        int finNum = 0;//完成序列的个数
        int index = 1;//下标从数组的一号位置开始

        System.out.println("运行进程：");
        System.out.println(work[0].workName);
        for (int j = 0; j < size-1; j++) {
        int num = 0;   //等待
        int k = 1;

        //等待序列
          System.out.println("等待进程：");
        for (int i = 1; i < this.size; i++) {
            if(work[i]!=null && work[i].submitTime <= tmpfinshTime){
                wait[k] = work[i];
                k++;
                num++;
            }
        }
        //遍历等待序列
            for (int i = 1 ; i <= num; i++) {
                System.out.print(wait[i].workName+" ");
            }
            System.out.println();

        float min = 0.0f;
        //找到等待序列的最小运行时间
            min = wait[1].runTime;
        for (int i = 1; i <= num; i++) {
                if (wait[i].runTime < min) {
                    min = wait[i].runTime;
                }
        }
        for (int i = 1; i < size ; i++) {
            if(work[i] != null && work[i].runTime == min){
                work[i].startTime = tmpfinshTime;
                work[i].finishTime = work[i].startTime+work[i].runTime;
                //更新完成时间
                tmpfinshTime = work[i].finishTime;
                finish[index++] = work[i];
                finNum++;
                work[i] = null;
            }
        }

            //输出运行过的进程
            System.out.println("运行进程：");
            System.out.println(finish[finNum].workName);
    }

    //将临时值放回原数组
        for (int i = 1; i <= finNum; i++) {
            work[i] = finish[i];
        }
        

            //求出周转时间和带权周转时间
            for (int i = 0; i < this.size; i++) {
                work[i].turnoverTime = work[i].finishTime - work[i].submitTime;
                work[i].wtTime = work[i].turnoverTime / work[i].runTime;
            }

            System.out.println("作业" + "	" + "提交时间" + "	" + "运行时间" + "	" + "开始时间" + "	" + "结束/完成时间" + "	" + "周转时间" + "	" + "带权周转时间");
            for (int i = 0; i < this.size; i++) {
                //小数点后保留一位，并且四舍五入
                System.out.println(work[i].workName + "    " + work[i].submitTime + "      " + work[i].runTime + "      " + work[i].startTime + "      "
                        + work[i].finishTime + "      " + (float) (Math.round(work[i].turnoverTime * 10)) / 10 + "      " + (float) (Math.round(work[i].wtTime * 10)) / 10);
            }
        float sumturnTime = 0;
        float sumwtfTime = 0;
        for (int i = 0; i < this.size; i++) {
            sumturnTime+= work[i].turnoverTime;
            sumwtfTime+= work[i].wtTime;
        }
        System.out.println("平均周转时间："+(float)(Math.round((sumturnTime/size)*100))/100+"  "+"平均带权周转时间："+(float)(Math.round((sumwtfTime/size)*100))/100);
        }

测试用例：

1  8.5  0.5  1
2  8.0  1.0  1
3  9.0  0.2  2
4  9.1  0.1  3

运行结果：

3.高响应比优先

       高响应比优先调度算法（Highest Response Ratio Next）是一种对CPU中央控制器响应比的分配的一种算法。HRRN是介于FCFS（先来先服务算法）与SJF（短作业优先算法）之间的折中算法，既考虑作业等待时间又考虑作业运行时间，既照顾短作业又不使长作业等待时间过长，改进了调度性能。

       响应比 =（等待时间+要求服务时间）/ 要求服务时间

private void HRRN() {
        //按提交时间排序得到新的序列
        float[] arr = new float[size];
        Processcourse[] tmpArr = new Processcourse[size];
        for (int i = 0; i < size; i++) {
            arr[i] = work[i].submitTime;
        }
        //排序提交时间
        Arrays.sort(arr);
        //重新赋值
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (arr[i] == work[j].submitTime) {
                    tmpArr[i] = work[j];
                }
            }
        }
        work = tmpArr;

        //得到第一个的任务的开始时间和完成时间
        work[0].startTime = work[0].submitTime;
        work[0].finishTime = work[0].submitTime + work[0].runTime;

        //存入第一个进程完成时间
        float tmpfinshTime = work[0].finishTime;

        //等待序列
        Processcourse[] wait = new Processcourse[this.size];
        //运行完成序列
        Processcourse[] finish = new Processcourse[this.size];
        int finNum = 0;//等待序列的个数
        int index = 1;//下标从数组的一号位置开始

        System.out.println("运行顺序如下：");
        System.out.println("运行进程：");
        System.out.println(work[0].workName);

        //运行的次数
        for (int j = 1; j < size; j++) {
            int num = 0;
            int k = 1;

            //等待序列
            System.out.println("等待进程：");
            for (int i = 1; i < this.size; i++) {
                if (work[i] != null && work[i].submitTime <= tmpfinshTime) {
                    wait[k] = work[i];
                    k++;
                    num++;
                }
            }
            //遍历等待序列
            for (int i = 1; i <= num; i++) {
                System.out.print(wait[i].workName + " ");
            }
            System.out.println();

            //找到等待序列的最高优先级
            float max = 0.0f;
            float waitTime = 0.0f;
            float tmp2 = 0.0f;//记录响应比
//            Processcourse[] tmp1 = new Processcourse[this.size];
            String tmpName = null;
            for (int i = 1; i <= num; i++) {
                waitTime =tmpfinshTime - wait[i].submitTime;
                tmp2 = 1.0F+(waitTime/wait[i].runTime);
                wait[i].priority = tmp2;
                max = (1.0f+((tmpfinshTime - wait[1].submitTime)/wait[1].runTime));
                if(tmp2 > max){
                   max = (1.0f+(waitTime/wait[i].runTime));
                    tmpName = wait[i].workName;
                }else {
                    tmpName = wait[1].workName;
                }
            }



            for (int i = 1; i < this.size; i++) {
                if(work[i] != null && tmpName.equals(work[i].workName)){
                    work[i].priority = max;
                }
            }
        //tmp1置空
//            tmp1 = null;
            for (int i = 1; i < size; i++) {
                if (work[i] != null && work[i].priority == max) {
                    work[i].startTime = tmpfinshTime;
                    work[i].finishTime = work[i].startTime + work[i].runTime;
                    //更新完成时间
                    tmpfinshTime = work[i].finishTime;
                    //更新
                    finish[index++] = work[i];
                    finNum++;
                    work[i] = null;
                }
            }

            //输出运行过的进程
            System.out.println("运行进程：");
            System.out.println(finish[finNum].workName);
        }

        //将临时值放回原数组
        for (int i = 1; i <= finNum; i++) {
            work[i] = finish[i];
        }
        

        //求出周转时间和带权周转时间
        for (int i = 0; i < this.size; i++) {
            work[i].turnoverTime = work[i].finishTime - work[i].submitTime;
            work[i].wtTime = work[i].turnoverTime / work[i].runTime;
        }

        System.out.println("作业" + "	" + "提交时间" + "	" + "运行时间" + "	" + "开始时间" + "	" + "结束/完成时间" + "	" + "周转时间" + "	" + "带权周转时间"+"	"+"响应比");
        for (int i = 0; i < this.size; i++) {
            //小数点后保留一位，并且四舍五入
            System.out.println(work[i].workName + "    " + work[i].submitTime + "      " + work[i].runTime + "      " + work[i].startTime + "      "
                    + work[i].finishTime + "      " + (float) (Math.round(work[i].turnoverTime * 100)) / 100 + "      " + (float) (Math.round(work[i].wtTime * 100)) / 100+"     "+(float) (Math.round(work[i].priority* 100)) / 100);
        }
        float sumturnTime = 0;
        float sumwtfTime = 0;
        for (int i = 0; i < this.size; i++) {
            sumturnTime += work[i].turnoverTime;
            sumwtfTime += work[i].wtTime;
        }
        System.out.println("平均周转时间：" + (float) (Math.round((sumturnTime / size) * 100)) / 100 + "  " + "平均带权周转时间：" + (float) (Math.round((sumwtfTime / size) * 100)) / 100);
    }

测试用例：

1  8.5  0.5  1
2  8.0  1.0  1
3  9.0  0.2  2
4  9.1  0.1  3

运行结果：

4.时间片轮转法

    时间片轮转（RR）是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。

    private void RR() {
        System.out.println("请输入时间片的大小：");
        float fTime = sc.nextFloat();//时间片大小
        if(fTime <= 0 ){
            System.out.println("无效输入");
            return;
        }

        //按提交时间排序得到新的序列
        float[] arr = new float[size];
        Processcourse[] tmpArr = new Processcourse[size];
        for (int i = 0; i < size; i++) {
            arr[i] = work[i].submitTime;
        }
        //排序提交时间
        Arrays.sort(arr);
        //重新赋值
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (arr[i] == work[j].submitTime) {
                    tmpArr[i] = work[j];
                }
            }
        }
        work = tmpArr;
        //方便再次调用
        for (int i = 0; i < this.size; i++) {
            work[i].flag = false;
        }
        //无该过程最终运行时间全为0.0(最终重新赋值给work)
        float tempRunTime[] = new float[this.size];
        for (int i = 0; i < this.size; i++) {
            tempRunTime[i] = work[i].runTime;
        }

        //等待序列
        Processcourse[] wait = new Processcourse[100];
        int num = 1;   //等待序列个数(开始默认一个)

        //运行完成序列
        Processcourse[] finish  = new Processcourse[this.size];
        int number = 0;  //完成个数
        //当前切换的时间
        float nowTime = work[0].submitTime;  //记录进程开始时间
        float overTime = 0;  //记录进程出来时间

        wait[0] = work[0];
        work[0].flag = true;//标记其已经进入等待序列(false么有进入过，true进入过，相当于原数组的元素只进入一次就绪队列，接下来的的其结束与否只在等待序列中判断)
        String tmpName = null;

        //临时记录在上一个么有完成的进程
        Processcourse[] tmpWait = new Processcourse[1];

        System.out.println("时刻："+nowTime+" 进程："+work[0].workName+" 开始运行");
        int k= 0;
        int stopFlag = 0;
        //当作业么有运行完，一直执行
        while (stopFlag != this.size){
            //当前任务么有运行完
            if(wait[k]!=null) {
                if (wait[k].runTime > fTime) {
                    wait[k].runTime -= fTime;
                    //更新当前还需要运行的时间
                    nowTime += fTime;//更新当前时间
                    System.out.println("时刻：" + nowTime + " 进程：" + wait[k].workName + " 停止运行，进入就绪队列");
                    tmpWait[0] = wait[k];
                } else {
                    nowTime += wait[k].runTime;
                    wait[k].runTime = 0;//说明运行结束
                    tmpName = wait[k].workName;
                    overTime = nowTime;
                    System.out.println("时刻：" + overTime + " 进程：" + wait[k].workName + " 运行结束");
                }
            }
            //如果等待序列里面其运行结束，将原数组直null，方便不去判断,并且完成数加一
            for (int j = 0; j < this.size; j++) {
                if(work[j] != null && tmpName!= null && tmpName.equals(work[j].workName)){//让运行过得不能排在么运行的前面
                    work[j].finishTime = overTime;
//                    work[j].turnoverTime = overTime - work[j].submitTime;
//                    work[j].wtTime = (work[j].turnoverTime/work[j].runTime);
                    finish[number++] = work[j];
                    work[j] = null;
                    stopFlag++;
                }
            }

            //判断进入等待序列
            for (int j = 0; j < this.size; j++) {
                if((work[j] != null)  && (work[j].submitTime <= nowTime) && (work[j].flag == false) ){
                    wait[num++] = work[j];
                    work[j].flag = true;
                }
            }

            if(tmpWait[0] != null) {
                wait[num++] = tmpWait[0];
            }
                tmpWait[0] = null;
            k++;

        }

       wait = null;
        //将其放回原work数组
        for (int i = 0; i < this.size; i++) {
            work[i] = finish[i];
        }

        //按提交时间排序得到新的序列
        float[] arr1 = new float[size];
        Processcourse[] tmpArr1 = new Processcourse[size];
        for (int i = 0; i < size; i++) {
            arr1[i] = work[i].submitTime;
        }
        //排序提交时间
        Arrays.sort(arr1);
        //重新赋值
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (arr1[i] == work[j].submitTime) {
                    tmpArr1[i] = work[j];
                }
            }
        }
        work = tmpArr1;

        //还原其初始运行时间
        for (int i = 0; i < this.size ; i++) {
            work[i].runTime = tempRunTime[i];
        }

        //求出周转时间和带权周转时间
        for (int i = 0; i < this.size; i++) {
            work[i].turnoverTime = work[i].finishTime - work[i].submitTime;
            work[i].wtTime = work[i].turnoverTime / work[i].runTime;
        }

        System.out.println("作业" + "	" + "提交时间" + "	" + "运行时间" +  "	" + "结束/完成时间" + "	" + "周转时间" + "	" + "带权周转时间");
        for (int i = 0; i < this.size; i++) {
            //小数点后保留一位，并且四舍五入
            System.out.println(work[i].workName + "    " + work[i].submitTime + "      " + work[i].runTime +  "      "
                    + work[i].finishTime + "      " + (float) (Math.round(work[i].turnoverTime * 100)) / 100 + "      " + (float) (Math.round(work[i].wtTime * 100)) / 100);
        }
        float sumturnTime = 0;
        float sumwtfTime = 0;
        for (int i = 0; i < this.size; i++) {
            sumturnTime += work[i].turnoverTime;
            sumwtfTime += work[i].wtTime;
        }
        System.out.println("平均周转时间：" + (float) (Math.round((sumturnTime / size) * 100)) / 100 + "  " + "平均带权周转时间：" + (float) (Math.round((sumwtfTime / size) * 100)) / 100);

    }

测试用例：

p1  0  5  1
p2  2  4  1
p3  4  1  1
p4  5  6  1

运行结果：

进程类：

public class Processcourse {
    String workName;//作业
    float submitTime; //提交时间
    float runTime;//运行时间
    float startTime;//开始时间
    float finishTime;  //完成时间
    float turnoverTime;//周转时间
    float wtTime;   //带权周转时间
    float priority;  //响应比
    float prior;     //优先级
    boolean flag;   //标记

    public Processcourse(String work, float submitTime, float runTime,float prior) {
        this.workName = work;
        this.submitTime = submitTime;
        this.runTime = runTime;
        this.prior = prior;
    }

    @Override
    public String toString() {
        return "Processcourse{" +
                "workName=" + workName +
                ", submitTime=" + submitTime +
                ", runTime=" + runTime +
                ", startTime=" + startTime +
                ", finishTime=" + finishTime +
                ", turnoverTime=" + turnoverTime +
                ", wtTime=" + wtTime +
                ",priority=" + priority+
                "prior="+prior+
                ",flag="+flag+
                '}';
    }

}

初始化以及main函数类：

public class Control {
    private Processcourse[] work;
    int maxWork = 100;
    int size; //真实作业个数
    private Scanner sc;
    public Control() {
      this.work = new Processcourse[maxWork];
      this.sc = new Scanner(System.in);
    }

    public static void main(String[] args) {
        Control con = new Control();
        con.start();//程序入口
    }

    private void start() {
        System.out.println("===================================");
        System.out.println("欢迎来到本系统");
        //初始化
        System.out.println("请输入进程的个数：" );
        int num = sc.nextInt();
        System.out.println("请依次输入进程号，提交时间，运行时间，优先级（中间用空格隔开）：");
        int i = 0;
        while(i < num){
            String workName = sc.next();//作业名
            float submitTime = sc.nextFloat(); //提交时间
            float runTime = sc.nextFloat();//运行时间
            float  prior = sc.nextFloat();//优先级
            if(i == size){
                this.work[this.size++] = new Processcourse(workName,submitTime,runTime,prior);
            }
            i++;
        }
        for (; ; ) {
            System.out.println("请选择进程调度方法：");
            System.out.println("1.先来先服务法");
            System.out.println("2.短作业优先法");
            System.out.println("3.高响应比法");
            System.out.println("4.时间片轮转法");
            System.out.println("5.高优先级法");
            System.out.println("6.退出");
            System.out.println("===================================");
            int ch = sc.nextInt();
            switch (ch){
                case 1:
                    FCFS();
                    break;
                case 2:
                    SJF();
                    break;
                case 3:
                    HRRN();
                    break;
                case 4:
                    RR();
                    break;
                case 5:
                    PSA();
                    break;
                case 6:
                    System.out.println("再见");
                    return;
                    default:
                        System.out.println("无效输入,请重新输入！");
            }
        }
    }

        以上便是除了高优先级的（高优先级同短作业优先代码类似）全部代码，由于采用数组代码比较冗长，输出函数可以单独写一个方法封装，也可以减少代码量，但是由于当时图方便，直接将第一个写的粘贴修改输出，自己可以将其封装。