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

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

2
00:00:10,240  -->  00:00:11,400
那在前边讲的

3
00:00:11,440  -->  00:00:13,040
局部置换算法里头呢

4
00:00:13,080  -->  00:00:17,440
我们没有讨论分配给一个进程的

5
00:00:17,480  -->  00:00:19,080
物理页面数到底是多少

6
00:00:19,120  -->  00:00:20,680
而全局置换算法呢

7
00:00:20,720  -->  00:00:23,040
我们在这里需要考虑这个问题

8
00:00:23,080  -->  00:00:26,600
也就是说考虑到不同的进程之间

9
00:00:26,640  -->  00:00:30,120
它对内存需求量的这种差异性

10
00:00:30,160  -->  00:00:32,720
那具体做法呢 我们这给出了两种

11
00:00:32,760  -->  00:00:35,000
一种叫工作集 一种叫缺页率

12
00:00:35,040  -->  00:00:37,360
工作集置换算法你可以理解为

13
00:00:37,400  -->  00:00:39,280
是我们前边说到的

14
00:00:39,320  -->  00:00:42,320
最优算法在全局里的一种体现

15
00:00:42,360  -->  00:00:44,600
它们之间有一定的关系

16
00:00:44,640  -->  00:00:47,280
好 我们说在局部置换算法里头

17
00:00:47,320  -->  00:00:50,920
它没有考虑到不同进程之间的差异

18
00:00:50,960  -->  00:00:52,600
也就是说在某些情况下

19
00:00:52,640  -->  00:00:55,280
你可能多给进程增加一个物理页面

20
00:00:55,320  -->  00:00:57,440
可能缺页率就会大幅度下降

21
00:00:57,480  -->  00:00:59,440
那么在这呢 我们先举一个例子

22
00:00:59,480  -->  00:01:00,640
在这是以FIFO

23
00:01:00,680  -->  00:01:03,880
实际上即使用LRU也会有类似的情况

24
00:01:03,920  -->  00:01:08,440
这地方呢 是说我有四个页面

25
00:01:08,480  -->  00:01:11,080
然后你分配给它三页 那这三页呢

26
00:01:11,120  -->  00:01:12,840
由于我这访问比较分散

27
00:01:12,880  -->  00:01:14,280
你分配给三页的时候

28
00:01:14,320  -->  00:01:15,360
在这给出来的例子是

29
00:01:15,400  -->  00:01:17,200
后边这是一片的缺页

30
00:01:17,240  -->  00:01:19,480
那缺页的次数有九次

31
00:01:19,520  -->  00:01:21,280
但实际上这时候对于这种情况

32
00:01:21,320  -->  00:01:23,360
你给它四页多一页之后

33
00:01:23,400  -->  00:01:26,920
缺页次数就变成了只有一次

34
00:01:26,960  -->  00:01:28,200
实际上这一次还是说

35
00:01:28,240  -->  00:01:30,560
我们因为两者之间的差异

36
00:01:30,600  -->  00:01:32,040
我把这一次算到里头

37
00:01:32,080  -->  00:01:34,280
那实际上按道理来说

38
00:01:34,320  -->  00:01:35,720
你把这四页全给它了

39
00:01:35,760  -->  00:01:37,240
它就没有缺页了

40
00:01:37,280  -->  00:01:39,080
对于这种情况你多给它一页

41
00:01:39,120  -->  00:01:42,440
实际上这时候所带来的好处是很大的

42
00:01:42,480  -->  00:01:44,800
那我们需要在全局置换算法里面

43
00:01:44,840  -->  00:01:47,000
就是要考虑到这种情况

44
00:01:47,040  -->  00:01:49,280
那具体说起来我们怎么考虑呢

45
00:01:49,320  -->  00:01:50,720
全局置换算法就是

46
00:01:50,760  -->  00:01:55,040
给进程分配可变数目的物理页面

47
00:01:55,080  -->  00:01:58,040
那分配可变 可变的依据是什么呢

