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

1
00:00:06,880   -->   00:00:09,840
接下来我们介绍时钟置换算法

2
00:00:09,880   -->   00:00:14,040
和最不常用置换算法

3
00:00:14,080   -->   00:00:15,960
这两个算法呢实际上是对

4
00:00:16,000   -->   00:00:21,360
前面的FIFO和LRU呢做的一些简化

5
00:00:21,400   -->   00:00:25,400
时钟置换算法呢是对这个

6
00:00:25,440   -->   00:00:28,840
LRU考察的是过去一段时间

7
00:00:28,880   -->   00:00:31,440
而现在在这里头呢 它是把

8
00:00:31,480   -->   00:00:37,360
在FIFO完全不考虑过去的访问情况

9
00:00:37,400   -->   00:00:39,680
变成是在这里呢有一定的考虑

10
00:00:39,720   -->   00:00:43,440
但又不像LRU呢那样考虑的那么长

11
00:00:43,480   -->   00:00:44,320
所以这时候呢

12
00:00:44,360   -->   00:00:46,880
在它俩之间做了一个折中

13
00:00:46,920   -->   00:00:50,040
而最不常用算法呢实际上是从

14
00:00:50,080   -->   00:00:52,000
考察过去这个间隔的时间

15
00:00:52,040   -->   00:00:55,840
变成是考察过去的访问次数

16
00:00:55,880   -->   00:00:57,120
时钟置换算法呢

17
00:00:57,160   -->   00:00:59,280
它的基本思路呢很简单

18
00:00:59,320   -->   00:01:03,640
就是对页面的访问情况进行大致的统计

19
00:01:03,680   -->   00:01:07,800
因为我LRU呢统计过于详细过于细致

20
00:01:07,840   -->   00:01:10,520
以至于开销太大 那我只做粗略统计

21
00:01:10,560   -->   00:01:12,080
那所谓的粗略统计呢

22
00:01:12,120   -->   00:01:14,840
它只是统计过去一段时间这个页面

23
00:01:14,880   -->   00:01:17,800
是否被访问过 访问过我留下

24
00:01:17,840   -->   00:01:20,400
没访问过的我就按照进来的先后顺序

25
00:01:20,440   -->   00:01:24,040
或者说它按照现有的顺序来做排序了

26
00:01:24,080   -->   00:01:26,320
那它在这里头 为了做这件事情

27
00:01:26,360   -->   00:01:28,880
它首先对数据结构做了一些改动

28
00:01:28,920   -->   00:01:31,960
页表项里头增加了一个访问位

29
00:01:32,000   -->   00:01:33,440
这个访问位呢用来描述

30
00:01:33,480   -->   00:01:36,600
在过去一段时间里头 是否被访问过

31
00:01:36,640   -->   00:01:37,960
而过去一段时间呢

32
00:01:38,000   -->   00:01:41,120
是靠这个指针来约定的

33
00:01:41,160   -->   00:01:43,520
那这个指针怎么约定过去一段时间呢

34
00:01:43,560   -->   00:01:46,720
它把这些页面组织成一个环形链表

35
00:01:46,760   -->   00:01:47,840
然后这个指针呢

36
00:01:47,880   -->   00:01:52,440
是在环形链表上进行周期性的循环

37
00:01:52,480   -->   00:01:55,840
这也是我们这个时钟这个词的来历

38
00:01:55,880   -->   00:01:57,800
看上去呢像一个钟表

39
00:01:57,840   -->   00:01:59,840
好 那在这里少的时候

40
00:01:59,880   -->   00:02:02,280
它是去看访问过的留下

41
00:02:02,320   -->   00:02:05,760
没访问过的它就按照链表里的顺序

42
00:02:05,800   -->   00:02:08,000
进行顺序的置换了

43
00:02:08,040   -->   00:02:09,200
那这是它的数据结构

44
00:02:09,240   -->   00:02:10,840
它的算法怎么做的呢

45
00:02:10,880   -->   00:02:13,520
是访问页面的时候

46
00:02:13,560   -->   00:02:17,160
那你要在页表项里记录它的访问情况

47
00:02:17,200   -->   00:02:20,000
也就是说访问过 我把相应的访问位置1

48
00:02:20,040   -->   00:02:22,800
没访问的那我就不做处理

49
00:02:22,840   -->   00:02:25,320
好 再有一个呢就是缺页的时候

50
00:02:25,360   -->   00:02:26,320
缺页的时候

51
00:02:26,360   -->   00:02:29,960
它从指针的位置开始顺序查找

52
00:02:30,000   -->   00:02:32,040
查找在上一次扫过

53
00:02:32,080   -->   00:02:34,200
到现在这一次扫描的时候

54
00:02:34,240   -->   00:02:35,840
它是否被访问过

55
00:02:35,880   -->   00:02:37,000
如果没访问过那就是

56
00:02:37,040   -->   00:02:38,960
在过去这段时间里头没有访问

57
00:02:39,000   -->   00:02:42,240
对于这些呢 它就可以对它进行置换

58
00:02:42,280   -->   00:02:43,560
找到第一个作为它的置换

59
00:02:43,600   -->   00:02:46,600
所以这儿呢它也有FIFO的那种思路

