精华内容
下载资源
问答
  • 高响应比优先调度算法(HRRN)例题详解

    万次阅读 多人点赞 2020-03-25 15:43:33
    高响应比优先调度算法 (HRRN) 高响应比优先调度算法(Highest Response Ratio Next)是一种对CPU中央控制器响应比的分配的一种算法。HRRN是介于FCFS(先来先服务算法)与SJF(短作业优先算法)之间的折中算法,既...

    高响应比优先调度算法 (HRRN)

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

    响应比=作业周转时间/作业处理时间=(作业处理时间+作业等待时间)/作业处理时间=1+(作业等待时间/作业处理时间)

    等待时间=最后一个的提交时间-该作业到达的时间
    作业执行规则,响应比高的先执行
    周转时间=完成时间-提交时间

    例题

    作业号提交时间执行时间完成时间周转时间
    p110.02.0
    p210.21.0
    p310.40.5
    p410.50.3

    先执行的是第一个提交作业,然后其余的作业再用响应比来判断执行顺序
    先执行p1 :

    作业号提交时间执行时间完成时间周转时间
    p110.02.012.02.0
    p210.21.0
    p310.40.5
    p410.50.3

    设响应比为R
    此时 R(p2)=1+((12.0-10.2)/1.0)=2.8
    R(p3)=1+((12.0-10.4)/0.5)=4.2
    R(p4)=1+((12.0-10.5)/0.3)=6
    所以 执行p4:

    作业号提交时间执行时间完成时间周转时间
    p110.02.012.02.0
    p210.21.0
    p310.40.5
    p410.50.312.31.8

    设响应比为R
    此时 R(p2)=1+((12.3-10.2)/1.0)=3.1
    R(p3)=1+((12.3-10.4)/0.5)=4.8
    所以 再执行p3:

    作业号提交时间执行时间完成时间周转时间
    p110.02.012.02.0
    p210.21.0
    p310.40.512.82.4
    p410.50.312.31.8

    因此最后执行p2:

    作业号提交时间执行时间完成时间周转时间
    p110.02.012.02.0
    p210.21.013.83.6
    p310.40.512.82.4
    p410.50.312.31.8

    此算法作业的平均周转时间为:(2.0+3.6+2.4+1.8)/4=2.45

    上一篇文章———>Python之format用法详解

    下一篇文章———>《scrapy基础操作教程(实例)》

    展开全文
  • 调度算法 轮循模拟器,HRRN,SRT
  • 用JAVA来实现操作系统中FCFS、SJF、HRRN三种算法的进程调度
  • SJF HRRN FCFS 算法

    2018-11-27 22:21:57
    SJF短作业优先 HRRN高响应比优先 FCFS先来先服务   源代码 #include<stdio.h> #include<malloc.h> #define LEN sizeof(struct process) #define MAX 99 struct process{//结构体...

    SJF短作业优先 HRRN高响应比优先 FCFS先来先服务

     

    源代码

    #include<stdio.h>
    #include<malloc.h>
    #define LEN sizeof(struct process)
    #define MAX 99
    struct process{//结构体进程
        int no;
        float pri;
        float arrtime;
        float sertime;
        float strtime;
        float fintime;//=arr+ser
        float roundtime;//=fin-arr
        float aroundtime;//roun/ser
        process *next;
    };
    void LISTtime(struct process a[],int count){
    float l,h,n;
    for(int i=0;i<count-1;i++) //按进程到达时间的先后排序
        {                               //如果两个进程同时到达,按在屏幕先输入的先运行
            for(int j=i+1;j<count;j++)
            { 
                if(a[j].arrtime < a[i].arrtime||a[j].arrtime==0)
                {
                    l  =a[j].arrtime;            
                    h  =a[j].sertime;
            n  =a[j].no;

                    a[j].arrtime=a[i].arrtime;        
                    a[j].sertime=a[i].sertime;
            a[j].no=a[i].no;

            a[i].no=n;
                    a[i].arrtime=l;
                    a[i].sertime=h;
                }
            }
        }
    }
    process *creat(){ //进程构造函数
        process *head;
        head=(process*)malloc(LEN);//head为头指针
        process *p1,*p2;//p1为新建指针,p2对尾指针
        head->next=NULL;
        p2=head;
        p1=(process*)malloc(LEN);
        printf("请输入进程号:\n");
        scanf("%d",&p1->no);
        printf("请输入进程到达时间:\n");
        scanf("%f",&p1->arrtime);
        printf("请输入进程需要时间:\n");
        scanf("%f",&p1->sertime);
        p1->fintime=0;
        p1->pri=0;
        while(p1->sertime!=0){
            p1->next=p2->next;
            p2->next=p1;
            p2=p1;
            p1=(process*)malloc(LEN);
            printf("请输入进程号:\n");
            scanf("%d",&p1->no);
            printf("请输入进程到达时间:\n");
            scanf("%f",&p1->arrtime);
            printf("请输入进程需要时间:\n");
            scanf("%f",&p1->sertime);
            p1->fintime=0;
            p1->pri=0;
        }
        free(p1);
        return head;
    }

    void PrintFS(struct process a[],int count){//FCFS和SJF输出
        int i;
            printf("      |到达时间  |服务时间  |开始时间  |完成时间  |周转时间  |带权周转时间\n");
        for(i=0;i<count;i++){
            printf("进程%d |%f  |%f  |%f  |%f  |%f  |%f  \n",a[i].no,a[i].arrtime,a[i].sertime,a[i].strtime,a[i].fintime,a[i].roundtime,a[i].aroundtime);
        }
    }
    void printPf(process a[],int count){//HRRN输出
            printf("");
            printf("进程号|到达时间  |需要时间  |开始时间  |完成时间  |周转时间  |带权周转时间|进程优先级\n");
        for(int i=0;i<count;i++){
            printf("     %d|%f  |%f  |%f  |%f  |%f  |%f  |%f\n",a[i].no,a[i].arrtime,a[i].sertime,a[i].strtime,a[i].fintime,a[i].roundtime,a

    [i].aroundtime,a[i].pri);
        }
        printf("");
    }
    void copy(process a[],process b[],int count){//复制进程组

        for(int i=0;i<count;i++){
                    b[i].no=a[i].no;
                    b[i].arrtime=a[i].arrtime;
                    b[i].sertime=a[i].sertime;
                    b[i].fintime=a[i].fintime;
            }
    }
    void SJF(process a[],int count){//先来先服务
        int i,st=0,zero=0;
        float l,h,n;
        int time=0;
        for(i=0;i<count;i++){
            if(a[i].arrtime==0)zero++;
            a[i].fintime=0;
            a[i].aroundtime=0;
            a[i].pri=0;
            a[i].roundtime=0;
        }
        for( i=0;i<count-1;i++) //按进程到达时间的先后排序
        {                          //如果两个进程同时到达,按在屏幕先输入的先运行
            for(int j=i+1;j<count;j++)
            {    
                if(a[j].arrtime<a[i].arrtime)
                {    
                    l  =a[j].arrtime;            
                    h  =a[j].sertime;
                    n  =a[j].no;

                    a[j].arrtime=a[i].arrtime;        
                    a[j].sertime=a[i].sertime;
                    a[j].no=a[i].no;

                    a[i].no=n;
                    a[i].arrtime=l;
                    a[i].sertime=h;
                }
            }
        }
        time=a[0].arrtime;
        for( i=0;i<zero-1;i++) //按进程服务时间的先后排序
        {                               //如果两个进程同时到达,按在屏幕先输入的先运行
            for(int j=i+1;j<zero;j++)
            { 
                if(a[j].sertime<a[i].sertime)
                {
                    l  =a[j].arrtime;            
                    h  =a[j].sertime;
                    n  =a[j].no;

                    a[j].arrtime=a[i].arrtime;        
                    a[j].sertime=a[i].sertime;
                    a[j].no=a[i].no;

                    a[i].no=n;
                    a[i].arrtime=l;
                    a[i].sertime=h;
                }
            }
        }
        while(st<count){
            for(i=0;i<count;i++){
                if(a[i].arrtime<=time&&a[i].fintime==0){
                    a[i].fintime=time+a[i].sertime;
                    a[i].strtime=time;
                    a[i].roundtime=a[i].fintime-a[i].arrtime;
                    a[i].aroundtime=a[i].roundtime/a[i].sertime;
                    time=a[i].fintime;
                    st++;
                    for(int i=st-1;i<count-1;i++) //按进程服务时间的先后排序
                        {                               //如果两个进程同时到达,按在屏幕先输入的先运行
                            for(int j=i+1;j<count;j++)
                            { 
                                if(a[j].sertime <a[i].sertime&&a[j].arrtime<=time&&a[i].arrtime<=time&&a[j].fintime==0&&a

    [i].fintime==0)
                                {
                                    l  =a[j].arrtime;            
                                    h  =a[j].sertime;
                                    n  =a[j].no;

                                    a[j].arrtime=a[i].arrtime;        
                                    a[j].sertime=a[i].sertime;
                                    a[j].no=a[i].no;

                                    a[i].no=n;
                                    a[i].arrtime=l;
                                    a[i].sertime=h;
                                }
                            }
                        }
                    }
                if(a[i+1].arrtime>=time&&a[i+1].fintime==0){
                    time=a[i+1].arrtime;
                    for(int i=st-1;i<count-1;i++) //按进程服务时间的先后排序
                        {                               //如果两个进程同时到达,按在屏幕先输入的先运行
                            for(int j=i+1;j<count;j++)
                            { 
                                if(a[j].sertime <a[i].sertime&&a[j].arrtime<=time&&a[i].arrtime<=time&&a[j].fintime==0&&a

    [i].fintime==0)
                                {
                                    l  =a[j].arrtime;            
                                    h  =a[j].sertime;
                                    n  =a[j].no;

                                    a[j].arrtime=a[i].arrtime;        
                                    a[j].sertime=a[i].sertime;
                                    a[j].no=a[i].no;

                                    a[i].no=n;
                                    a[i].arrtime=l;
                                    a[i].sertime=h;
                                }
                            }
                        }
                    }
                }
        }
    }
    void HRRN(struct process a[],int count){//高响应比优先
                    //p为指针头 及只记录队列首地址的指针
        float time=0,m=0;//m为优先级标志
        int i=0;
        float l,h,n;
        float ap[99];//记录优先级
        int count1=count;//记录优先级参数
        int ai=count;//未完成进程数标志
        for(i=0;i<count;i++){
            a[i].fintime=0;
            a[i].aroundtime=0;
            a[i].pri=0;
            a[i].roundtime=0;
        }
        for( i=0;i<count-1;i++) //按进程到达时间的先后排序
        {                          //如果两个进程同时到达,按在屏幕先输入的先运行
            for(int j=i+1;j<count;j++)
            {    
                if(a[j].arrtime<a[i].arrtime)
                {    
                    l  =a[j].arrtime;            
                    h  =a[j].sertime;
                    n  =a[j].no;

                    a[j].arrtime=a[i].arrtime;        
                    a[j].sertime=a[i].sertime;
                    a[j].no=a[i].no;

                    a[i].no=n;
                    a[i].arrtime=l;
                    a[i].sertime=h;
                }
            }
        }
        time=a[0].arrtime;
        for(i=0;i<count;i++){
            if(a[i].fintime==0){//为每一个未完成的进程计算优先级
                a[i].pri=(time+a[i].sertime)/a[i].sertime;
                ap[i]=a[i].pri;
                }
        }
        for( i=0;i<count-1;i++) //优先级升序排序
        {    
            float l;
            for(int j=i+1;j<count;j++)
            { 
                if(ap[j]<=ap[i])
                {
                    l =ap[j];          
                    ap[j]=ap[i];      
                    ap[i]=l;
                }
            }
        }
        m=ap[count-1];//记录最大优先级
        while(ai>0){//有无未完成进程
                    for(i=0;i<count;i++){
                        if(a[i].pri==m&&a[i].fintime==0){//服务
                            if(time<a[i].arrtime)time=a[i].arrtime;
                            {
                            a[i].fintime=time+a[i].sertime;
                            a[i].strtime=time;
                            a[i].roundtime=a[i].fintime-a[i].arrtime;
                            a[i].aroundtime=a[i].roundtime/a[i].sertime;
                            time=a[i].fintime;
                            ai--;break;
                            }
                        }
                    }
                        for( i=0;i<count;i++)//优先级初始化
                        {    
                            ap[i]=0;
                        }
                        for(i=0;i<count;i++){
                                if(a[i].fintime==0&&a[i].arrtime<=time){//为每一个未完成且到达的进程计算优先级
                                a[i].pri=(time-a[i].arrtime+a[i].sertime)/a[i].sertime;
                                ap[i]=a[i].pri;
                                }
                                if(a[i+1].fintime==0&&a[i+1].arrtime>=time&&a[i].fintime!=0){//如果当前进程已完成
                                //下一个应该到达的进程的到达时间大于当前时间
                                a[i+1].pri=(a[i+1].sertime)/a[i+1].sertime;
                                ap[i+1]=a[i+1].pri;
                                }
                        }
                        for( i=0;i<count-1;i++) //优先级升序排序
                        {    
                                float l;
                                for(int j=i+1;j<count;j++)
                                { 
                                    if(ap[j]<=ap[i])
                                    {
                                    l =ap[j];          
                                    ap[j]=ap[i];      
                                    ap[i]=l;
                                    }
                                }
                        }
                        m=ap[count-1];//记录最大优先级
        }
    }
    void FCFS(struct process a[],int count){//先来先服务
        int i;
        a[0].fintime=a[0].arrtime+a[0].sertime;
        a[0].strtime=a[0].arrtime;
        a[0].roundtime=a[0].fintime-a[0].arrtime;
        a[0].aroundtime=a[0].roundtime/a[0].sertime;
        for(i=1;i<count;i++){
            if(a[i].arrtime<a[i-1].fintime){
            a[i].fintime=a[i-1].fintime+a[i].sertime;
            a[i].strtime=a[i-1].fintime;
            a[i].roundtime=a[i].fintime-a[i].arrtime;
            a[i].aroundtime=a[i].roundtime/a[i].sertime;
            }
            else{
            a[i].fintime=a[i].arrtime+a[i].sertime;
            a[i].strtime=a[i].arrtime;
            a[i].roundtime=a[i].fintime-a[i].arrtime;
            a[i].aroundtime=a[i].roundtime/a[i].sertime;
            }
            
        }
    }
    void main(){
        int count=0;
        int flag=0;
        process af[MAX];//fcfs
        process bs[MAX];//sjf
        process ch[MAX];//hrrn
        process *head;
        printf("请输入进程 服务时间为0停止\n");
        head=creat();
            {
            process *p;
            int i=0;
            p=head->next;
                while(p!=NULL){
                    af[i].no=p->no;
                    af[i].arrtime=p->arrtime;
                    af[i].sertime=p->sertime;
                    af[i].fintime=p->fintime;
                    p=p->next;
                    i++;
                    count++;
                }
            }
            copy(af,bs,count);
            copy(af,ch,count);
        while(flag!=4){
            printf("请选择算法: 1 FCFS 2 SJF 3 HRRN 4退出 \n");
            scanf("%d",&flag);
            switch(flag){
            case 1:{LISTtime(af,count);FCFS(af,count);PrintFS(af,count);break;}
            case 2:{SJF(bs,count);PrintFS(bs,count);break;}
            case 3:    {HRRN(ch,count);printPf(ch,count);break;}
            case 4: break;
            default :printf("输入错误!");break;
            }
        }

    }

    这个程序可以运行出来但是我想知道有什么错误,希望有人能看到我这篇帖子,指出我的错误和不足

    展开全文
  • 文章目录FCFS、SJF、HRRN调度算法知识总览图先来先服务(FCFS,First Come First Serve)短作业优先(SJF,Shortest Job First)对FCFS和SJF两种算法的思考高响应比优先算法(HRRN,Highest Response Ratio Next) ...

    FCFS、SJF、HRRN调度算法

    知识总览图

    在这里插入图片描述

    什么叫做饥饿?就是进程一直不被CPU处理。FCFS算法不会导致饥饿是因为,它的所有的进程按到来的时间先后顺序依次执行,所以每个进程都会被执行到。SJF/SPF算法会导致饥饿,是因为可能有大量的短作业,这样长作业进程永远也不会进行。HRRN算法不会导致饥饿是因为,它会先执行高响应比(你可以粗略地理解成等待时间长,但是并不是)的进程,所以不会有进程一直等待被CPU处理,因此不会饥饿。

    注:这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标,但是不关心“响应时间”,也并不区分任务的紧急程度,因此对于用户来说,交互性很糟糕。因此这三种算法一1111111111般适合用于早期的批处理系统

    先来先服务(FCFS,First Come First Serve)

    img

    例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

    在这里插入图片描述

    先来先服务调度算法:按照到达的先后顺序调度,事实上就是等待时间越久的越优先得到服务。因此,调度顺序为:P1–>P2–>P3–>P4

    在这里插入图片描述

    周转时间=完成时间-到达时间 P1=7-0=7; P2=11-2=9; P3=12-4=8; P4=16-5=11

    带权周转时间=周转时间/运行时间 P1=7/7=1; P2=9/4=2.25; P3=8/1=8; P4=11/4=2.75;

    等待时间=周转时间-运行时间 P1=7-7=0; P2=9-4=5; P3=8-1=7; P4=11-4=7; (注意:本例中的进程都是纯计算型的进程,一个进程到达后要么在等待,要么在运行。如果是又有计算、又有I/O操作的进程,其等待时间就是周转时间-运行时间-I/O操作的时间)

    平均周转时间=(7+9+8+11)/4=8.75

    平均带权周转时间=(1+2.25+8+2.75)/4=3.5

    平均等待时间=(0+5+7+7)/4=4.75

    短作业优先(SJF,Shortest Job First)

    在这里插入图片描述

    例题:各进程到达就绪队列的时间、需要的运行时间如下表所示。使用非抢占式(短进程优先调度算法(SPF))的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间,带权周转时间、平均带权周转时间。

    在这里插入图片描述

    短作业/进程优先调度算法:每次调度时选择当前已到达运行时间最短的作业/进程。因此调度顺序为:P1–>P3–>P2–>P4

    在这里插入图片描述

    刚开始时刻为0的时候,只有P1进程,虽然它的运行时间很长,但P1仍是第一个被调度的,然后P3的运行时间是1,所以P3优先调度,而P2和P4的运行时间都是4,但是P2先来的,所以P2会优先调度。

    周转时间=完成时间-到达时间 P1=7-0=7; P3=8-4=4; P2=12-2=10; P4=16-5=11

    带权周转时间=周转时间/运行时间 P1=7/7=1; P3=5/1=5; P2=10/4=2.5; P4=11/4=2.75;

    等待时间=周转时间-运行时间 P1=7-7=0; P3=4-1=3; P2=10-4=6; P4=11-4=7;

    平均周转时间=(7+4+10+11)/4=8

    平均带权周转时间=(1+4+2.5+2.75)/4=2.56

    平均等待时间=(0+3+6+7)/4=4

    对比FCFS算法的结果,显然SPF算法的平均等待/周转/带权周转时间都要更低

    例题:各进程到达就绪队列的事件、需要的运行时间如下表所示。使用抢占式(抢占式的短作业优先算法又称"最短剩余时间优先算法(SRTN)")的短作业优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

    在这里插入图片描述

    最短剩余时间优先算法:每当有进程加入就绪队列改变时就需要调度,如果新到达的进程运行的剩余时间比当前运行的进程运行的剩余时间更短,则由新进程抢占处理机,当前运行进程重新回到就绪队列。另外,当一个进程完成时也需要调度剩余时间最短的进程

    在这里插入图片描述

    需要注意的是,当有新进程到达时就绪队列就会改变,就要按照上述规则进行检查。一下Pn(m)表示当前Pn进程剩余时间为m。各个时刻的情况如下:

    0时刻(P1到达):P1(7) 此时P1进程运行

    2时刻(P2到达):P1(5),P2(4) 此时会停止P1进程运行,切换P2进程

    4时刻(P3到达):P1(5),P2(2),P3(1) 此时会停止P2进程,切换P3进程

    5时刻(P3完成且P4刚好到达):P1(5),P2(2),P4(4) 此时P2剩余运行时间最少,会切换到P2进程

    7时刻(P2完成):P1(5),P4(4) 此时P4剩余运行时间最少,会切换到P4进程

    11时刻(P4完成):P1(5) 此时只剩P1进程,会切换到P1进程

    周转时间=完成时间-到达时间 P1=16-0=16; P2=7-2=5; P3=5-4=1; P4=11-5=6

    带权周转时间 P1=16/7=2.28; P2=5/4=1.25; P3=1/1=1; P4=6/4=1.5

    等待时间=周转时间-运行时间 P1=16-7=9; P2=5-4=1; P3=1-1=0; P4=6-4=2;

    平均周转时间=(16+5+1+6)/4=7

    平均带权周转时间=(2.28+1.25+1+1.5)/4=1.50

    平均等待时间=(9+1+0+2)/4=3

    对比非抢占式的短作业优先算法,显然抢占式的平均周转/带权周转/等待时间又要更低。

    对FCFS和SJF两种算法的思考

    FCFS算法是在每次调度的时候选择一个等待时间最长的作业(进程)为其服务。但是没有考虑到作业的运行时间,因此导致了对短作业不友好的问题。

    SJF算法是选择一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间,因此导致了对长作业不友好的问题,甚至还会造成饥饿问题。

    能不能设计一个算法,即考虑到各个作业的等待时间,也能兼顾运行时间呢?可以,那就是高响应比优先算法。

    高响应比优先算法(HRRN,Highest Response Ratio Next)

    在这里插入图片描述

    例题:各进程到达就绪队列的事件、需要的运行时间如下表所示。使用高响应比优先调度算法,计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

    在这里插入图片描述

    高响应比优先算法:非抢占式的调度算法,只有当前运行的进程主动放弃CPU时(正常/异常完成,或主动阻塞),才需要进行调度,调度时计算所有就绪进程的响应比,选响应比最高的进程上处理机。

    在这里插入图片描述

    0时刻:只有P1到达就绪队列,P1上处理机

    7时刻(P1主动放弃CPU):就绪对垒中有P2(响应比=(5+4)/4=2.25)、P3((3+1)/1=3)、P4((2+4)/4=1.5)

    8时刻(P3完成):P2(2.5),P4(1.75)

    12时刻(P2完成):就绪队列中只剩下P4

    展开全文
  • FCFS,SJF,HRRN调度算法 各种调度算法的学习思路 算法思想 算法规划 这种调度算法是用于作业调度还是进程调度 抢占式?非抢占式? 优缺点 是否会导致饥饿(某进程/作业长期得不到服务) 先来先服务(FCFS) 算法...

    FCFS,SJF,HRRN调度算法

    各种调度算法的学习思路

    1. 算法思想
    2. 算法规划
    3. 这种调度算法是用于作业调度还是进程调度
    4. 抢占式?非抢占式?
    5. 优缺点
    6. 是否会导致饥饿(某进程/作业长期得不到服务)

    先来先服务(FCFS)

    1. 算法思想:主要从“公平”的角度考虑(类似于排队购物)
    2. 算法规则:按照作业/进程到达的先后顺序进行服务
    3. 用于作业调度/进程调度:用于作业调度时,考虑的是哪个作业先到达后备队列;用于进程调度时,考虑的是哪个进程先到达就绪队列
    4. 是否可抢占:非抢占式的算法
    5. 优缺点:
      • 优点:公平,算法实现简单;
      • 缺点:排在长作业(进程)后面的短作业需要等待很长时间,带权周转时间很大,对短作业来说用户体验不好,即对长作业有利,对短作业不利
    6. 是否会导致饥饿:不会

    例子:
    QQ图片20210327101314

    短作业优先(SJF)

    1. 算法思想:追求最少的平均等待时间,最少的平均周转时间,最少的平均带权周转时间
    2. 算法规则:最短的作业/进程优先得到服务(所谓最短,指要求服务时间最短)
    3. 用于作业/进程调度:既可用于作业调度,又可用于进程调度。用于进程调度时称为“短进程优先”SPF算法(shortest process first)
    4. 是否可抢占的:SJF和SPF是非抢占式的算法,但是也有抢占式的版本→最短剩余时间优先算法(SRTN,shortest remaining time next)
    5. 优缺点:
      • 优点:”最短的“平均等待时间,平均周转时间
      • 缺点:不公平,对短作业有利,对长作业不利,可能产生饥饿现象,另外,作业/进程的运行时间是由用户提供的,并不一定真实,不一定能做到真正的短作业优先
    6. 是否会导致饥饿

    例子:非抢占式:

    QQ图片20210327103558

    抢占式:

    QQ图片20210327103604

    QQ图片20210327103608

    注:

    1. 题目为特别说明,默认非抢占式
    2. 抢占式的短作业/进程优先调度算法的平均等待时间,平均周转时间最少;在所有进程都几乎同时到达/所有进程同时可运行的情况下,SJF算法的平均等待时间,平均周转时间最少

    高响应比优先(HHRN,highest response ratio next)

    1. 算法思想:综合考虑作业/进程的等待时间和要求服务的时间

    2. 算法规划:在每次调度时先计算各个作业/进程的响应比,选择响应比最高的作业/进程为其服务

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

    3. 用于作业进程调度:既可以用于作业调度,也可以用于进程调度

    4. 是否可抢占:非抢占式的算法,因此只有当前运行的进程/作业主动放弃处理机时,才需要调度,才需要计算响应比

    5. 优缺点:

      • 优点:综合考虑了等待时间和运行时间(要求服务时间),等待时间相同时,要求服务时间短的优先(SJF的优点);要求服务时间相同时,等待时间长的优先(FCFS的优点),对于长作业来说,随者等待时间越来越长,其响应比也会越来越大,从而避免了长作业饥饿的问题
    6. 是否会导致饥饿:不会

    例子:

    QQ图片20210327111022

    展开全文
  • c语言实现进程调度FCFS SJF HRRN RR
  • C++模拟处理机HRRN调度算法

    千次阅读 2018-12-05 09:40:23
    三、HRRN(最高响应比调度算法)原理 最高响应比调度:在每次调度作业时,先计算后备队中每个作业的响应比,然后挑选响应比高者投入运行。 响应比R定义: R=(w+S)/S (R:响应比,W=等待时间,S=运行时间) 响应比R= ...
  • ????FCFS SJF HRRN调度算法 学习资源来源: 王道考研 操作系统
  • FCFS,SJF,HRRN调度算法总结分析(全)

    千次阅读 多人点赞 2020-06-22 22:37:35
    FCFS,SJF,HRRN调度算法三种基本的调度算法先来先服务(FCFS, First Come First Serve )短作业优先(SJF, Shortest Job First )高响应比优先(HRRN,Highest Response Ratio Next )**三种算法的总结:** 三种基本的调度...
  • HRRN(高响应比优先算法) 算法思想: 要综合考虑作业/进程的等待时间和要求服务时间 算法规则: 在每次调度时先计算各个作业/进程的响应比,选择响应比最高 的作业/进程为其服务 响应比: 响应比=(等待时间+要求...
  • HRRN是介于FCFS(先来先服务算法)与SJF(短作业优先算法)之间的折中算法,既考虑作业等待时间又考虑作业运行时间,既照顾短作业又不使长作业等待时间过长,改进了调度性能。 ——百度百科 其中响应比的计算公式为...
  • 先来先服务(FCFS) 短作业(SJF) 高响应比优先(HRRN
  • 单处理器进程调度算法实现FCFS,RR,SPN,SRT,HRRN,使用C++实现
  • 高响应比优先---HRRN4.三种算法的对比和总结 0.思维导图 1.先来先服务—FCFS First come first sever 2.短作业优先—SJF Shortest Job First 非抢占式—SJF 抢占式—SJF(SRTN) 注意几个细节 3.高响应...
  • 设计程序模拟进程的高响应比HRRN和时间片轮转RR调度过程。假设有n个进程分别在T1, … ,Tn时刻到达系统,它们需要的服务时间分别为S1, … ,Sn。如果选择RR算法,还需要指定时间片大小q。分别采用高响应比HRRN和时间片...
  • 操作系统【作业调度算法 调度图 例题(SPF、HPF、HRRN)】
  • 操作系统 系统开销比率 操作系统中的HRRN调度是什么? (What is HRRN Scheduling in Operating System?) HRRN is the abbreviation of Highest Response Ratio Next Scheduling. It is an optimal scheduling ...
  • 随机给出一个进程调度实例,如: ...模拟进程调度,给出按照算法先来先服务FCFS、轮转RR(q=1)、最短进程优先SPN、最短剩余时间SRT、最高响应比优先HRRN进行调度各进程的完成时间、周转时间、响应比的值。
  • 设有四个进程,它们的到达时刻和处理时间如下所示: Process Arrival Time ... 采用最高响应比优先(HRRN)调度算法在时刻50进行调度,所选中的进程是? 再次强调一点:最高相应比算法不发生抢占 50时...
  • FCFS(first come first served):先来...HRRN(highest response ratio next):根据响应比从大到小依次执行,响应比动态计算 周转时间 = 完成时间 - 到达时间 带权周转时间 = 周转时间 / 运行时间 响应比 = (运行
  • 实验三 模拟处理机HRRN调度算法   一、实验目的:用c,c++,java设计HRRN调度算法程序。 二、实验内容:本实验随机输入的进程个数、进程名称、进程提交到系统的时间、进程运行所需时间。通过模拟程序。显示以下...
  • HRRN算法C语言实现

    2021-09-18 19:06:44
    刷某客网题,初遇此高响应比优先算法,正在学操作系统任务调度,尝试用C语言写了下,VC环境,验证无误。 综合作业执行时间和作业等待时间,本着“即照顾短作业,又不使长作业等待时间过长”的思想,改进调度性能。...
  • Python实战——实现进程调度算法:FCFS、SJF和HRRN 实验要求 进程调度算法:采用先来先服务、短作业、动态最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)。 每个进程有一个进程控制块( PCB)表示。...
  • 高响应比优先—HRRN4.三种算法的对比和总结 0.思维导图 1.先来先服务—FCFS First come first sever 后备队列是在外存中的 就绪队列是在内存中的 2.短作业优先—SJF Shortest Job First 非抢占式—SJF P2先到达...
  • 本次操作系统试验是使用程序来模拟操作系统中进程调度的不同的调度策略,分别为FIFO先进先出,SJF最短时间优先,RR时间片轮换以及HRRN最高响应比算法。 模拟的情况下,进程数为8,进程所需执行时间为随机产生的整数...
  • 文章目录前言知识总览先来先服务(FCFS, First Come First Serve)短作业优先(SJF, Shortest Job First)对FCFS和SJF两种算法的思考高响应比优先算法(HRRN)知识回顾与重要考点 前言 此篇文章是我在B站学习时所做的...
  • FCFS: 先来先服务,也可以称为先进先出 轮转: 以一个周期性间隔产生时钟中断,此时当前正在运行的进程被置于就绪队列,基于FCFS...HRRN:最高响应比优先,R=(w+s)/s,其中R表示响应比,w表示已经等待的时间,s表示期

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,632
精华内容 652
关键字:

hrrn