C++编程实现进程调度算法

实验二 进程调度算法的设计

实验题目

  1. 先来先服务（FCFS）调度算法

    • 原理：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。

    • 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。

    • 按照就绪进程进入就绪队列的先后次序进行调度，简单易实现，利于长进程，CPU繁忙型作业，不利于短进程，排队时间相对过长。

      image-20211111101042496

  2. 时间片轮转调度算法RR

    • 原理：时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度按一定时间片(q)轮番运行各个进程。
    • 进程按到达时间在就绪队列中排队，调度程序每次把CPU分配给就绪队列首进程使用一个时间片，运行完一个时间片释放CPU，排到就绪队列末尾参加下一轮调度，CPU分配给就绪队列的首进程。

    image-20211111182747792

    • 固定时间片轮转法：
      1. 所有就绪进程按 FCFS 规则排队。
      2. 处理机总是分配给就绪队列的队首进程。
      3. 如果运行的进程用完时间片，则系统就把该进程送回就绪队列的队尾，重新排队。
      4. 因等待某事件而阻塞的进程送到阻塞队列。
      5. 系统把被唤醒的进程送到就绪队列的队尾
    • 可变时间片轮转法：

      1. 进程状态的转换方法同固定时间片轮转法。

      2. 时间片的长短依据就绪队列进程数量的多少由T=N∗(q+t)T=N*(q+t)的关系调整（T为响应时间（固定），N为就绪队列进程数，q为时间片的长短，t为上下文切换时间。其中q为毫秒级及以上，上下文切换时间t为纳秒级而忽略不计）。即就绪队列进程数有变化时，时间片需要调整。

        image-20211112102915716

程序中使用的数据结构及符号说明

  • 结构体表示进程，结构体数组记录各个进程的信息：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    struct process
    {
    	int id; //编号
    	int pos; //排序后的位置
    	int arrive; //到达时间
    	int work; //区间时间
    	int begin; //开始时间
    	int end; //完成时间
    	int turnaround; //周转时间
    	int wait; //等待时间
    	bool in; //是否进入过就绪队列
    	bool finish; //是否完成
    	int rest; //剩余区间时间（RR）
    	int block_p; //最近一次被阻塞的时间点
    	int block_t; //阻塞时间长度（RR）
    } proc[N];

  • 使用数据结构queue（队列）:

    1
    2
    3
    queue <process> ready; //就绪队列
    queue <process> block; //阻塞队列（RR）
    queue <process> block_new; //(临时)新阻塞队列,用于阻塞队列的更新（RR）

  • 整型变量：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //全局变量
    int k, k_RR, n, q;
    /* 	k：算法类型（0:FCFS 1:RR）
    	k_RR：RR算法类型（0:时间片固定 1:可变）
    	n：进程数
    	q：时间片
    */
    int now = 0; //当前时间

    //FCFS_And_RR函数内部
    int left = n; //剩余的未完成进程数
    int once_max; //一个时间片内一个进程最大运行时间
    int once; //记录一个时间片内的运行时间
    int min_arrive = 0x3f3f3f; //未到达进程的最小到达时间（可能有多个进程）
    int in_flag = 0; //当前时间是否有进程入就绪队列

  • 函数：

    bool cmp_FCFS(process a, process b) ：FCFS规则排队的比较函数；

    bool cmp_id(process a, process b) ：按编号顺序的排序函数

    void init() :输入信息进行初始化的函数

    void block_check(): 查看阻塞队列中是否有进程被唤醒的函数

    void FCFS_And_RR():FCFS调度算法和RR调度算法的函数

    void display()：用于输出结果的函数

源程序及注释：

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
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
#define N 100001
//算法类型（0:FCFS 1:RR），RR算法类型（0:时间片固定 1:可变）,进程数，时间片
int k, k_RR, n, q;

int now = 0; //当前时间
struct process
{
	int id; //编号
	int pos; //排序后的位置
	int arrive; //到达时间
	int work; //区间时间
	int begin; //开始时间
	int end; //完成时间
	int turnaround; //周转时间
	int wait; //等待时间
	bool in; //是否进入过就绪队列
	bool finish; //是否完成
	int rest; //剩余区间时间
	int block_p; //最近一次被阻塞的时间点
	int block_t; //阻塞时间长度
} proc[N];
queue <process> ready; //就绪队列
queue <process> block; //阻塞队列（RR）
queue <process> block_new; //(临时)新阻塞队列,用于阻塞队列的更新（RR）