60
00:02:46,640   -->   00:02:48,440
好 那这种做法呢

61
00:02:48,480   -->   00:02:52,800
它的特征是在LRU和FIFO之间做折中

62
00:02:52,840   -->   00:02:55,680
那所谓的折中是在于

63
00:02:55,720   -->   00:02:56,880
    

64
00:02:56,920   -->   00:03:00,960
它对过去的访问情况有考虑

65
00:03:01,000   -->   00:03:02,160
做了统计

66
00:03:02,200   -->   00:03:05,280
所以它不像FIFO完全不考虑

67
00:03:05,320   -->   00:03:06,880
这里的访问情况

68
00:03:06,920   -->   00:03:08,200
然后再有一个呢

69
00:03:08,240   -->   00:03:11,160
它又不像LRU考虑的很详细

70
00:03:11,200   -->   00:03:13,640
FIFO里说 只是说在过去一段时间里头

71
00:03:13,680   -->   00:03:15,560
没有访问的那它就做置换了

72
00:03:15,600   -->   00:03:17,800
这个时候呢如果说你所有都没访问

73
00:03:17,840   -->   00:03:20,680
那它就退化成是FIFO了

74
00:03:20,720   -->   00:03:23,120
那具体说起来呢是这样的

75
00:03:23,160   -->   00:03:24,440
我们怎么来实现呢

76
00:03:24,480   -->   00:03:26,360
装入一个页面的时候

77
00:03:26,400   -->   00:03:28,760
那把它的访问位清0

78
00:03:28,800   -->   00:03:29,640
  

79
00:03:29,680   -->   00:03:33,120
然后访问的时候呢把访问位置1

80
00:03:33,160   -->   00:03:36,080
那你在执行的过程当中访问了哪些页面

81
00:03:36,120   -->   00:03:40,480
你就把哪些页面的标志位置为1

82
00:03:40,520   -->   00:03:42,600
好 出现缺页的时候我怎么处理呢

83
00:03:42,640   -->   00:03:45,920
出现缺页的时候从当前的指针位置

84
00:03:45,960   -->   00:03:48,560
开始扫描环形链表 检查

85
00:03:48,600   -->   00:03:49,920
如果访问位为0

86
00:03:49,960   -->   00:03:51,960
那这一页呢是我可以置换的

87
00:03:52,000   -->   00:03:53,360
那我直接置换 好

88
00:03:53,400   -->   00:03:55,960
这个指针移到下一个地方就结束了

89
00:03:56,000   -->   00:03:58,600
好 如果说页面是访问过的

90
00:03:58,640   -->   00:03:59,360
那这个时候呢

91
00:03:59,400   -->   00:04:01,600
我就去把它的标志位改成0

92
00:04:01,640   -->   00:04:03,560
也就是说我从现在这个点开始

93
00:04:03,600   -->   00:04:05,600
进行一次新的计时

94
00:04:05,640   -->   00:04:08,160
好 并且把指针移向下一个页面

95
00:04:08,200   -->   00:04:09,640
如果下一个页面仍然是访问过的

96
00:04:09,680   -->   00:04:10,720
继续往后找

97
00:04:10,760   -->   00:04:13,440
一直到找到一个可以置换的页面

98
00:04:13,480   -->   00:04:15,000
找到一个访问位为0的

99
00:04:15,040   -->   00:04:17,160
按照头一条进行置换

100
00:04:17,200   -->   00:04:19,520
那这是呢它的处理的办法

101
00:04:19,560   -->   00:04:20,640
  

102
00:04:20,680   -->   00:04:23,520
那我们用一个图示来说明这个过程

103
00:04:23,560   -->   00:04:27,520
那这是一个内存当中的物理页面

104
00:04:27,560   -->   00:04:30,120
它把它组织成一个环形

105
00:04:30,160   -->   00:04:31,640
然后在这儿呢加了一个指针

106
00:04:31,680   -->   00:04:33,280
开始的时候指向这儿了

107
00:04:33,320   -->   00:04:35,560
好 如果在这里头我们访问某一个页面

108
00:04:35,600   -->   00:04:38,880
在这儿 它把这访问位置1

109
00:04:38,920   -->   00:04:41,040
好 如果说已经置1的你再访问

110
00:04:41,080   -->   00:04:43,160
那这个1就不动就行了

111
00:04:43,200   -->   00:04:45,840
然后在我发生缺页的时候

112
00:04:45,880   -->   00:04:47,880
那这一页没在这里头那我怎么办呢

113
00:04:47,920   -->   00:04:50,000
就从这指针的位置开始扫描

114
00:04:50,040   -->   00:04:54,280
找访问位为0的 访问位为1的我清0

115
00:04:54,320   -->   00:04:56,040
那这个时候呢应该是找到这儿

116
00:04:56,080   -->   00:04:59,080
我们看 好 这儿清0 这儿清0

117
00:04:59,120   -->   00:05:02,200
然后到这儿清0 这地方清0

118
00:05:02,240   -->   00:05:04,120
找到这个地方它停下来

119
00:05:04,160   -->   00:05:04,920
好 这个页面呢

120
00:05:04,960   -->   00:05:07,120
是我们可以用来做置换的

121
00:05:07,160   -->   00:05:09,760
把它置换成新的页面

