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

1
00:00:06,720  -->  00:00:10,000
好 接下来我们介绍置换算法

2
00:00:10,040  -->  00:00:13,080
首先我们来介绍局部置换算法

3
00:00:13,120  -->  00:00:15,520
也就是说假定给一个进程的

4
00:00:15,560  -->  00:00:17,920
物理页面数是已经确定了

5
00:00:17,960  -->  00:00:19,560
那在这些页面里头呢

6
00:00:19,600  -->  00:00:21,680
我们来进行置换

7
00:00:21,720  -->  00:00:23,640
那第一个要说的置换算法呢

8
00:00:23,680  -->  00:00:27,400
是最优置换算法 最优置换算法呢

9
00:00:27,440  -->  00:00:29,640
它的基本思路是说

10
00:00:29,680  -->  00:00:32,440
我在任何一次缺页的时候

11
00:00:32,480  -->  00:00:34,480
我会去观察

12
00:00:34,520  -->  00:00:39,240
这内存当中存在的各个逻辑页

13
00:00:39,280  -->  00:00:42,200
它在未来什么时间会被访问

14
00:00:42,240  -->  00:00:44,880
那我们要置换的是在未来

15
00:00:44,920  -->  00:00:49,400
最长时间不会被访问的这个页面

16
00:00:49,440  -->  00:00:52,120
那这个思路我们怎么来做呢

17
00:00:52,160  -->  00:00:55,360
它的做法是这样的

18
00:00:55,400  -->  00:00:58,200
缺页的时候我来计算内存当中

19
00:00:58,240  -->  00:01:02,280
每一个逻辑页面的下一次访问时间

20
00:01:02,320  -->  00:01:04,280
假定你能计算出来的话

21
00:01:04,320  -->  00:01:07,640
然后我去看 比较它们的大小

22
00:01:07,680  -->  00:01:10,320
未来最长时间不访问的页面

23
00:01:10,360  -->  00:01:12,160
就是我要被置换的页面

24
00:01:12,200  -->  00:01:13,440
那这个思路很简单

25
00:01:13,480  -->  00:01:17,280
你把内存当中的所有逻辑页面排序

26
00:01:17,320  -->  00:01:20,840
排序的依据是下一次访问的时间

27
00:01:20,880  -->  00:01:23,600
然后最长的那个就是你要置换的

28
00:01:23,640  -->  00:01:27,920
那这种算法呢 它思路很清楚

29
00:01:27,960  -->  00:01:29,440
但是它的特征呢

30
00:01:29,480  -->  00:01:33,680
这是缺页的次数最少的

31
00:01:33,720  -->  00:01:36,760
但是它也有一个致命的问题

32
00:01:36,800  -->  00:01:38,920
就是它没法实现

33
00:01:38,960  -->  00:01:42,480
原因在于我无法预知该逻辑页面

34
00:01:42,520  -->  00:01:44,560
它的下一次访问的时间

35
00:01:44,600  -->  00:01:45,960
到底是在什么时候

36
00:01:46,000  -->  00:01:48,160
在这之前我要等多长时间

37
00:01:48,200  -->  00:01:49,600
实际上如果我知道那个

38
00:01:49,640  -->  00:01:50,680
等的时间有多长的话

39
00:01:50,720  -->  00:01:52,400
那我就把等的时间最长的那个

40
00:01:52,440  -->  00:01:55,080
放到外存里面去 这是最理想的

41
00:01:55,120  -->  00:01:56,520
但是这种做法呢 

42
00:01:56,560  -->  00:01:57,960
为什么我们还要在这说

43
00:01:58,000  -->  00:01:59,960
实际上就是因为它可以作为

44
00:02:00,000  -->  00:02:02,920
其它算法性能评测的依据

45
00:02:02,960  -->  00:02:05,440
也就是说你设计了一种置换算法

46
00:02:05,480  -->  00:02:08,600
能跟这个最优置换算法相比

47
00:02:08,640  -->  00:02:11,400
你比它差多少

48
00:02:11,440  -->  00:02:13,800
那你最好是能达到它的状态

49
00:02:13,840  -->  00:02:14,920
你不会比它再好

50
00:02:14,960  -->  00:02:16,080
所以在这用它来

51
00:02:16,120  -->  00:02:19,360
作为评测依据是比较好的

52
00:02:19,400  -->  00:02:20,600
那具体怎么做呢

53
00:02:20,640  -->  00:02:24,320
是说我在模拟器里头运行该程序

54
00:02:24,360  -->  00:02:27,880
假定它的对外界的影响都是固定的

55
00:02:27,920  -->  00:02:29,200
好 那这时候我记录下

56
00:02:29,240  -->  00:02:32,080
它每一个页面的访问的情况

57
00:02:32,120  -->  00:02:34,720
第二次我再来运行的时候

58
00:02:34,760  -->  00:02:39,160
我就得到它的最少的缺页次数了

59
00:02:39,200  -->  00:02:41,080
那另设计一个算法和它比较

60
00:02:41,120  -->  00:02:44,000
你就能知道这个算法的好坏了

61
00:02:44,040  -->  00:02:46,240
这是最优置换算法

62
00:02:46,280  -->  00:02:48,200
那我们在这用一个例子

63
00:02:48,240  -->  00:02:50,640
来说它到底该怎么做

64
00:02:50,680  -->  00:02:53,520
在这里呢 上边是时间的顺序

65
00:02:53,560  -->  00:02:55,120
中间这一行

66
00:02:55,160  -->  00:02:58,760
是请求访问的页面的顺序

