操作系统高响应比优先模拟算法

  这学期刚开始学习操作系统,收到一个作业,百度关于高响应比优先(HRRN,Highest Response Ratio Next)的CPU进程调度模拟算法,基本思想:短作业优先调度算法 + 动态优先权机制;既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务(FCFS,First Come First Served)和最短作业优先(SJF,Shortest Job First)两种算法的特点。

                                                                                 实验一、作业调度模拟程序实验

  之后经过多番揣摩... ...决定界面用命令行算了,反正啥也不会...

                                                                            13物联网工程    刘烨   201306104146

  关于响应比:

一、 实验目的

    RR =  (预计运行时间 + 等待时间) / 预计运行时间 = 1 + 等待时间/预计运行时间;

(1)加深对作业调度算法的理解;

  响应比高者优先进行调度;

(2)进行程序设计的训练。 

 

二、 实验内容和要求

  关于要求中的周转时间、带权周转时间、平均周转时间和平均带权周转时间:

用高级语言编写一个或多个作业调度的模拟程序。

    周转时间 =(作业完成的时间 - 作业提交时间);

单道批处理系统的作业调度程序。作业一投入运行,它就占有计算机的一切资源直到作业完成为止,因此调度作业时不必考虑它所需要的资源是否得到满足,它所运行的时间等因素。

    带权周转时间 = 作业周转时间 / 作业运行时间;

     作业调度算法:

    平均周转时间 = (周转时间1+周转时间2+...+周转时间n)/ n;

1) 采用先来先服务(FCFS)调度算法,即按作业到达的先后次序进行调度。总是首先调度在系统中等待时间最长的作业。

    平均带权周转时间 = (带权周转时间1+带权周转时间2+...+带权周转时间n)/ n;

2) 短作业优先 (SJF) 调度算法,优先调度要求运行时间最短的作业。

 

3) 响应比高者优先(HRRN)调度算法,为每个作业设置一个优先权(响应比),调度之前先计算各作业的优先权,优先数高者优先调度。RP (响应比)= 作业周转时间 / 作业运行时间=1+作业等待时间/作业运行时间

  开始,用vector存储提交的作业结构体指针,自己设置一个系统时间,毕竟模拟不可能时间流速一毛一样,接下来就是毫无技术含量的选择了,关于测试数据,想了想好难输,还得自己编,于是用随机函数产生数据;再在主函数参数中提供一个传递生成数据数量的参数。

每个作业由一个作业控制块JCB表示,JCB可以包含以下信息:作业名、提交(到达)时间、所需的运行时间、所需的资源、作业状态、链指针等等。

  说到这里得说一下,关于java老师(没错,java老师)说的关于main()的一些情况:

三、 实验方法、步骤及结果测试

1 int main(int argc, char** argv){ ////argc为参数个数, argv为接下来传的参数
2     ...
3     return 0;
4 }
  1. 源程序名:实验二 修改版.c

 

可执行程序名:修改版.exe

比如在命令行中调用该函数,***.exe 100,此时有两个参数,一个为"***.exe", 另一个就是"100"了,分别在argv[0]和argv[1]中。

  1. 原理分析及流程图

  首先是数据生成,用为要求格式,所以要小处理一下,感觉这种方法可以在刷ACM题被题目玄学时使用,一个为标准代码,一个为自己的代码,目前未试过:

   本次实验主要用了结构体数组来实现。首先定义一个JCB模块用于存放作业信息,如到达时间,运行时间等。后来各个函数分别实现相应的作业调度。其中用到冒泡排序将作业按到达时间或者运行时间排序。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 
 4 int ch_to_int(char* s){
 5     int ans = 0, len = strlen(s);
 6     for(int i = 0; i < len; i++) ans = ans*10 + s[i]-'0';
 7     return ans;
 8 }
 9 int main(int argc, char** argv){
10     int k, N, tj/*0~23*/, ys/*0~59*/, tmp;
11     freopen("test.txt", "w", stdout);
12     srand(time(NULL));   //以系统时间为种子生成真正的随机数
13     N = k = ch_to_int(argv[1]);
14     while(k--){
15         tmp = (rand() + 24)%24 * 100 + (rand() + 6)%6*10 + (rand() + 10)%10;
16         printf("%04d %dn", tmp, (rand() + N)%N + 1);
17     }
18     return 0;
19 }

