注册 登录
电子工程世界-论坛 返回首页 EEWORLD首页 频道 EE大学堂 下载中心 Datasheet 专题
懒猫爱飞的个人空间 https://home.eeworld.com.cn/space-uid-238351.html [收藏] [复制] [分享] [RSS]
日志

C语言基本功-FIFO服务和高响应比优先调度算法

已有 2992 次阅读2018-4-3 09:49 |个人分类:C语言学习| FIFO, 高优先级

1、进程调度与作业调度的区别:

&  作业调度:根据作业控制块(JCB:Job control block)中的信息,检查系统中的资源是否满足作业对资源的需求,以及按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度。

&  进程调度:保存当前进程的处理机的现场信息,如程序计数器、多个通用寄存器中的内容等,然后按某种算法从就绪队列中选取一个进程,将其状态转换为运行状态,再把进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中,把处理器的控制权交予该进程,让它从上次的断点处恢复运行。

&  进程调度时让某个就绪状态的进程到处理机上运行,而作业调度只是使作业具有了竞争处理机的机会。

2、单道批处理系统与多道批处理系统的区别:

&  单道批处理系统(Simple Batch Processing System):系统对作业的处理是成批进行的,但在内存中始终只保持一道作业。

特点:自动性、顺序性、单道性

主要问题:CPUI/O设备忙闲不均,对计算为主的作业,外设空闲;对I/O为主的

作业,CPU空闲。

&  多道批处理系统(Multiprogrammed Batch Processing System):在内存中同时存放几个作业,宏观上并行运行——都处于运行状态,但都没运行完;微观上串行运行各作业交替使用CPU

特点:调度性、无序性、多道性

主要问题:①作业平均周转时间长:短作业的周转时间显著增长;

②无交互能力:整个作业完成后或者中间出错时,才与用户交互,不利

于调试和修改。

3、程序设计用到的公式:

ü  完成时间 = 开始时间 +  需要运行时间

ü  周转时间 = 完成时间 -  到达时间

ü  带权周转时间 = 周转时间 / 需要运行时间

ü  等待时间 = 当前时间 -  到达时间

ü  优先权 = (等待时间 + 需要运行时间) / 需要运行时间

4、高响应比优先算法特点:

?  当等待时间相同时,短进程的优先权高;

?  当需要运行时间相同时,作业的优先权又取决于等待时间,相当于先到先服务;

长作业的优先级可以随着等待时间的增加而提高,因此长作业等待一段时间后仍能得

到调度。

5、源代码示例:

/*********************************************************************************

 * Copyright (C) 2000-2018 Hefei LonBon Technology Co., Ltd. All Rights Reserved.

 *

 * 文件名称 : Fifo_Test.c

 *

 * 文件描述 : FIFO服务和高响应比优先调度算法测试我

 *

 * 文件作者 :LonBon R&D Team

 *

 * 文件备注 :测试平台 - wxDev-C++ 7.4.2.569

 *

 ---------------------------------------------------------------------------------

 * 修改日期 : XXXXxxxx      xx:xx

 *

 * 编辑人员 :xx xx

 *

 * 修改内容 : NULL

**********************************************************************************/

#include <stdlib.h> 

#include <string.h> 

#include <stdio.h>

#include <cstdlib>

#include <iostream>

 

using namespace std;

 

/*********************************************************************************

 * 相关宏定义

**********************************************************************************/

// 就绪状态

#define WAIT                             "Wait"

// 运行状态  

#define RUN                        "Run"

// 完成状态

#define FINISH                           "Finish"

// 设置进程测试数为5    

#define JOBNUMBER                   (5)

// 进程名称长度

#define JOB_NAME_SIZE_MAX      (10)

// 进程长度状态

#define JOB_PROCESS_STA_LEN          (10)

/*********************************************************************************

 * 数据类型声明

**********************************************************************************/

typedef struct JCB{

    // 作业名     

    char jobName[JOB_NAME_SIZE_MAX];

    // 到达时间  

    int arriveTime;

      // 需要运行时间 

    int runTime;

      // 开始时间  

    int startTime;

      // 完成时间  

    int endTime;

      // 周转时间 

    int turnoverTime;

      // 带权周转时间 

    float useWeightTurnoverTime;

      // 进程状态 

    char processStatus[JOB_PROCESS_STA_LEN];  

}; 

 

/*********************************************************************************

 * 全局变量声明

**********************************************************************************/

// 当前时间

static int currentTime = 0;

// 进程完成数量    

static int finishNumber = 0;

// 存放数组名信息的二元数组

char JobArray[JOBNUMBER][10];

// 存放进程优先级的一元数组    

float priority[JOBNUMBER];

 

 

 

