大奖888网页版登陆实验二报告，操作系统高响应比优先模拟算法
这学期刚开始学习操作系统，收到一个作业，百度关于高响应比优先（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 }
- 源程序名：实验二 修改版.c
可执行程序名：修改版.exe
比如在命令行中调用该函数，***.exe
100，此时有两个参数，一个为”***.exe”，
另一个就是”100″了，分别在argv[0]和argv[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 }
- 主要程序段及其解释：
调度算法：
#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].zhouzhuan=jcb[k].finish-jcb[k].arrive;
jcb[k].weight=jcb[k].zhouzhuan/jcb[k].run;
}
}
void FCFS() //先来先服务
{
int i,j;
for(j=0;j<num;j++) //冒泡排序，按到达时间排序
{
for(i=0;i<num-j-1;i++)
{
if(jcb[i].arrive>jcb[i+1].arrive)
{
temp=jcb[i];
jcb[i]=jcb[i+1];
jcb[i+1]=temp;
}
}
}
fcfsrunning();
output();
void SJF(float allruntime) //非抢占
{
float mintime=0; struct JCB jtemp={0};
int min=0;
int startwork=0;
float i;
int k;
for (i=0;i<allruntime;)
{
mintime=jcb[startwork].run;//假设一个剩余时间的最小值
for(k=startwork;k<num;k++)
{
if(jcb[k].run<=mintime&&jcb[k].arrive<=i)
{
mintime=jcb[k].run;
min=k;
}
}
jcb[min].start=i;
jcb[min].finish=jcb[min].start+jcb[min].run;
jcb[min].zhouzhuan=jcb[min].finish-jcb[min].arrive;
jcb[min].weight=jcb[min].zhouzhuan/jcb[min].run;
jtemp=jcb[startwork];
jcb[startwork]=jcb[min];
jcb[min]=jtemp;
startwork++;
i=i+mintime;
}
output();
}
void HRRF(float allruntime)
{
float maxrb=0;
struct JCB jtemp={0};
int z=0;
float time=0;
int startwork=0;
float i;
int k;
for(i=0;i<allruntime;)
{
maxrb=(i-jcb[startwork].arrive)/jcb[startwork].run+1;//假设是最高响应比
for(k=startwork;k<num;k++)
{
if(jcb[k].arrive<=i&&(i-jcb[k].arrive)/jcb[k].run+1>=maxrb)//若此作业的最高响应比更高，则将其记为更高
{
time=jcb[k].run;
z=k;
}
}
jcb[z].start=i;
jcb[z].finish=jcb[z].start+jcb[z].run;
jcb[z].zhouzhuan=jcb[z].finish-jcb[z].arrive;
jcb[z].weight=jcb[z].zhouzhuan/jcb[z].run;
jtemp=jcb[startwork];
jcb[startwork]=jcb[z];
jcb[z]=jtemp;
startwork++;
i=i+time;
}
output();
}
main()
{
int n;
float allruntime=0.0;
input();
allruntime=addallruntime();
do{
printf(“tt作业调度模拟程序n”);
printf(“—————————————————————-n”);
printf(“t请选择调度算法(1~3)：n”);
printf(“tt1:FCFS(先来先服务)ntt2:SJF(短作业优先)ntt3:HRRF(最高响应比优先)ntt0:exit(退出)n”);
scanf(“%d”,&n);
if(n!=0&&n!=1&&n!=2&&n!=3)
{
printf(“nt请重新输入!!nn”);
}
switch(n)
{
case 1:FCFS(); break;
case 2:SJF(allruntime); break;
case 3:HRRF(allruntime); break;
case 0: break;
}
}
while(n!=0);
}
- 运行结果及分析
一般必须配运行结果截图，结果是否符合预期及其分析。
（截图需根据实际，截取有代表性的测试例子）
先来先服务（FCFS）：
短作业优先（SJF）：
四、实验总结：
一开始毫无头绪，因为并不清楚怎样算出调度结果。后来看多几次例子，做了练习，然后老师讲解几次后，开始了解算法的过程。但是用程序表达出来还是困难的。然而想参考网上的，但由于大多是用链表写的，看得不太懂。后来发现用数组的形式也是可以的。而且比较直观，没那么难理解。但是写了先来先服务后，短作业优先就没那么容易实现了。因为要比较作业的运行时间，后来用了冒泡排序算法先进行一番排序，再慢慢实现相应的要求。至于最高相应比优先，虽然知道了怎样算出调度结果，但程序实现不了.