澳门新葡亰1495app 1

 

  1. 主要程序段及其解释:

  调度算法:

#include<stdio.h>

 1 #include "bits/stdc++.h"
 2 #include "windows.h"
 3 using namespace std;
 4 typedef long long ll; 
 5 
 6 //(所有时间以分钟为单位存储,需要时转化) 
 7 
 8 ll systemTime;    //自定义系统当前时间
 9 
10 struct Task{
11     int Tij; //提交时间 
12     int Ysi; //预计运行时间 
13     ll waitingTime;  //等待时间
14     int id; //作业号
15     
16     ll prior(){
17         return 1 + waitingTime*1.0/Ysi;
18     }
19     
20     Task(int T, int Y){
21         Tij = T;
22         Ysi = Y;
23         waitingTime = 0;
24     }
25     ll aroundTime(){
26         return systemTime - Tij + Ysi;
27     }
28     
29     double priorTime(){
30         return aroundTime()*1.0/Ysi;
31     }
32     void disp(int ord){
33         printf("--调度次序: %d --作业号: %04d --调度时间:%02d%02d --周转时间: %d min(s) --带权周转时间%.2f  ...n", 
34             ord, id, (systemTime/100 + systemTime/60)%24, systemTime%60, aroundTime(), priorTime());
35     }
36 };
37 
38 int cmp1(const Task* a, const Task* b){
39     return (a->Tij) < (b->Tij);
40 }
41 
42 int main(){
43     vector<Task*> taskArr;    ///以不定长数组存储作业队列
44     
45     int Tij, Ysi, order;
46     ll ave_aroundTime = 0;
47     double ave_prior_aroundTime = 0;
48     
49     freopen("test.txt", "r", stdin);
50     system(".\生成测试数据.exe 1024");    //调用测试数据生成程序
51     
52     while(cin>>Tij>>Ysi) taskArr.push_back(new Task(Tij%100 + Tij/100*60, Ysi));
53     
54     ////按提交时间进行排序并编号 
55     sort(taskArr.begin(), taskArr.end(), cmp1);
56     std::vector<Task*>::iterator pos;
57     for(pos = taskArr.begin(); pos != taskArr.end(); pos++){
58         (*pos)->id = pos - taskArr.begin();
59     }
60     
61     std::vector<Task*>::iterator willRun;  //指向即将运行程序 
62     systemTime = (*taskArr.begin())->Tij;    ///将系统当前时间设置为最早提交的作业时间 
63     order = -1;
64     while(!taskArr.empty()){
65         bool flag = false; ///判定是否有新的程序提交 
66         willRun = taskArr.begin();
67         for(pos = taskArr.begin(); pos != taskArr.end(); pos++){
68             if((*pos)->Tij > systemTime) break;
69             willRun = (*willRun)->prior() < (*pos)->prior() ? pos : willRun;
70             flag = true;
71         }
72         if(!flag){
73             willRun = taskArr.begin();
74             systemTime = (*willRun)->Tij;
75         }
76         
77         (*willRun)->disp(++order);
78         
79         ave_aroundTime += (*willRun)->aroundTime();  //总周转 
80         ave_prior_aroundTime += (*willRun)->priorTime();  //总带权周转 
81         
82         for(pos = taskArr.begin(); pos != taskArr.end(); pos++){  //更新等待时间 
83             if((*pos)->Tij < systemTime){
84                 (*pos)->waitingTime += (*willRun)->Ysi;
85             }
86         }
87 
88         systemTime += (*willRun)->Ysi;  //系统时间增加 
89 
90         taskArr.erase(willRun); //结束则删除 
91         
92         //Sleep(10);
93     }
94     cout<<ave_aroundTime<<' '<<ave_prior_aroundTime<<endl;
95     printf("n----平均周转时间: %.2f --平均带权周转时间: %.2f ...n作业结束..", ave_aroundTime*1.0/order, ave_prior_aroundTime/order);
96 
97     return 0;
98 } 