48
00:01:58,080  -->  00:02:01,880
可变的依据会是说进程需求的量

49
00:02:01,920  -->  00:02:04,120
那这个需求量是变化的

50
00:02:04,160  -->  00:02:05,880
那我接下来的问题是说

51
00:02:05,920  -->  00:02:08,080
你要依据这个需求的不同

52
00:02:08,120  -->  00:02:09,880
而给它分配可变的数目

53
00:02:09,920  -->  00:02:12,080
我这个需求我怎么来度量

54
00:02:12,120  -->  00:02:13,560
好 那针对这个需求呢

55
00:02:13,600  -->  00:02:14,920
它度量是这样的

56
00:02:14,960  -->  00:02:17,840
我们先对进程的内存访问特征

57
00:02:17,880  -->  00:02:21,240
做某种程度的分析 在不同的阶段

58
00:02:21,280  -->  00:02:23,600
它所需求的量是不一样的

59
00:02:23,640  -->  00:02:25,160
你比如说我一个排序程序

60
00:02:25,200  -->  00:02:26,680
我可能会分成三段

61
00:02:26,720  -->  00:02:29,000
刚开始的时候是数据读入

62
00:02:29,040  -->  00:02:31,320
那这是一段情况 然后后边是一段

63
00:02:31,360  -->  00:02:32,720
中间一段我是排序

64
00:02:32,760  -->  00:02:34,520
排完了之后 结果我把它输出

65
00:02:34,560  -->  00:02:36,920
这三个阶段 你从直观上来想

66
00:02:36,960  -->  00:02:39,440
它肯定是它们之间有很大的区别的

67
00:02:39,480  -->  00:02:41,280
那有了这个之后

68
00:02:41,320  -->  00:02:43,720
我们依据这种需求

69
00:02:43,760  -->  00:02:45,040
来给它分配物理页面数

70
00:02:45,080  -->  00:02:47,000
那这时候算法要讨论的问题就是

71
00:02:47,040  -->  00:02:49,480
如何来确定我给它分配多少

72
00:02:49,520  -->  00:02:51,480
你可以把这件事情分成两段

73
00:02:51,520  -->  00:02:52,880
一个是用来确定

74
00:02:52,920  -->  00:02:54,800
给进程分配的物理页面数

75
00:02:54,840  -->  00:02:57,960
另一个是说我到底是哪些页面

76
00:02:58,000  -->  00:02:59,640
也可以把这两个问题混在一起

77
00:02:59,680  -->  00:03:02,520
我不考虑到底分配多少

78
00:03:02,560  -->  00:03:04,560
分配哪一个 我把它搁在一起

79
00:03:04,600  -->  00:03:06,400
你需要的时候我就往里加

80
00:03:06,440  -->  00:03:08,840
这种方式也可以

81
00:03:08,880  -->  00:03:10,920
好 在具体讨论做法之前呢

82
00:03:10,960  -->  00:03:14,960
我们再进一步来分析CPU的利用率

83
00:03:15,000  -->  00:03:17,440
和并发进程数之间的关系

84
00:03:17,480  -->  00:03:21,560
这是一张图说纵轴是CPU的利用效率

85
00:03:21,600  -->  00:03:23,560
横轴是并发的进程数

86
00:03:23,600  -->  00:03:25,360
我们直观上想象会是说

87
00:03:25,400  -->  00:03:26,720
你只有一个进程的时候

88
00:03:26,760  -->  00:03:29,000
CPU的利用效率肯定是低的

89
00:03:29,040  -->  00:03:31,720
那我可以让多个进程并发运行

90
00:03:31,760  -->  00:03:33,760
随着并发运行的进程的增加

91
00:03:33,800  -->  00:03:36,920
这条线 CPU的利用效率是增加的

92
00:03:36,960  -->  00:03:38,360
但是这条线大家也可以想象

93
00:03:38,400  -->  00:03:41,360
它肯定没有办法无限制的增加上去