bool cmp_FCFS(process a, process b)
{
	if (a.arrive != b.arrive)
		return a.arrive < b.arrive;
	else
		return a.id < b.id;
}

bool cmp_id(process a, process b)
{
	return a.id < b.id;
}

void init()
{
	cout << "请输入算法类型（0:FCSS 1:RR）：";
	cin >> k;
	cout << "请输入进程个数：";
	cin >> n;
	if (k == 1)
	{
		cout << "请输入时间片大小：";
		cin >> q;
		cout << "请输入RR算法类型（0:时间片固定 1:时间片可变）:";
		cin >> k_RR;
	}
	cout << "请按进程到达先后输入进程信息（1~n）：到达时间 区间时间" <<
		endl; //要求按到达先后顺序输入，以便于到达时间相同时判断先后
	for (int i = 1; i <= n; i++)
	{
		cout << "进程" << i << ":";
		cin >> proc[i].arrive >> proc[i].work;
		//信息初始化
		proc[i].id = i;
		proc[i].in = 0;
		proc[i].begin = -1; //表示还没开始
		proc[i].finish = 0;
		proc[i].block_t = 0;
		proc[i].rest = proc[i].work;
	}
	sort(proc, proc + n + 1, cmp_FCFS);
	for (int i = 1; i <= n; i++)
	{
		proc[i].pos = i;
	}
}

void block_check() //查看阻塞队列中是否有进程被唤醒
{
	while (!block.empty()) //遍历旧阻塞队列一次
	{
		process t2 = block.front();
		block.pop();
		if (t2.block_p != now) //如果不是刚被阻塞，则有唤醒的可能
		{
			if (rand() % 2) //设定阻塞进程有1/2的概率被唤醒
			{
				t2.block_t += (now - t2.block_p); //更新阻塞时长
				cout << "在时刻" << now << "，进程" << t2.id << "被唤醒" << endl;
				ready.push(t2);
			}
			else //仍被阻塞，入新阻塞队列
			{
				block_new.push(t2);
			}
		}
		else //刚被阻塞，入新阻塞队列
		{
			block_new.push(t2);
		}
	}
	block = block_new; //阻塞队列更新
	while (!block_new.empty()) //清空临时的阻塞队列
	{
		block_new.pop();
	}
}