67
00:02:58,800  -->  00:03:00,960
这是逻辑页的编号

68
00:03:01,000  -->  00:03:02,760
我们用A B C D来表示

69
00:03:02,800  -->  00:03:04,120
好 这地方呢

70
00:03:04,160  -->  00:03:07,240
是物理内存分配的页面数

71
00:03:07,280  -->  00:03:08,400
那在这我们假定

72
00:03:08,440  -->  00:03:10,160
给它分了四个页面

73
00:03:10,200  -->  00:03:12,200
然后底下我们来记录

74
00:03:12,240  -->  00:03:13,840
它缺页的情况

75
00:03:13,880  -->  00:03:16,080
那我们执行起来会什么样子呢

76
00:03:16,120  -->  00:03:20,960
首先执行第一次请求访问C

77
00:03:21,000  -->  00:03:22,560
那这时候呢没有缺页

78
00:03:22,600  -->  00:03:25,480
第二次也没有 那我都能访问

79
00:03:25,520  -->  00:03:28,240
第三次D也能访问

80
00:03:28,280  -->  00:03:30,120
第四B在这里也有

81
00:03:30,160  -->  00:03:32,200
那我们这些都没问题 正常访问了

82
00:03:32,240  -->  00:03:35,240
等到你访问E的时候就会发现

83
00:03:35,280  -->  00:03:38,080
这时候不在你的物理内存里头了

84
00:03:38,120  -->  00:03:39,240
产生了缺页 

85
00:03:39,280  -->  00:03:42,000
那在缺页处理例程里头呢

86
00:03:42,040  -->  00:03:45,840
我们就会引用最优置换算法

87
00:03:45,880  -->  00:03:47,200
最优置换算法就来判断

88
00:03:47,240  -->  00:03:49,600
当时我这几个选哪一个呢

89
00:03:49,640  -->  00:03:52,080
那我们就看在未来的时间里头

90
00:03:52,120  -->  00:03:54,880
它都会在什么时间会被访问到

91
00:03:54,920  -->  00:03:57,800
好 那我们看内存里有A

92
00:03:57,840  -->  00:04:00,280
A会在这地方访问到

93
00:04:00,320  -->  00:04:09,160
好 B是在这 C是9 还有个D是10

94
00:04:09,200  -->  00:04:10,880
这几个比较起来呢 

95
00:04:10,920  -->  00:04:12,960
10是离的最远的

96
00:04:13,000  -->  00:04:14,160
那我们在这就把

97
00:04:14,200  -->  00:04:19,000
这个10对应的D给替换掉

98
00:04:19,040  -->  00:04:20,720
那替换完了之后结果

99
00:04:20,760  -->  00:04:23,120
就是把D变成了E

100
00:04:23,160  -->  00:04:24,760
好 那我这个缺页中断处理呢

101
00:04:24,800  -->  00:04:26,160
就处理完了

102
00:04:26,200  -->  00:04:27,600
回来你再来访问 

103
00:04:27,640  -->  00:04:30,880
这个就算是成功了

104
00:04:30,920  -->  00:04:33,800
好 继续访问B没有问题

105
00:04:33,840  -->  00:04:37,040
访问A也没有问题

106
00:04:37,080  -->  00:04:39,120
再访问B也没有问题

107
00:04:39,160  -->  00:04:42,440
再访问C也没有问题

108
00:04:42,480  -->  00:04:45,480
好 那这时候说我们再访问D

109
00:04:45,520  -->  00:04:46,320
那这时候呢 

110
00:04:46,360  -->  00:04:48,840
这个D又不在这里头了

111
00:04:48,880  -->  00:04:49,920
那这时候怎么办

112
00:04:49,960  -->  00:04:51,600
我们接着说未来会访问

113
00:04:51,640  -->  00:04:53,480
但是这时候已经再往后

114
00:04:53,520  -->  00:04:55,920
它的未来已经结束了

115
00:04:55,960  -->  00:04:57,960
那就你说什么都可以了

116
00:04:58,000  -->  00:04:58,720
所以在这呢

117
00:04:58,760  -->  00:05:00,480
后边你再怎么置换都无所谓了

118
00:05:00,520  -->  00:05:02,080
所以在这 最好的情况

119
00:05:02,120  -->  00:05:04,400
你是缺页两次

120
00:05:04,440  -->  00:05:06,360
那其它的算法你写完之后

121
00:05:06,400  -->  00:05:07,720
就看跟这两个比较

122
00:05:07,760  -->  00:05:09,480
在对于这个特定的序列

123
00:05:09,520  -->  00:05:11,920
谁好谁坏就清楚了

124
00:05:11,960  -->  00:05:14,080
那这是最优置换算法

125
00:05:14,120  -->  00:05:15,280
那它的毛病是在于

126
00:05:15,320  -->  00:05:16,440
我在缺页的时候

127
00:05:16,480  -->  00:05:17,520
我没有办法知道

128
00:05:17,560  -->  00:05:19,360
后边到底是什么样的访问

129
00:05:19,400  -->  00:05:21,200
特别是你比如说我的一个程序

130
00:05:21,240  -->  00:05:22,120
每次处理的时候

131
00:05:22,160  -->  00:05:23,440
它的数据是不一样的

132
00:05:23,480  -->  00:05:24,040
我们前边说

133
00:05:24,080  -->  00:05:25,360
你可以重复两次来用

134
00:05:25,400  -->  00:05:26,480
但是我通常情况下