94
00:03:41,400  -->  00:03:43,400
好 那增加到一定程度

95
00:03:43,440  -->  00:03:46,040
这个时候你的内存开始紧张之后

96
00:03:46,080  -->  00:03:47,480
这条线就增加的没那么快了

97
00:03:47,520  -->  00:03:48,920
然后到某一个位置之后

98
00:03:48,960  -->  00:03:50,240
你再往上增加

99
00:03:50,280  -->  00:03:52,840
它有可能就会直线下降

100
00:03:52,880  -->  00:03:55,480
好 那这种关系体现成什么样呢

101
00:03:55,520  -->  00:03:58,680
这样来描述CPU利用率和并发进程数

102
00:03:58,720  -->  00:04:02,600
存在相互促进和制约的关系

103
00:04:02,640  -->  00:04:05,840
前边是促进 后边就变成制约了

104
00:04:05,880  -->  00:04:08,440
那我们需要让CPU效率提的好

105
00:04:08,480  -->  00:04:10,920
就是我得掌握一个合适的尺度

106
00:04:10,960  -->  00:04:12,440
那怎么叫合适呢

107
00:04:12,480  -->  00:04:13,920
也就是说我在这里头

108
00:04:13,960  -->  00:04:15,880
我需要考察它的状态

109
00:04:15,920  -->  00:04:18,440
进程数少的时候那是前边这一段

110
00:04:18,480  -->  00:04:20,440
它CPU效率提高

111
00:04:20,480  -->  00:04:22,440
好 进程数增加的时候

112
00:04:22,480  -->  00:04:25,640
那这个访存的也增加了

113
00:04:25,680  -->  00:04:29,800
那再增加的时候到这

114
00:04:29,840  -->  00:04:32,080
那我的局部性就下降了

115
00:04:32,120  -->  00:04:33,720
因为并发进程的使用

116
00:04:33,760  -->  00:04:35,920
导致我们切换之后

117
00:04:35,960  -->  00:04:37,840
你执行两个完全不相干的事

118
00:04:37,880  -->  00:04:38,880
那这时候它的局部性

119
00:04:38,920  -->  00:04:40,480
我们前边说那些就没有了

120
00:04:40,520  -->  00:04:42,560
至少两个进程之间是没有了

121
00:04:42,600  -->  00:04:46,360
那这时候呢 它就会导致这一段

122
00:04:46,400  -->  00:04:48,600
如果再继续增加

123
00:04:48,640  -->  00:04:52,960
那它就会CPU用更多的时间

124
00:04:53,000  -->  00:04:55,480
来进行缺页处理

125
00:04:55,520  -->  00:04:57,080
而这个缺页处理的增加呢

126
00:04:57,120  -->  00:05:00,120
就会导致你CPU利用效率的下降

127
00:05:00,160  -->  00:05:00,840
那这样我们就能

128
00:05:00,880  -->  00:05:02,760
把这条曲线解释清楚了

129
00:05:02,800  -->  00:05:04,520
如果说我们把这条曲线解释清楚之后

130
00:05:04,560  -->  00:05:06,480
我们想要达到的状态是什么呢

131
00:05:06,520  -->  00:05:09,280
尽可能让系统里的

132
00:05:09,320  -->  00:05:11,600
并发进程数对内存使用

133
00:05:11,640  -->  00:05:13,920
在这两者之间这个状态

134
00:05:13,960  -->  00:05:16,320
好 那对这种情况我们怎么来描述呢

135
00:05:16,360  -->  00:05:18,720
我们引入一个概念叫做工作集

136
00:05:18,760  -->  00:05:21,600
工作集是指进程当前使用的

137
00:05:21,640  -->  00:05:23,680
逻辑页面的集合

138
00:05:23,720  -->  00:05:25,120
那这里头比较诡异的地方

139
00:05:25,160  -->  00:05:29,440
是在于当前俩字 什么算是当前

140
00:05:29,480  -->  00:05:31,920
过去一段时间 过去多长时间

