0
00:00:00,000 --> 00:00:06,880


1
00:00:06,920 --> 00:00:08,520
那前面给大家介绍了

2
00:00:08,560 --> 00:00:11,480
整个调度算法的一个支撑框架

3
00:00:11,520 --> 00:00:12,520
我们也知道

4
00:00:12,560 --> 00:00:14,840
支撑框架何时会去驱动

5
00:00:14,880 --> 00:00:16,320
那些调度算法的函数

6
00:00:16,360 --> 00:00:17,600
接下来我们看一看

7
00:00:17,640 --> 00:00:18,640
一个具体的调度算法

8
00:00:18,680 --> 00:00:19,960
是怎么来实现的

9
00:00:20,000 --> 00:00:21,600
那我们这里面是以Round Robin

10
00:00:21,640 --> 00:00:24,080
调度算法来作为一个例子来介绍

11
00:00:24,120 --> 00:00:25,560
这里面Round Robin

12
00:00:25,600 --> 00:00:27,840
就是我们叫做时间片轮转

13
00:00:27,880 --> 00:00:30,040
那么这个时间片轮转调度算法呢

14
00:00:30,080 --> 00:00:31,720
它主要是基于

15
00:00:31,760 --> 00:00:33,040
每个进程都有一个时间片

16
00:00:33,080 --> 00:00:34,000
当时间片用完之后

17
00:00:34,040 --> 00:00:36,160
它就会等到下一轮再去执行

18
00:00:36,200 --> 00:00:37,680
这是它的一个基本原理

19
00:00:37,720 --> 00:00:39,400
我们来看看它是怎么实现的

20
00:00:39,440 --> 00:00:41,560
前面已经介绍我们要完成一个

21
00:00:41,600 --> 00:00:44,000
就是schedule一个class

22
00:00:44,040 --> 00:00:45,840
要把这些相应的函数填完

23
00:00:45,880 --> 00:00:47,600
这些函数的具体实现

24
00:00:47,640 --> 00:00:48,680
就体现了你这个

25
00:00:48,720 --> 00:00:50,480
时间片轮转的一个特征

26
00:00:50,520 --> 00:00:51,960
它的接口是一样的

27
00:00:52,000 --> 00:00:56,160
包括初始化 进队 出队 选择和tick

28
00:00:56,200 --> 00:00:58,440
这是大致它这几个关键的一些函数

29
00:00:58,480 --> 00:01:00,160
我们看看它怎么来实现的

30
00:01:00,200 --> 00:01:02,880
首先是这个初始化

31
00:01:02,920 --> 00:01:06,400
我们可以知道一个运行队列

32
00:01:06,440 --> 00:01:07,440
就是说就绪队列

33
00:01:07,480 --> 00:01:08,760
需要来把所有这些

34
00:01:08,800 --> 00:01:10,800
处于就绪态的这个进程管理起来

35
00:01:10,840 --> 00:01:12,600
这么一个run_list

36
00:01:12,640 --> 00:01:14,240
同时还记录了一个

37
00:01:14,280 --> 00:01:15,800
当前这个进程的个数

38
00:01:15,840 --> 00:01:17,440
就是处于就绪态进程的个数

39
00:01:17,480 --> 00:01:19,400
这是一个关键的数据结构

40
00:01:19,440 --> 00:01:21,520
然后呢 在初始化的时候呢

41
00:01:21,560 --> 00:01:22,760
我们会把这个队列

42
00:01:22,800 --> 00:01:24,840
给做一个初始化清空

43
00:01:24,880 --> 00:01:26,520
使得这个proc_num等于0

44
00:01:26,560 --> 00:01:29,840
这是最开始的时候要做的一个事情

45
00:01:29,880 --> 00:01:30,760
那我们来看一下

46
00:01:30,800 --> 00:01:32,600
关于Round Robin调度算法

47
00:01:32,640 --> 00:01:34,640
它怎么来实现tick这个函数的

48
00:01:34,680 --> 00:01:36,120
首先我们要知道tick函数

49
00:01:36,160 --> 00:01:37,160
什么时候被调用

50
00:01:37,200 --> 00:01:40,000
它是在产生时钟中断的时候呢

51
00:01:40,040 --> 00:01:42,360
会触发这个函数的调用

52
00:01:42,400 --> 00:01:44,240
那么产生一次时钟中断

53
00:01:44,280 --> 00:01:46,240
意味着时间流失了一小段

54
00:01:46,280 --> 00:01:47,440
所以说呢