135
00:05:26,520  -->  00:05:28,280
我们的程序每次执行的时候

136
00:05:28,320  -->  00:05:29,840
它处理的数据都是不一样的

137
00:05:29,880  -->  00:05:31,640
好 这个序列你也是没办法

138
00:05:31,680  -->  00:05:34,800
完全准确的预测出来的

139
00:05:34,840  -->  00:05:37,440
这是第一种做法

140
00:05:37,480  -->  00:05:38,720
那么第二个做法呢 

141
00:05:38,760  -->  00:05:41,360
是先进先出算法

142
00:05:41,400  -->  00:05:43,280
FIFO那它的做法呢

143
00:05:43,320  -->  00:05:47,160
是我们想知道未来的情况 没办法知道

144
00:05:47,200  -->  00:05:50,240
那我们就采用一种最简单的做法

145
00:05:50,280  -->  00:05:53,960
那谁来进来 我按照进来的顺序排

146
00:05:54,000  -->  00:05:55,640
这实际上我们在很多地方

147
00:05:55,680  -->  00:05:59,200
我比较不出谁更好谁更坏的时候

148
00:05:59,240  -->  00:06:02,040
我们就按照先来后到

149
00:06:02,080  -->  00:06:03,880
这是我们在做各种各样算法的时候

150
00:06:03,920  -->  00:06:05,600
一种最基本的做法

151
00:06:05,640  -->  00:06:07,000
那它的依据是说

152
00:06:07,040  -->  00:06:10,560
在内存驻留时间最长的页面进行替换

153
00:06:10,600  -->  00:06:11,880
也就是说我第一个进来

154
00:06:11,920  -->  00:06:13,040
那它的时间是最长的

155
00:06:13,080  -->  00:06:15,760
最后一个进来它的时间是最短的

156
00:06:15,800  -->  00:06:18,200
好 那怎么做呢

157
00:06:18,240  -->  00:06:21,280
那维护一个逻辑页面的链表

158
00:06:21,320  -->  00:06:24,720
按先来后到的顺序 按驻留时间排序

159
00:06:24,760  -->  00:06:27,840
好 在头上的呢 是最长时间的

160
00:06:27,880  -->  00:06:29,840
你置换的时候就从头上选

161
00:06:29,880  -->  00:06:32,040
然后最先进来的呢 放在最后头

162
00:06:32,080  -->  00:06:34,240
那缺页的时候呢

163
00:06:34,280  -->  00:06:37,600
我从链首取相应的页面进行置换

164
00:06:37,640  -->  00:06:41,400
新加的页面呢 放在链尾里头

165
00:06:41,440  -->  00:06:42,920
那这种做法呢 它的麻烦是什么呢

166
00:06:42,960  -->  00:06:44,960
是性能比较差

167
00:06:45,000  -->  00:06:47,720
好处是我比较好实现

168
00:06:47,760  -->  00:06:49,280
性能比较差怎么说呢

169
00:06:49,320  -->  00:06:50,600
就是因为它只是按照

170
00:06:50,640  -->  00:06:54,960
你进内存的先后顺序再排序

171
00:06:55,000  -->  00:06:57,920
有可能你会出现这样一种情况

172
00:06:57,960  -->  00:07:01,000
我刚把一个页面拿出去

173
00:07:01,040  -->  00:07:03,000
它是在这里待的最长时间的

174
00:07:03,040  -->  00:07:05,120
好 你马上就会去用它

175
00:07:05,160  -->  00:07:07,320
如果说我们出现这种极端的情况

176
00:07:07,360  -->  00:07:09,800
那这时候呢 它的缺页率就会很高了

177
00:07:09,840  -->  00:07:12,400
好 甚至于会出现这种情况

178
00:07:12,440  -->  00:07:14,480
这种FIFO算法

179
00:07:14,520  -->  00:07:15,640
它可能会出现什么呢

180
00:07:15,680  -->  00:07:19,400
我分配它N个页面的时候它缺页M次

181
00:07:19,440  -->  00:07:21,520
我把它N+1之后

182
00:07:21,560  -->  00:07:23,040
可能那个通常情况下

183
00:07:23,080  -->  00:07:24,520
我们理解一个算法

184
00:07:24,560  -->  00:07:26,360
我分配的物理页面越多

185
00:07:26,400  -->  00:07:28,720
它的缺页次数应该更少 但这时候呢

186
00:07:28,760  -->  00:07:31,200
它有可能缺页次数不但不减少

187
00:07:31,240  -->  00:07:32,400
反而会增加

188
00:07:32,440  -->  00:07:35,040
这是我们后边说到的Belady的现象

189
00:07:35,080  -->  00:07:36,040
这个时候呢

190
00:07:36,080  -->  00:07:37,280
实际上从另一个角度上说明

191
00:07:37,320  -->  00:07:40,360
这个算法它是有缺陷的

192
00:07:40,400  -->  00:07:42,680
好 通常情况下呢 这种算法呢

193
00:07:42,720  -->  00:07:44,720
我们不会直接把它

194
00:07:44,760  -->  00:07:46,000
作为一个独立的算法来用

195
00:07:46,040  -->  00:07:48,160
它会把它揉到别的算法里来用

196
00:07:48,200  -->  00:07:50,840
所以我们在这还会继续去说它

197
00:07:50,880  -->  00:07:54,040
那我们也通过一个示例来说明

198
00:07:54,080  -->  00:07:56,440
FIFO的执行过程

199
00:07:56,480  -->  00:07:58,920
假定我这个进程分配了四个页面