141
00:05:31,960  -->  00:05:35,040
好 那在这我们也给它一个近似

142
00:05:35,080  -->  00:05:36,600
实际上这已经开始有近似了

143
00:05:36,640  -->  00:05:39,080
把它表示成一个二元组

144
00:05:39,120  -->  00:05:43,160
W（t,Δ）那在这里头呢

145
00:05:43,200  -->  00:05:46,160
t是你当前的时刻 随着时间的移动

146
00:05:46,200  -->  00:05:49,040
那你当前正在使用的逻辑页面数

147
00:05:49,080  -->  00:05:52,760
它是会不同的 然后过去一段时间

148
00:05:52,800  -->  00:05:55,600
我会有一个定长的访问时间窗口

149
00:05:55,640  -->  00:05:58,960
那这里头呢我们有一个定长两个字

150
00:05:59,000  -->  00:06:01,160
正常情况下根据你的

151
00:06:01,200  -->  00:06:02,400
程序的特征的不同

152
00:06:02,440  -->  00:06:05,000
时间的窗口可能也会不同的

153
00:06:05,040  -->  00:06:06,320
但是在我们这个算法里呢

154
00:06:06,360  -->  00:06:07,680
这一段我就没考虑了

155
00:06:07,720  -->  00:06:10,000
好 我把它设置成一个定长的

156
00:06:10,040  -->  00:06:11,880
然后在这里头呢

157
00:06:11,920  -->  00:06:15,800
得到当前时刻往过去一段时间里头

158
00:06:15,840  -->  00:06:19,320
它访问的这些页面所构成的集合

159
00:06:19,360  -->  00:06:22,920
就是这里的W 那也是这里说的

160
00:06:22,960  -->  00:06:25,320
W是我们当前时刻之前的

161
00:06:25,360  -->  00:06:26,480
Δ时间窗口内

162
00:06:26,520  -->  00:06:29,960
所有访问的页面的集合

163
00:06:30,000  -->  00:06:32,200
那这时候呢 就把我们前边说的

164
00:06:32,240  -->  00:06:35,160
当前俩字给具体化了

165
00:06:35,200  -->  00:06:36,720
也就是说我做了个近似

166
00:06:36,760  -->  00:06:40,040
然后这里头页面的数的大小

167
00:06:40,080  -->  00:06:42,720
就是你的工作集的大小

168
00:06:42,760  -->  00:06:45,480
然后在这我们给了工作集一个定义

169
00:06:45,520  -->  00:06:47,080
那具体说起来呢

170
00:06:47,120  -->  00:06:48,680
我们在这给了一个示例

171
00:06:48,720  -->  00:06:51,000
说这是你的一个进程的

172
00:06:51,040  -->  00:06:52,680
页面访问顺序

173
00:06:52,720  -->  00:06:54,160
然后在这我给它定了一个

174
00:06:54,200  -->  00:06:57,520
时间窗口是10 就是这一段

175
00:06:57,560  -->  00:07:00,680
然后我们看在这一段时间里

176
00:07:00,720  -->  00:07:01,920
它访问了哪些页面

177
00:07:01,960  -->  00:07:03,520
从当前起头的状态来看

178
00:07:03,560  -->  00:07:09,920
这是1 2 5 6 7 这是当前这一段

179
00:07:09,960  -->  00:07:11,280
我们把这个时间轴

180
00:07:11,320  -->  00:07:13,080
随着时间轴往后移

181
00:07:13,120  -->  00:07:16,040
这里的状态是变的

182
00:07:16,080  -->  00:07:23,880
在某一段时间呢 它是相对稳定的

183
00:07:23,920  -->  00:07:26,640
到这 到这一段的时候

184
00:07:26,680  -->  00:07:30,680
基本上到最后就只剩3 4

185
00:07:30,720  -->  00:07:32,600
因为这一段它在访问3 4

186
00:07:32,640  -->  00:07:36,000
我们考察了两个时间点t1和t2