// 创建JCB 

void createJCB(struct JCB* jcb)

{ 

    freopen("input.txt","r",stdin); 

    printf("从文件中读入三个参数的数据:\n"); 

    printf("作业号 到达时间 需要运行时间\n");  

    for(int i = 0; i < JOBNUMBER; i++)

      { 

        // 作业号

        scanf("%s", &jcb[i].jobName);

        // 到达时间           

        scanf("%d", &jcb[i].arriveTime);

           // 需要运行时间  

        scanf("%d", &jcb[i].runTime);

        jcb[i].startTime = 0; 

        jcb[i].endTime = 0; 

        jcb[i].turnoverTime = 0; 

        jcb[i].useWeightTurnoverTime = 0.0; 

        strcpy(jcb[i].processStatus, WAIT); 

        printf("%s\t%d\t%d\n",jcb[i].jobName, jcb[i].arriveTime,jcb[i].runTime); 

    } 

    printf("---------------------------------------------\n"); 

    freopen("CON", "r", stdin); 

 } 

  

//打印用途 

void printJob(struct JCB* jcb)

{ 

    printf("当前时间为%d\n", currentTime); 

    printf("作业号 到达时间 需要运行时间 开始时间 完成时间 周转时间 带权周转时间 进程状态\n"); 

    for(int i = 0; i < JOBNUMBER; i++)

      {   

        if(strcmp(jcb[i].processStatus, FINISH) == 0)

           {

                 //如果进程为finish状态,这样输出  

            printf("%s\t%d\t%4d\t\t%d\t%d\t  %d\t  %.2f\t  %s\n",

                        jcb[i].jobName, jcb[i].arriveTime, jcb[i].runTime,

                         jcb[i].startTime, jcb[i].endTime, jcb[i].turnoverTime,

                         jcb[i].useWeightTurnoverTime, jcb[i].processStatus);

        }             

        else if(strcmp(jcb[i].processStatus, RUN) == 0)

           {

                 //如果进程为run状态,这样输出   

            printf("%s\t%d\t%4d\t\t%d\t运行中\t  none\t  none    %s\n",

                     jcb[i].jobName, jcb[i].arriveTime,

                            jcb[i].runTime, jcb[i].startTime,

                            jcb[i].processStatus);

        }             

        else

           {

                 //如果进程为wait状态,这样输出 

            printf("%s\t%d\t%4d\t\t未运行\tnone\t  none\t  none    %s\n",

                        jcb[i].jobName, jcb[i].arriveTime,

                         jcb[i].runTime, jcb[i].processStatus); 

           }

    } 

    printf("---------------------------------------------\n"); 

} 

 

//计算平均带权周转时间  

float weightTurnoverTimeCount(struct JCB* jcb)

{ 

    float sum = 0.0; 

     

    for(int i = 0; i < JOBNUMBER; i++) 

        sum += jcb[i].useWeightTurnoverTime;

     

    return sum / JOBNUMBER; 

} 

 

//计算平均周转时间  

float turnOverTimeCount(struct JCB* jcb)

{  

    float sum = 0.0; 

     

    for(int i = 0; i < JOBNUMBER; i++) 

        sum += jcb[i].turnoverTime; 

     

    return sum / JOBNUMBER; 

} 

 

//比较各个进程之间的到达时间,按升序排列  

void compare(struct JCB* jcb)

{ 

    for(int i = 0; i < JOBNUMBER; i++)

      { 

        int min = jcb[i].arriveTime, minIndex = i;

          

        for(int j = i + 1; j < JOBNUMBER; j++)

           { 

            if(jcb[j].arriveTime < min)

                 { 

                min = jcb[j].arriveTime; 

                minIndex = j;        

            }    

        } 

        struct JCB temp = jcb[i]; 

        jcb[i] = jcb[minIndex]; 

        jcb[minIndex] = temp; 

    }    

} 

 

//打印进程调度顺序,平均周转时间及平均带权周转时间  

void printInfo(struct JCB* jcb)

{ 

    printf("1、进程调度顺序为:%s -> %s -> %s -> %s -> %s\n", JobArray[0], JobArray[1], JobArray[2], JobArray[3], JobArray[4]); 

    printf("2、平均周转时间为:%.2f\n",turnOverTimeCount(jcb)); 

    printf("3、平均带权周转时间为:%.2f\n", weightTurnoverTimeCount(jcb)); 

    printf("------------------测试完毕 欢迎使用------------------\n"); 

} 

 

//两算法共同循环遍历部分  

void loop(struct JCB* jcb, int i)