200
00:07:58,960  -->  00:08:01,480
然后我维护一个链表

201
00:08:01,520  -->  00:08:03,480
然后在这依据它访问的顺序

202
00:08:03,520  -->  00:08:05,600
我来判断

203
00:08:05,640  -->  00:08:08,160
那这是我们刚才那个例子

204
00:08:08,200  -->  00:08:10,480
我们接着分配给它四个页面

205
00:08:10,520  -->  00:08:14,080
看看在FIFO算法里头

206
00:08:14,120  -->  00:08:17,160
它会缺页多少次 那在前边呢

207
00:08:17,200  -->  00:08:20,280
这地方先访问这四个页面没问题

208
00:08:20,320  -->  00:08:23,400
它肯定都在 这个你用哪个算法呢

209
00:08:23,440  -->  00:08:26,560
它的效果都是一样的

210
00:08:26,600  -->  00:08:28,880
好 开始不一样的地方是在这

211
00:08:28,920  -->  00:08:32,080
我在访问E的时候呢 它产生了缺页

212
00:08:32,120  -->  00:08:34,120
在最优算法里头

213
00:08:34,160  -->  00:08:36,000
我们是依据后来做判断的

214
00:08:36,040  -->  00:08:37,920
现在我得不到这个了

215
00:08:37,960  -->  00:08:40,040
我根据什么 我根据它进出的顺序

216
00:08:40,080  -->  00:08:42,880
在这我假定它进内存的顺序

217
00:08:42,920  -->  00:08:44,360
是按照A B C进来的

218
00:08:44,400  -->  00:08:45,840
那这样的话很容易

219
00:08:45,880  -->  00:08:50,280
我就知道我要用A来做替换

220
00:08:50,320  -->  00:08:52,200
替换完了把A换成了E

221
00:08:52,240  -->  00:08:53,920
好 然后后边再访问的时候

222
00:08:53,960  -->  00:08:56,520
B在里头访问得到没问题

223
00:08:56,560  -->  00:08:59,600
A这时候又缺页了

224
00:08:59,640  -->  00:09:00,640
这时候缺页怎么办呢 

225
00:09:00,680  -->  00:09:02,120
我又要进行替换

226
00:09:02,160  -->  00:09:04,360
替换我选的内存当中的页面

227
00:09:04,400  -->  00:09:05,680
选哪一个呢

228
00:09:05,720  -->  00:09:06,880
选这里头时间最长的

229
00:09:06,920  -->  00:09:10,360
A进来之后 E实际上是排在最后的

230
00:09:10,400  -->  00:09:11,480
那这时候呢

231
00:09:11,520  -->  00:09:15,320
我把B替换了 B替换成A

232
00:09:15,360  -->  00:09:17,880
然后这个时候呢 再下一个

233
00:09:17,920  -->  00:09:20,120
我又访问了B 正好不错

234
00:09:20,160  -->  00:09:22,600
我刚拿出去就访问它了

235
00:09:22,640  -->  00:09:23,680
再访问B的时候

236
00:09:23,720  -->  00:09:27,000
这时候我有A E C D这几个

237
00:09:27,040  -->  00:09:30,680
按照先后顺序是C D E A

238
00:09:30,720  -->  00:09:35,280
好 那我们这个时候呢说我们换C

239
00:09:35,320  -->  00:09:36,760
好 把C换了 

240
00:09:36,800  -->  00:09:38,240
然后到这来了之后呢

241
00:09:38,280  -->  00:09:41,880
再下一次访问C 它又出现缺页

242
00:09:41,920  -->  00:09:45,920
那么这时候呢 我们看 这内存有哪

243
00:09:45,960  -->  00:09:49,080
D E A B是这个顺序

244
00:09:49,120  -->  00:09:52,360
那这时候我们换D

245
00:09:52,400  -->  00:09:54,680
换完之后是这样一个结果

246
00:09:54,720  -->  00:09:57,880
然后我再换 再下一步

247
00:09:57,920  -->  00:09:59,000
那这个地方的时候呢

248
00:09:59,040  -->  00:10:03,320
我们看到这时候D被换出去了

249
00:10:03,360  -->  00:10:09,840
这里头E A B C 那这时候要换的是E

250
00:10:09,880  -->  00:10:13,040
那到这我们这个访问序列执行完毕

251
00:10:13,080  -->  00:10:14,400
我们看缺页几次

252
00:10:14,440  -->  00:10:17,640
1 2 3 4 5 5次

253
00:10:17,680  -->  00:10:19,280
和我们最优算法的两次

254
00:10:19,320  -->  00:10:21,800
比较起来它多了

255
00:10:21,840  -->  00:10:23,640
那你说你在这里头构造的这个例子

256
00:10:23,680  -->  00:10:26,560
正好是极端情况

257
00:10:26,600  -->  00:10:28,320
你刚把哪一个拿出去

258
00:10:28,360  -->  00:10:30,080
你下边就要访问哪一个

259
00:10:30,120  -->  00:10:31,920
那当然会是这样 那这时候是说

260
00:10:31,960  -->  00:10:33,440
是不是我任何一个算法

261
00:10:33,480  -->  00:10:35,320
都可能构造出一个极端的例子

262
00:10:35,360  -->  00:10:38,080
你的性能会很差 那实际上这个呢

263
00:10:38,120  -->  00:10:41,600
从理论上我们是可以证明

264
00:10:41,640  -->  00:10:45,760
最优算法它的这种特征是最好的

265
00:10:45,800  -->  00:10:48,560
好 这是FIFO算法