187
00:07:36,040  -->  00:07:39,600
这是它最后访问工作集的大小

188
00:07:39,640  -->  00:07:42,040
那从这可以看到 在不同时间段里头

189
00:07:42,080  -->  00:07:44,680
它访问的页面的数目是不一样的

190
00:07:44,720  -->  00:07:47,080
好 如果说我能根据这个来确定

191
00:07:47,120  -->  00:07:49,200
到后边这段的时候给它分配两页

192
00:07:49,240  -->  00:07:50,920
到前边这段的时候给它分配五页

193
00:07:50,960  -->  00:07:52,240
那这样的话就能很好的

194
00:07:52,280  -->  00:07:54,920
满足进程的这种需求了

195
00:07:54,960  -->  00:07:57,600
刚才我们给了工作集的

196
00:07:57,640  -->  00:07:59,840
定义和一个图示

197
00:07:59,880  -->  00:08:03,080
给出我如何来看到

198
00:08:03,120  -->  00:08:05,080
一个进程它实际的工作集

199
00:08:05,120  -->  00:08:06,400
那接下来呢

200
00:08:06,440  -->  00:08:08,320
我们看一下工作集它变化

201
00:08:08,360  -->  00:08:09,760
有些什么样的规律

202
00:08:09,800  -->  00:08:11,600
那这是一个示意图

203
00:08:11,640  -->  00:08:13,960
说横轴是时间轴

204
00:08:14,000  -->  00:08:16,800
纵轴是工作集的大小

205
00:08:16,840  -->  00:08:18,560
那随着这个进程的变化呢

206
00:08:18,600  -->  00:08:22,800
它这条曲线会体现出某种规律

207
00:08:22,840  -->  00:08:25,520
这些规律呢 我们把它分成这样几条

208
00:08:25,560  -->  00:08:28,480
第一个是说我在刚开始起头的时候

209
00:08:28,520  -->  00:08:32,480
进程访问的页面是增加

210
00:08:32,520  -->  00:08:36,440
然后到一个阶段逐步稳定 就到了这

211
00:08:36,480  -->  00:08:39,080
然后在这些稳定的阶段呢

212
00:08:39,120  -->  00:08:40,880
大致稳定这些区域呢

213
00:08:40,920  -->  00:08:43,440
基本上是理解为我在系统里头

214
00:08:43,480  -->  00:08:46,440
这个进程正在做某一件事情

215
00:08:46,480  -->  00:08:48,720
你比如说这里头数据采集

216
00:08:48,760  -->  00:08:51,400
数据处理和最后的数据展现

217
00:08:51,440  -->  00:08:53,520
那根据你当前做的事情不同

218
00:08:53,560  -->  00:08:55,200
它所需要的内存量

219
00:08:55,240  -->  00:08:56,880
工作集的大小是不一样的

220
00:08:56,920  -->  00:09:00,120
然后在两者之间做切换的时候

221
00:09:00,160  -->  00:09:01,680
这个工作集会有一个快速的

222
00:09:01,720  -->  00:09:04,040
扩张和收缩的过程

223
00:09:04,080  -->  00:09:07,480
那这里头呢 就对应着我这个峰值

224
00:09:07,520  -->  00:09:10,080
这个峰值和这个峰值

225
00:09:10,120  -->  00:09:13,600
如果说我们给出来的全局置换算法

226
00:09:13,640  -->  00:09:16,080
能够很好的近似这条曲线

227
00:09:16,120  -->  00:09:19,240
那我们这件事情做起来就相对容易了

228
00:09:19,280  -->  00:09:21,720
好我们来看怎么来做这件事情

229
00:09:21,760  -->  00:09:24,160
为了对工作集有个刻画

230
00:09:24,200  -->  00:09:26,720
我们在这定义了一个叫常驻集

231
00:09:26,760  -->  00:09:28,520
常驻集是指什么呢

232
00:09:28,560  -->  00:09:30,120
当前时刻进程

