分为三级反馈队列
每次只从第一级队列里取出进程。
每执行三次一级队列的进程发生一次队列调整。

三次执行:前两次遵从最短优先调度,最后一次随机取进程,
为的是让调整上来的进程可以有机会执行

调整:从二级队列和三级队列分别随机取两个和一个进程
放入一级队列里面参与竞争。

直到一级队列空则所有的进程执行完毕

加了一个线程专门产生进程

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
/**
* title :C++模拟进程调度---多线程加入信号量控制临界区
* author : liyunhao
* date:2018.04.24
* time : 21:10
*/
/*
调度的思想,分为三级反馈队列。
每次只从第一级队列里取出进程。

每执行三次一级队列的进程发生一次队列调整。

三次执行:前两次遵从最短优先调度,最后一次随机取进程,
为的是让调整上来的进程可以有机会执行

调整:从二级队列和三级队列分别随机取两个和一个进程
放入一级队列里面参与竞争。

直到一级队列空则所有的进程执行完毕

加了一个线程专门产生进程
*/

#include<iostream>
#include<list>
#include <time.h>
#include <stdlib.h>
#include <windows.h>
using namespace std;
int mutex = 0;
class tool{//工具类
public:
int timeInterval;
tool(){
srand((unsigned)time( NULL ));//设置随机数
timeInterval = 10;//进程执行的单位间隔
}

int getRandom(int a,int b){//返回指定范围的随机数
int range = b - a;
if(range==0){
return 0;
}else{
return a + rand()%range;
}

}

};

class process{//进程类
public:
int pid; //进程编号
int length;
int level;
process(int pid,int lengthOfProcess ){
length = lengthOfProcess;
if(length <= 0){
cout<<"进程创建失败!"<<endl;
}else if(length <= 10){
level = 1;
this->pid = pid;
cout<<"进程"<<pid<<"创建,长度"<<length <<endl;
}else if(length <= 20){
level = 2;
this->pid = pid;
cout<<"进程"<<pid<<"创建,长度"<<length <<endl;
}else{
level = 3;
this->pid = pid;
cout<<"进程"<<pid<<"创建,长度"<<length <<endl;
}
}
bool ajustLevel(){//调整进程的优先级
if(length <= 0){
cout<<"进程运行完毕!"<<endl;
return false;
}else if(length <= 10){
level = 1;
return true;
}else if(length <= 20){
level = 2;
return true;
}else{
level = 3;
return true;
}
}
bool doTheProcess(int timeLength){
if(length <=0 ){
cout<<"进程已经运行完毕!"<<endl;
return false;
}else{
length -= timeLength;
ajustLevel();
if(length < 0){
length = 0;
return true;
}else{
return true;
}
}

}
bool finishThePro(){
cout<<"进程"<<pid<<"执行完毕"<<endl;
}

};

