0
00:00:00,000 --> 00:00:16,040


1
00:00:16,080 --> 00:00:17,560
各位同学大家好

2
00:00:17,600 --> 00:00:23,120
今天我们来开始介绍置换算法

3
00:00:23,160 --> 00:00:25,400
那在置换算法这一部分里头呢

4
00:00:25,440 --> 00:00:27,880
我们分成这样三部分来讨论

5
00:00:27,920 --> 00:00:30,160
首先是置换算法的概念

6
00:00:30,200 --> 00:00:31,320
也就是说置换算法

7
00:00:31,360 --> 00:00:33,120
到底是干什么的

8
00:00:33,160 --> 00:00:34,880
然后接下来两个部分是

9
00:00:34,920 --> 00:00:37,440
两种类型的置换算法

10
00:00:37,480 --> 00:00:40,360
局部置换算法是说我

11
00:00:40,400 --> 00:00:42,720
假定分配给一个物理页面数

12
00:00:42,760 --> 00:00:44,000
已经定了之后

13
00:00:44,040 --> 00:00:47,960
然后我去选择到底哪个被置换

14
00:00:48,000 --> 00:00:50,040
而全局置换算法

15
00:00:50,080 --> 00:00:53,880
是不区分置换的这个页面

16
00:00:53,920 --> 00:00:55,680
到底属于哪个进程 这样的话

17
00:00:55,720 --> 00:00:57,760
隐含着后边有每个进程

18
00:00:57,800 --> 00:00:59,000
分配的物理页面数

19
00:00:59,040 --> 00:01:01,560
也会做调整的这样一种情况

20
00:01:01,600 --> 00:01:04,880
好 那我们接下来一个一个的说

21
00:01:04,920 --> 00:01:06,360
置换算法是干什么的呢

22
00:01:06,400 --> 00:01:08,320
置换算法是说我们在

23
00:01:08,360 --> 00:01:10,880
虚拟存储系统当中

24
00:01:10,920 --> 00:01:12,640
出现缺页的时候

25
00:01:12,680 --> 00:01:14,800
我需要把一个新的页面

26
00:01:14,840 --> 00:01:17,240
换到内存当中来 换入

27
00:01:17,280 --> 00:01:19,440
但这时候内存当中的页面

28
00:01:19,480 --> 00:01:22,000
已经全部都用完了

29
00:01:22,040 --> 00:01:24,880
那这时候我必须选择一个页面

30
00:01:24,920 --> 00:01:27,000
把它放到外存当中去

31
00:01:27,040 --> 00:01:29,800
那我新要用的页面才能放进来

32
00:01:29,840 --> 00:01:31,720
置换算法的功能就是

33
00:01:31,760 --> 00:01:34,120
选择被置换的物理页面

34
00:01:34,160 --> 00:01:35,880
你到底选择哪一个

35
00:01:35,920 --> 00:01:37,720
那你说我选择的时候

36
00:01:37,760 --> 00:01:39,080
我怎么来选择呢

37
00:01:39,120 --> 00:01:41,080
那选择有它的依据

38
00:01:41,120 --> 00:01:42,400
那这时候就是我们在这里头

39
00:01:42,440 --> 00:01:43,760
你的依据到底是啥

40
00:01:43,800 --> 00:01:46,800
这就是置换算法的设计目标

41
00:01:46,840 --> 00:01:47,800
那在这里头呢

42
00:01:47,840 --> 00:01:50,720
我们想要来设计一种置换算法

43
00:01:50,760 --> 00:01:53,400
它的目标呢 是说我希望尽可能的

44
00:01:53,440 --> 00:01:58,080
减少页面的调入和调出的次数

45
00:01:58,120 --> 00:02:00,720
那要想让你这个调入调出的次数

46
00:02:00,760 --> 00:02:01,760
实际上这个时候

47
00:02:01,800 --> 00:02:03,320
跟你实际运行的那个程序

48
00:02:03,360 --> 00:02:04,880
对存储访问的特征

49
00:02:04,920 --> 00:02:06,960
是有密切关系的

50
00:02:07,000 --> 00:02:09,360
好 那这时候我希望能够了解

51
00:02:09,400 --> 00:02:12,680
程序在执行的过程当中

52
00:02:12,720 --> 00:02:14,280
它的内存的访问特征

53
00:02:14,320 --> 00:02:16,320
然后我来设计这个置换算法

54
00:02:16,360 --> 00:02:17,240
那这样一来

55
00:02:17,280 --> 00:02:18,640
你得是针对

56
00:02:18,680 --> 00:02:21,120
每一个应用程序来设计吗