void FCFS_And_RR()
{
	srand((unsigned int)(time(0))); //随机数生成种子随系统时间变化
	int left = n; //剩余的未完成进程数
	int once_max; //一个进程最大连续运行时间
	int once; //记录一个进程一次的运行时间
	while (left > 0) //有进程没有完成
	{
		int min_arrive = 0x3f3f3f; //未到达进程的最小到达时间（可能有多个进程）
		int in_flag = 0; //当前时间是否有进程入就绪队列
		for (int i = 1; i <= n; i++)
		{
			if (!proc[i].in && proc[i].arrive < min_arrive)
			{
				min_arrive = proc[i].arrive;
				in_flag = 1;
			}
		}
		if (min_arrive >= now && in_flag)
		{
			//若当前时间小于剩余未完成进程（存在时in_flag=1）的最小到达时间，则输出以下信息并更新值
			if (min_arrive > now)
				cout << "在时间" << now << "-" << min_arrive << "内,没有进程在运行" << endl;
			now = min_arrive;
			for (int i = 1; i <= n; i++)
			{
				if (proc[i].arrive == min_arrive)
				{
					proc[i].in = 1;
					ready.push(proc[i]);
				}
			}
		}
		if (!ready.empty())
		{
			process t = ready.front(); //取出就绪队列队首
			ready.pop();
			if (t.begin == -1) //如果是第一次出就绪队列
			{
				t.begin = now; //开始时间=当前时间
			}
			if (k == 0) //FCFS
			{
				once_max = t.rest; //一个进程单次最大运行时间为剩余区间时间（即不发生阻塞的情况）
			}
			else //RR
			{
				once_max = min(q, t.rest);
				//一个进程单次最大运行时间为时间片长度和剩余区间时间的相比较的最小值
			}
			once = 0;
			while (once < once_max) //一个进程运行中
			{
				now++; //当前时间加1
				once++; //单次进程运行时间加1
				t.rest--; //剩余时间减1
				for (int i = 1; i <= n; i++) //遍历所有进程
				{
					if (!proc[i].in && proc[i].arrive == now) //若有进程还没有进入过就绪队列，且当前到达
					{
						proc[i].in = 1; //更改标记
						ready.push(proc[i]); //进入就绪队列
					}
				}
				block_check(); //查看阻塞队列中是否有进程被唤醒
				if (rand() % 10 == 0 && t.rest != 0)	//设定当前进程单位时间有1/10的概率发生阻塞
				{
					t.block_p = now; //更新最近一次被阻塞的时间点
					block.push(t); //阻塞，入阻塞队列队尾
					break;
				}
			}
			if (t.rest > 0) //剩余时间大于0
			{
				cout << "在时间" << now - once << "-" << now << "内,进程" << t.id << "在运行";
				if (t.block_p == now) //说明阻塞
				{
					cout << ",后阻塞";
				}
				else //没阻塞则入就绪队列
				{
					ready.push(t);
				}
				cout << endl;
			}
			else //剩余时间等于0，表示运行完成
			{
				cout << "在时间" << now - once << "-" << now << "内,进程" << t.id << "在运行。该进程完成。" << endl;
				t.end = now; //完成时间=当前时间
				t.finish = 1; //更新标记：已完成
				t.turnaround = t.end - t.arrive; //周转时间=完成时间-到达时间
				t.wait = t.turnaround - t.work - t.block_t; //等待时间=周转时间-区间时间-阻塞时间
				proc[t.pos] = t; //更新（已完成的）进程信息
				left--; //剩余进程数减1
				if (k == 1 && k_RR == 1) //时间片可变的RR算法
				{
					q = ((double)n / left) * q;
				}
			}
		}
		else //可能当就绪队列为空时，也有进程在阻塞队列
		{
			int in_block = 0; //停留在阻塞队列的时间
			while (1)
			{
				block_check();//查看阻塞队列中是否有进程被唤醒
				if (left == block.size() && left > 0) //如果未完成的进程都在阻塞队列里
				{
					in_block++; //更新停留在阻塞队列的时间，继续进行循环
					now++;
				}
				else
				{
					break; //否则只进行一次遍历，因为还有其他没有在阻塞队列的进程
				}
			}
			if (in_block > 0) //只剩阻塞队列中的进程，且没运行，输出信息
			{
				cout << "在时间" << now - in_block << "-" << now  << "内,没有进程在运行" << endl;
			}
		}
	}
}

//输出结果
void display()
{
	sort(proc, proc + n + 1, cmp_id);
	cout << "所有进程已完成，结果如下：" << endl;
	cout << setw(8) << "进程编号" << setw(10) << "到达时间" << setw(10) << "区间时间" << setw(10) << "开始时间" << setw(
		10) << "完成时间" << setw(10) << "周转时间" << setw(10) << "等待时间" << setw(10) << "阻塞时间";
	cout << endl;
	int sum_work = 0, sum_turnaround = 0, sum_wait = 0, sum_block = 0;
	//总区间（服务）时间，总周转时间，总等待时间，平均阻塞时间
	for (int i = 1; i <= n; i++)
	{
		sum_work += proc[i].work;
		sum_turnaround += proc[i].turnaround;
		sum_block += proc[i].block_t;
		sum_wait += proc[i].wait;
		cout << left << setw(10) << proc[i].id << setw(10) << proc[i].arrive << setw(10) << proc[i].work << setw(10) << proc[i].begin << setw(10) << proc[i].end << setw(10) << proc[i].turnaround << setw(10) << proc[i].wait << setw(10) << proc[i].block_t << endl;
	}
	cout << "平均周转时间：" << (double)sum_turnaround / n << endl;
	cout << "平均带权周转时间：" << (double)sum_turnaround / sum_work / n << endl;
	cout << "平均等待时间：" << (double)sum_wait / n << endl;
	cout << "平均阻塞时间：" << (double)sum_block / n << endl;
	return;
}