266
00:10:48,600  -->  00:10:52,640
那这种算法呢 它实际上过于简单

267
00:10:52,680  -->  00:10:54,640
那接下来我们说

268
00:10:54,680  -->  00:10:57,560
我是不是可以把这种简单的算法和

269
00:10:57,600  -->  00:10:58,960
不可实现的算法之间

270
00:10:59,000  -->  00:11:00,640
做某种程度的折中呢

271
00:11:00,680  -->  00:11:02,520
这是第一种折中的办法

272
00:11:02,560  -->  00:11:07,200
最近最久未使用算法 LRU

273
00:11:07,240  -->  00:11:08,400
那它的做法是什么呢

274
00:11:08,440  -->  00:11:12,160
我们刚才考察未来的引用情况

275
00:11:12,200  -->  00:11:14,600
这事我没有办法考察得到

276
00:11:14,640  -->  00:11:17,640
那怎么办 我们去考察过去

277
00:11:17,680  -->  00:11:20,960
选择最长时间没有被引用的

278
00:11:21,000  -->  00:11:23,480
也就是说我们原始考察当前时间点

279
00:11:23,520  -->  00:11:28,080
往后最远被访问到的

280
00:11:28,120  -->  00:11:29,800
我把它置换出去 那现在呢

281
00:11:29,840  -->  00:11:32,760
我是过去的情况我是可以统计的

282
00:11:32,800  -->  00:11:34,160
我在当前这个时间点

283
00:11:34,200  -->  00:11:35,640
看过去在内存当中

284
00:11:35,680  -->  00:11:37,120
这些页面的访问情况

285
00:11:37,160  -->  00:11:38,640
离的最远的那个

286
00:11:38,680  -->  00:11:40,680
最长时间没有被引用的

287
00:11:40,720  -->  00:11:43,200
我把它置换掉 这是可能的

288
00:11:43,240  -->  00:11:45,280
这种做法的依据是什么呢

289
00:11:45,320  -->  00:11:46,840
这种做法的依据是在于

290
00:11:46,880  -->  00:11:49,200
我们通常情况下认为

291
00:11:49,240  -->  00:11:52,680
在过去一段时间经常访问的页面

292
00:11:52,720  -->  00:11:55,160
那在未来也会经常访问

293
00:11:55,200  -->  00:11:57,640
在过去一段时间很少访问的

294
00:11:57,680  -->  00:12:00,000
在未来也很少访问

295
00:12:00,040  -->  00:12:01,160
基于这样一种假测

296
00:12:01,200  -->  00:12:04,080
我们依据过去来预测未来

297
00:12:04,120  -->  00:12:07,280
好 那这是它的思路 它怎么做呢

298
00:12:07,320  -->  00:12:10,640
缺页的时候我去看在内存当中的

299
00:12:10,680  -->  00:12:11,720
每一个逻辑页面

300
00:12:11,760  -->  00:12:13,720
它的上一次的访问时间

301
00:12:13,760  -->  00:12:16,000
那这个时间我是可以计算出来的

302
00:12:16,040  -->  00:12:16,960
计算出来之后

303
00:12:17,000  -->  00:12:20,000
上一次访问到当前这个时间

304
00:12:20,040  -->  00:12:22,720
最长的那一个那就是最远的

305
00:12:22,760  -->  00:12:25,200
那一次被访问者

306
00:12:25,240  -->  00:12:27,680
我把那个页面置换出去

307
00:12:27,720  -->  00:12:29,080
好 这样做法之后呢

308
00:12:29,120  -->  00:12:30,440
它有什么特征呢

309
00:12:30,480  -->  00:12:33,760
它是最优算法的一种近似

310
00:12:33,800  -->  00:12:37,280
但是这种算法仍然足够复杂

311
00:12:37,320  -->  00:12:40,280
以至于我们在这里要实施的话

312
00:12:40,320  -->  00:12:42,280
是不太可能的

313
00:12:42,320  -->  00:12:46,560
好 那这次说我们在这里头说的LRU

314
00:12:46,600  -->  00:12:48,680
我们也通过一个实例来看

315
00:12:48,720  -->  00:12:51,560
刚才这个序列它的执行情况

316
00:12:51,600  -->  00:12:52,440
那在这呢

317
00:12:52,480  -->  00:12:56,520
前边的几个正常情况下都没问题

318
00:12:56,560  -->  00:13:01,520
C A D B 这访问完了

319
00:13:01,560  -->  00:13:04,160
然后下一个E出现缺页

320
00:13:04,200  -->  00:13:06,400
那这时候呢 我们要去考察

321
00:13:06,440  -->  00:13:10,280
过去一段时间这几个的引用情况

322
00:13:10,320  -->  00:13:14,280
那我们看A在哪访问 第二个

323
00:13:14,320  -->  00:13:17,280
B呢 是第四个

324
00:13:17,320  -->  00:13:24,200
C呢 是第一个 D呢是第三个

325
00:13:24,240  -->  00:13:27,640
这个顺序和我们的最优算法很相像

326
00:13:27,680  -->  00:13:28,400
区别在哪

327
00:13:28,440  -->  00:13:31,120
区别在于最优算法是往后考察

328
00:13:31,160  -->  00:13:33,920
最近最久未使用算法是往前考察

329
00:13:33,960  -->  00:13:36,440
然后得出它上一次访问的时间

330
00:13:36,480  -->  00:13:38,360
然后我选其中最小的那个

331
00:13:38,400  -->  00:13:43,120
这里头是C 好 我替换C