233
00:09:30,160  -->  00:09:33,880
实际驻留内存的页面的集合

234
00:09:33,920  -->  00:09:35,920
实际上我们用常驻集

235
00:09:35,960  -->  00:09:40,120
来对进程的工作集做一个近似

236
00:09:40,160  -->  00:09:43,120
工作集和常驻集是什么联系呢

237
00:09:43,160  -->  00:09:45,840
工作集是进程运行过程当中的

238
00:09:45,880  -->  00:09:47,600
固有属性 它是它的特征

239
00:09:47,640  -->  00:09:51,280
随着你那个运行的过程的不同而不同

240
00:09:51,320  -->  00:09:54,480
而常驻集是系统分配给进程的

241
00:09:54,520  -->  00:09:57,240
物理页面数和置换算法都有关系

242
00:09:57,280  -->  00:09:58,800
那实际在的这些页

243
00:09:58,840  -->  00:10:02,120
那我们这个置换算法要干的事情

244
00:10:02,160  -->  00:10:05,120
就是依据置换算法

245
00:10:05,160  -->  00:10:07,600
和进程运行的特征

246
00:10:07,640  -->  00:10:10,640
来确定我给常驻集到底有多大

247
00:10:10,680  -->  00:10:13,880
里头都有哪些页面

248
00:10:13,920  -->  00:10:15,680
好 具体做起来的时候呢

249
00:10:15,720  -->  00:10:20,040
我们是以这样一个做法来实施的

250
00:10:20,080  -->  00:10:23,000
这就是常驻集和我的缺页率

251
00:10:23,040  -->  00:10:25,200
也就是说我通过控制常驻集

252
00:10:25,240  -->  00:10:26,920
来影响缺页率

253
00:10:26,960  -->  00:10:29,480
那这个缺页率和常驻集有什么关系

254
00:10:29,520  -->  00:10:35,000
如果说常驻集包含了工作集

255
00:10:35,040  -->  00:10:38,200
也就相当于工作集里当前正在访问的

256
00:10:38,240  -->  00:10:40,960
这些面都在内存里 都在常驻集里头

257
00:10:41,000  -->  00:10:44,480
那这时候它的缺页率是比较小的

258
00:10:44,520  -->  00:10:46,560
如果说你在这里头

259
00:10:46,600  -->  00:10:50,520
进程正在执行的功能 模块有切换

260
00:10:50,560  -->  00:10:54,160
那这时候工作集会发生一个变化

261
00:10:54,200  -->  00:10:55,000
这个变化呢

262
00:10:55,040  -->  00:10:56,720
你需要去调整你的常驻集

263
00:10:56,760  -->  00:10:59,440
这时候缺页率会比较多

264
00:10:59,480  -->  00:11:01,600
如果说我在这里头常驻集

265
00:11:01,640  -->  00:11:04,600
达到一定的尺度之后 你继续去增加

266
00:11:04,640  -->  00:11:06,120
也就相当于你能够满足它

267
00:11:06,160  -->  00:11:08,280
当前功能需要的内存之后

268
00:11:08,320  -->  00:11:10,160
你再加内存 放的其它东西

269
00:11:10,200  -->  00:11:11,600
实际上这时候对它缺页率

270
00:11:11,640  -->  00:11:13,560
并没有明显的影响

271
00:11:13,600  -->  00:11:15,560
也就是说它不会明显的下降

272
00:11:15,600  -->  00:11:17,320
你这时候再给它分配多的页面

273
00:11:17,360  -->  00:11:19,240
这个效率是下降的 在这种情况下

274
00:11:19,280  -->  00:11:21,600
我们希望是CPU的利用效率提高

275
00:11:21,640  -->  00:11:24,680
整个系统的并发程度提高

276
00:11:24,720  -->  00:11:25,920
好 有了这几条之后

277
00:11:25,960  -->  00:11:29,680
我们就可以来讨论工作集置换算法

278
00:11:29,720  -->  00:11:31,160
它的思路是什么样的

