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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
char name[20]; //进程的名字
int prio; //进程的优先级
int round; //分配CPU的时间片
int cputime; //CPU执行时间
int needtime; //进程执行所需要的时间
char state; //进程的状态,W——就绪态,R——执行态,F——完成态
int count; //记录执行的次数
struct node *next; //链表指针
}PCB;
PCB *ready=NULL,*run=NULL,*finish=NULL; //定义三个队列,就绪队列,执行队列和完成队列
int num;
void GetFirst(); //从就绪队列取得第一个节点
void Output(); //输出队列信息
void InsertPrio(PCB *in); //创建优先级队列,规定优先数越小,优先级越高
void InsertTime(PCB *in); //时间片队列
void InsertFinish(PCB *in); //时间片队列
void PrioCreate(); //优先级输入函数
void TimeCreate(); //时间片输入函数
void Priority(); //按照优先级调度
void RoundRun(); //时间片轮转调度
int main(void)
{
char chose;
printf("请输入要创建的进程数目:\n");
scanf("%d",&num);
getchar();
printf("输入进程的调度方法:(P/R)\n");
scanf("%c",&chose);
switch(chose)
{
case 'P':
case 'p':
PrioCreate();
Priority();
break;
case 'R':
case 'r':
TimeCreate();
RoundRun();
break;
default:break;
}
Output();
return 0;
}
void GetFirst() //取得第一个就绪队列节点
{
run = ready;
if(ready!=NULL)
{
run ->state = 'R';
ready = ready ->next;
run ->next = NULL;
}
}
void Output() //输出队列信息
{
PCB *p;
p = ready;
printf("进程名\t优先级\t轮数\tCPU时间\t需要时间\t进程状态\t计数器\n");
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t\t%c\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
p = finish;
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t%c\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
p = run;
while(p!=NULL)
{
printf("%s\t%d\t%d\t%d\t%d\t%c\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);
p = p->next;
}
}
void InsertPrio(PCB *in) //创建优先级队列,规定优先数越小,优先级越低
{
PCB *fst,*nxt;
fst = nxt = ready;
if(ready == NULL) //如果队列为空,则为第一个元素
{
in->next = ready;
ready = in;
}
else //查到合适的位置进行插入
{
if(in ->prio >= fst ->prio) //比第一个还要大,则插入到队头
{
in->next = ready;
ready = in;
}
else
{
while(fst->next != NULL) //移动指针查找第一个别它小的元素的位置进行插入
{
nxt = fst;
fst = fst->next;
}
if(fst ->next == NULL) //已经搜索到队尾,则其优先级数最小,将其插入到队尾即可
{
in ->next = fst ->next;
fst ->next = in;
}
else //插入到队列中
{
nxt = in;
in ->next = fst;
}
}
}
}
void InsertTime(PCB *in) //将进程插入到就绪队列尾部
{
PCB *fst;
fst = ready;
if(ready == NULL)
{
in->next = ready;
ready = in;
}
else
{
while(fst->next != NULL)
{
fst = fst->next;
}
in ->next = fst ->next;
fst ->next = in;
}
}
void InsertFinish(PCB *in) //将进程插入到完成队列尾部
{
PCB *fst;
fst = finish;
if(finish == NULL)
{
in->next = finish;
finish = in;
}
else
{
while(fst->next != NULL)
{
fst = fst->next;
}
in ->next = fst ->next;
fst ->next = in;
}
}
void PrioCreate() //优先级调度输入函数
{
PCB *tmp;
int i;
printf("输入进程名字和进程所需时间:\n");
for(i = 0;i < num; i++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc");
exit(1);
}
scanf("%s",tmp->name);
getchar(); //吸收回车符号
scanf("%d",&(tmp->needtime));
tmp ->cputime = 0;
tmp ->state ='W';
tmp ->prio = 50 - tmp->needtime; //设置其优先级,需要的时间越多,优先级越低
tmp ->round = 0;
tmp ->count = 0;
InsertPrio(tmp); //按照优先级从高到低,插入到就绪队列
}
}
void TimeCreate() //时间片输入函数
{
PCB *tmp;
int i;
printf("输入进程名字和进程时间片所需时间:\n");
for(i = 0;i < num; i++)
{
if((tmp = (PCB *)malloc(sizeof(PCB)))==NULL)
{
perror("malloc");
exit(1);
}
scanf("%s",tmp->name);
getchar();
scanf("%d",&(tmp->needtime));
tmp ->cputime = 0;
tmp ->state ='W';
tmp ->prio = 0;
tmp ->round = 2; //假设每个进程所分配的时间片是2
tmp ->count = 0;
InsertTime(tmp);
}
}
void Priority() //按照优先级调度,每次执行一个时间片
{
int flag = 1;
GetFirst();
while(run != NULL) //当就绪队列不为空时,则调度进程如执行队列执行
{
Output(); //输出每次调度过程中各个节点的状态
while(flag)
{
run->prio -= 3; //优先级减去三
run->cputime++; //CPU时间片加一
run->needtime--;//进程执行完成的剩余时间减一
if(run->needtime == 0)//如果进程执行完毕,将进程状态置为F,将其插入到完成队列
{
run ->state = 'F';
run->count++; //进程执行的次数加一
InsertFinish(run);
flag = 0;
}
else //将进程状态置为W,入就绪队列
{
run->state = 'W';
run->count++; //进程执行的次数加一
InsertTime(run);
flag = 0;
}
}
flag = 1;
GetFirst(); //继续取就绪队列队头进程进入执行队列
}
}
void RoundRun() //时间片轮转调度算法
{
int flag = 1;
GetFirst();
while(run != NULL)
{
Output();
while(flag)
{
run->count++;
run->cputime++;
run->needtime--;
if(run->needtime == 0) //进程执行完毕
{
run ->state = 'F';
InsertFinish(run);
flag = 0;
}
else if(run->count == run->round)//时间片用完
{
run->state = 'W';
run->count = 0; //计数器清零,为下次做准备
InsertTime(run);
flag = 0;
}
}
flag = 1;
GetFirst();
}
}

转载自 CSDN eaglewood2005