55
00:01:47,480 --> 00:01:49,920
它这个time_slice会做减操作

56
00:01:49,960 --> 00:01:51,120
减一这么一个操作

57
00:01:51,160 --> 00:01:52,240
在最开始初始化的时候

58
00:01:52,280 --> 00:01:53,200
一个进程

59
00:01:53,240 --> 00:01:54,720
它有它的一个time_slice

60
00:01:54,760 --> 00:01:55,760
一旦它的time_slice

61
00:01:55,800 --> 00:01:57,760
从它的减操作变成0之后

62
00:01:57,800 --> 00:01:59,080
也就意味着

63
00:01:59,120 --> 00:02:01,560
这个进程的时间片用完了

64
00:02:01,600 --> 00:02:04,840
它有必要就是放弃对CPU的执行

65
00:02:04,880 --> 00:02:06,200
让另一个进程去执行

66
00:02:06,240 --> 00:02:07,040
所以说就可以看到

67
00:02:07,080 --> 00:02:10,080
在这里面一旦time_slice等于0了

68
00:02:10,120 --> 00:02:12,120
我们就会把一个重要的标记

69
00:02:12,160 --> 00:02:13,400
就是need_resched

70
00:02:13,440 --> 00:02:15,800
就是存在着进程控制块里面的

71
00:02:15,840 --> 00:02:18,120
这个need_resched置成1

72
00:02:18,160 --> 00:02:21,280
代表着这个进程应该被换出去

73
00:02:21,320 --> 00:02:23,080
在接下来的中断处理例程中呢

74
00:02:23,120 --> 00:02:25,520
会探询这个当前进程

75
00:02:25,560 --> 00:02:27,280
这个标记位是否为1

76
00:02:27,320 --> 00:02:31,320
一旦为1 它就会执行schedule完成切换

77
00:02:31,360 --> 00:02:34,520
那我们再看看就是进队出队的实现

78
00:02:34,560 --> 00:02:36,040
我们说这个

79
00:02:36,080 --> 00:02:37,520
所有处于就绪态的进程呢

80
00:02:37,560 --> 00:02:39,000
它是在一个就绪队列里面

81
00:02:39,040 --> 00:02:40,200
就绪队列呢

82
00:02:40,240 --> 00:02:41,840
我们是用前面讲到的一个

83
00:02:41,880 --> 00:02:44,240
就是双向链表来实现的

84
00:02:44,280 --> 00:02:46,640
当有一个进程要进队列的时候呢

85
00:02:46,680 --> 00:02:49,200
我们会把它插入到就绪队列的头

86
00:02:49,240 --> 00:02:51,840
就是list_add_before

87
00:02:51,880 --> 00:02:54,160
这是它的一个大致实现

88
00:02:54,200 --> 00:02:55,760
同时呢 也会对它的其它

89
00:02:55,800 --> 00:03:00,400
一些参数做一定的调整 这是进队

90
00:03:00,440 --> 00:03:03,760
那如果说我们要去选择一个进程

91
00:03:03,800 --> 00:03:06,360
就是pick_next怎么来实现的呢

92
00:03:06,400 --> 00:03:10,040
它是从这个队列的尾选出一个进程

93
00:03:10,080 --> 00:03:11,760
这个进程代表当前应该去

94
00:03:11,800 --> 00:03:13,280
占用CPU执行的一个进程

95
00:03:13,320 --> 00:03:14,760
就是说所以说用

96
00:03:14,800 --> 00:03:18,040
list_next来完成这个选择

97
00:03:18,080 --> 00:03:20,080
一旦选择出这个进程之后呢

98
00:03:20,120 --> 00:03:21,760
我们会进一步去做switch_to

99
00:03:21,800 --> 00:03:25,920
来完成对这个进程的切换

100
00:03:25,960 --> 00:03:27,120
那接下来我们看一下

101
00:03:27,160 --> 00:03:29,600
完成这个pick_next怎么来实现的

102
00:03:29,640 --> 00:03:31,800
这个pick_next函数要选择下一个

103
00:03:31,840 --> 00:03:33,640
要占用CPU执行的这个进程

104
00:03:33,680 --> 00:03:36,000
OK 那会从处于

105
00:03:36,040 --> 00:03:37,800
就绪队列里面的进程选一个

106
00:03:37,840 --> 00:03:40,320
选哪个呢 list_next

107
00:03:40,360 --> 00:03:41,200
很明显可以看出来