int main()
{
	init();
	FCFS_And_RR();
	display();
	return 0;
}

程序运行时的初值和运行结果

FCFS

初值

image-20211116174257026

结果

image-20211116173854064

RR-时间片固定

初值

image-20211116173837962

结果

image-20211116173854064

RR-可变时间片

初值

image-20211115234014542

结果

image-20211116173951387

思考题

  • 根据上面的观察结果，比较这两种算法各自的优缺点，根据结果再和其他的算法比较。

    • FCFS（先到先服务）调度算法优点：

      • 简单，容易理解。

    • FCFS（先到先服务）调度算法缺点：

      • 所有其他进程都等待一个大进程释放 CPU，与让较短进程先进行相比，这会导致 CPU 和设备的使用率降低。

      • FCFS 调度算法是非抢占的。一旦 CPU 分配给了一个进程，该进程就会使用 CPU 直到释放 CPU 为止，不适用于分时系统。

    • RR（轮转法）调度算法优点：

      • 适合分时系统，公平性较好。

    • RR（轮转法）调度算法缺点：

      • 紧迫任务响应较慢。
      • 时间片选取若太小，会频繁发生中断、进程上下文切换，增加系统开销，但利于短作业；若太大，退化成FCFS

实验心得

  • 这个程序是我三番五次精心打磨写成的。在最开始的时候，我先不考虑阻塞队列，分别完成了FCFS算法和RR算法，并且没有逐时刻去模拟入队出队情况，而是在用FCFS规则排序的基础上，逐进程/时间片去模拟并打印一个时间段的信息。但是后来考虑阻塞后，因为阻塞队列中的进程随时可能被唤醒，则使得程序要逐时刻地去查看进程出队入队情况，在这方面的修改我花了一番功夫。同时需要注意对于时间的模拟是连续的，这要求更改当前时间的代码位置和关系式需要合适，否则可能出现时间不正常跨越等异常情况。
  • 在打印信息方面，在进程调度过程中，某时刻进程被唤醒的信息和各个时间段进程的运行情况将会输出到屏幕上。对于最终结果，我则是在输出每个进程“开始时间”、“完成时间”、“周转时间”、“等待时间“的基础上额外添加了总体的平均周转时间、平均加权周转时间、平均等待时间、平均阻塞时间，方便不同的算法进行比较。提及时间，在时间片可变的轮转法调度中，何时改变时间片也是需要考虑的：根据要求，响应时间一定，时间片的长短依据就绪队列进程数量的多少由T=N∗(q+t)T=N*(q+t)的关系调整（T为响应时间（固定），N为就绪队列进程数，q为时间片的长短，t为上下文切换时间。其中q为毫秒级及以上，上下文切换时间t为纳秒级而忽略不计）。即就绪队列进程数有变化时，时间片需要调整。
  • 后来我还发现FCFS算法和RR算法只有在一个进程最大连续运行时间（代码中为once_max）上有所不同。故我把两个算法的函数合并在一起写，即在FCFS算法的基础上增加关于once_max的判断和是否改变时间片的判断。同时，我将使用两次查看阻塞队列中是否有进程被唤醒的过程提取出来单独作一个函数（代码中为block_check()）。这两个修改大大减少了代码量（从400+行减至260+行）。整个实验过程中还出现了不少bug（死循环等），这时候我通常通过使用调试工具来解决问题，改进代码。
  • 总之，通过本次实验，我对进程的调度算法有了更深的理解。在从课堂中学到的知识基础上，只有当自己实现代码来模拟算法时，才能切身感受到进程调度算法的精妙之处。因为编写这个代码除了了解进程各个时间的含义和计算方法，还有知道在调度过程中进程何时出入就绪队列和阻塞队列，选用哪种数据结构更合适等细节问题。整个实验加深了对进程的“先入先服务”和“时间片轮转”这两种调度方式的理解，有效地提高了我的逻辑思维和编程能力。
操作系统课程实验
操作系统实验

本博客所有文章除特别声明外，均为博客作者本人编写整理，转载请联系作者！