122
00:05:09,800   -->   00:05:12,680
这个缺页中断呢就算处理完了

123
00:05:12,720   -->   00:05:15,920
再次缺页的时候 它继续往后扫

124
00:05:15,960   -->   00:05:19,240
到这儿又找着一个再做替换

125
00:05:19,280   -->   00:05:20,560
它就周而复始的

126
00:05:20,600   -->   00:05:22,360
那这样的话我们就可以使程序

127
00:05:22,400   -->   00:05:24,240
在正常情况下可以访问

128
00:05:24,280   -->   00:05:26,920
缺页的时候我可以找到一页替换

129
00:05:26,960   -->   00:05:28,720
然后继续执行

130
00:05:28,760   -->   00:05:32,200
那这是时钟置换算法的大致的过程

131
00:05:32,240   -->   00:05:35,000
那我们下面用一个更详细的表格

132
00:05:35,040   -->   00:05:37,560
来说明它处理的情况

133
00:05:37,600   -->   00:05:38,800
这是我们前面例子里

134
00:05:38,840   -->   00:05:41,040
说到的一个访问序列

135
00:05:41,080   -->   00:05:43,320
然后我也给它分配了四个页面

136
00:05:43,360   -->   00:05:45,360
但在这里呢我页表项里头

137
00:05:45,400   -->   00:05:48,320
我记录了一下它的访问的情况

138
00:05:48,360   -->   00:05:50,400
好 那在这里起始的时候

139
00:05:50,440   -->   00:05:51,800
它们都没有访问过

140
00:05:51,840   -->   00:05:53,120
那访问第一个页面

141
00:05:53,160   -->   00:05:55,200
那这时候在内存里头访问的是c

142
00:05:55,240   -->   00:05:58,880
好 那这时候c的访问位是置1的

143
00:05:58,920   -->   00:06:02,480
好 再往后走 这回访问的是a

144
00:06:02,520   -->   00:06:05,680
那这个地方呢访问位置1

145
00:06:05,720   -->   00:06:08,040
再访问 下一步访问d

146
00:06:08,080   -->   00:06:13,600
这里d呢它置1 好 再访问b

147
00:06:13,640   -->   00:06:18,400
那到这上头b置1 再往下走

148
00:06:18,440   -->   00:06:20,960
访问e的时候那这里没有了

149
00:06:21,000   -->   00:06:22,440
那这个时候会出现缺页

150
00:06:22,480   -->   00:06:24,640
缺页的时候呢 那我缺页的处理是什么

151
00:06:24,680   -->   00:06:26,320
那个指针 这个蓝颜色

152
00:06:26,360   -->   00:06:28,320
表示当前指针所在的位置

153
00:06:28,360   -->   00:06:30,280
好 那从这儿开始扫描

154
00:06:30,320   -->   00:06:32,360
是1的改成0

155
00:06:32,400   -->   00:06:33,720
  

156
00:06:33,760   -->   00:06:36,720
好 找到下一个 再是1 再继续改成0

157
00:06:36,760   -->   00:06:38,240
再是1再改成0

158
00:06:38,280   -->   00:06:39,680
全是1改了一圈之后

159
00:06:39,720   -->   00:06:43,360
回到最顶上它发现了一个不是1的

160
00:06:43,400   -->   00:06:46,920
那这时候我把它替换成我的缺页这个

161
00:06:46,960   -->   00:06:48,560
OK 这样的话我把它改成1

162
00:06:48,600   -->   00:06:49,920
改完之后的结果呢

163
00:06:49,960   -->   00:06:53,360
在这儿 a被替换成e了

164
00:06:53,400   -->   00:06:54,720
好 那这个时候呢

165
00:06:54,760   -->   00:06:56,680
我这个缺页中断就算处理完了

166
00:06:56,720   -->   00:07:00,360
好 再往下继续执行 访问b

167
00:07:00,400   -->   00:07:04,120
这个时候呢又改成1 再访问a

168
00:07:04,160   -->   00:07:04,880
  

169
00:07:04,920   -->   00:07:07,320
那这个时候呢a不在里头又发生缺页

170
00:07:07,360   -->   00:07:09,720
缺页的时候我就要从这里继续找

171
00:07:09,760   -->   00:07:11,160
当前在这个b的位置

172
00:07:11,200   -->   00:07:13,040
这个b是1改成0

173
00:07:13,080   -->   00:07:16,600
那下一个就可以了 这时候

174
00:07:16,640   -->   00:07:19,400
它处理是先改0到这儿

175
00:07:19,440   -->   00:07:21,440
这是找到的一项改成1

176
00:07:21,480   -->   00:07:23,760
OK把c换成了a

177
00:07:23,800   -->   00:07:25,960
那处理完的结果呢在这儿

178
00:07:26,000   -->   00:07:27,360
c换成a 

179
00:07:27,400   -->   00:07:28,560
  

180
00:07:28,600   -->   00:07:31,760
好 那这时候呢执行到这儿继续往下走

181
00:07:31,800   -->   00:07:33,480
访问b b在里头

182
00:07:33,520   -->   00:07:36,680
把它的0改成1就行了

183
00:07:36,720   -->   00:07:40,600
好 再访问c那它又会出现缺页

184
00:07:40,640   -->   00:07:41,680
缺页之后呢