108
00:03:41,240 --> 00:03:44,960
它是取就绪队列里面最尾的那个

109
00:03:45,000 --> 00:03:46,400
这个进程就代表当前

110
00:03:46,440 --> 00:03:48,840
应该占用CPU执行的进程

111
00:03:48,880 --> 00:03:50,760
这个list是一个双向链表

112
00:03:50,800 --> 00:03:52,360
就是我们前面在lab0的时候

113
00:03:52,400 --> 00:03:54,280
给大家介绍过的一个数据结构

114
00:03:54,320 --> 00:03:56,680
有两种情况

115
00:03:56,720 --> 00:03:59,920
有可能你得到这个元素entry可能是空

116
00:03:59,960 --> 00:04:02,040
或者是一个具体的值

117
00:04:02,080 --> 00:04:03,160
一个具体的值呢

118
00:04:03,200 --> 00:04:04,560
就代表我们选着了

119
00:04:04,600 --> 00:04:06,040
有就绪的这个进程存在

120
00:04:06,080 --> 00:04:07,840
但是如果是空的话

121
00:04:07,880 --> 00:04:09,240
就意味着选不出来

122
00:04:09,280 --> 00:04:10,680
当前没有就绪进程

123
00:04:10,720 --> 00:04:12,280
存在在就绪队列里面

124
00:04:12,320 --> 00:04:13,480
这时候怎么办

125
00:04:13,520 --> 00:04:17,040
这时候我们会让idle_thread去执行

126
00:04:17,080 --> 00:04:18,920
这个idle_thread是一个内核线程

127
00:04:18,960 --> 00:04:21,280
它干的主要工作就是不停的轮询

128
00:04:21,320 --> 00:04:22,520
看这个就绪队列里面

129
00:04:22,560 --> 00:04:25,320
是否有就绪进程存在

130
00:04:25,360 --> 00:04:26,800
如果有就会去执行它

131
00:04:26,840 --> 00:04:30,680


132
00:04:30,720 --> 00:04:33,640
好 一旦我们选择到一个进程之后呢

133
00:04:33,680 --> 00:04:34,960
我们会把这个进程

134
00:04:35,000 --> 00:04:36,640
从就绪队列里面取出来

135
00:04:36,680 --> 00:04:38,200
前面只是选择没有取

136
00:04:38,240 --> 00:04:41,000
所以取出来是一个dequeue的实现

137
00:04:41,040 --> 00:04:44,960
那么这个list_del_init就完成了

138
00:04:45,000 --> 00:04:46,200
从就绪队列里面

139
00:04:46,240 --> 00:04:48,840
把具体的进程取出来这么一个过程

140
00:04:48,880 --> 00:04:51,080
从而就绪队列里面少这么一个元素

141
00:04:51,120 --> 00:04:53,560


142
00:04:53,600 --> 00:04:56,240
OK假定我们实现了这些函数

143
00:04:56,280 --> 00:05:01,320
init 进队 出队 pick_next和tick

144
00:05:01,360 --> 00:05:04,600
其实我们就完成了这个时间片轮转

145
00:05:04,640 --> 00:05:06,120
可以看出来这个实现过程

146
00:05:06,160 --> 00:05:07,680
其实还是挺简单的

147
00:05:07,720 --> 00:05:10,000
然后呢 最后还有哪一步呢

148
00:05:10,040 --> 00:05:11,280
就是在schedule初始化的时候呢

149
00:05:11,320 --> 00:05:13,160
要让我们实现的这个

150
00:05:13,200 --> 00:05:16,560
调度算法的这个类呢

151
00:05:16,600 --> 00:05:19,440
指向具体的一个sched_class

152
00:05:19,480 --> 00:05:20,400
从而可以使得我们

153
00:05:20,440 --> 00:05:21,960
这个schedule这个函数呢

154
00:05:22,000 --> 00:05:24,120
可以找到一个正确的一个调度算法

155
00:05:24,160 --> 00:05:27,640
对应的函数去完成具体的调度过程

156
00:05:27,680 --> 00:05:29,920
这就是说Round Robin这个调度算法

157
00:05:29,960 --> 00:05:31,960
它大致的一个设计

158
00:05:32,000 --> 00:05:33,200
和实现的一个方法

159
00:05:33,240 --> 00:05:34,440
可以看出来比较简单

160
00:05:34,480 --> 00:05:36,920
只要能够明确这几个函数就OK了

161
00:05:36,960 --> 00:05:37,000