class processQueue{
public:
int level; //队列的优先级
list<process* > List[3];//三个不同优先级的队列
processQueue(){
;
}

bool processIncoming(process*pro){
int level = pro->level;
int pid = pro->pid;
if(level ==1){
List[0].push_back(pro);
cout<<"进程"<<pid<<"加入队列"<<level<<endl;
return true;
}else if(level ==2){
List[1].push_back(pro);
cout<<"进程"<<pid<<"加入队列"<<level<<endl;
return true;
}else if(level ==3){
List[2].push_back(pro);
cout<<"进程"<<pid<<"加入队列"<<level<<endl;
return true;
}else{
cout<<"未知的优先级!"<<endl;
return false;
}
}

//从指定队列里面找一个进程,并从原来的队列删除该进程
process* findProFromList(int listNum){
listNum--;
list<process*>::iterator itor;
list<process*>::iterator delNode;
int currentMin = 9999;
process* shortestPro;
if(List[listNum].size() == 0){
//cout<<"队列"<<listNum+1<<"的进程已经执行完毕,获取失败"<<endl;
return NULL;
}else{
//cout<<"元素个数"<<List1.size()<<endl;// 返回list中的元素个数
for(itor = List[listNum].begin();itor!=List[listNum].end();itor ++){
if((*itor)->length < currentMin){
currentMin = (*itor)->length;
shortestPro = (*itor);
delNode = itor;
}
}
List[listNum].erase(delNode);//从进程队列中删除该进程
return shortestPro;
}

}


process* findProFromListByRandom(int listNum){
listNum--;
list<process*>::iterator itor;
int currentMin = 9999;
process* shortestPro;
tool atool;

if(List[listNum].size() == 0){
//cout<<"队列"<<listNum+1<<"的进程已经执行完毕,获取失败"<<endl;
return NULL;
}else{
itor = List[listNum].begin();
int queLen = List[listNum].size();
//cout<<"queLen :"<<queLen<<endl;
int randomNum = atool.getRandom(0,queLen-1);
//cout<<"randomNum :"<<randomNum<<endl;
//cout<<"随机选取进程"<<randomNum<<endl;
advance(itor,randomNum);
shortestPro = (*itor);
List[listNum].erase(itor);//从进程队列中删除该进程
//printQue(1);
return shortestPro;
}


}
process* selectFromList1AndDoIt(){

process* shortestPro;
shortestPro = findProFromList(1);
if(shortestPro!= NULL){
shortestPro->finishThePro();
//ajustLevelQueues();
return shortestPro;
}else{
return NULL;
}

}
process* selectList1ByRondomAndDoIt(){

process* RondomPro;
RondomPro = findProFromListByRandom(1);
if(RondomPro!= NULL){
RondomPro->finishThePro();
//ajustLevelQueues();
return RondomPro;
}else{
return NULL;
}

}
bool ajustLevelQueues(){
cout<<"调整"<<endl;
Sleep(500);
process* p[3];
p[0] = findProFromListByRandom(2);//从第二级队列随机获取进程
p[1] = findProFromListByRandom(2);//从第二级队列随机获取进程
p[2] = findProFromListByRandom(3);//从第三级队列随机获取进程
//process* p3 = findProFromList(3);//从第三极队列中获取最短时间进程
if( (p[0]==NULL) &&(p[1]==NULL) && (p[2]== NULL)){

//cout<<"2,3队列已经空了,调整失败"<<endl;
return false;
}else if((p[0]==NULL) && (p[2]!= NULL)){
p[0] = findProFromListByRandom(3);//从第二级队列获取最短时间进程
p[1] = findProFromListByRandom(3);//从第三级队列获取最短时间进程
}else if((p[0]!=NULL) &&(p[1]==NULL) && (p[2]!= NULL)){
p[1] = findProFromListByRandom(3);//从第二级队列获取最短时间进程
}else if((p[0]!=NULL) &&(p[1]!=NULL) && (p[2]== NULL)){
p[2] = findProFromListByRandom(2);//从第二级队列获取最短时间进程
}


if(p[0]){
p[0]->level = 1;
cout<<"调整"<<p[0]->pid<<endl;
List[0].push_back(p[0]);//放入第一级队列
}
if(p[1]){
p[1]->level = 1;
cout<<"调整"<<p[1]->pid<<endl;
List[0].push_back(p[1]);//放入第一级队列
}
if(p[2]){
p[2]->level = 1;
cout<<"调整"<<p[2]->pid<<endl;
List[0].push_back(p[2]);//放入第一级队列
}
return true;
}
void printQue(int listNum){
listNum--;
list<process*>::iterator itor;
for(itor = List[listNum].begin();itor!=List[listNum].end();itor ++){

cout<<(*itor)->pid<<" ";
}
cout<<endl;
}

};
class GanttChart{//输出甘特图的类
public:
string GamtString;
int proNum;
GanttChart(){
GamtString += "|";
proNum = 0;

}
bool add(process *p){
//for(int i=0 ;i<p->length;i++){
char temp[10];
itoa(p->pid,temp,10);
GamtString += temp;
//}
GamtString += "|";
proNum ++;
if(proNum!=0 && proNum % 25 ==0){
GamtString ="";//每隔25个清空一次甘特图
}
}
void print(){
cout<<" 该进程调度的甘特图:"<<endl;
cout<<"____________________________________________________________________"<<endl;
cout<<GamtString<<endl;
cout<<" ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄"<<endl;
}

};
//主函数与线程的共享变量
int currPro;
tool tool1;
processQueue proqueue;
process *pro ;
process *proPrint;
GanttChart gant;
int timeInterval;

class index{
public:


index(){
currPro = 0;

timeInterval = tool1.timeInterval;
}

void IndexGo(){
int proCountForPrint = 0;
while(1){
while(mutex==1);
mutex=1;//加锁保护临界区
cout<<"在主函数里面"<<endl;
for(int i=0;i<3;i++){
if(proqueue.List[0].size()>0){
proPrint=proqueue.selectFromList1AndDoIt();
Sleep(proPrint->length * timeInterval);
gant.add(proPrint);
proCountForPrint++;
}
}

proqueue.ajustLevelQueues();
if(proCountForPrint!=0 && proCountForPrint % 24==0){
gant.print();
}

mutex=0;//解锁
Sleep(1000);//便于观察
}


}
};


DWORD WINAPI ThreadProc(LPVOID lpParameter)
{


while(1){
while(mutex==1);
mutex = 1; //加锁保护临界区
cout<<"在线程里面"<<endl;
int RandomPronum = tool1.getRandom(1,5);
for(int i = 0;i < RandomPronum;i++){//随机生成不同(1-5个)的进程
int Len = tool1.getRandom(1,50);
pro = new process(currPro,Len);
proqueue.processIncoming(pro);
currPro++;
}

mutex = 0;//解锁
Sleep(1000);//便于观察

}

return 0;
}
int main(){
cout<<"模拟进程调度---基于多级队列"<<endl;
index inde;
HANDLE hThread1 = CreateThread(NULL, 0, ThreadProc, NULL, 0, NULL);
inde.IndexGo();


return 0;
}