57
00:02:21,160 --> 00:02:22,000
那不是这样的

58
00:02:22,040 --> 00:02:23,440
我在操作系统没办法这么做

59
00:02:23,480 --> 00:02:26,680
我只能是设计一个置换算法

60
00:02:26,720 --> 00:02:29,240
然后考虑到它可能运行环境的

61
00:02:29,280 --> 00:02:32,840
这一系列的进程的访问特征

62
00:02:32,880 --> 00:02:34,160
然后从里头找出

63
00:02:34,200 --> 00:02:36,320
适用面比较广的这种情况

64
00:02:36,360 --> 00:02:38,480
那具体说起来呢 我们希望是这样的

65
00:02:38,520 --> 00:02:40,400
把未来不再访问

66
00:02:40,440 --> 00:02:42,720
或者说近期不再访问的

67
00:02:42,760 --> 00:02:44,640
这些页面调出去

68
00:02:44,680 --> 00:02:46,520
那这一条实际上很大的麻烦

69
00:02:46,560 --> 00:02:49,440
是在于我如何能知道这一点

70
00:02:49,480 --> 00:02:52,480
我如何能对未来的情况做一个估计

71
00:02:52,520 --> 00:02:55,960
而这是我们在设计置换算法的时候

72
00:02:56,000 --> 00:02:58,240
考虑最多的一些因素

73
00:02:58,280 --> 00:03:01,640
好 在具体讨论我如何来做这种选择

74
00:03:01,680 --> 00:03:03,800
如何来设计置换算法之前呢

75
00:03:03,840 --> 00:03:06,160
还有一个小问题需要在这先说一下

76
00:03:06,200 --> 00:03:07,840
就是页面锁定

77
00:03:07,880 --> 00:03:10,200
这个是虚拟存储当中的一个概念

78
00:03:10,240 --> 00:03:13,200
说我在进行置换的时候

79
00:03:13,240 --> 00:03:14,160
有一些页面

80
00:03:14,200 --> 00:03:16,920
你是不可以把它换到外存里头的

81
00:03:16,960 --> 00:03:19,280
那这种情况呢 通常情况下是说

82
00:03:19,320 --> 00:03:22,400
我有一些必须在内存里头的

83
00:03:22,440 --> 00:03:24,720
重要的这些逻辑页面

84
00:03:24,760 --> 00:03:25,600
这时候你比如说

85
00:03:25,640 --> 00:03:28,040
操作系统里头的关键代码

86
00:03:28,080 --> 00:03:29,080
然后还有一些呢

87
00:03:29,120 --> 00:03:32,000
它并不一定是操作系统里的关键代码

88
00:03:32,040 --> 00:03:34,800
但是它要求响应速度比较快

89
00:03:34,840 --> 00:03:36,800
你要是说访问的那页在外存里头

90
00:03:36,840 --> 00:03:38,920
那这个性能下降是它接受不了的

91
00:03:38,960 --> 00:03:41,200
好 这些代码我也放在这里头

92
00:03:41,240 --> 00:03:42,800
好 我们怎么来做到这一点呢

93
00:03:42,840 --> 00:03:44,440
实际上在虚拟页式里头

94
00:03:44,480 --> 00:03:46,480
它就在页表里的页表项

95
00:03:46,520 --> 00:03:50,000
相应的页面上加一个锁定标志

96
00:03:50,040 --> 00:03:51,000
有了这个标志之后

97
00:03:51,040 --> 00:03:53,960
置换算法在运行的过程当中就

98
00:03:54,000 --> 00:03:57,280
不会把这个页面放在外存里面去

99
00:03:57,320 --> 00:03:58,880
那在具体讨论之前呢

100
00:03:58,920 --> 00:04:00,400
我们还有一个问题需要大家讨论

101
00:04:00,440 --> 00:04:02,600
那就是我设计了一种置换算法

102
00:04:02,640 --> 00:04:06,000
你设计一种 到底我们俩谁算好

103
00:04:06,040 --> 00:04:07,640
那这种好 实际上在这

104
00:04:07,680 --> 00:04:10,560
是通过统计测试用例

105
00:04:10,600 --> 00:04:12,320
的形式来给出来的

106
00:04:12,360 --> 00:04:14,720
那在这我们为了后续讨论方便

107
00:04:14,760 --> 00:04:17,280
我们需要给出一些约定

108
00:04:17,320 --> 00:04:18,680
也就是说我怎么知道

109
00:04:18,720 --> 00:04:22,160
一个进程的访问内存的序列呢

110
00:04:22,200 --> 00:04:24,080
我就是记录它访问

111
00:04:24,120 --> 00:04:26,520
所有存储单元的这个轨迹

