操作系统 作业调度实验报告(进程调度-先到先服务FCFS 最短作业优先SJF 高相应比优先 优先权调度 时间片轮转）_高响应比优先调度算法实验报告

完成五个进程调度的模拟包括：1.先到先服务调度(FCFS) 2.最短作业优先调度(SJF)
3.高响应比优先调度 4.（抢占式）优先权调度 5.时间片轮转调度

1. FCFS算法：按照作业/进程进入队列的先后顺序进行挑选，先进入的将先进行后续步骤的处理。
2. SJF算法：以进入系统的作业所要求的CPU运行时间的长短为挑选依据，优先选取预计所需服务时间最短的作业进行调度，可以分别用于高级调度和低级调度。
3. 高响应比优先调度算法:既考虑作业等待时间又考虑作业运行时间把CPU分配给就绪队列中响应比最高的进程。
4. （抢占式）优先权调度：可抢占优先权调度，系统把处理机分配给优先权最高的进程，使之执行但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程（原优先权最高的进程）的执行，重新将处理机分配给新到的优先权最高的进程。
5. 时间片轮转算法：将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把处理机分配给队首进程，并令其执行一个时间片。
   设计流程图如下：

#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#define N 10				//允许最大进程个数
#define M 100				//进程名长度
int n;						//进程个数
char name[N][M]; 			//进程名
int Arival[N]={0};			//到达时间
int Go[N]={0};				//运行时间
int Start[N]={0};			//开始时间
int End[N]={0};				//结束时间
int Timer[N]={0};			//周转时间
float DTimer[N]={0};		//带权周转时间
int Check[N]={0};			//判断作业是否完成，完成值为1
int prio[N]={0};           //优先权，初始化为100，优先权=100-运行时间，运行时间越短优先级越高，先进行调度
int left[N]={0};            //剩余时间，抢占、轮转调度时剩余时间
void input(){
        int i;
		printf("输入进程的个数:");
		scanf("%d",&n);
		for(i=0;i<n;i++){
			printf("输入 进程名：");
			scanf("%s",&name[i]);
			printf("第%d个进程的到达时间:",i+1);
			scanf("%d",Arival+i);
			printf("第%d个进程的运行时间:",i+1);
			scanf("%d",Go+i);
			prio[i]=100-Go[i];
			left[i]=Go[i];
		}
}
/*先来先服务调度算法*/
 /**选出先到达的作业
 *a[] 到达时间
 *n 进程个数
 **/
int Select1(int a[],int n){
	int i=0;
	for(int k=0;k<n;k++){
		if(Check[k]==0){
			i=k;
			break;
		}
	}
	for(int j=0;j<n;j++){
		if(a[i]>a[j]&&Check[j]==0){
			i=j;
		}
	}
	Check[i]=1;
	return i;
}
/*短作业优先调度算法*/
/**选出短作业
 *a[] 运行时间
 *n 进程个数
 *local 当前时间
 **/
int Select2(int a[],int n,int local){
	int i=0;
	for(int k=0;k<n;k++){
		if(Check[k]==0){
			i=k;
			break;
		}
	}
	for(int j=0;j<n;j++){
		if(a[i]>a[j]&&Check[j]==0&&Arival[j]<=local){
			i=j;
		}
	}
	Check[i]=1;
	return i;
}
/*高响应比优先调度算法*/
/**选出响应比最高作业
 *优先权=等待时间+要求服务时间/要求服务时间
 *a[] 到达时间
 *b[] 要求服务时间
 *n 进程个数
 *local 当前时间
 **/
 int Select3(int a[],int b[],int n,int local){
	int i=0;
	double rate;
	for(int k=0;k<n;k++){
		if(Check[k]==0){
			i=k;
			break;
		}
	}
	rate=(local-a[i]+b[i])/b[i];
	for(int j=0;j<n;j++){
            double temp=(local-a[j]+b[j])/b[j];
		if(temp>rate&&Check[j]==0&&Arival[j]<=local){
			i=j;
            rate=temp;
		}
	}
	Check[i]=1;
	return i;
}
void diaodu(int x){
	int k=0;			//每次选出即将服务的进程
	int l=0;			//本次服务的进程
	int Atimer=0;		//周转时间之和
	float timer=0;		//带权周转时间之和
	int localtime=0;	//当前时间
	memset(Check,0,sizeof(Check));//每次开始之前Check数组要全部置0
	if(x==1)
	 k=Select1(Arival,n);
	if(x==2)
	 k=Select2(Go,n,localtime);
	if(x==3)
	 k=Select3(Arival,Go,n,localtime);
	Start[k]=Arival[k];
	End[k]=Start[k]+Go[k];
	Timer[k]=End[k]-Arival[k];
	DTimer[k]=(float)Timer[k]/Go[k];
	localtime=End[k];
	printf("作业  提交时间  运行时间  开始时间  结束时间  周转时间  带权周转时间\n");
	for(int m=0;m<n;m++){
		l=k;
		if(x==1)
	     k=Select1(Arival,n);
	    if(x==2)
         k=Select2(Go,n,localtime);
	    if(x==3)
	     k=Select3(Arival,Go,n,localtime);
		Start[k]=End[l];
		End[k]=Start[k]+Go[k];
		Timer[k]=End[k]-Arival[k];
		DTimer[k]=(float)Timer[k]/Go[k];
		Atimer=Timer[l]+Atimer;
		timer=timer+DTimer[l];
		printf(" %s     %2d        %2d         %2d        %2d        %2d         %.2f\n",name[l],Arival[l],Go[l],Start[l],End[l],Timer[l],DTimer[l]);
	}
	printf("平均周转时间:%.2f\n",(float)Atimer/n);
	printf("平均带权周转时间:%.2f\n",(float)timer/n);
}
/*抢占式优先权调度算法*/
/**选出该时刻前优先级最高的进程
 *a[] 优先级
 *left[] 剩余时间
 *n 进程个数
 *local 当前时间
 **/
 int Select4(int a[],int left[],int n,int local){
	int i=0;
	for(int k=0;k<n;k++){
		if(Check[k]==0){
			i=k;
			break;
		}
	}
	for(int j=0;j<n;j++){
		if(a[j]>a[i]&&left[j]!=0&&Arival[j]<=local){
			i=j;
		}
	}
	return i;
}
void p_prio(){
    int k=0;			//每次选出即将服务的进程
	int l=0;			//本次服务的进程
	int Atimer=0;		//周转时间之和
	float timer=0;		//带权周转时间之和
	int localtime=0;	//当前时间
	memset(Check,0,sizeof(Check));//每次开始之前Check数组要全部置0
    k=Select4(prio,left,n,localtime);
    Start[k]=Arival[k];
	int sum=0;         //记录完成进程数
	printf("作业  提交时间  运行时间  开始时间  剩余运行时间  结束时间  周转时间  带权周转时间\n");
	while(sum<n){
	    localtime++;
        left[k]--;
        prio[k]++;
        if(left[k]==0){
        sum++;
        Check[k]=1;
	    End[k]=localtime;
	    Timer[k]=End[k]-Arival[k];
	    DTimer[k]=(float)Timer[k]/Go[k];
            printf(" %s     %2d        %2d         %2d        %2d        %2d        %2d         %.2f\n",name[k],Arival[k],Go[k],Start[k],left[k],End[k],Timer[k],DTimer[k]);
        }
        else
            printf(" %s     %2d        %2d         %2d        %2d         未完成     未完成    未完成\n",name[k],Arival[k],Go[k],Start[k],left[k]);

        l=Select4(prio,left,n,localtime);//有新进程抢占
        if(l!=k){
            if(left[l]==Go[l])//第一次被选中记录开始时间
                Start[l]=localtime;
            k=l;
        }
	}
    for(int i=0;i<n;i++){
        Atimer=Timer[i]+Atimer;
		timer=timer+DTimer[i];
    }
	printf("平均周转时间:%.2f\n",(float)Atimer/n);
	printf("平均带权周转时间:%.2f\n",(float)timer/n);
}
/*时间片轮转调度算法*/
void lun(){
    int k=0;			//每次选出即将服务的进程
	int l=0;			//本次服务的进程
	int Atimer=0;		//周转时间之和
	float timer=0;		//带权周转时间之和
	int localtime=0;	//当前时间
	memset(Check,0,sizeof(Check));//每次开始之前Check数组要全部置0
    //k=Select4(prio,left,n,localtime);
    Start[k]=Arival[k];
	int sum=0;         //记录完成进程数
	printf("作业  提交时间  运行时间  开始时间  剩余运行时间  结束时间  周转时间  带权周转时间\n");
	while(true){
	    localtime++;
        left[k]--;
        if(left[k]==0){
        sum++;
        Check[k]=1;
	    End[k]=localtime;
	    Timer[k]=End[k]-Arival[k];
	    DTimer[k]=(float)Timer[k]/Go[k];
            printf(" %s     %2d        %2d         %2d        %2d        %2d        %2d         %.2f\n",name[k],Arival[k],Go[k],Start[k],left[k],End[k],Timer[k],DTimer[k]);
            if(sum==n)
                break;
        }
        else
            printf(" %s     %2d        %2d         %2d        %2d         未完成     未完成    未完成\n",name[k],Arival[k],Go[k],Start[k],left[k]);
        while(true){
            k++;
            if(k==n)
            k=k-n;
            if(left[k]!=0)
                break;

        }
        if(left[k]==Go[k]){
            Start[k]=localtime;
        }
	}
    for(int i=0;i<n;i++){
        Atimer=Timer[i]+Atimer;
		timer=timer+DTimer[i];
    }
	printf("平均周转时间:%.2f\n",(float)Atimer/n);
	printf("平均带权周转时间:%.2f\n",(float)timer/n);
}
void menu(){
	int choice;
	while(1){
		printf("              请选择调度算法           \n\t1、先来先服务（FCFS）\n\t2、短作业优先（SJF）\n\t3、高响应比优先\n\t4、（抢占式）优先权调度\n\t5、时间片轮转调度\n\t0、退出\n请输入：");//
		scanf("%d",&choice);
		if(choice==0){
			break;
		}
        else if(choice<=3){
            diaodu(choice);
        }
        else if(choice==4){
            p_prio();
        }
        else{
            lun();
        }
	}
}
int main(){
	input();
	menu();
	return 0;
}

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273