#include <stdlib.h>

加油( ̄▽ ̄)"

int i,k,num,m,n;

#define N  24

struct JCB{

        char name[10];      //作业名

        float arrive;           //作业提交时间  

        float run;           //作业运行时间  

        float start;          //开始时间       

        float finish;       //完成时刻       

        float zhouzhuan;         //周转时间       

        float weight;       //带权周转时间  

}jcb[N],temp;

void input()                //用户输入模块

{

    int i;  

    do{

        printf("nt请输入作业数(2-24):");

        scanf("%d",&num); 

        printf("n");

        if(num<2||num>24)

{

            printf("t请重新输入!n");

        }

    }

    while(num<2||num>24);

    for(i=0;i<num;i++){

        printf("t第%d个作业名:",i+1);   

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

        printf("nt请输入作业提交时间:");   

        scanf("%f",&jcb[i].arrive);   

        printf("nt请输入作业运行时间:");   

        scanf("%f",&jcb[i].run);   

        printf("n");

    }

}

void output()             //输出模块

{

    float   numT=0;  

float numW=0;

float avgT=0;  //平均周转时间

float avgW=0;   //平均带权作业周转时间

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

    printf(" 作业名  提交时间  运行时间  开始时间  完成时间  周转时间  带权周转时间n");

    for(i=0;i<num;i++)

    {

        printf("   %-8s%-10.2f%-10.2f%-10.2f%-10.2f%-10.2f%-10.2f",jcb[i].name,jcb[i].arrive,jcb[i].run,jcb

 

        [i].start,jcb[i].finish,jcb[i].zhouzhuan,jcb[i].weight);

        printf("n");

        numT=numT+jcb[i].zhouzhuan;

        numW=numW+jcb[i].weight; 

    }

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

    avgT=numT/num;

    avgW=numW/num;

    printf("平均作业周转时间:%.2fn",avgT);

    printf("n");

    printf("平均带权作业周转时间:%.2fn",avgW); 

    printf("n");

}

 float addallruntime()//得到所有作业运行时间

 {

    int i;

     float allruntime=0.0;

           for(i=0;i<num;i++)

           {             

               allruntime=allruntime+jcb[i].run;

           }

           return allruntime;

 }

 

void fcfsrunning()

{

    for(k=0;k<num;k++)

    {

        if(k==0)/*运行第一个作业*/

        {

            jcb[k].start=jcb[k].arrive;    

            jcb[k].finish=jcb[k].arrive+jcb[k].run; 

        }

        else

        {

            if(jcb[k].arrive>=jcb[k-1].finish)/*当前作业运行完,但后面作业没到达*/

            {

                jcb[k].start=jcb[k].arrive;     

                jcb[k].finish=jcb[k].arrive+jcb[k].run;

            }

            else/*当前作业没运行完,后面作业已到达*/

            {

                jcb[k].start=jcb[k-1].finish;     

                jcb[k].finish=jcb[k-1].finish+jcb[k].run; 

            }

        }

            

    }

    for(k=0;k<num;k++)

    {

        jcb[k]澳门新葡亰1495app,.zhouzhuan=jcb[k].finish-jcb[k].arrive;   

        jcb[k].weight=jcb[k].zhouzhuan/jcb[k].run;

    }

}

void FCFS()     //先来先服务

{

本文由澳门新葡亰1495app发布于网络技术,转载请注明出处:操作系统高响应比优先模拟算法

相关阅读