{ 

    jcb[i].startTime = currentTime; 

    jcb[i].endTime = jcb[i].startTime + jcb[i].runTime; 

    jcb[i].turnoverTime = jcb[i].endTime - jcb[i].arriveTime; 

    jcb[i].useWeightTurnoverTime = jcb[i].turnoverTime * 1.0 / jcb[i].runTime; 

    strcpy(jcb[i].processStatus, RUN); 

    while(true)

      { 

        if(currentTime == jcb[i].endTime)

           {   

            strcpy(jcb[i].processStatus, FINISH); 

            finishNumber++; 

            if(finishNumber == JOBNUMBER) 

                printJob(jcb); 

            currentTime--; 

            break; 

        } 

        else

           { 

            printJob(jcb); 

            currentTime++;   

        }    

    } 

}  

 

//先来先服务调度算法 

void firstComeFirstServed(struct JCB* jcb)

{ 

    createJCB(jcb); 

    compare(jcb); 

    int i = 0;  

    //进程调度currentTime每次加1,直到进程全部被调度完成为止  

    for(; finishNumber != JOBNUMBER; currentTime++)

      { 

        if(currentTime < jcb[0].arriveTime)

           {

                 //当前时间小于第一个节点到来时间时,直接打印  

            printJob(jcb);

          }

        else

           { 

            strcpy(JobArray[i], jcb[i].jobName); 

            loop(jcb, i); 

            i++; 

        } 

    }

     

      // 打印进程调度顺序,平均周转时间及平均带权周转时间  

    printInfo(jcb);

      // 静态变量当前时间置位

    currentTime = 0;

    // 静态变量完成进程数量置位

    finishNumber = 0; 

} 

 

//高响应比优先调度算法  

void highestResponseRatioNext(struct JCB* jcb)

{ 

    createJCB(jcb); 

    compare(jcb); 

    int i = 0, j = 0;  

    for(; finishNumber != JOBNUMBER; currentTime++)

      {  

        float maxPriority = 0.0; 

        int indexPriority = 0; 

        if(currentTime < jcb[0].arriveTime)

           {

                 //当前时间小于第一个节点到来时间时,直接打印  

            printJob(jcb);

        }             

        else

           { 

            for(int i = 0; i < JOBNUMBER; i++)

                 { 

                if(strcmp(jcb[i].processStatus, FINISH) != 0)

                      { 

                    int waitTime = currentTime - jcb[i].arriveTime; 

                    priority[i] = (waitTime + jcb[i].runTime) * 1.0 / jcb[i].runTime; 

                    if(priority[i] > maxPriority)

                            { 

                        maxPriority = priority[i]; 

                        indexPriority = i; 

                    } 

                }                

            } 

            strcpy(JobArray[j++], jcb[indexPriority].jobName); 

            loop(jcb, indexPriority); 

        } 

    } 

    printInfo(jcb);//打印进程调度顺序,平均周转时间及平均带权周转时间  

    currentTime = 0;//当前时间置位 

    finishNumber = 0;//完成进程数量置位  

} 

 

//菜单函数 

void menu(struct JCB* jcb)

{ 

    int input;   

    while(true)

      { 

        printf("------------MarkXu QQ:2912615383--------------\n"); 

        printf("|        1、先来先服务调度算法               |\n"); 

        printf("|        2、响应比高者优先调度算法           |\n"); 

        printf("|        3、退出                             |\n"); 

        printf("----------------------------------------------\n"); 

        printf("请输入序号以继续程序:"); 

        scanf("%d", &input); 

        switch(input)

           { 

            case 1:firstComeFirstServed(jcb); 

                break;  

            case 2:highestResponseRatioNext(jcb); 

                break; 

            case 3: 

                exit(0); 

            default:printf("输入有误,请重新输入!!!\n"); 

                break;  

        }    

    } 

} 

 

int main(int argc, char *argv[])

{

    struct JCB jcb[JOBNUMBER]; 

    menu(jcb);

    cout << "Press the enter key to continue ...";

    cin.get();

    return EXIT_SUCCESS;

}

6、测试用例:

建立一个txt文件,命名为input.txt,输入下面的内容,保存到工程文件夹下,

说明:三个参数分别是作业名称,到达时间以及需要运行时间

 

7、运行结果:

1)菜单页面:

   

2)先到先服务算法调度过程:

①当前时间为0时,模拟系统从外存的后备队列中选取五项作业(job1job2job3

job4job5)调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程

排在就绪队列上等待调度,其进程状态为wait状态。

②当前时间为1时,job5到达,并开始执行,进程状态由wait转换为run;当前时间为3时,job5执行完毕,开始时间1 + 需要运行时间2 =完成时间3,进程状态由run转换为finish。与此同时,job2开始执行,进程状态由wait转换为run

③当前时间为8时,job2执行完毕,进程状态由run转换为finish,与此同时job3开始执行,进程状态由wait转换为run

