高响应比优先HRRN算法实验

发表于 更新于 分类于 阅读次数： Valine： 本文字数： 81 阅读时长 ≈ 1 分钟

下表列出了JOB1、JOB2、JOB3、JOB4四个作业分别到达系统的时间、要求服务的时间、开始执行的时间及各自的完成时间，并计算出各自的周转时间和带权周转时间。

请输入图片描述

请输入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include<stdio.h>
#include<math.h>
#define N 4

int last_id=0;					//此时计算完成的进程

//时间结构体，用于进入时间、开始时间、结束时间
struct time
{
	int shi;
	int fen;
};

struct Gzuo {
	int id;						 //进程名字
	struct time dt;				 //进入到达时间 
	int st;						 //估计服务时间
	struct time rs;				 //开始时间 
	struct time wct;			 //完成时间 
	int zt;						 //周转时间
	float dczt;				     //带权周转时间
	int flag;					 //标志位，用来检测此进程是否已经执行过了
};
struct Gzuo a[N];

//查找最先到达的进程 ，并计算他的开始时间和结束时间 
void first_p()
{
	int i;
	int f_id = 0;
	struct time f_t = a[0].dt;
	for (i = 1; i < 4; i++)
	{
		if (a[i].dt.shi < f_t.shi) {
			f_t = a[i].dt;
			f_id = i;
		}
		else if (a[i].dt.shi == f_t.shi) {
			if (a[i].dt.fen < f_t.fen) {
				f_t = a[i].dt;
				f_id = i;
			}
		}
	}
	a[f_id].rs = a[f_id].dt;								//开始时间
	a[f_id].wct.shi = a[f_id].rs.shi + (a[f_id].st / 60);	//完成的时
	a[f_id].wct.fen = a[f_id].rs.fen + (a[f_id].st % 60);	//完成的分
	a[f_id].zt = (a[f_id].wct.shi*60 + a[f_id].wct.fen) - (a[f_id].dt.shi*60 + a[f_id].dt.fen);		//周转时间（分钟）
	a[f_id].dczt = (float)a[f_id].zt / (float)a[f_id].st;	//带权周转时间
	last_id = f_id;											//标志当前计算的是哪一个进程
	a[last_id].flag = 1;									//这个进程已经计算过

}

//计算剩余进程中最高的响应比的进程
void response() 
{
	float resp[N][2] = {0};
	int i=0;
	float max=0;
	int max_id=0;

	//计算各进程的响应比
	for (i = 0; i < N; i++)
	{
		resp[i][0] = i;
		if (a[i].flag==0)
		{	
			resp[i][3] = (float)(((a[last_id].wct.shi * 60 + a[last_id].wct.fen) - (a[i].dt.shi * 60 + a[i].dt.fen)) + a[i].st) / (float)a[i].st;
		}
	}

	//选择还未进行运行的第一进程假设作为最高响应比的进程
	for ( i = 0; i < N; i++)
	{
		if (a[i].flag == 0) {
			max = resp[i][4];
			break;
		}
	}
	


	//比较最高响应比，然后找出找最高响应比的进程
	for ( i = 0; i < N; i++)
	{
		if (a[i].flag == 0) {
			if (resp[i][5] >= max)
			{
				max = resp[i][6];
				max_id = resp[i][0];
				
			}
		}
	}

	//计算响应比最高的进程
	a[max_id].rs = a[last_id].wct;
	int temp_cnt = (a[max_id].rs.shi * 60 + a[max_id].rs.fen) + a[max_id].st;		//用来计算开始时间+估计运行时间的总分钟数
	a[max_id].wct.shi = temp_cnt / 60;												//利用总分钟数计算出结束时间的时
	a[max_id].wct.fen = temp_cnt % 60;												//利用总分钟数计算出结束时间的分
	a[max_id].zt = (a[max_id].wct.shi * 60 + a[max_id].wct.fen) - (a[max_id].dt.shi * 60 + a[max_id].dt.fen);
	a[max_id].dczt = (float)a[max_id].zt / (float)a[max_id].st;
	last_id = max_id;
	a[last_id].flag = 1;		//把此时的进程作为已经结束的最后一个进程
}

void main()
{
	//初始化进程 
	a[0].id = 1;
	a[0].dt.shi = 8;
	a[0].dt.fen = 0;
	a[0].st = 120;

	a[1].id = 2;
	a[1].dt.shi = 8;
	a[1].dt.fen = 50;
	a[1].st = 50;

	a[2].id = 3;
	a[2].dt.shi = 9;
	a[2].dt.fen = 0;
	a[2].st = 10;

	a[3].id = 4;
	a[3].dt.shi = 9;
	a[3].dt.fen = 50;
	a[3].st = 20;

	int i;
	int temp_last; //此时的进程计算结束 

	//查找最先到达的进程，计算它的开始时间和服务时间 
	first_p();

	//将没有进行计算的进程进行计算
	for ( i = 0; i <= N; i++)
	{
		if (a[i].flag==0)
		{
			response();
		}
		
	}
	

	//打印输出
	for (i = 0; i < N; i++)
	{
		printf("id:%d  dt:%d:%d  st:%d  rs:%d:%d  wct:%d:%d   zt:%d   dczt:%.2f  flag:%d\n",a[i].id, a[i].dt.shi, a[i].dt.fen, a[i].st,a[i].rs.shi, a[i].rs.fen, a[i].wct.shi, a[i].wct.fen, a[i].zt, a[i].dczt, a[i].flag);

	}
	printf("\n");
			
}