112
00:04:26,560 --> 00:04:28,760
然后那你比如说这里头

113
00:04:28,800 --> 00:04:30,360
我们通常情况下

114
00:04:30,400 --> 00:04:34,600
访问页面的时候是页号 页内偏移

115
00:04:34,640 --> 00:04:35,880
那在我们这里头呢

116
00:04:35,920 --> 00:04:38,320
我们关心的是访问的是哪一页

117
00:04:38,360 --> 00:04:40,240
实际上一页内部

118
00:04:40,280 --> 00:04:42,360
到底是哪一个存储单元

119
00:04:42,400 --> 00:04:44,160
这时候是我们不太关心的

120
00:04:44,200 --> 00:04:46,640
好 我们在这页号 页内偏移

121
00:04:46,680 --> 00:04:47,880
我得到这个序列

122
00:04:47,920 --> 00:04:51,320
然后我把页内偏移都去掉

123
00:04:51,360 --> 00:04:54,680
做简化就变成了底下这个序列了

124
00:04:54,720 --> 00:04:57,600
好 为了我们在后边说置换算法的时候

125
00:04:57,640 --> 00:04:58,640
说起来方便

126
00:04:58,680 --> 00:05:00,760
我们在这里头又给它换了一种表示

127
00:05:00,800 --> 00:05:01,920
用字母来表示

128
00:05:01,960 --> 00:05:06,160
这样避免和我们的顺序的1 2 3 4搞混了

129
00:05:06,200 --> 00:05:07,400
好 有了这个之后

130
00:05:07,440 --> 00:05:09,280
那这时候哪种算法比较好呢

131
00:05:09,320 --> 00:05:10,800
那我们的评价标准是

132
00:05:10,840 --> 00:05:14,360
模拟置换算法的行为 然后记录

133
00:05:14,400 --> 00:05:16,920
在这个置换的过程当中

134
00:05:16,960 --> 00:05:20,040
各个算法到底有多少次缺页

135
00:05:20,080 --> 00:05:23,280
少的就是好的 那有了这两条之后

136
00:05:23,320 --> 00:05:24,520
我们大概就可以开始

137
00:05:24,560 --> 00:05:26,640
来讨论置换算法了

138
00:05:26,680 --> 00:05:28,480
那在讨论之前呢

139
00:05:28,520 --> 00:05:33,360
我们还是首先把置换算法做一个分类

140
00:05:33,400 --> 00:05:34,960
因为你要界定你在讨论

141
00:05:35,000 --> 00:05:38,080
置换算法的时候能够借用的外界条件

142
00:05:38,120 --> 00:05:39,080
那在这里头呢

143
00:05:39,120 --> 00:05:40,400
按照借用的外界条件的不同

144
00:05:40,440 --> 00:05:41,360
我们分成两类

145
00:05:41,400 --> 00:05:44,080
一类叫做局部置换算法

146
00:05:44,120 --> 00:05:46,120
那在局部置换算法里头呢

147
00:05:46,160 --> 00:05:48,520
分配给一个进程的物理页面数

148
00:05:48,560 --> 00:05:50,000
是已经确定了

149
00:05:50,040 --> 00:05:52,160
那我们在置换的时候

150
00:05:52,200 --> 00:05:55,960
选择的范围仅限于当前进程

151
00:05:56,000 --> 00:05:56,920
有了这一条之后

152
00:05:56,960 --> 00:05:59,040
那也就相当于我在置换的过程当中

153
00:05:59,080 --> 00:06:00,280
每个进程分配的

154
00:06:00,320 --> 00:06:02,920
页面的总数是不会变化的

155
00:06:02,960 --> 00:06:03,880
那这里头呢

156
00:06:03,920 --> 00:06:08,040
我们有一系列的算法 最优算法

157
00:06:08,080 --> 00:06:09,800
也就是说如果我能预测未来的话

158
00:06:09,840 --> 00:06:13,320
我依据未来来决定我换哪个页面

159
00:06:13,360 --> 00:06:16,120
这个是理论上的最好状态

160
00:06:16,160 --> 00:06:18,560
没有算法比它更好

161
00:06:18,600 --> 00:06:20,120
但是它的问题是

162
00:06:20,160 --> 00:06:21,960
这个算法你在实际用的时候

163
00:06:22,000 --> 00:06:23,360
你没办法知道

164
00:06:23,400 --> 00:06:25,160
它所依赖的那个前提条件

165
00:06:25,200 --> 00:06:27,960
就是未来什么时候会用到这个页面

166
00:06:28,000 --> 00:06:30,120
第二个呢 是先进先出

