0%

Round Robin Scheduling in C Programming

​ 由于是操作系统的作业,很难顶,必须按着老师的格式来。老师不知道从哪里找来了一个实验报告模板丢给我们,给过来的代码结合了C和C++(非要用C++进行文件操作…..)

​ 然后就有了下面这货,跟着祖传代码魔改,勉强完成作业了。(真的要改吐了

时间片轮转调度算法的C还是C++语言还是C和C++实现

代码
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
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
#include <bits/stdc++.h>
#include <windows.h>
#include <conio.h>

using namespace std;

void Create_ProcInfo(); /* 建立进程调度需要的数据 */
void Display_ProcInfo(); /* 显示当前系统全部进程的状态 */
void Scheduler_FF();
void Cpu_Sched();
void IO_Sched();
void NextRunProcess();
void DisData();
void NewReadyProc();
void Read_Process_Info();


/* 定义全局变量 */
long ClockNumber; /* 系统时钟 */
int RunPoint; /* 运行进程指针,-1时为没有运行进程 */
int WaitPoint; /* 阻塞队列指针,-1时为没有阻塞进程 */
int ReadyPoint; /* 就绪队列指针,-1时为没有就绪进程 */
int ProcNumber; /* 系统中模拟产生的进程总数 */
int FinishedProc; /* 系统中模拟产生的进程总数 */
int q = 10; /* 时间片 */


/* 进程信息结构 */
struct ProcStruct
{
int p_pid; /* 进程的标识号 */
char p_state; /* 进程的状态,C--运行 R--就绪 W--组塞 B--后备 F--完成 */
int p_rserial[10]; /* 模拟的进程执行的CPU和I/O时间数据序列,间隔存储,第0项存储随后序列的长度(项数),以便知晓啥时该进程执行结束 */
int p_pos; /* 当前进程运行到的位置,用来记忆执行到序列中的哪项 */
int p_starttime; /* 进程建立时间 */
int p_endtime; /* 进程运行结束时间 */
int p_cputime; /* 当前运行时间段进程剩余的需要运行时间 */
int p_iotime; /* 当前I/O时间段进程剩余的I/O时间 */
int p_next; /* 进程控制块的链接指针 */
int p_excutetime; /* 记录一次时间片内执行的时间 */
int p_startruntime;
} proc[10];


void Create_ProcInfo() /* 随机生成进程数量和每个CPU--I/O时间数据序列,进程数量控制在5到10之间 */
{
int s, i, j;

srand( GetTickCount() ); /* 初始化随机数队列的"种子" */
ProcNumber = ( (float) rand() / 32767) * 5 + 5; /* 随机产生数量5~10 */

for ( i = 0; i < ProcNumber; i++ ) /* 生成进程的CPU--I/O时间数据序列 */
{
proc[i].p_pid = ( (float) rand() / 32767) * 1000; /* 初始化随机的进程ID号 */
proc[i].p_state = 'B'; /* 初始都为后备状态 */

s = ( (float) rand() / 32767) * 6 + 6; /* 产生的进程数据序列长度在6~12间 */
proc[i].p_rserial[0] = s; /* 第一项用于记录序列的长度 */
for ( j = 1; j <= s; j++ ) /* 生成时间数据序列 */
proc[i].p_rserial[j] = ( (float) rand() / 32767) * 10 + 5;
/* 赋其他字段的值 */
proc[i].p_pos = 1;
proc[i].p_starttime = ( (float) rand() / 32767) * 49 + 1; /* 随机设定进程建立时间 */
proc[i].p_endtime = 0;
proc[i].p_cputime = proc[i].p_rserial[1];
proc[i].p_iotime = proc[i].p_rserial[2];
proc[i].p_next = -1;
proc[i].p_excutetime = 0;
proc[i].p_startruntime = 0;
}
printf( "\n---------------------------\n 建立了%2d 个进程数据序列\n\n", ProcNumber );
DisData(); /* 该函数为在屏幕上打印所创建的进程的具体信息 */
printf( "\nPress Any Key To Continue......." );
_getch();
}


void DisData()
{
int i, j;
ofstream out;

out.open( "Process_Info.txt" );
if ( !out )
{
cout << "open file failed" << endl;
return;
}

for ( i = 0; i < ProcNumber; i++ )
{
printf( "ID=%4d %2d > ", proc[i].p_pid, proc[i].p_rserial[0] );
out << "ID=" << proc[i].p_pid << "(len=" << proc[i].p_rserial[0] << ",start=" << proc[i].p_starttime << "):";
for ( j = 1; j <= proc[i].p_rserial[0]; j++ )
{
printf( "%4d", proc[i].p_rserial[j] );
out << " " << proc[i].p_rserial[j];
}

printf( "\n" );
out << endl;
}
out.close();
}


void Display_ProcInfo( void ) /* 显示系统当前状态 */
{
int i, n, k;
system( "cls" );
printf( " 时间片为%d", q );
printf( "\n 当前系统模拟%2d 个进程的运行 时钟:%ld\n\n", ProcNumber, ClockNumber );
printf( " 就绪指针=%d, 运行指针=%d, 阻塞指针=%d\n\n", ReadyPoint, RunPoint, WaitPoint );
if ( RunPoint != -1 )
{
printf( " 当前运行的进程 No.%5d ID : %d(%d,%d) 总CPU时间=%d, 剩余CPU时间=%d \n", RunPoint, proc[RunPoint].p_pid,
proc[RunPoint].p_rserial[0], proc[RunPoint].p_starttime, proc[RunPoint].p_rserial[proc[RunPoint].p_pos], proc[RunPoint].p_cputime );
}else
printf( " 当前运行的进程ID:No Process Is Running !\n" );
n = ReadyPoint;
printf( "\n=================== 就绪进程 ====================\n" );
while ( n != -1 ) /* 显示就绪进程信息 */
{
printf( " No.%d ID:%5d,%6d,%6d,%6d\n", n, proc[n].p_pid, proc[n].p_starttime, proc[n].p_rserial[proc[n].p_pos], proc[n].p_cputime );
n = proc[n].p_next;
}
n = WaitPoint;
printf( "\n=================== 阻塞进程 ====================\n" );
while ( n != -1 ) /* 显示阻塞进程信息 */
{
printf( " No.%d ID:%5d,%6d,%6d,%6d\n", n, proc[n].p_pid, proc[n].p_starttime, proc[n].p_rserial[proc[n].p_pos], proc[n].p_iotime );
n = proc[n].p_next;
}
printf( "\n=================== 后备进程 ====================\n" );
for ( i = 0; i < ProcNumber; i++ )
if ( proc[i].p_state == 'B' )
{
printf( " No.%d ID:%5d,%6d\n", i, proc[i].p_pid, proc[i].p_starttime );
printf( " serial:" );
for ( k = 1; k <= proc[i].p_rserial[0]; k++ )
{
printf( " %4d", proc[i].p_rserial[k] );
}
printf( "\n" );
}
printf( "\n================ 已经完成的进程 =================\n" );
for ( i = 0; i < ProcNumber; i++ )
if ( proc[i].p_state == 'F' )
{
printf( " 已完成的进程\tNo.%d ID:%5d(%d,%d)\t完成时间=%d\t周转时间= %d\t加权周转时间= %f", i, proc[i].p_pid, proc[i].p_rserial[0], proc[i].p_starttime, proc[i].p_endtime, proc[i].p_endtime - proc[i].p_starttime,
(proc[i].p_endtime - proc[i].p_starttime) * 1.0 / (proc[i].p_endtime - proc[i].p_startruntime) );
printf( "\tserial:" );
for ( k = 1; k <= proc[i].p_rserial[0]; k++ )
{
printf( " %4d", proc[i].p_rserial[k] );
}
printf( "\n" );
}
}


void NextRunProcess( void )
{
if ( ReadyPoint == -1 )
{
RunPoint = -1; return;
} /* 就绪队列也没有等待的进程 */

proc[ReadyPoint].p_state = 'C'; /* ReadyPoint所指示的进程状态变为执行状态 */
RunPoint = ReadyPoint;
if ( proc[ReadyPoint].p_excutetime == -1 ) /* 进程为执行成功,接着上次的cpu时间执行 */
{
proc[ReadyPoint].p_excutetime = 0;
}else
proc[ReadyPoint].p_cputime = proc[ReadyPoint].p_rserial[proc[ReadyPoint].p_pos];
ReadyPoint = proc[ReadyPoint].p_next;
proc[RunPoint].p_next = -1;
}


void Cpu_Sched( void )
{
int n;


if ( RunPoint == -1 ) /* 没有进程在CPU上执行 */
{
NextRunProcess(); return;
}

if ( !proc[RunPoint].p_startruntime )
proc[RunPoint].p_startruntime = ClockNumber; /* 当程序的第一次运行开始时间为零时,证明他是第一次运行 ,记录该时刻 */

proc[RunPoint].p_cputime--; /* 进程CPU执行时间减少1个时钟单位 */
proc[RunPoint].p_excutetime++;
if ( (proc[RunPoint].p_cputime == 0 && proc[RunPoint].p_excutetime <= q) ) /* 若时间片未完,但进程已经结束 */
{
/* printf("若时间片未完,但进程已经结束\n"); */
proc[RunPoint].p_excutetime = 0; /* 清空运行时间 */
/* 进程完成本次CPU后的处理 */
if ( proc[RunPoint].p_rserial[0] == proc[RunPoint].p_pos ) /* 进程全部序列执行完成 */
{
FinishedProc++;
proc[RunPoint].p_state = 'F';
proc[RunPoint].p_endtime = ClockNumber;
RunPoint = -1; /* 无进程执行 */
NextRunProcess();
}else { /* 进行IO操作,进入阻塞队列 */
proc[RunPoint].p_pos++;
proc[RunPoint].p_state = 'W';
proc[RunPoint].p_iotime = proc[RunPoint].p_rserial[proc[RunPoint].p_pos];
printf( "进入阻塞队列\n" );
n = WaitPoint;
if ( n == -1 ) /* 是阻塞队列第一个I/O进程 */
WaitPoint = RunPoint;
else{ do /* 放入阻塞队列第尾 */
{
if ( proc[n].p_next == -1 )
{
proc[n].p_next = RunPoint;
break;
}
n = proc[n].p_next;
}
while ( n != -1 ); }
RunPoint = -1;
NextRunProcess();
}
return;
}
if ( proc[RunPoint].p_cputime > 0 && proc[RunPoint].p_excutetime < q ) /* 时间片未完 程序未执行结束 继续执行 */
{
/* printf("时间片未完 程序未执行结束 继续执行\n"); */
return;
}
/* { printf("\n RunPoint=%d,ctime=%d",RunPoint,proc[RunPoint].p_cputime);getchar();return; } */
if ( proc[RunPoint].p_cputime > 0 && proc[RunPoint].p_excutetime == q ) /* 时间片完,但是程序未执行完 放到就绪队列尾部 */
{
/* printf("时间片完,但是程序未执行完 放到就绪队列尾部\n"); */
int n;
proc[RunPoint].p_state = 'R'; /* 进程状态修改为就绪 */
proc[RunPoint].p_next = -1;
proc[RunPoint].p_excutetime = -1; /* 清空运行时间,-1代表程序未执行完成 */
if ( ReadyPoint == -1 ) /* 就绪队列无进程 */
ReadyPoint = RunPoint;
else{ /* 就绪队列有进程,放入队列尾 */
n = ReadyPoint;
while ( proc[n].p_next != -1 )
n = proc[n].p_next;
proc[n].p_next = RunPoint;
}
RunPoint = -1;
NextRunProcess(); /* 执行下一个进程 */
}
}


void IO_Sched() /* I/O调度 */
{
int n, bk;

if ( WaitPoint == -1 )
return; /* 没有等待 I/O 的进程,直接返回 */
proc[WaitPoint].p_iotime--; /* 进行 1 个时钟的 I/O 时间 */
if ( proc[WaitPoint].p_iotime > 0 )
return; /* 还没有完成本次 I/O */
/* 进程的 I/O 完成处理 */
if ( proc[WaitPoint].p_rserial[0] == proc[WaitPoint].p_pos ) /* 进程全部任务执行完成 */
{
FinishedProc++;
proc[WaitPoint].p_endtime = ClockNumber;
proc[WaitPoint].p_state = 'F';

if ( proc[WaitPoint].p_next == -1 )
{
WaitPoint = -1;
return;
}else { /* 调度下一个进程进行 I/O 操作 */
n = proc[WaitPoint].p_next;
proc[WaitPoint].p_next = -1;
WaitPoint = n;
proc[WaitPoint].p_iotime = proc[WaitPoint].p_rserial[proc[WaitPoint].p_pos];
return;
}
}else { /* 进行下次 CPU 操作,进就绪队列 */
bk = WaitPoint;
WaitPoint = proc[WaitPoint].p_next;
proc[bk].p_pos++;
proc[bk].p_state = 'R'; /* 进程状态为就绪 */
proc[bk].p_next = -1;

n = ReadyPoint;
if ( n == -1 ) /* 是就绪队列的第一个进程 */
{
ReadyPoint = bk;
return;
}else {
do
{
if ( proc[n].p_next == -1 )
{
proc[n].p_next = bk;
break;
}
n = proc[n].p_next;
}
while ( n != -1 );
}
}
return;
}


void NewReadyProc( void ) /* 检查是否有新进程到达,有则放入就绪队列 */
{
int i, n;

for ( i = 0; i < ProcNumber; i++ )
{
if ( proc[i].p_starttime == ClockNumber ) /* 进程进入时间达到系统时间 */
{
proc[i].p_state = 'R'; /* 进程状态修改为就绪 */
proc[i].p_next = -1;

if ( ReadyPoint == -1 ) /* 就绪队列无进程 */
ReadyPoint = i;
else{ /* 就绪队列有进程,放入队列尾 */
n = ReadyPoint;
while ( proc[n].p_next != -1 )
n = proc[n].p_next; /* 找到原来队伍中的尾巴 */
proc[n].p_next = i; /* 挂在这个尾巴后面 */
}
}
}
}


void Scheduler_FF() /* 调度模拟算法 */
{
if ( ProcNumber == 0 ) /* 该值居然是0? 只能说用户没创建进程 */
{
Read_Process_Info(); /* 那么,从磁盘读取上次创建的进程信息,赋值给相应变量 */
}

ClockNumber = 0; /* 时钟开始计时, 开始调度模拟 */
while ( FinishedProc < ProcNumber ) /* 执行算法 */
{
ClockNumber++; /* 时钟前进1个单位 */
NewReadyProc(); /* 判别新进程是否到达 */
Cpu_Sched(); /* CPU调度 */
IO_Sched(); /* IO调度 */
Display_ProcInfo(); /* 显示当前状态 */
Sleep( 100 );
}
Display_ProcInfo();
getch();
}


void Read_Process_Info()
{
ifstream inFile; /* 定义打开文件的文件流 */
char ch;
int i, j, k, tmp;
inFile.open( "Process_Info.txt" ); /* 打开上次写的txt进行信息文件流 */
i = 0;
while ( inFile )
{
inFile.get( ch );
for ( j = 0; j < 3; j++ )
inFile.get( ch ); /* 扔掉3个字符, */
inFile >> proc[i].p_pid;
for ( j = 0; j < 5; j++ )
inFile.get( ch ); /* 继续读,扔掉5个字符 */
inFile >> proc[i].p_rserial[0];
for ( j = 0; j < 7; j++ )
inFile.get( ch ); /* 继续读,扔掉7个字符 */
inFile >> proc[i].p_starttime;
for ( j = 0; j < 2; j++ )
inFile.get( ch ); /* 继续读,扔掉2个字符 */
for ( k = 1; k <= proc[i].p_rserial[0]; k++ )
{
inFile >> tmp;
proc[i].p_rserial[k] = tmp;
}
proc[i].p_state = 'B';
proc[i].p_pos = 1;
proc[i].p_endtime = 0;
proc[i].p_excutetime = 0;
proc[i].p_startruntime = 0;
proc[i].p_next = -1;
proc[i].p_cputime = proc[i].p_rserial[1];
proc[i].p_iotime = proc[i].p_rserial[2];
i++; /* 本行结束,一个进程信息读完,序号+1, 准备 next process */
}
ProcNumber = i - 1; /* 给ProcNumber赋值,i最后有++,回位下 */
inFile.close(); /* 完工后,记得归位,关灯。 */
}


int main( int argc, char* argv[] ) /*主函数 */
{
char ch;

RunPoint = -1; /* 运行进程指针,-1时为没有运行进程 */
WaitPoint = -1; /* 阻塞队列指针,-1时为没有阻塞进程 */
ReadyPoint = -1; /* 就绪队列指针,-1时为没有就绪进程 */
ClockNumber = 0; /* 系统时钟 */
ProcNumber = 0; /* 当前系统中的进程总数 */

system( "cls" );
while ( true )
{
printf( "***********************************\n" );
printf( " 1: 建立进程调度数据序列 \n" );
printf( " 2: 读进程信息,执行调度算法\n" );
printf( "***********************************\n" );
printf( "Enter your choice (1 ~ 2): " );

do
{
ch = (char) _getch(); /* 如果输入信息不正确,继续输入 */
}
while ( ch != '1' && ch != '2' );

if ( ch == '2' )
Scheduler_FF(); /* 选择2 */
else if ( ch == '1' )
Create_ProcInfo(); /* 选择1 */

_getch();
system( "cls" );
}
/* 结束 */
printf( "\nPress Any Key To Continue:" );
_getch();
return(0);
}
运行结果

image.png

PS.还有些常见流程图也贴上来8

进程调度分析流程图

CPU调度函数流程图

image.png

IO调度函数流程图

image.png

进程随机创建流程图
image.png
进程调度流程图
image.png
判断新进程到达函数流程图
image.png