185
00:07:41,720   -->   00:07:43,320
在这个页表项里头进行扫描

186
00:07:43,360   -->   00:07:44,720
这个地方正好它就是0

187
00:07:44,760   -->   00:07:46,160
所以这项直接可以替换

188
00:07:46,200   -->   00:07:50,280
替换完了之后的结果呢在这儿

189
00:07:50,320   -->   00:07:51,560
  

190
00:07:51,600   -->   00:07:53,960
好 它换成c

191
00:07:54,000   -->   00:07:56,640
那到这儿之后把这儿换成c

192
00:07:56,680   -->   00:07:58,760
好 我们在这里呢继续往下走

193
00:07:58,800   -->   00:07:59,720
这时候看到

194
00:07:59,760   -->   00:08:01,560
往d的时候这里仍然没有

195
00:08:01,600   -->   00:08:02,960
它还会再出现缺页

196
00:08:03,000   -->   00:08:05,520
那这个缺页呢我会再继续找

197
00:08:05,560   -->   00:08:06,920
这又是一圈全是1

198
00:08:06,960   -->   00:08:08,680
全部改成0又回到这儿

199
00:08:08,720   -->   00:08:09,240
  

200
00:08:09,280   -->   00:08:13,160
第二步 第三步 第四步 回到这儿

201
00:08:13,200   -->   00:08:15,880
那应该是把e是我可以选择的

202
00:08:15,920   -->   00:08:20,360
把e换成d 这是换完之后的结果

203
00:08:20,400   -->   00:08:21,600
好 到这个地方呢

204
00:08:21,640   -->   00:08:25,440
我们就把这个时钟置换算法的

205
00:08:25,480   -->   00:08:28,400
基本流程说完了

206
00:08:28,440   -->   00:08:29,640
那在这里头呢

207
00:08:29,680   -->   00:08:33,120
我们考虑到的仅仅是它访问的情况

208
00:08:33,160   -->   00:08:35,280
如果说你访问的那一页

209
00:08:35,320   -->   00:08:36,840
你是被修改过的

210
00:08:36,880   -->   00:08:39,600
那么这时候呢它缺页中断的处理时间

211
00:08:39,640   -->   00:08:42,440
就会是当前这个时间的至少是2倍

212
00:08:42,480   -->   00:08:44,080
你需要把原来的内容写出去

213
00:08:44,120   -->   00:08:46,240
再把新的内容读进来

214
00:08:46,280   -->   00:08:47,200
那这个过程呢

215
00:08:47,240   -->   00:08:49,200
在缺页中断这段时间太长

216
00:08:49,240   -->   00:08:51,080
那我们需要对它做改进

217
00:08:51,120   -->   00:08:53,640
那这个地方就是改进的时钟算法

218
00:08:53,680   -->   00:08:57,360
它的基本思路呢是说对有修改的地方

219
00:08:57,400   -->   00:09:00,280
这些缺页的开销呢我把它减小

220
00:09:00,320   -->   00:09:03,280
它怎么减小呢 就是如果你有修改

221
00:09:03,320   -->   00:09:06,440
那我这时候跳过这一页我不做置换

222
00:09:06,480   -->   00:09:09,040
那在系统里呢它会定期的

223
00:09:09,080   -->   00:09:11,680
把这些修改过的呢写到外存里头去

224
00:09:11,720   -->   00:09:12,360
那在这儿呢

225
00:09:12,400   -->   00:09:14,400
我们这个细节不再仔细讨论

226
00:09:14,440   -->   00:09:16,120
好 它的做法是什么呢

227
00:09:16,160   -->   00:09:19,480
在页表项里头加上一个修改位

228
00:09:19,520   -->   00:09:23,120
然后在你做访问的时候进行修改

229
00:09:23,160   -->   00:09:26,640
那我们前面说有一个访问位

230
00:09:26,680   -->   00:09:28,760
是你在访问的时候它被置1

231
00:09:28,800   -->   00:09:31,000
那这里头又加了一个修改位

232
00:09:31,040   -->   00:09:32,280
那这时候我在访问的时候

233
00:09:32,320   -->   00:09:35,960
就有两位来做状态的变化

234
00:09:36,000   -->   00:09:38,680
你是读那只是改访问位

235
00:09:38,720   -->   00:09:40,160
修改位还是0

236
00:09:40,200   -->   00:09:42,840
如果说你是写 那这两位同时改

237
00:09:42,880   -->   00:09:44,720
好 缺页的时候呢

238
00:09:44,760   -->   00:09:46,880
我仍然是跟原来一样去找

239
00:09:46,920   -->   00:09:48,720
但这时候找的过程当中呢

240
00:09:48,760   -->   00:09:51,640
修改过的页面它是直接跳过的

241
00:09:51,680   -->   00:09:53,920
那具体说起来是这样的

242
00:09:53,960   -->   00:09:56,280
这是它指针扫描的时候

243
00:09:56,320   -->   00:09:59,680
它改状态位的方法

244
00:09:59,720   -->   00:10:00,920
如果两个都是0

245
00:10:00,960   -->   00:10:03,600
那这时候呢肯定是前一轮里头

246
00:10:03,640   -->   00:10:06,880
它没有访问过 那这时候我可以替换