167
00:06:30,160 --> 00:06:32,840
这个算法是说用最简单的办法

168
00:06:32,880 --> 00:06:34,120
我不知道它未来是啥情况

169
00:06:34,160 --> 00:06:37,480
我就按照进来的时候的先后顺序

170
00:06:37,520 --> 00:06:39,800
但是这个进来的先后顺序呢

171
00:06:39,840 --> 00:06:42,880
并不一定反映了

172
00:06:42,920 --> 00:06:45,520
实际的存储的访问特征

173
00:06:45,560 --> 00:06:46,600
好 那这样的话

174
00:06:46,640 --> 00:06:48,400
这个算法的性能不好

175
00:06:48,440 --> 00:06:49,280
再有一个就是

176
00:06:49,320 --> 00:06:51,720
最近最久未使用算法

177
00:06:51,760 --> 00:06:53,560
那它实际上是在这里头呢

178
00:06:53,600 --> 00:06:55,760
这个算法先进先出太差

179
00:06:55,800 --> 00:06:58,240
最优算法没法实现

180
00:06:58,280 --> 00:07:00,960
因为你是预测未来没法实现

181
00:07:01,000 --> 00:07:02,880
好 那在这最近最久未使用算法

182
00:07:02,920 --> 00:07:04,440
就是我把预测未来

183
00:07:04,480 --> 00:07:06,880
变成是我统计过去

184
00:07:06,920 --> 00:07:08,840
在过去一段时间的特征

185
00:07:08,880 --> 00:07:12,200
我们通常情况下认为你过去的特征

186
00:07:12,240 --> 00:07:14,160
对你未来是一种预测

187
00:07:14,200 --> 00:07:16,160
好 我们基于这样一种假设前提呢

188
00:07:16,200 --> 00:07:19,720
来讨论最近最久未使用算法

189
00:07:19,760 --> 00:07:23,400
但是这种算法呢 它可能实现

190
00:07:23,440 --> 00:07:26,360
但是仍然它的复杂度比较高

191
00:07:26,400 --> 00:07:27,400
好 那这时候呢

192
00:07:27,440 --> 00:07:29,720
就由它的这两种近似算法

193
00:07:29,760 --> 00:07:30,960
我们这会说到

194
00:07:31,000 --> 00:07:34,520
时钟算法和最不常用算法

195
00:07:34,560 --> 00:07:36,200
那这都是对最近最久

196
00:07:36,240 --> 00:07:38,440
未使用算法的一种近似

197
00:07:38,480 --> 00:07:39,920
那具体的近似的做法呢

198
00:07:39,960 --> 00:07:41,720
我们在后边再详细去说

199
00:07:41,760 --> 00:07:43,120
这是一类 也就是相当于

200
00:07:43,160 --> 00:07:46,760
我在当前进程暂用的页面里

201
00:07:46,800 --> 00:07:49,200
来讨论我换谁

202
00:07:49,240 --> 00:07:50,600
还有一类算法呢 

203
00:07:50,640 --> 00:07:53,360
叫全局置换算法

204
00:07:53,400 --> 00:07:57,160
它不关心你当前换的这个页面

205
00:07:57,200 --> 00:07:58,200
属于哪个进程

206
00:07:58,240 --> 00:08:00,040
它讨论的范围是说置换的范围

207
00:08:00,080 --> 00:08:03,160
是在所有可能换出的物理页面

208
00:08:03,200 --> 00:08:04,360
它不管是哪个进程的

209
00:08:04,400 --> 00:08:06,920
这隐含着 如果说我在置换的时候

210
00:08:06,960 --> 00:08:11,000
是进程A的一个需要访问的页面

211
00:08:11,040 --> 00:08:12,680
被置换出去那是进程B的

212
00:08:12,720 --> 00:08:13,720
实际上这时候就隐含了

213
00:08:13,760 --> 00:08:15,680
这两个进程之间分配的

214
00:08:15,720 --> 00:08:18,840
物理页面数的一个变化

215
00:08:18,880 --> 00:08:21,440
好 这时候呢 它也有两种算法

216
00:08:21,480 --> 00:08:22,440
我们在这会说到

217
00:08:22,480 --> 00:08:26,440
工作集算法和缺页率算法

218
00:08:26,480 --> 00:08:28,320
好 有了这样一个大致分类之后

219
00:08:28,360 --> 00:08:30,680
我们就先按照局部置换算法和

220
00:08:30,720 --> 00:08:32,160
全局置换算法的顺序

221
00:08:32,200 --> 00:08:34,400
来一个一个的进行讨论

222
00:08:34,440 --> 00:08:34,480