Shen Huang's Blog
0%

Gantt图 解释抢先式SJF调度算法

Posted on Edited on

这是操作系统课上的作业，SJF的那个调度要计算的实在太多就写了个程序帮我跑了。

题目如下：

**进程 到达时间 执行时间**
**P1 0 10**
** P2 1 8**
** P3 2 2**
** P4 3 4**
** P5 4 8**
**画****Gantt****图说明使用****FCFS****、非抢先式****SJF****、抢先式****SJF****、****RR****（时间片＝****3****）调度算法进程调度情况。并分别求四种算法的平均周转时间，平均等待时间。平均权周转时间。**
用程序模拟了下实践过程 
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
#include <iostream>
using namespace std;
int main(int argc, char const *argv[])
{
	int wait[6] = {0};
	int p[6] = {0,10,8,2,4,8};
	int use[6] = {0};
	int arrive[6] = {0,0,1,2,3,4};
	int end[6] = {0};
	int flag = 1;
	for (int t = 0; ; t ++){

		//判断进程是否都执行完
		for (int cnt = 0,i = 1; i <= 5; i ++){
			if (use[i] == p[i]) cnt ++;
			if (use[i] == p[i] && end[i] == 0) end[i] = t;
			if (cnt == 5) flag = 0;
		}
		if (!flag) break;

		//判定这一秒该分配给哪一个进行调度
		//vali表示哪一个进程，val指的最大响应比
		int vali;double val = -1;
		for (int i = 1; i <= 5; i ++){
			if (arrive[i] <= t && use[i] < p[i]){
				//算响应比
				double tmp = (0.0 + wait[i] + p[i] - use[i]) / (p[i] - use[i]);
				//安排调度时先看哪个
				//>表示继续做先出现的 >=表示做继续做最后出现的那个进程
				if (tmp >= val){
					val = tmp;
					vali = i;
				}
			}	
		}

		use[vali] ++;
		for (int i = 1; i <= 5; i ++){
			if (arrive[i] <= t && use[i] < p[i] && vali != i)
				wait[i] ++;
		}

		cout << "Time:" << t << " P" << vali << endl;  
	}

	for (int i = 1; i <= 5; i ++){
		cout << "P" << i << " wait_time: " << wait[i] << endl;
	}
	for (int i = 1; i <= 5; i ++){
		cout << "P" << i << " cycling_time: " << end[i] - arrive[i] << endl;
	}
	return 0;
}

结果如下，有可能出现两种调度，具体怎样还不清楚是哪种

Time:0 P1 Time:0 P1
Time:1 P1 Time:1 P2
Time:2 P2 Time:2 P1
Time:3 P3 Time:3 P3
Time:4 P3 Time:4 P3
Time:5 P4 Time:5 P4
Time:6 P4 Time:6 P4
Time:7 P4 Time:7 P4
Time:8 P4 Time:8 P4
Time:9 P2 Time:9 P2
Time:10 P2 Time:10 P2
Time:11 P2 Time:11 P2
Time:12 P2 Time:12 P2
Time:13 P2 Time:13 P2
Time:14 P2 Time:14 P2
Time:15 P2 Time:15 P2
Time:16 P1 Time:16 P1
Time:17 P1 Time:17 P1
Time:18 P1 Time:18 P1
Time:19 P1 Time:19 P1
Time:20 P1 Time:20 P1
Time:21 P1 Time:21 P1
Time:22 P1 Time:22 P1
Time:23 P1 Time:23 P1
Time:24 P5 Time:24 P5
Time:25 P5 Time:25 P5
Time:26 P5 Time:26 P5
Time:27 P5 Time:27 P5
Time:28 P5 Time:28 P5
Time:29 P5 Time:29 P5
Time:30 P5 Time:30 P5
Time:31 P5 Time:31 P5
P1 wait_time: 14 P1 wait_time: 14
P2 wait_time: 7 P2 wait_time: 7
P3 wait_time: 1 P3 wait_time: 1
P4 wait_time: 2 P4 wait_time: 2
P5 wait_time: 20 P5 wait_time: 20
P1 cycling_time: 24 P1 cycling_time: 24
P2 cycling_time: 15 P2 cycling_time: 15
P3 cycling_time: 3 P3 cycling_time: 3
P4 cycling_time: 6 P4 cycling_time: 6
P5 cycling_time: 28 P5 cycling_time: 28