279
00:11:31,200  -->  00:11:34,360
它的思路是把不在工作集的页面

280
00:11:34,400  -->  00:11:37,040
把它换出去 这跟我们前边的

281
00:11:37,080  -->  00:11:39,680
讨论局部置换算法不一样

282
00:11:39,720  -->  00:11:41,440
局部置换算法基本上是说

283
00:11:41,480  -->  00:11:43,520
我把缺的那一页拿进来 

284
00:11:43,560  -->  00:11:46,440
这个时刻来靠把哪一页置换出去

285
00:11:46,480  -->  00:11:47,800
来得到它的集合

286
00:11:47,840  -->  00:11:49,840
在这它并不一定是在

287
00:11:49,880  -->  00:11:53,000
你这个缺页的时候来做这件事情

288
00:11:53,040  -->  00:11:55,400
好 那这时候呢 怎么做呢

289
00:11:55,440  -->  00:11:56,880
在这里面还有一个τ

290
00:11:56,920  -->  00:11:58,880
这是一个参数 是窗口大小

291
00:11:58,920  -->  00:12:00,760
相当于我们在这考察的时候

292
00:12:00,800  -->  00:12:02,480
过去一段时间

293
00:12:02,520  -->  00:12:06,040
这个τ这个时刻就是它窗口大小

294
00:12:06,080  -->  00:12:07,600
具体做法是这样的

295
00:12:07,640  -->  00:12:11,280
我们在这里维护一个访存的链表

296
00:12:11,320  -->  00:12:17,040
有点像我们LRU里头的特殊的栈

297
00:12:17,080  -->  00:12:20,560
然后在访存的时候 这个算法呢

298
00:12:20,600  -->  00:12:25,320
需要去把不在工作集的页面 把它换出

299
00:12:25,360  -->  00:12:27,960
那我们说访存实际上是非常频繁的

300
00:12:28,000  -->  00:12:32,520
你要做换出的判断和动作呢

301
00:12:32,560  -->  00:12:34,440
它的开销是很大的

302
00:12:34,480  -->  00:12:37,120
那在这里头呢 而在缺页的时候

303
00:12:37,160  -->  00:12:38,520
这件事情反倒是简单 

304
00:12:38,560  -->  00:12:39,600
它在缺页的时候只是需要

305
00:12:39,640  -->  00:12:42,200
把你缺的那一页加进来就行了

306
00:12:42,240  -->  00:12:43,720
那这时候 我们在前边局部置换算法

307
00:12:43,760  -->  00:12:45,640
复杂的地方是在缺页里头

308
00:12:45,680  -->  00:12:47,080
现在它把它复杂的地方

309
00:12:47,120  -->  00:12:51,160
放到了访存的时候 那这种算法呢

310
00:12:51,200  -->  00:12:53,320
相对来讲它肯定也是开销大的

311
00:12:53,360  -->  00:12:55,600
我们在这也还是用一个实例

312
00:12:55,640  -->  00:12:59,400
来说一下它的工作过程 它怎么在做

313
00:12:59,440  -->  00:13:00,960
以前我们基本上不考虑

314
00:13:01,000  -->  00:13:02,800
在刚开始的时候有哪几个页面

315
00:13:02,840  -->  00:13:05,360
为了让这个地方能够进行的顺利

316
00:13:05,400  -->  00:13:07,920
我们在这先假定了一个起头的时候

317
00:13:07,960  -->  00:13:10,240
这几个页面的顺序

318
00:13:10,280  -->  00:13:12,000
假设它的意思是在于

319
00:13:12,040  -->  00:13:14,040
我想知道在第一个时刻的时候

320
00:13:14,080  -->  00:13:15,720
过去有几个页面

321
00:13:15,760  -->  00:13:17,800
它是已经超出了工作集

322
00:13:17,840  -->  00:13:19,280
这只是个假例

323
00:13:19,320  -->  00:13:20,280
好 那在这里头呢

