作业调度

本文主要介绍了OS作业调度的三种算法(FCFS SJF HRN)，希望对您有所帮助

一. 实验目的

  1. 掌握作业调度的基本思想
  2. 熟练使用各种作业调度算法描述的过程
  3. 掌握各种算法的优缺点
  4. 提高理论和实践结合的能力

二. 实验内容

  1. FCFS 先来先服务
  2. SJF 最短作业优先
  3. HRN 最高响应比优先算法

三. 实验环境

  1. 实践平台 windows
  2. 编写环境 java
  3. 编译器 idea

四. 实验设计原理

  1. FCFS：先来先服务

    根据作业进入的先后顺序来进行调度，最先进的最先执行

  2. SJF：最短作业优先

    根据执行所需的时间来确定下一个执行的作业

  3. HRN：最高相应比优先

    根据作业的响应比选出最高的那个对应的作业执行

五. 实验详细实现过程和算法流程

  1. FCFS 先来先服务

  2. SJF 最短作业优先

  3. HRN 最高相应比优先

六. 实验调试与结果分析

  1. FCFS

  2. SJF

  3. HRN

七. 源代码

  1. job类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public class job {
        public int index;//job序列号
        public int arriveTime;//到达时间
        public int serviceTime;//执行总时间
        public int startTime =0;//开始执行时间
        public int finishTime =0;//结束时间
        public int turnTime =0;//周转时间
        public double powerTime =0;//带权周转时间

        public job(int index,int arriveTime, int serviceTime){
            this.index = index;
            this.arriveTime = arriveTime;
            this.serviceTime = serviceTime;
        }
        public void display(){
            System.out.println("  "+index+"      "+arriveTime+"       "+serviceTime+"         "+startTime+"       "+finishTime+"     "+turnTime+"      "+powerTime);
        }
    }

  2. 主类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    public class test {
        public static int digitToTime(int a,int b){//计算时间求和换算
            int ans = 0;
            int h = a/100;
            int m = a%100;
            h += (m+b)/60;
            m = (m+b)%60;
            ans = h*100 + m;
            return ans;
        }
        public static int subTime(int a,int b){//计算时间差值
            int h1 = a/100;
            int m1 = a%100;
            int h2 = b/100;
            int m2 = b%100;
            int t1 = h1*60+m1;
            int t2 = h2*60+m2;
            return t1-t2;
        }
        public static void FCFS(job[] data){//先来先服务
            int preFinishTime = 0; // 前一个作业的完成时间即为下一个作业的开始时间
            preFinishTime = data[0].arriveTime;//初始化前一个完成时间
             
            for (job datum : data) {
                //开始时间等于上一个完成时间
                datum.startTime = preFinishTime;
                // 作业的完成时间为上一个作业的完成时间加当前作业的服务时间
                datum.finishTime = digitToTime(preFinishTime,datum.serviceTime) ;
                preFinishTime = datum.finishTime;
                // 周转时间 = 完成时间 - 到达时间
                datum.turnTime = subTime(datum.finishTime,datum.arriveTime);
                // 带权周转时间 = 作业的周转时间 / 系统提供服务的时间
                datum.powerTime = (double) datum.turnTime / datum.serviceTime;
            }
            ansDisplay(data);
        }
        public static void SJF(job[] data){//短作业优先
            int preFinishTime = 0; // 前一个作业的完成时间即为下一个作业的开始时间
            preFinishTime = data[0].arriveTime;//初始化前一个完成时间
            int index=0;
            for(int i=0;i<data.length;i++){//这一层for循环实际起的作用是作业次数
                int min_job = 999;
                for (int j=0;j<data.length;j++){//这一层循环判断所有作业中还未执行的最短作业
                    //判断条件
                    //还未执行
                    //比min_job还要小才可更换
                    //到达时间小于上一个完成时间
                    if(data[j].startTime==0 && data[j].serviceTime<min_job && data[j].arriveTime<=preFinishTime){
                        min_job = data[j].serviceTime;
                        index = j;//循环结束后得到下一次作业的index
                    }
                }
                //与上面的一致 根本区别就是循环选取的不是早到的那个 而是最短的那个
                data[index].startTime = preFinishTime;
                data[index].finishTime = digitToTime(preFinishTime,data[index].serviceTime);
                preFinishTime = data[index].finishTime;
                data[index].turnTime = subTime(data[index].finishTime,data[index].arriveTime);
                data[index].powerTime = (double) data[index].turnTime / data[index].serviceTime;
            }
            ansDisplay(data);
        }
        public static void HRN(job[] data){//最高响应比优先
            int preFinishTime = 0; // 前一个作业的完成时间即为下一个作业的开始时间
            preFinishTime = data[0].arriveTime;//初始化前一个完成时间
            int index=0;
            for(int i=0;i<data.length;i++){//这一层for循环实际起的作用是作业次数
             
                double max_response = 0;
                for (int j=0;j<data.length;j++){//这一层循环判断所有作业中还未执行的响应比最高的作业
                    //判断条件
                    //还未执行
                    //到达时间小于上一个完成时间
                    if(data[j].startTime==0 && data[j].arriveTime<=preFinishTime){
                        //比max_response大才可更换
                        double response = (digitToTime(preFinishTime,data[j].serviceTime)-data[j].arriveTime) / (double)data[j].serviceTime;
                        if(response>max_response){
                            index = j;//循环结束后得到下一次作业的index
                            max_response = response;
                        }
                    }
                }
                data[index].startTime = preFinishTime;
                data[index].finishTime = digitToTime(preFinishTime,data[index].serviceTime);
                preFinishTime = data[index].finishTime;
                data[index].turnTime = subTime(data[index].finishTime,data[index].arriveTime);
                data[index].powerTime = (double) data[index].turnTime / data[index].serviceTime;
            }
            ansDisplay(data);
        }
        public static void ansDisplay(job[] data){
            double avgTurnTime = 0;
            double avgPowerTime = 0;
            System.out.println("作业序号\t"+"到达时间\t" + "执行总时间\t" + "开始执行时间\t" + "结束时间\t" + "周转时间\t" + "带权周转时间\t");
            for (job datum : data) {
                avgTurnTime += datum.turnTime;
                avgPowerTime += datum.powerTime;
                datum.display();
            }
            avgTurnTime /= data.length;
            avgPowerTime /= data.length;
            System.out.println("平均周转时间"+avgTurnTime);
            System.out.println("平均带权周转时间"+avgPowerTime);
        }
        public static void main(String[] args) {
            int way;
            Scanner stdin = new Scanner(System.in);
            System.out.println("请输入调度方式(1.FCFS 2.SJF 3.HRN)");
            way = stdin.nextInt();
            int sum;
            System.out.println("请输入作业数");
            sum = stdin.nextInt();
            job[] data = new job[sum];
            System.out.println("请输入作业数据(1 800 50)");
            for(int i =0; i <sum; i++){
                int a,b,c;
                a = stdin.nextInt();
                b = stdin.nextInt();
                c = stdin.nextInt();
                data[i] = new job(a,b,c);
            }
    //        测试读入代码
    //        for(int i=0;i<sum;i++){
    //            data[i].display();
    //        }
            if(way == 1)
                FCFS(data);
            else if(way == 2)
                SJF(data);
            else 
                HRN(data);
        }
    }
操作系统
#操作系统
作业调度
http://kaikai12321.github.io/2022/11/20/作业调度/
作者
Hou Kai
发布于
2022年11月20日
许可协议