精华内容
下载资源
问答
  • 响应比最高优先调度算法(HRRF)

    万次阅读 多人点赞 2018-05-10 22:32:29
    响应比最高优先算法是通过计算输入井后备队列中每个作业的响应比大小,从中选择响应比最高的作业装入主存,这样既考虑了作业的等待时间,又考虑了作业的运行时间。 二、实验要求 假设本系统仍采用单道批处理...

    一、实验目的

           作业调度算法是指依照某种原则或策略从后备作业队列中选取作业的方法。响应比最高者优先算法是通过计算输入井后备队列中每个作业的响应比大小,从中选择响应比最高的作业装入主存,这样既考虑了作业的等待时间,又考虑了作业的运行时间。

    二、实验要求

           假设本系统仍采用单道批处理系统,忽略设备工作时间和系统进行调度所花的时间。要求从键盘输入作业个数N,及每个作业的作业名、作业入井时间、估计运行时间。请编程输出采用响应比最高者优先算法得到的每个作业调度序号、作业名、作业入井时间、开始调度时间、运行时间、结束时间、周转时间,以及所有作业的平均周转时间。

    三、源代码

    #include <stdio.h>
    #define N 10
    
    typedef struct {
        int hour;
        int min;
    }time;
    typedef struct hrrf{
        char hrrf_id[20];
        double hrrf_run;  //运行时间
        time hrrf_entertime; //进入时间
        int enter;
        time hrrf_needtime;  //调度时间
        int needtime;
        time hrrf_endtime;   //结束时间
        int endtime;
        int hrrf_longtime;  //周转时间
        int hrrf_waittime;   //等待时间
        double hrrf_pjlongtime; //平均周转时间
        double hrrf_rate;       //响应比
    
        struct hrrf* next;
    }HRRF;
    //输入作业信息
    void hrrfinput(HRRF s[N],int k)
    {
        printf("\t请输入第%d个作业名:",k+1);
        scanf("%s",&s[k].hrrf_id);
        printf("\t请输入%s作业进入时间:",s[k].hrrf_id);
        scanf("%d:%d",&s[k].hrrf_entertime.hour,&s[k].hrrf_entertime.min);
        s[k].enter=s[k].hrrf_entertime.hour*60+s[k].hrrf_entertime.min;
        printf("\t请输入%s作业运行时间:",s[k].hrrf_id);
        scanf("%lf",&s[k].hrrf_run);
    }
    //计算作业的响应比
    void rate(HRRF s[N],int k,int m)
    {
        double ratenum;
        ratenum = (s[k].hrrf_run+(double)(s[m].endtime-s[k].enter))/(s[k].hrrf_run);
        s[k].hrrf_rate=ratenum;
        printf("\n\t每次算响应比:%s---%f\n",s[k].hrrf_id,s[k].hrrf_rate);
    }
    //按响应比大小对作业进行排序(降序排序)
    void ratesort(HRRF s[N],int k,int m)
    {
        int maxratenum;
        HRRF temp;
        int i,j;
        for(i=k;i<m;i++)         //简单选择排序
        {
            maxratenum=i;
            for(j=i+1;j<m;j++)
                if(s[j].hrrf_rate>s[maxratenum].hrrf_rate)
                    maxratenum=j;
            if(maxratenum!=i)
            {
                temp=s[i];
                s[i]=s[maxratenum];
                s[maxratenum]=temp;
            }
    
        }
    }
    //打印表单
    void print(HRRF s[N],int k)
    {
        printf("\t序号\t作业名\t进入时间\t调度时间\t结束时间\t运行时间\t等待时间\t周转时间\n");
        int i,j;
        for(i=0;i<k;i++)
            printf("\t%d\t%s\t%d:%d\t\t%d:%d\t\t%d:%d\t\t%.0f min\t\t%d\t\t%d min\n",i+1,s[i].hrrf_id,(s[i].enter/60),(s[i].enter%60),(s[i].needtime/60),(s[i].needtime%60),(s[i].endtime/60),(s[i].endtime%60),s[i].hrrf_run,s[i].hrrf_waittime,s[i].hrrf_longtime);
    
    }
    
    //hrrf算法
    void HRRF_run(HRRF s[N],int k)
    {
        int i,j=k,n;
        double sum;
        HRRF temp;
        //按到达时间进行排序
        while(j>1)
        {
            for(i=0;i<j-1;i++)
            {
                if(s[i+1].enter<s[i].enter)
                {
                    temp=s[i];
                    s[i]=s[i+1];
                    s[i+1]=temp;
                }
            }
            j--;
        }
        printf("\n\t--------------------------------------------初始状态------------------------------------------------\n");
        print(s,k);
        j=0;
        //执行
        do{
                if(j==0)
                {
                    s[j].needtime=s[j].enter;
                    s[j].hrrf_waittime=0;
                    s[j].endtime=s[j].enter+s[j].hrrf_waittime+(int)(s[j].hrrf_run);
                    s[j].hrrf_longtime=s[j].endtime-s[j].enter;
                }
                else
                {
                    s[j].needtime=s[j-1].endtime;
                    s[j].hrrf_waittime=s[j-1].endtime-s[j].enter;
                    s[j].endtime=s[j].needtime+(int)(s[j].hrrf_run);
                    s[j].hrrf_longtime=s[j].endtime-s[j].enter;
                }
                j++;  //到了第几个作业
                //计算响应比
                n=j-1;  //此次已经执行完的作业序号-1,因为数组从0开始
                for(i=j;i<k;i++)
                {
                    rate(s,i,n);    //计算响应比
                }
                ratesort(s,j,k);    //按响应比由大到小排序
                printf("\n\t-----------------------------------------每次响应比排序---------------------------------------------\n");
                print(s,k);
    
        }while(j<k);
    
        printf("\n\t--------------------------------------------作业调度------------------------------------------------\n");
        print(s,k);
        for(i=0;i<k;i++)
        {
            sum+=(double)(s[i].hrrf_longtime);
        }
    
        printf("\n\t平均周转时间为:%.2f\n",sum/k);
    }
    
    int main()
    {
        HRRF a[N]={0};
        int i,j;
        printf("请输入创建作业数目:");
        scanf("%d",&i);
        for(j=0;j<i;j++)  //输入作业信息
            hrrfinput(a,j);
        //HRRF算法
        HRRF_run(a,j);
    
        return 0;
    }
    

    四、实验截图

     

    1、输入

     

     

    2、执行过程

     

     

     

    有问题欢迎指正,先谢了~~~

    展开全文
  • 最高响应比优先算法

    千次阅读 2020-03-20 17:14:26
    最高响应比优先算法(HRN) eg: process Arrival Burst time P1 0 10 P2 2 16 P3 5 5 如果题干说从0时刻开始运行:        由于P1先到达所以先运行P1,由于HRN算法...

    最高响应比优先算法(HRN)


    eg:

    process Arrival Burst time
    P1 0 10
    P2 2 16
    P3 5 5

    如果题干说从0时刻开始运行:

           由于P1先到达所以先运行P1,由于HRN算法是不可剥夺的,所以P1需运行完,才能运行下一个进程。
    P1运行时间为10
    根据响应比公式求响应比RR,公式如下:

    RR=1+WT/BT

    RR(p2)=1+8/16=1.5
    RR(p3)=1+5/5=2
    由于 RR(p2)<RR(p3),所以P3的响应度高,先运行P3:

    10+5=15

    P3运行结束,运行P2:

    15+16=31

    P1 P3 P2

    进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间
    P1 0 10 0 10 10 1
    P2 2 16 10 15 13 0.8
    P3 5 5 15 31 26 5.2

    其他情况按照这个步骤分析即可

    展开全文
  • 操作系统--响应比最高优先算法(Python代码)响应比最高优先算法简介原理Python代码(1) 原始数据(2) 代码实现1.创建进程2.第一次排序3. 找出在作业结束前被创建的作业4.找出响应比最大的作业相对应的索引(大...

    响应比最高者优先算法

    简介

    响应比最高者优先算法(Highest Respone Patio First,HRRF)是介于这两种算法(FCFS和SJF)之间的一种折中的策略,既考虑了作业等待时间,又考虑了作业的运行时间,这样既照顾了短作业又不使长作业的等待时间过长,改进了调度性能。缺点是每次计算各道作业响应比会有一定的时间开销,需要估计期待的服务时间,性能要比SJF略差。

    原理

    采用HRRF算法进行调度时,必须对输入井中的所有作业计算出各自的响应比,从资源能得到满足的作业中选择响应比最高的作业优先转入主存运行。
    响应比的定义为:
    响应比 = (作业等待时间 + 作业运行时间)/ 作业运行时间 ==> 响应比 = 作业响应时间 / 作业运行时间
    作业从进入输入井到执行完成就是该作业的响应过程,因此该作业的响应时间就是作业的等待时间与运行时间之和。从响应比公式可以看出:

    1. 若作业的等待时间相同,则运行时间越短的作业,其响应比越高,因而该算法有利于短作业;
    2. 若作业的运行时间相同,则作业的等待时间越长,其响应比越高,因而该算法实现的时“先来先服务”;
    3. 对于长作业,作业的响应比随等待时间的增加而提高,当其等待时间足够长时,其响应比便可提升到很高,不至于发生饥饿现象。

    Python代码

    (1) 原始数据

    作业名 进入时间 运行时间/min
    JOB2 50 50
    JOB3 60 10
    JOB1 0 120
    JOB4 110 20

    (2) 代码实现

    1.创建进程
    def Creat():
        dic = {}
        i = 0
        while True:
            name = input("请输入进程名(输入Z结束):")
            if name == 'Z':
                return dic
            enter_time = eval(input("请输入进入时间:"))
            run_time = eval(input("请输入运行时间:"))
            values = {i:{'作业名': name,
                         '进入时间': enter_time,
                         '运行时间': run_time,
                         '开始时间': enter_time,
                         '完成时间': enter_time+run_time,
                         '周转时间': run_time,
                         '带权周转时间': 1}}
            dic.update(values)
            i += 1
            
    

    创建一个大字典,大字典的键为数字,作为最后的输出顺序。而键所对应的值是字典类型的。用于储存作业的各个数据。
    首先数据的初始化都默认是第一个作业被执行所生成的数据(方便找到第一个作业后可以直接跳过修改阶段)。
    当作业名为Z时,作业的创建结束。

    2.第一次排序
    def first_sort(data):
        for i in range(len(data)):
            Min = data[i]
            cnt = i
            for j in range(i, len(data)):
                if Min['进入时间'] > data[j]['进入时间']:
                    Min = data[j]
                    cnt = j
            temp = data[i]
            data[i] = Min
            data[cnt] = temp
    

    这一步比较有趣,我是以进入时间为对象,使用冒泡排序对作业进行排序。索引越小对应的键里的进入时间越早,即作业被创建的越早,索引值越小。

    第一次排序后的结果

    作业名 进入时间 运行时间/min
    JOB1 0 120
    JOB2 50 50
    JOB3 60 10
    JOB4 110 20
    3. 找出在作业结束前被创建的作业
    def Select_enter_time(data,finish,i):
        dic = {}
        for j in range(i, len(data)):
            if finish >= data[j]['进入时间']:
                ans = {j: data[j]}
                dic.update(ans)
        return dic
    

    这一步可能会有些迷,但是又是必不可少的一步,少了这步就可能出现BUG(即还没创建就开始执行)。所以这一步就是在进行筛选,找出符合条件的作业。

    4.找出响应比最大的作业相对应的索引(大字典的键)
    def Response(Filter,finish,i):
        MAX = (finish-Filter[i]['进入时间']+Filter[i]['运行时间'])/Filter[i]['运行时间']
        MAX_cnt = i
        for j in range(i, len(Filter)):
            wait = finish-Filter[j]['进入时间']
            res_time = (wait+Filter[j]['运行时间'])/Filter[j]['运行时间']
            if MAX < res_time:
                MAX = res_time
                MAX_cnt = j
        return MAX_cnt
    

    在符合条件的作业下,找出响应比最大的作业的索引,因为在主函数中需要进行小字典(即作业)的交换。

    5.修改数据
    def Write(data,finish,i):
        data[i]['开始时间'] = finish
        data[i]['完成时间'] = finish + data[i]['运行时间']
        data[i]['周转时间'] = data[i]['完成时间'] - data[i]['进入时间']
        data[i]['带权周转时间'] = data[i]['周转时间'] / data[i]['运行时间']
    

    修改开始时间、完成时间、周转时间、带权周转时间。

    6.打印输出
    def PPrint(data):
        SZ,SD = 0, 0
        for i in range(len(data)):
            print(data[i])
            SZ+=data[i]['周转时间']
            SD+=data[i]['带权周转时间']
        print("平均周转时间{0:.2f},平均带权周转时间{1:.2f}".format(SZ/len(data),SD/len(data)))
    

    打印输出数据

    7.主函数
    def main():
        data = Creat()
        first_sort(data)
        finish = data[0]['完成时间']
        for i in range(1, len(data)):
            Filter = Select_enter_time(data, finish, i)
            if Filter == {}:
                break
            Index = Response(Filter, finish, i)
            temp = data[i]
            data[i] = Filter[Index]
            data[Index] = temp
            Write(data,finish,i)
            finish = data[i]['完成时间']
        PPrint(data)
    
    if __name__ == '__main__':
        main()
    
    

    将Create()创建的作业赋值给data,然后对作业进行第一次排序first_sort(data),将第一个被执行作业的结束时间赋值给finish。进入for循环,每进行一次for循环,大字典{1:{作业},2:{作业},…,i:{作业}}已经排好执行顺序,这个for 循环相当于一个变形的顺序排序。

    8.完整代码
    def Creat():
        dic = {}
        i = 0
        while True:
            name = input("请输入进程名(输入Z结束):")
            if name == 'Z':
                return dic
            enter_time = eval(input("请输入进入时间:"))
            run_time = eval(input("请输入运行时间:"))
            values = {i:{'作业名': name,
                         '进入时间': enter_time,
                         '运行时间': run_time,
                         '开始时间': enter_time,
                         '完成时间': enter_time+run_time,
                         '周转时间': run_time,
                         '带权周转时间': 1}}
            dic.update(values)
            i += 1
    
    def first_sort(data):
        for i in range(len(data)):
            Min = data[i]
            cnt = i
            for j in range(i, len(data)):
                if Min['进入时间'] > data[j]['进入时间']:
                    Min = data[j]
                    cnt = j
            temp = data[i]
            data[i] = Min
            data[cnt] = temp
    
    def Select_enter_time(data,finish,i):
        dic = {}
        for j in range(i, len(data)):
            if finish >= data[j]['进入时间']:
                ans = {j: data[j]}
                dic.update(ans)
        return dic
    
    def Response(Filter,finish,i):
        MAX = (finish-Filter[i]['进入时间']+Filter[i]['运行时间'])/Filter[i]['运行时间']
        MAX_cnt = i
        for j in range(i, len(Filter)):
            wait = finish-Filter[j]['进入时间']
            res_time = (wait+Filter[j]['运行时间'])/Filter[j]['运行时间']
            if MAX < res_time:
                MAX = res_time
                MAX_cnt = j
        return MAX_cnt
    
    def Write(data,finish,i):
        data[i]['开始时间'] = finish
        data[i]['完成时间'] = finish + data[i]['运行时间']
        data[i]['周转时间'] = data[i]['完成时间'] - data[i]['进入时间']
        data[i]['带权周转时间'] = data[i]['周转时间'] / data[i]['运行时间']
    
    def PPrint(data):
        SZ,SD = 0, 0
        for i in range(len(data)):
            print(data[i])
            SZ+=data[i]['周转时间']
            SD+=data[i]['带权周转时间']
        print("平均周转时间{0:.2f},平均带权周转时间{1:.2f}".format(SZ/len(data),SD/len(data)))
    
    def main():
        data = Creat()
        first_sort(data)
        finish = data[0]['完成时间']
        for i in range(1, len(data)):
            Filter = Select_enter_time(data, finish, i)
            if Filter == {}:
                break
            Index = Response(Filter, finish, i)
            temp = data[i]
            data[i] = Filter[Index]
            data[Index] = temp
            Write(data,finish,i)
            finish = data[i]['完成时间']
        PPrint(data)
    
    if __name__ == '__main__':
        main()
    
    
    9.输出
    请输入进程名(输入Z结束):JOB1
    请输入进入时间:0
    请输入运行时间:120
    请输入进程名(输入Z结束):JOB2
    请输入进入时间:50
    请输入运行时间:50
    请输入进程名(输入Z结束):JOB3
    请输入进入时间:60
    请输入运行时间:10
    请输入进程名(输入Z结束):JOB4
    请输入进入时间:110
    请输入运行时间:20
    请输入进程名(输入Z结束):Z
    {'作业名': 'JOB1', '进入时间': 0, '运行时间': 120, '开始时间': 0, '完成时间': 120, '周转时间': 120, '带权周转时间': 1}
    {'作业名': 'JOB3', '进入时间': 60, '运行时间': 10, '开始时间': 120, '完成时间': 130, '周转时间': 70, '带权周转时间': 7.0}
    {'作业名': 'JOB2', '进入时间': 50, '运行时间': 50, '开始时间': 130, '完成时间': 180, '周转时间': 130, '带权周转时间': 2.6}
    {'作业名': 'JOB4', '进入时间': 110, '运行时间': 20, '开始时间': 180, '完成时间': 200, '周转时间': 90, '带权周转时间': 4.5}
    平均周转时间102.50,平均带权周转时间3.77
    
    展开全文
  • 例题:最高响应比优先调度算法

    千次阅读 2020-11-05 18:43:38
    在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比最高的作业投入运行。 响应比的变化规律可描述为: 响应比=(等待时间+服务时间)/服务时间 根据公式可知: 当作业的等待时间相同时,...

    高响应比优先HRRN

    高响应比优先调度算法主要用于作业调度,该算法是对FCFS调度算法和SJF调度算法的一种综合平衡,同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时,先计算后备作业队列中每个作业的响应比,从中选出响应比最高的作业投入运行。

    响应比的变化规律可描述为:

    响应比=(等待时间+服务时间)/服务时间

    根据公式可知:

    当作业的等待时间相同时,则要求服务时间越短,其响应比越高,有利于短作业。

    当要求服务时间相同时,作业的响应比由其等待时间决定,等待时间越长,其响应比越高,因而它实现的是先来先服务。

    对于长作业,作业的响应比可以随等待时间的增加而提高,当其等待时间足够长时,其响应比便可升到很高,从而也可获得处理机。克服了饥饿状态,兼顾了长作业。

    参考文章:
    1、操作系统中调度算法(FCFS、RR、SPN、SRT、HRRN)
    2、高响应比优先调度算法(HRRN)例题详解

    作业提交时刻(时)运行时间(小时)开始时刻完成时刻周转时间18:002.08:00  28:500.5   39:000.1   49:500.2   

    展开全文
  • 这是用C语言写的3个作业调度算法,包括先来先服务,短作业优先最高响应比优先。这是用C语言写的3个作业调度算法,包括先来先服务,短作业优先最高响应比优先
  • 进程调度模拟设计(非强占式短进程优先算法、最高响应比优先调度算法)在此基础上增加了先来先服务算法。直接复制粘贴就能运行
  • Java 操作系统 最高响应比优先算法

    千次阅读 2018-05-19 22:08:55
    在进程管理中,进程调度是核心,因为在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态,当就绪进程个数大于处理器数目时,就必须依照某种策略决定哪些进程优先占用处理器。本设计模拟在单处理器情况下...
  • 在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务 (3)用于作业/进程调度 既可用 于作业调度,也可用于进程调度 (4)是否可抢占? 非抢占式的算法。因此只有当前运行的作业/进程...
  • 算法规则: 在每次调度时先计算各个作业/进程的响应比,选择响应比最高 的作业/进程为其服务 响应比: 响应比=(等待时间+要求服务时间)/要求服务时间 用于调度: 即可以用于作业调度,也可以用于进程调度 是否可以...
  • 为照顾紧迫性作业,使之在进入系统后便获得优先处理,引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中,作为作业调度算法,也作为多种操作系统中的进程调度算法,还可用于实时系统中。它分为两种...
  • 2-2-4 调度算法(适用与早期的批处理系统):先来先服务,最短作业优先最高响应比优先 学习思路: 算法思想 算法规则 用于作业调度还是进程调度? 抢占式算法还是非抢占式算法? 优点和缺点 是否会导致饥饿(某进程...
  • Java模拟最短作业优先、时间片轮转、最高响应比和先来先服务进程调度算法 rar中有四种算法和俩个对进程用时和周转时间制图的java源代码,另外有jcommon-1.0.23.jar和jfreechart-1.0.19.jar俩个制图包
  • 6、调度算法适用于早期批处理机系统的调度算法思维导图1、先来先服务FCFS2、最短作业优先SJF非抢占式最短作业优先抢占式最短作业优先(最短剩余时间优先算法)注3、最高响应比优先HRRN 适用于早期批处理机系统的调度...
  • * 最高响应比优先算法 */ public void HRNAlgorithm ( int index ) { if ( readyQueue . size ( ) == 0 ) { System . out . println ( "就绪队列为空,调度完毕!" ) ; return ; } ...

空空如也

空空如也

1 2 3 4 5 ... 11
收藏数 201
精华内容 80
关键字:

响应比最高优先