xswlhhh的黄金屋
0%

操作系统实验四——多级反馈队列调度算法

发表于 分类于 6.8k 6 分钟

操作系统实验四——多级反馈队列调度算法

实验要求

多级反馈队列**(****Multi-leveled feedback queue)**调度算法

按以下要求实现多级反馈队列调度算法：假设有5个就绪队列，它们的优先级分别为1，2，3，4，5，它们的时间片长度分别为10ms,20ms,40ms,80ms,160ms，即第i个队列的优先级比第i-1个队列要低一级，但是时间片比第i-1个队列的要长一倍。调度算法包括四个部分：主程序main，进程产生器generator，进程调度器函数scheduler，进程运行器函数executor。

（1） 主程序：设置好多级队列以及它们的优先级、时间片等信息；创建两个信号量，一个用于generator和executor互斥的访问第1个运行队列(因为产生的新进程都是先放到第1个队列等待执行)，另一个用于generator和scheduler的同步(即，仅当多级队列中还有进程等待运行时，scheduler才能开始执行调度)。创建进程产生器线程，然后调用进程调度器。

（2） 进程产生器generator****：用线程来实现进程产生器。每隔一个随机的时间段，例如[1,100]ms之间的一个随机数，就产生一个新的进程，创建PCB并填上所有的信息。注意，每个进程所需要运行的时间neededTime在一定范围内(假设为[2,200]ms)内由随机数产生，初始优先级为1。PCB创建完毕后，将其插入到第1个队列进程链表的尾部（要用到互斥信号量，因为executor有可能正好从第1个队列中取出排在队列首的进程来运行）。插入完毕后，generator调用Sleep函数卡睡眠等待随机的一个时间间隔(例如在[1，100**]范围产生的1个随机数****)**，然后再进入下一轮新进程的产生。当创建的进程数量达到预先设定的个数，例如20个，generator就执行完毕退出。

（3） 进程调度器函数scheduler：在该函数中，依次从第1个队列一直探测到第5个队列，如果第1个队列不为空，则调用执行器executor来执行排在该队列首部的进程。仅当第i号队列为空时，才去调度第i+1个队列的进程。如果时间片用完了但是执行的进程还没有完成（即usedTime<neededTime），则调度器把该进程移动到下一级队列的尾部。当所有的进程都执行完毕，调度器退出，返回主程序。

（4） 进程执行器executor：根据scheduler传递的队列序号，将该队列进程链表首部的PCB取出，分配该队列对应的时间片给它运行(我们用Sleep函数，睡眠时间长度为该时间片，以模拟该进程得到CPU后的运行期间)。睡眠结束后，所有队列中的进程的等待时间都要加上该时间片。注意，在访问第1个队列时，要使用互斥信号量，以免跟进程产生器generator发生访问冲突。

实现思路：

假设五个就绪队列，它们的优先级为12345，其实数组索引就决定了优先级的顺序。这里考虑创建一个队列数组，然后根据索引，算出对应的时间即可。

队列用C++STL中的deque实现，这个数据结构有队列的性质，同时也具备遍历的功能，十分强大。

调度算法包含四个部分：main、进程产生器generator、进程调度器scheduler、进程运行器executor。main函数主要是信号量的设置和相关结构体的初始化，这里信号量设计mutex作为generator和executor第一个运行队列的互斥访问信号量；tongbu设置为generator和scheduler先后顺序的信号量；再来一个信号量mutex_sche进行对scheduler线程间操作临界资源的保护。其他基本上按照题目一一对应。

另外，信号量、线程和调度队列存储在一个结构体内，方便传参与管理

1
2
3
4
5
6
7
8
struct SIG {
	PRO* process[PROC_MAX_COUNT];
	HANDLE mutex;			//generator和executor互斥的访问第1个运行队列(
	HANDLE tongbu;			//用于generator和scheduler的同步
	deque<PRO*> que[5];//10ms 20 40 80 160 //队列+数组
	unsigned cap;			//时间片
	unsigned ProcCount;		//用于已有进程计数
};

遇到问题：

  1. 我们这里创建了两个函数的线程，这样才能实现产生进程和调度进程并行的效果。但是要注意，等待所有线程执行完毕的线程数组，要接收的是调度器的返回值。不然只是产生玩进程直接返回并不是我们先要的效果

img

  1. for循环内（短时间一秒钟内）随机数相同的问题，这里用了srand(time(NULL))初始化种子，但是time函数的单位是秒。我们解决方法要么用sleep函数睡眠将近一秒钟的时间，要么用clock()函数，其单位是毫秒。这里采用clock，同时不影响速率。
  2. 调度时只采用了一层循环。这样并不能满足我们需要调度进程的流程，我们进程调度的流程是，按照优先级顺序判断是否有进程就绪，有则从队列头部取出进程，然后执行，执行完毕则删除头部的进程，否则移动至下一优先级进程，然后继续判断有无进程; 如果无则去往下一优先级的队列。

实验代码：

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
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <windows.h>

#include <deque>
#include <math.h>
#include <string>
#include <time.h>
using namespace std;

//产生最大进程数
#define PROC_MAX_COUNT 20
#define BIGBIGBIG 9999
//PCB
struct	PRO {
	unsigned int pid;
	unsigned int start_time;//开始时间
	unsigned int need_time;	//需要的时间
	unsigned int run_time;	//已经运行的时间
	unsigned int end_time;	//完成时间
	unsigned int wait_time;		//等待的时间
	//HANDLE proc;
};