247
00:10:06,920   -->   00:10:09,440
好 剩下的三种情况访问位为0

248
00:10:09,480   -->   00:10:10,400
修改位为1

249
00:10:10,440   -->   00:10:11,720
那这时候也就相当于

250
00:10:11,760   -->   00:10:13,680
我这里前一轮转过的时候

251
00:10:13,720   -->   00:10:15,360
修改过的地方你还没写出去

252
00:10:15,400   -->   00:10:17,080
那这时候我把它清0

253
00:10:17,120   -->   00:10:17,760
  

254
00:10:17,800   -->   00:10:19,080
好 通常情况在这个过程里

255
00:10:19,120   -->   00:10:21,480
会启动往外存里写

256
00:10:21,520   -->   00:10:23,560
好 同时继续往下走

257
00:10:23,600   -->   00:10:25,360
那这两个情况呢

258
00:10:25,400   -->   00:10:27,320
访问位1 修改位为0

259
00:10:27,360   -->   00:10:29,280
那这时候呢 我把它改成0

260
00:10:29,320   -->   00:10:30,920
如果访问位两个都是1

261
00:10:30,960   -->   00:10:32,080
我把第一个改成1

262
00:10:32,120   -->   00:10:33,240
第二个继续留着

263
00:10:33,280   -->   00:10:34,560
那就会出现上面

264
00:10:34,600   -->   00:10:36,560
这个地方的这种情况

265
00:10:36,600   -->   00:10:39,360
好 在这儿也有一个示意图来说

266
00:10:39,400   -->   00:10:42,600
我们看在这儿多加了一位修改位

267
00:10:42,640   -->   00:10:45,960
那这个时候在那个指针扫描的时候

268
00:10:46,000   -->   00:10:48,000
会是什么样的呢

269
00:10:48,040   -->   00:10:51,720
把1改成0 两个1

270
00:10:51,760   -->   00:10:52,800
好 这找到一个

271
00:10:52,840   -->   00:10:54,960
这是我们可以替换的 两个都是0

272
00:10:55,000   -->   00:10:57,200
好 我把它改成我要的页面

273
00:10:57,240   -->   00:10:59,720
如果说在下一次再出现缺页的时候

274
00:10:59,760   -->   00:11:02,480
我从这儿继续往下找

275
00:11:02,520   -->   00:11:04,360
两个1的改过来

276
00:11:04,400   -->   00:11:06,360
那在这儿找到一个

277
00:11:06,400   -->   00:11:08,480
好 那我把它做替换

278
00:11:08,520   -->   00:11:12,360
好 那这样的话就是改进的时钟算法

279
00:11:12,400   -->   00:11:13,640
在这个算法里头呢

280
00:11:13,680   -->   00:11:15,280
它在缺页中断的时候

281
00:11:15,320   -->   00:11:16,560
对于修改过的页面

282
00:11:16,600   -->   00:11:19,400
它的处理呢速度会比原来快

283
00:11:19,440   -->   00:11:21,800
那你说在这里头 它快到底在哪呢

284
00:11:21,840   -->   00:11:23,000
一个是延迟之后

285
00:11:23,040   -->   00:11:25,360
后续有可能的改动的页面

286
00:11:25,400   -->   00:11:28,680
写出它可能会被合并和延时

287
00:11:28,720   -->   00:11:29,840
  

288
00:11:29,880   -->   00:11:31,640
好 这个地方也是把刚才

289
00:11:31,680   -->   00:11:36,480
加了改进的时钟算法它的执行过程

290
00:11:36,520   -->   00:11:39,120
那跟刚才的时钟算法不一样的地方

291
00:11:39,160   -->   00:11:41,280
这地方加了两个标志位了

292
00:11:41,320   -->   00:11:45,360
那处理的过程也是在前面类似的

293
00:11:45,400   -->   00:11:48,080
这是对c的访问是只读的

294
00:11:48,120   -->   00:11:50,920
好 那这个地方只是改成10

295
00:11:50,960   -->   00:11:54,680
对a的访问是写的

296
00:11:54,720   -->   00:11:57,840
好 那这时候把0改成11了

297
00:11:57,880   -->   00:12:01,360
好 然后再是d那是改成10

298
00:12:01,400   -->   00:12:02,880
  

299
00:12:02,920   -->   00:12:08,240
然后再是b 那是改成11

300
00:12:08,280   -->   00:12:11,360
再到e的时候它产生缺页了

301
00:12:11,400   -->   00:12:13,600
这时候我要去找一个页面

302
00:12:13,640   -->   00:12:15,200
可以来做替换的

303
00:12:15,240   -->   00:12:17,840
那怎么找呢 那做循环

304
00:12:17,880   -->   00:12:20,480
11的改成01 

305
00:12:20,520   -->   00:12:23,320
10的改成00

306
00:12:23,360   -->   00:12:25,960
那改一圈之后回来应该是找到c

307
00:12:26,000   -->   00:12:28,840
我们看一下它执行过程

308
00:12:28,880   -->   00:12:32,160
11改成10  11改成10

309
00:12:32,200   -->   00:12:35,200
10改成00  10改成00

310
00:12:35,240   -->   00:12:38,080
好 这个地方01改成00 