④当前时间为12时,job3运行完毕,进程状态由run转换为finish,与此同时job4开始执行,进程状态由wait转换为run

⑤当前时间为19时,job4运行完毕,进程状态由run转换为finish,与此同时job1开始执行,进程状态由wait转换为run

⑥当前时间为21时,job5执行完毕,进程状态由run转换为finish,此时五个进程状态全部转换为finish,进程调度算法停止,打印出进程调度顺序,平均周转时间,以及平均带权周转时间。算法调度完毕后回到菜单界面:

3)高响应比优先算法调度过程:

①当前时间为0时,模拟系统从外存的后备队列中选取五项作业(job1job2job3job4job5)调入内存,并为它们创建进程,分配必要的资源。然后再将新创建的进程排在就绪队列上等待调度,其进程状态为wait状态;当前时间为1时,只有job5到达,并开始执行,进程状态由wait转换为run;当前时间为3时,job5执行完毕,开始时间1 +需要运行时间2 =完成时间3,进程状态由run转换为finish。与此同时,job3开始执行,进程状态由wait转换为run

②当前时间为7时,job3执行完毕,开始时间3 +需要运行时间4  =完成时间7,进程状态由run转换为finish。与此同时,job2开始执行,进程状态由wait转换为run

③当前时间为12时,job2执行完毕,进程状态由run转换为finish,与此同时job1开始执行,进程状态由wait转换为run

④当前时间为14时,job5执行完毕,进程状态由run转换为finish,与此同时job4开始执行,进程状态由wait转换为run

⑤当前时间为21时,job4执行完毕,进程状态由run转换为finish,此时五个进程状态全部转换为finish,进程调度算法停止,打印出进程调度顺序,平均周转时间,以及平均带权周转时间。算法调度完毕后回到菜单界面:

⑥按3退出

4)对实现高响应比的验证:

    优先权 = (等待时间 + 需要运行时间) / 需要运行时间

    当前时间为1时,只有job5到了,那就先运行它,需要运行时间为2,运行到时间3结束,开始调度下一进程;

    当前时间为3时,job5运行完毕,job2job3job4也已经到达,比较三者的优先权:

    Job2:(1 + 5/ 5 = 1.2job3:(1 + 4/  4  = 1.25job4:(0 + 7/ 7  = 1,优先权最大为job3,执行它,需要运行时间为4,因此直到时间7结束,开始调度下一进程;

    当前时间为7时,job3运行完毕,此时job2,job4,job1全都已经到达,比较三者的优先权:

    Job2:(5 + 5/ 5 = 2job4:(4+ 7/  7  = 1.57job1:(2 + 2/ 2  = 2,优先权最大为job2job1,优先权相同时执行先到的进程,因此执行进程job2,需要运行时间为5,因此直到时间12结束,开始调度下一进程;

    当前时间为12时,job2运行完毕,比较job1job4的优先权:

    Job1:(7 + 2/ 2 = 4.5job4:(9 + 7/  7  = 2.29, 优先权最大为job1,执行它,需要运行时间为2,因此直到时间14结束,开始调度下一进程;

    当前时间为14时,剩余进程job4,执行它,需要运行时间为7,因此直到时间21结束,此时后备队列中五个进程执行完毕,调度完毕。

    验证结果为:job5 >> job3 >> job2 >> job1 >> job4,与程序运行结果一致。

5)二者对比:

    先来先服务算法:

高响应比优先算法:

二者在调度顺序上出现了不一致,

?  在平均周转时间上:先来先服务 > 高响应比优先

?  在平均带权周转时间上:先来先服务 > 高响应比优先

?  在这次运行的测试用例中可以看出,二者算法在两项指标性能上,高响应比优先算法要优于先来先服务算法。

首先高响应比优先算法兼顾了等待时间和需要运行时间,其短进程的优先权高,与此同时长作业的优先级可以随着等待时间的增加而提高,因此长作业等待一段时间后仍能得到调度而不会长期得不到服务。而先来先服务算法则很容易导致长作业到来过多时,短作业再到达造成的“饥饿”现象;也避免了短进程优先中存在大量短作业时造成的长作业“饥饿”现象;高响应比算法在优先权相同的时候,执行到达时间早的进程。

回归到我司的产品,以B3为例,在绘制显示页面的时候,可以绘制绘制综合利用时间短的界面,再绘制其它,会节约很多MCU资源,也会使刷屏效果不那么明显,还有一些呼叫及请求增援等,也可以用类似方法处理。当然有人会不以为然,挤这点资源,无疑杯水车薪,但是就单个bit必争的MCU来说,还是大大有好处的。

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

热门文章