332
00:13:43,160  -->  00:13:45,840
好 替换完的结果呢是这样的

333
00:13:45,880  -->  00:13:48,240
好 然后再继续往下走

334
00:13:48,280  -->  00:13:51,320
B访问在里头 A访问在里头

335
00:13:51,360  -->  00:13:55,120
B访问还在里头 C访问的时候

336
00:13:55,160  -->  00:13:58,000
那这时候又出现缺页了

337
00:13:58,040  -->  00:13:59,920
那这时候我们说我们又需要

338
00:13:59,960  -->  00:14:01,960
按刚才一样的做法去考察

339
00:14:02,000  -->  00:14:06,440
在内存当中的A B E D这几个

340
00:14:06,480  -->  00:14:08,360
它的上一次访问时间

341
00:14:08,400  -->  00:14:09,720
那怎么考察呢

342
00:14:09,760  -->  00:14:13,400
我们看这是A上一次访问时间是7

343
00:14:13,440  -->  00:14:16,600
B上一次访问时间是8

344
00:14:16,640  -->  00:14:20,680
然后E上一次访问时间是5

345
00:14:20,720  -->  00:14:24,240
然后还有一个D上一次访问时间是3

346
00:14:24,280  -->  00:14:26,440
那这时候比较下的结果呢

347
00:14:26,480  -->  00:14:30,480
这个D是最早的 我们把D替换掉

348
00:14:30,520  -->  00:14:32,320
替换成我这里的C

349
00:14:32,360  -->  00:14:35,320
替换完的结果呢 是这样的

350
00:14:35,360  -->  00:14:37,920
好 然后这时候说

351
00:14:37,960  -->  00:14:40,560
我接下来执行下一个 那这时候呢

352
00:14:40,600  -->  00:14:45,040
访问到的D正好是刚被替换出去的

353
00:14:45,080  -->  00:14:46,160
你又要出现缺页

354
00:14:46,200  -->  00:14:48,880
那这时候按照我们最优置换算法

355
00:14:48,920  -->  00:14:50,480
因为最后一个没有未来了

356
00:14:50,520  -->  00:14:53,560
给哪个都一样 实际上也是这样的

357
00:14:53,600  -->  00:14:56,760
但是在最近最久未使用算法里头呢

358
00:14:56,800  -->  00:14:57,960
我们就需要去看

359
00:14:58,000  -->  00:15:00,360
过去一段时间它的情况

360
00:15:00,400  -->  00:15:02,520
当然我们知道这种考察呢

361
00:15:02,560  -->  00:15:05,280
实际上对未来的执行是没有意义的

362
00:15:05,320  -->  00:15:06,640
从这个角度来说呢

363
00:15:06,680  -->  00:15:09,040
这个LRU 在最优算法的

364
00:15:09,080  -->  00:15:10,200
近似的过程当中

365
00:15:10,240  -->  00:15:11,800
它也有不准确的地方 

366
00:15:11,840  -->  00:15:13,560
所以它是个近似

367
00:15:13,600  -->  00:15:14,960
好 我们看这时候呢

368
00:15:15,000  -->  00:15:22,000
A是7  B是8  E是5

369
00:15:22,040  -->  00:15:25,080
那唯一变化的就是这个C

370
00:15:25,120  -->  00:15:27,880
那它是9 这几个我选择下来呢

371
00:15:27,920  -->  00:15:33,120
这个E是最早的一个 我把它替换

372
00:15:33,160  -->  00:15:35,480
那这是替换之后的结果

373
00:15:35,520  -->  00:15:37,000
那我们看到在这里头呢

374
00:15:37,040  -->  00:15:39,720
它的缺页次数是三次

375
00:15:39,760  -->  00:15:41,800
和我们前边说到的

376
00:15:41,840  -->  00:15:44,360
先进先出算法要好很多

377
00:15:44,400  -->  00:15:47,920
和最优算法比较它又多一次

378
00:15:47,960  -->  00:15:51,640
那这是最近最久未使用算法

379
00:15:51,680  -->  00:15:53,600
那我们看到 实际上它处理呢

380
00:15:53,640  -->  00:15:55,680
是比较复杂的 在缺页的时候

381
00:15:55,720  -->  00:15:57,440
我要把所有内存的页面

382
00:15:57,480  -->  00:16:00,520
全部去统计一遍 那这个统计呢

383
00:16:00,560  -->  00:16:02,960
有可能你是在缺页的时候

384
00:16:03,000  -->  00:16:03,880
你再来做这个统计

385
00:16:03,920  -->  00:16:04,920
你已经统计不出来了

386
00:16:04,960  -->  00:16:05,960
所以这个统计呢

387
00:16:06,000  -->  00:16:08,320
应该是落实到你每一次访问的时候

388
00:16:08,360  -->  00:16:10,280
你才有可能统计得出来

389
00:16:10,320  -->  00:16:11,680
好 那这个呢

390
00:16:11,720  -->  00:16:14,680
我们就说到下一个它的实现办法

391
00:16:14,720  -->  00:16:15,800
第一种实现办法呢

392
00:16:15,840  -->  00:16:20,200
是我构造一个页面的链表

393
00:16:20,240  -->  00:16:21,600
那在这个链表里头呢

394
00:16:21,640  -->  00:16:23,920
它的排列顺序是按照

395
00:16:23,960  -->  00:16:28,520
最近一次访问的时间来排序的

396
00:16:28,560  -->  00:16:31,720
然后是链表的首结点