311
00:12:38,120   -->   00:12:39,560
好 最后找到这个地方

312
00:12:39,600   -->   00:12:41,600
那这一项是替换成1

313
00:12:41,640   -->   00:12:44,760
替换完的结果呢 是这儿

314
00:12:44,800   -->   00:12:49,840
好 那接下来再往下走

315
00:12:49,880   -->   00:12:51,680
那我们访问到这个地方是b

316
00:12:51,720   -->   00:12:52,840
我把b的标志改了

317
00:12:52,880   -->   00:12:54,000
在这个地方注意一下

318
00:12:54,040   -->   00:12:55,480
我这个地方加了两个星号

319
00:12:55,520   -->   00:12:57,840
实际上就相当于我在改标志的时候

320
00:12:57,880   -->   00:12:59,000
实际上这相应的内容

321
00:12:59,040   -->   00:13:00,840
并没有写到外存里头去

322
00:13:00,880   -->   00:13:02,960
需要系统里另外的部分呢

323
00:13:03,000   -->   00:13:04,000
来对这种情况做处理

324
00:13:04,040   -->   00:13:05,680
要不然的话这两者就不一样了

325
00:13:05,720   -->   00:13:06,440
  

326
00:13:06,480   -->   00:13:08,080
好 继续往后走

327
00:13:08,120   -->   00:13:11,680
a是写00改成11

328
00:13:11,720   -->   00:13:14,520
再有b再访问 这已经改过来了

329
00:13:14,560   -->   00:13:17,200
所以这时候页表项里内容没有做变化

330
00:13:17,240   -->   00:13:18,560
好 然后再是c

331
00:13:18,600   -->   00:13:20,280
这时候又产生缺页

332
00:13:20,320   -->   00:13:21,400
看到结果是什么

333
00:13:21,440   -->   00:13:23,240
这地方直接d 这地方是00

334
00:13:23,280   -->   00:13:25,120
我直接可以替换d

335
00:13:25,160   -->   00:13:30,800
OK 替换完的结果就是在这儿换成c

336
00:13:30,840   -->   00:13:34,080
好 上边的指这儿

337
00:13:34,120   -->   00:13:35,280
实际上刚替换完之后

338
00:13:35,320   -->   00:13:37,960
接下来它又访问d 还是产生缺页

339
00:13:38,000   -->   00:13:39,600
那这时候会找到哪儿呢

340
00:13:39,640   -->   00:13:41,320
这地方不是 这地方不是

341
00:13:41,360   -->   00:13:44,760
改过一圈之后回过身来会在b这个地方

342
00:13:44,800   -->   00:13:47,200
  

343
00:13:47,240   -->   00:13:54,200
01  00  00  00好再倒过来这改成00

344
00:13:54,240   -->   00:13:57,920
好 这时候找到b 替换

345
00:13:57,960   -->   00:14:00,880
那这是我们刚才说的时钟算法

346
00:14:00,920   -->   00:14:03,560
和改进的时钟算法

347
00:14:03,600   -->   00:14:07,200
那改进的地方就是对于写操作的页面

348
00:14:07,240   -->   00:14:12,680
它的置换会有一个稍微不一样的处理

349
00:14:12,720   -->   00:14:15,280
那接下来我们说最不常用算法

350
00:14:15,320   -->   00:14:18,440
这个算法也是对LRU的一种简化

351
00:14:18,480   -->   00:14:21,520
它所谓的简化呢就是它统计的依据

352
00:14:21,560   -->   00:14:23,960
不再是我们刚才说的时间

353
00:14:24,000   -->   00:14:27,120
时钟算法里修改或者是没修改的01状态

354
00:14:27,160   -->   00:14:28,600
它是在这里加了次数

355
00:14:28,640   -->   00:14:29,800
所以在这种情况下

356
00:14:29,840   -->   00:14:32,520
它的统计开销相对来说就会大一些

357
00:14:32,560   -->   00:14:34,440
那看一下它的具体怎么做的呢

358
00:14:34,480   -->   00:14:35,320
  

359
00:14:35,360   -->   00:14:36,760
它是在这里每一个页面

360
00:14:36,800   -->   00:14:38,360
加一个访问计数

361
00:14:38,400   -->   00:14:39,640
我们刚才说的访问位呢

362
00:14:39,680   -->   00:14:40,760
某种程度上来讲

363
00:14:40,800   -->   00:14:42,520
你也可以认为它是一个计数

364
00:14:42,560   -->   00:14:44,440
只是说这个计数

365
00:14:44,480   -->   00:14:47,760
它计的范围是比较小的

366
00:14:47,800   -->   00:14:49,040
只有0 1两种状态

367
00:14:49,080   -->   00:14:51,200
而我可以设置一个多位的计数

368
00:14:51,240   -->   00:14:54,240
这时候多位计数的话那它就会加1

369
00:14:54,280   -->   00:14:55,880
加1的操作会复杂

370
00:14:55,920   -->   00:14:58,360
但这时候呢我可以统计的更精确

371
00:14:58,400   -->   00:14:59,720
好 缺页的时候呢

372
00:14:59,760   -->   00:15:03,160
我置换那个计数最小的那一页

373
00:15:03,200   -->   00:15:04,040
那也就是说