struct SIG {
	PRO* process[PROC_MAX_COUNT];
	HANDLE mutex;			//generator和executor互斥的访问第1个运行队列(
	HANDLE tongbu;			//用于generator和scheduler的同步
	deque<PRO*> que[5];//10ms 20 40 80 160 //队列+数组
	unsigned cap;			//时间片
	unsigned ProcCount;		//用于已有进程计数
};
//统计进程数量
int ProCessCount = 0;
HANDLE mutex_sche;
/*
进程产生器，产生进程，有互斥量
需要传入信号量，队列等信息，线程实现（传递参数用的结构体）
*/
void generator(SIG* sig);
//进程调度函数
void scheduler(SIG* sig);
//进程执行器
void executor(SIG* sig, int quenum);

int main()
{
	//优先级由队列组成的数组循环索引idx来自然实现，时间片同理。
	SIG sig;//信号量等信息
	sig.mutex = CreateMutex(NULL, 0, L"mutex");
	mutex_sche = CreateMutex(NULL, 0, L"Smutex_sche");
	sig.tongbu = CreateSemaphore(NULL,0,100, L"tongbu");
	sig.cap = 0;
	sig.ProcCount = 0;
	HANDLE ThreadArray[PROC_MAX_COUNT];
	
	//创建进程产生器线程，然后调用进程调度器
	for (int i = 0; i < PROC_MAX_COUNT; i++)
	{
		CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)generator, &sig, 0, NULL);
		ThreadArray[ProCessCount] = CreateThread(NULL, 0, (LPTHREAD_START_ROUTINE)scheduler, &sig, 0, NULL);

		ProCessCount++;
	}
	WaitForMultipleObjects(PROC_MAX_COUNT, ThreadArray, true, INFINITE);//一直等待，直到子进程全部返回

	return 0;
}

void generator(SIG* sig)
{
	
	//20
	
	WaitForSingleObject(sig->mutex, INFINITE);//与executor互斥
	if (sig->ProcCount >= 20)
	{
		return;
	}
	//每隔一个随机时段，产生一个新进程
	srand(clock());
	Sleep((rand() % 99));
	sig->process[sig->ProcCount] = (PRO *)malloc(sizeof(struct PRO));

	// 填补PCB上面的信息
	sig->process[sig->ProcCount]->pid = sig->ProcCount;
	sig->process[sig->ProcCount]->need_time= rand() % 198 + 2;
	sig->process[sig->ProcCount]->start_time = sig->cap;
	sig->process[sig->ProcCount]->run_time = 0;
	sig->process[sig->ProcCount]->end_time = BIGBIGBIG;
	sig->process[sig->ProcCount]->wait_time = 0;
	printf("线程%d产生,需要运行的时间:%d，开始时间:%d\n", sig->process[sig->ProcCount]->pid, sig->process[sig->ProcCount]->need_time, sig->process[sig->ProcCount]->start_time, sig->process[sig->ProcCount]->start_time);

	//插入队列
	
	sig->que[0].push_back(sig->process[sig->ProcCount]);//入队队列指针
	sig->ProcCount++;
	ReleaseMutex(sig->mutex);//释放互斥信号量

	//插入完毕，调用Sleep
	ReleaseSemaphore(sig->tongbu,1,NULL);//释放同步信号量
	
	unsigned sleep_time = rand() % 99 + 1;
	Sleep(sleep_time);

}

void executor(SIG* sig,int quenum)
{
	//根据schedule传递的队列序号,取出pcb，然后分配该队列的时间片给它运行
	//sleep
	
	WaitForSingleObject(sig->mutex, INFINITE);//与generator互斥

	unsigned tim = pow(2, (quenum + 1));//睡眠的时间
	unsigned timcap = tim * 10;
	PRO* temp;
	//printf("size: %d\n", sig->que[quenum].size());
	temp = sig->que[quenum].front();//取出队列中的元素但是不删除
	
	//睡眠结束后，所有队列中的进程的等待时间加上时间片
	Sleep(timcap);
	temp->run_time += timcap;
	//printf("进程已运行%dms,进程需要运行的时间%d\n", temp->run_time,temp->need_time);
	sig->cap += timcap;
	printf("队列情况\n");
	for (int i = 0;i<5; i++) {
		printf("队列%d:", i);
		for (int j = 0; j<sig->que[i].size(); j++) {
			
			sig->que[i][j]->wait_time += timcap;//通过下标访问deque
			if (j != 0)
				printf("<-");
			printf("%d", sig->que[i][j]->pid);
		}
		puts("");
	}
	temp->wait_time -= timcap;
	ReleaseMutex(sig->mutex);//释放同步信号量
	
	return;
}


void scheduler(SIG* sig)
{
	WaitForSingleObject(sig->tongbu, INFINITE);
	WaitForSingleObject(mutex_sche, INFINITE);//与generator互斥
	for (int i = 0; i < 5; i++){
		for (int j = 0; j < sig->que[i].size(); j++) {
			//队列不为空则调用执行器
			//printf("正在调度%d队列中的进程\n", i);
			executor(sig, i);
			//时间片用完了，进程没执行完。调度器移动到下一级
			//如果需要的时间依旧大于运行的时间，则移动到下一级队列尾部
			if (sig->que[i].front()->need_time> sig->que[i].front()->run_time) {
				if (i <= 4) {
					sig->que[i + 1].push_back(sig->que[i].front());
					sig->que[i].pop_front();//移动
				}
			}
			else
			{
				printf("进程%d运行结束，结束时间:%d\n", sig->que[i].front()->pid, sig->cap);
				sig->que[i].front()->end_time = sig->cap;
				sig->que[i].pop_front();
			}
		}
	}
	ReleaseMutex(mutex_sche);
	return;
	
}

运行结果

img