397
00:16:31,760  -->  00:16:33,440
是最近被访问过的

398
00:16:33,480  -->  00:16:38,560
链表的尾结点是最久未使用的页面

399
00:16:38,600  -->  00:16:40,960
好 然后在这里访问页面的时候呢

400
00:16:41,000  -->  00:16:42,000
每一次访问

401
00:16:42,040  -->  00:16:44,440
我都把访问到的那个页面

402
00:16:44,480  -->  00:16:48,280
把它从这个队列链表里摘出来

403
00:16:48,320  -->  00:16:51,720
放到它的链表首部

404
00:16:51,760  -->  00:16:53,520
然后缺页的时候怎么办呢

405
00:16:53,560  -->  00:16:55,760
缺页的时候我从最后一个

406
00:16:55,800  -->  00:16:58,000
来作为我选的这个缺页

407
00:16:58,040  -->  00:17:00,800
不像我们刚才给的那个表里头

408
00:17:00,840  -->  00:17:02,280
我是到每次缺页的时候

409
00:17:02,320  -->  00:17:04,000
再把那些重新计算一遍

410
00:17:04,040  -->  00:17:06,440
而把这件事情落实到平时当中

411
00:17:06,480  -->  00:17:09,280
每一次访问的时候来做这件事情

412
00:17:09,320  -->  00:17:10,200
但是这样做呢

413
00:17:10,240  -->  00:17:11,800
实际上你每一次访问的时候

414
00:17:11,840  -->  00:17:14,680
它的开销是很大的

415
00:17:14,720  -->  00:17:16,520
好 再一种做法呢

416
00:17:16,560  -->  00:17:19,720
是说我做成一个活动的页面栈

417
00:17:19,760  -->  00:17:20,760
思路都是一样的

418
00:17:20,800  -->  00:17:24,400
只是实现的手段有一些区别

419
00:17:24,440  -->  00:17:26,800
那访问的时候我把这个页号呢

420
00:17:26,840  -->  00:17:28,200
压到栈点

421
00:17:28,240  -->  00:17:30,920
同时压完之后我要把栈内相同

422
00:17:30,960  -->  00:17:32,600
也就是说 以前访问到的

423
00:17:32,640  -->  00:17:34,560
同一个页面的 过去的情况

424
00:17:34,600  -->  00:17:36,760
我就把它去掉了

425
00:17:36,800  -->  00:17:38,680
把这个结点从这里抽出来

426
00:17:38,720  -->  00:17:39,920
实际上这还是维护了

427
00:17:39,960  -->  00:17:41,320
跟前边一样的一个栈

428
00:17:41,360  -->  00:17:43,480
只是它做法是压进去之后

429
00:17:43,520  -->  00:17:44,880
把相同的页号抽出来

430
00:17:44,920  -->  00:17:47,600
那这时候我的链表的维护变少了

431
00:17:47,640  -->  00:17:48,680
但实际上这时候呢

432
00:17:48,720  -->  00:17:49,920
你压进去一个之后

433
00:17:49,960  -->  00:17:52,440
你要把整个这个队列呢

434
00:17:52,480  -->  00:17:55,040
完全的搜索一遍 去掉重复的

435
00:17:55,080  -->  00:17:57,240
实际上这个工作量仍然是很大的

436
00:17:57,280  -->  00:17:58,800
好 缺页的时候呢

437
00:17:58,840  -->  00:18:02,240
我从这个栈底的页面

438
00:18:02,280  -->  00:18:04,920
把它作为我被置换的页面

439
00:18:04,960  -->  00:18:06,240
好 那这时候呢

440
00:18:06,280  -->  00:18:13,200
说LRU算法它最大的问题是开销大

441
00:18:13,240  -->  00:18:15,440
那我们下边需要解决的就是

442
00:18:15,480  -->  00:18:18,880
我如何能让这件事情开销变的小

443
00:18:18,920  -->  00:18:20,120
我们先来看一下它到底

444
00:18:20,160  -->  00:18:21,680
都有些什么样的开销

445
00:18:21,720  -->  00:18:24,480
那我们用栈的方式来实现

446
00:18:24,520  -->  00:18:26,720
我们的最近最久未使用算法

447
00:18:26,760  -->  00:18:29,000
看实施的过程是个啥样子

448
00:18:29,040  -->  00:18:31,320
那我们前边说

449
00:18:31,360  -->  00:18:33,680
在最近最久未使用算法里头

450
00:18:33,720  -->  00:18:34,800
前面那个示例的时候

451
00:18:34,840  -->  00:18:36,640
我在访问的时候没有做任何事情

452
00:18:36,680  -->  00:18:38,240
现在我们把那个统计的事情

453
00:18:38,280  -->  00:18:39,960
放到你访问的时候来做

454
00:18:40,000  -->  00:18:41,440
那就会变成什么样子呢

455
00:18:41,480  -->  00:18:43,080
首先访问第一个页面

456
00:18:43,120  -->  00:18:45,360
那这时候我维护这个栈

457
00:18:45,400  -->  00:18:47,080
这里头只有一个元素

458
00:18:47,120  -->  00:18:49,840
好 我访问第二个页面的时候

459
00:18:49,880  -->  00:18:52,360
我就把这个页面作为压下一格

460
00:18:52,400  -->  00:18:55,200
在上边加上你刚才访问的这个页面

461
00:18:55,240  -->  00:18:58,640
那这就是这个栈里就有两个了

462
00:18:58,680  -->  00:19:02,040
访问第三步的时候 我再复制一遍