374
00:15:04,080   -->   00:15:05,680
过去一段时间你访问最少的

375
00:15:05,720   -->   00:15:09,600
我认为它是这个需要置换的

376
00:15:09,640   -->   00:15:11,080
当然这时候也有可能有这种情况

377
00:15:11,120   -->   00:15:13,960
就是一个页刚拿进来没访问几次

378
00:15:14,000   -->   00:15:14,920
又把它置换出去

379
00:15:14,960   -->   00:15:17,560
这是它存在的一个麻烦

380
00:15:17,600   -->   00:15:19,720
它的问题是开销大 并且呢

381
00:15:19,760   -->   00:15:21,440
计数值还没长的很大的时候

382
00:15:21,480   -->   00:15:23,400
可能频繁的是这些页面

383
00:15:23,440   -->   00:15:24,840
刚拿进来又拿出去

384
00:15:24,880   -->   00:15:25,920
所以它的做法呢

385
00:15:25,960   -->   00:15:28,480
后续有一个改进就是对这个

386
00:15:28,520   -->   00:15:30,840
已经计了数的这些值比较大的

387
00:15:30,880   -->   00:15:32,800
它会定期做衰减右移

388
00:15:32,840   -->   00:15:34,960
那这样的话它计数值会变小

389
00:15:35,000   -->   00:15:37,200
用这种办法来做

390
00:15:37,240   -->   00:15:43,240
实际上这个LRU和LFU之间区别在哪

391
00:15:43,280   -->   00:15:47,640
LRU考察的是过去的未访问的时间

392
00:15:47,680   -->   00:15:50,640
这地方考察的是访问的次数

393
00:15:50,680   -->   00:15:52,400
这两者到底有啥区别呢

394
00:15:52,440   -->   00:15:56,720
因为这个统计时间我要去维护那个栈

395
00:15:56,760   -->   00:15:59,280
统计次数相对来说好弄点

396
00:15:59,320   -->   00:16:01,320
  

397
00:16:01,360   -->   00:16:05,920
我们也还是通过一个具体的例子来说

398
00:16:05,960   -->   00:16:07,440
这是我们刚才那个例子

399
00:16:07,480   -->   00:16:09,720
但是跟刚才那个不太一样的

400
00:16:09,760   -->   00:16:12,160
我们如果按原来那个序列的话

401
00:16:12,200   -->   00:16:13,000
它就太短了

402
00:16:13,040   -->   00:16:17,800
以至于LFU不足以显示它算法的特征

403
00:16:17,840   -->   00:16:20,440
那么在这儿呢给上边加了一个数值

404
00:16:20,480   -->   00:16:23,400
表示我多少次访问

405
00:16:23,440   -->   00:16:25,680
也就说原来我这一次访问的话是一次

406
00:16:25,720   -->   00:16:27,040
那我在这儿呢 统计了

407
00:16:27,080   -->   00:16:29,920
在这里访问过的它是有多少次

408
00:16:29,960   -->   00:16:31,200
好 我们在这里头呢

409
00:16:31,240   -->   00:16:33,760
这是实际分的四个页面

410
00:16:33,800   -->   00:16:36,920
假定初始的时候它的访问次数是这样

411
00:16:36,960   -->   00:16:40,200
那我们看执行的过程当中会是啥样的

412
00:16:40,240   -->   00:16:42,120
好 首先在访问的时候

413
00:16:42,160   -->   00:16:44,800
我要去修改每一个的计数

414
00:16:44,840   -->   00:16:47,360
比如说在这里头原来有6次

415
00:16:47,400   -->   00:16:49,720
那我在这一段时间里头呢

416
00:16:49,760   -->   00:16:50,880
它访问了7次

417
00:16:50,920   -->   00:16:51,880
好 那这样的话

418
00:16:51,920   -->   00:16:56,040
我就会把这个值6加7 13在这儿

419
00:16:56,080   -->   00:17:01,080
再往下走访问的时候a这里头有

420
00:17:01,120   -->   00:17:04,200
计数加上相应的值那这是加1

421
00:17:04,240   -->   00:17:08,040
好 在访问d的时候也是一样

422
00:17:08,080   -->   00:17:10,280
这地方2加14 16

423
00:17:10,320   -->   00:17:11,760
  

424
00:17:11,800   -->   00:17:16,200
再访问b再继续往上加变成10了

425
00:17:16,240   -->   00:17:17,960
再访问e的时候这里没有了

426
00:17:18,000   -->   00:17:22,040
那就会产生缺页 那缺页怎么办

427
00:17:22,080   -->   00:17:25,280
我去找我当前这些计数里最小的那个

428
00:17:25,320   -->   00:17:28,480
那是a 好 我把a替换成e

429
00:17:28,520   -->   00:17:29,840
那并且这时候

430
00:17:29,880   -->   00:17:31,200
替换完之后你访问多次

431
00:17:31,240   -->   00:17:32,480
那计数加这里头

432
00:17:32,520   -->   00:17:33,920
  

433
00:17:33,960   -->   00:17:38,160
继续往下到b这个地方又继续往上加

434
00:17:38,200   -->   00:17:39,280
那就会发现存在里头

435
00:17:39,320   -->   00:17:42,160
如果时间越长的话 这数会越加越大