324
00:13:20,320  -->  00:13:21,760
我们访问第一个页面

325
00:13:21,800  -->  00:13:24,520
缺页的时候按照工作集置换算法

326
00:13:24,560  -->  00:13:26,920
它怎么做 缺哪个 把哪个补进来

327
00:13:26,960  -->  00:13:30,360
我在访存的时候 这个正好访存

328
00:13:30,400  -->  00:13:31,640
但是这时候我在访存的时候

329
00:13:31,680  -->  00:13:32,720
还需要判断

330
00:13:32,760  -->  00:13:35,080
我哪一个页面不在工作集里头

331
00:13:35,120  -->  00:13:38,520
我们这个τ是4 从这个开始往4

332
00:13:38,560  -->  00:13:39,800
那这个时候那个E

333
00:13:39,840  -->  00:13:41,880
就已经过去超过四个了

334
00:13:41,920  -->  00:13:43,080
没有访问过 

335
00:13:43,120  -->  00:13:45,000
这时候我得把它去掉了

336
00:13:45,040  -->  00:13:47,240
再访问D的时候呢

337
00:13:47,280  -->  00:13:49,680
那这时候说在这的这三个

338
00:13:49,720  -->  00:13:53,360
D肯定是要有的 C A还在里头

339
00:13:53,400  -->  00:13:55,640
那这时候看的情况是这样的

340
00:13:55,680  -->  00:13:59,720
然后再访问B是加进来

341
00:13:59,760  -->  00:14:02,000
那这个时候 你在访问B的时候

342
00:14:02,040  -->  00:14:06,200
A也已经超过4个了

343
00:14:06,240  -->  00:14:09,000
过去是C D B这三个

344
00:14:09,040  -->  00:14:12,400
这个A就给剔除出去了

345
00:14:12,440  -->  00:14:17,760
再访问C还会有哪 C在里头

346
00:14:17,800  -->  00:14:21,520
那是访问成功的 然后B和D在里头

347
00:14:21,560  -->  00:14:24,920
那还是这三个 然后再访问E的时候

348
00:14:24,960  -->  00:14:27,680
把E加进来 E过去这四个

349
00:14:27,720  -->  00:14:30,040
应该就是这四个

350
00:14:30,080  -->  00:14:32,240
然后再访问C的时候

351
00:14:32,280  -->  00:14:36,600
C B 那个D应该去掉了

352
00:14:36,640  -->  00:14:39,000
这时候D去掉了

353
00:14:39,040  -->  00:14:41,360
再访问E的时候呢

354
00:14:41,400  -->  00:14:44,520
这四个加起来只有C和E

355
00:14:44,560  -->  00:14:48,320
这B也会去掉 然后再访问A

356
00:14:48,360  -->  00:14:51,280
这回是有一个缺页

357
00:14:51,320  -->  00:14:55,560
然后再访问D仍然没在里头

358
00:14:55,600  -->  00:15:00,000
再缺页 这时候A C E D

359
00:15:00,040  -->  00:15:02,720
这是它整个执行的过程情况

360
00:15:02,760  -->  00:15:03,840
那在这我们可以看到

361
00:15:03,880  -->  00:15:05,440
你平时在访问的时候

362
00:15:05,480  -->  00:15:07,560
你要做的判断是比较多的

363
00:15:07,600  -->  00:15:09,080
你维护了那个链表

364
00:15:09,120  -->  00:15:10,760
我们这时候可以理解为

365
00:15:10,800  -->  00:15:12,080
那个链表是什么

366
00:15:12,120  -->  00:15:14,280
是你访问的先后顺序

367
00:15:14,320  -->  00:15:16,800
这和我们的LRU的算法

368
00:15:16,840  -->  00:15:19,040
维护的那个栈是类似的

369
00:15:19,080  -->  00:15:21,640
所以在这 这个工作集置换算法

370
00:15:21,680  -->  00:15:23,120
它的开销也是很大的

371
00:15:23,160  -->  00:15:23,200