463
00:19:02,080  -->  00:19:05,680
然后把新访问的这个页面放到栈顶

464
00:19:05,720  -->  00:19:09,840
再访问B 第四次的时候再压栈

465
00:19:09,880  -->  00:19:13,520
这时候是刚开始没有缺页的情况

466
00:19:13,560  -->  00:19:15,680
缺页的时候访问E的时候

467
00:19:15,720  -->  00:19:18,560
它出现缺页 缺页的时候怎么办呢

468
00:19:18,600  -->  00:19:20,000
我们从这里头这个栈里头

469
00:19:20,040  -->  00:19:23,400
把最底下的那一个E

470
00:19:23,440  -->  00:19:27,600
这个C拿出来 把它置换掉

471
00:19:27,640  -->  00:19:29,400
然后把它换成E

472
00:19:29,440  -->  00:19:31,080
这个栈就是把底下那个取掉

473
00:19:31,120  -->  00:19:32,160
在顶上加一个

474
00:19:32,200  -->  00:19:34,080
实际上这个C在哪呢 在这个地方

475
00:19:34,120  -->  00:19:35,280
换完之后这个结果

476
00:19:35,320  -->  00:19:37,840
就把这个E换到C那去

477
00:19:37,880  -->  00:19:39,480
好 这是第一次

478
00:19:39,520  -->  00:19:41,000
那实际上我们在前边做些什么

479
00:19:41,040  -->  00:19:42,400
在这里维护这个栈

480
00:19:42,440  -->  00:19:44,960
是你平时访问的时候的开销

481
00:19:45,000  -->  00:19:47,040
好 正经到这缺页的时候

482
00:19:47,080  -->  00:19:48,720
我只需要从这里取出一个

483
00:19:48,760  -->  00:19:50,040
在栈顶再加一个

484
00:19:50,080  -->  00:19:52,360
那开销比我们前边做的时候呢

485
00:19:52,400  -->  00:19:54,480
已经要省事很多了

486
00:19:54,520  -->  00:19:58,120
好 再是访问B 那这时候呢

487
00:19:58,160  -->  00:20:01,360
从这里抽出来 把它放到栈顶

488
00:20:01,400  -->  00:20:04,400
这是你平常访问的时候需要的开销

489
00:20:04,440  -->  00:20:06,280
然后再访问A的时候呢

490
00:20:06,320  -->  00:20:08,560
那抽出来 把它放到栈顶

491
00:20:08,600  -->  00:20:10,000
那这是从最底下抽出来的

492
00:20:10,040  -->  00:20:13,240
所以移动的区域就会比较长

493
00:20:13,280  -->  00:20:16,520
然后再访问B的时候呢 一样的

494
00:20:16,560  -->  00:20:19,360
这时候抽出一个来放到栈顶

495
00:20:19,400  -->  00:20:23,080
好 再访问C的时候又出现缺页了

496
00:20:23,120  -->  00:20:24,520
那这时候怎么办

497
00:20:24,560  -->  00:20:28,400
把这D拽到最底下 把它置换出去

498
00:20:28,440  -->  00:20:31,040
然后把C放到D的位置

499
00:20:31,080  -->  00:20:36,160
那这是置换完的结果

500
00:20:36,200  -->  00:20:37,720
把C放出去

501
00:20:37,760  -->  00:20:41,600
好 然后再来 这地方呢

502
00:20:41,640  -->  00:20:45,560
到下一步再访问D的时候又缺页

503
00:20:45,600  -->  00:20:47,960
好 把这个E挪出去

504
00:20:48,000  -->  00:20:49,640
把这个D放到栈顶

505
00:20:49,680  -->  00:20:52,600
那这就变成这样了

506
00:20:52,640  -->  00:20:54,560
好 置换完的结果

507
00:20:54,600  -->  00:20:57,200
跟我们上一个呢 是完全一样的

508
00:20:57,240  -->  00:20:58,200
但是这时候呢

509
00:20:58,240  -->  00:21:00,480
我们跟前边的做法有什么区别

510
00:21:00,520  -->  00:21:03,280
前边的做法我到缺页的时候挨个去查

511
00:21:03,320  -->  00:21:06,000
现在我在每次的访问的时候呢

512
00:21:06,040  -->  00:21:07,520
做一些记录

513
00:21:07,560  -->  00:21:08,880
缺页的时候我只需要看一下

514
00:21:08,920  -->  00:21:11,360
这个数据结构我就可以换了

515
00:21:11,400  -->  00:21:12,520
那这种做法呢

516
00:21:12,560  -->  00:21:14,800
我们看到平时的这个开销是很大的

517
00:21:14,840  -->  00:21:16,280
特别是在这个地方

518
00:21:16,320  -->  00:21:18,720
你要把这个栈整个捋一遍 移一遍

519
00:21:18,760  -->  00:21:21,000
然后把最底下的那个挪到最上边来

520
00:21:21,040  -->  00:21:23,800
这个时候的开销确实是很大

521
00:21:23,840  -->  00:21:25,600
好 那接下来呢

522
00:21:25,640  -->  00:21:27,560
我们还会再进一步的去讨论

523
00:21:27,600  -->  00:21:31,640
我怎么把这个算法做进一步的近似

524
00:21:31,680  -->  00:21:36,160
使得它访问的特征不是太差

525
00:21:36,200  -->  00:21:37,720
但是它的开销呢

526
00:21:37,760  -->  00:21:38,760
会大幅度的减少

527
00:21:38,800  -->  00:21:38,840