436
00:17:42,200   -->   00:17:44,080
你加的越大你日后

437
00:17:44,120   -->   00:17:47,480
再被置换出去的机率也就会变小

438
00:17:47,520   -->   00:17:49,640
好 如果说你这时候访问的特征

439
00:17:49,680   -->   00:17:51,080
从一个区域变到另一个区域

440
00:17:51,120   -->   00:17:53,320
那么前一个区域里多次访问的页面

441
00:17:53,360   -->   00:17:55,160
有可能会保留很长的时间

442
00:17:55,200   -->   00:17:56,160
  

443
00:17:56,200   -->   00:17:58,320
好 然后再访问a

444
00:17:58,360   -->   00:18:00,200
那这时候前面没有了 缺页

445
00:18:00,240   -->   00:18:01,960
好 这时候找你最小的是哪个

446
00:18:02,000   -->   00:18:03,800
b把它换掉 

447
00:18:03,840   -->   00:18:05,200
  

448
00:18:05,240   -->   00:18:08,280
那这时候呢它的访问次数清0之后

449
00:18:08,320   -->   00:18:11,800
先换出来把它当前访问次数加上

450
00:18:11,840   -->   00:18:14,240
好 再往下一步呢 又访问b

451
00:18:14,280   -->   00:18:15,760
那这时候又没有了

452
00:18:15,800   -->   00:18:18,520
好 它又要有缺页

453
00:18:18,560   -->   00:18:21,200
在这里找 哪一个c

454
00:18:21,240   -->   00:18:24,760
它只有13次 好 最小的置换掉

455
00:18:24,800   -->   00:18:28,320
那这个地方就换成20次了

456
00:18:28,360   -->   00:18:30,080
这是我这里b的情况

457
00:18:30,120   -->   00:18:32,360
好 再过来访问c

458
00:18:32,400   -->   00:18:34,080
  

459
00:18:34,120   -->   00:18:37,040
那又是缺页 这里最小的是啥

460
00:18:37,080   -->   00:18:40,760
是16 把16置换掉

461
00:18:40,800   -->   00:18:42,280
那这时候有一个问题是说

462
00:18:42,320   -->   00:18:44,440
你这里写的数 好像你要想置换别的

463
00:18:44,480   -->   00:18:46,400
你这个数只能越写越大

464
00:18:46,440   -->   00:18:50,560
如果说你刚开始几次基本上会换一个

465
00:18:50,600   -->   00:18:51,920
  

466
00:18:51,960   -->   00:18:54,480
好 那这时候说 再访问d的时候

467
00:18:54,520   -->   00:18:58,440
这里最小的是什么 18  e

468
00:18:58,480   -->   00:18:58,960
换掉之后

469
00:18:59,000   -->   00:19:03,360
这是执行到这个时候的状态的结果

470
00:19:03,400   -->   00:19:06,200
那到这儿呢 我们可以看到这个

471
00:19:06,240   -->   00:19:09,280
时钟算法和最不常用算法

472
00:19:09,320   -->   00:19:10,840
这两个算法呢

473
00:19:10,880   -->   00:19:15,440
都是对LRU的某种程度的简化

474
00:19:15,480   -->   00:19:17,920
那简化之后呢 这个开销会小

475
00:19:17,960   -->   00:19:20,960
但是它统计的精度也会下降

476
00:19:21,000   -->   00:19:22,360
那这时候实际上我们在这里

477
00:19:22,400   -->   00:19:23,840
做这个置换算法的时候

478
00:19:23,880   -->   00:19:25,960
就是需要在这种

479
00:19:26,000   -->   00:19:30,480
近似的程度和它的准确性之间做折中

480
00:19:30,520   -->   00:19:32,320
必须是简化到足够的程度

481
00:19:32,360   -->   00:19:35,480
以便于我们在每一次调指令的时候

482
00:19:35,520   -->   00:19:37,000
都有很多的存储访问

483
00:19:37,040   -->   00:19:39,480
都能在很快的时间里头来实现

484
00:19:39,520   -->   00:19:40,640
或者我用硬件

485
00:19:40,680   -->   00:19:42,760
可以很方便简单地来实现

486
00:19:42,800   -->   00:19:47,240
那像这种情况 LFU就比较难实现了

487
00:19:47,280   -->   00:19:49,760
那为什么我们还在这儿会讨论呢

488
00:19:49,800   -->   00:19:51,440
实际上这个存储的访问呢

489
00:19:51,480   -->   00:19:53,960
它不仅仅是有CPU到内存

490
00:19:54,000   -->   00:19:57,560
也有我读硬盘的这种存储访问的情况

491
00:19:57,600   -->   00:19:59,120
这时候呢它时间长一些

492
00:19:59,160   -->   00:20:00,160
像这些算法呢

493
00:20:00,200   -->   00:20:04,080
在那个地方就相对来说就可以用了

494
00:20:04,120   -->   00:20:05,920
好 那这是我们说的

495
00:20:05,960   -->   00:20:06,920
  

496
00:20:06,960   -->   00:20:11,160
时钟算法和LFU最不常用算法的情况

497
00:20:11,200   -->   00:20:17,440


498
00:20:17,480   -->   00:20:23,840


499
00:20:23,880   -->   00:20:23,920