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

1
00:00:06,800     -->     00:00:09,680
接下来我们讨论

2
00:00:09,720     -->     00:00:13,240
全局置换算法当中的缺页率算法

3
00:00:13,280     -->     00:00:14,720
那缺页率算法呢

4
00:00:14,760     -->     00:00:17,400
实际上它是依据缺页之间的间隔

5
00:00:17,440     -->     00:00:20,400
来调整我哪些页面放到内存里头

6
00:00:20,440     -->     00:00:22,600
哪些页面被置换

7
00:00:22,640     -->     00:00:24,880
在具体说明缺页率算法之前

8
00:00:24,920     -->     00:00:26,320
我们需要对缺页率

9
00:00:26,360     -->     00:00:27,880
给出一个准确的定义

10
00:00:27,920     -->     00:00:30,040
通常情况下我们理解的缺页率

11
00:00:30,080     -->     00:00:33,360
是缺页的次数和访存次数之间的

12
00:00:33,400     -->     00:00:35,600
一个比值 这个比值实际上

13
00:00:35,640     -->     00:00:38,960
在我们缺页率算法里用的时候

14
00:00:39,000     -->     00:00:41,360
它比较不好把握 那我们更多的

15
00:00:41,400     -->     00:00:45,200
会用缺页平均时间间隔的倒数

16
00:00:45,240     -->     00:00:46,600
这个来作为我们缺页率

17
00:00:46,640     -->     00:00:48,360
也就是说两次缺页之间

18
00:00:48,400     -->     00:00:51,360
它有个间隔 这个间隔可能长可能短

19
00:00:51,400     -->     00:00:53,160
那我们在这取它的平均值

20
00:00:53,200     -->     00:00:55,680
然后给倒数作为它缺页率

21
00:00:55,720     -->     00:00:58,920
好 那缺页率受哪些因素的影响呢

22
00:00:58,960     -->     00:01:01,320
影响缺页率的因素有这样一些

23
00:01:01,360     -->     00:01:03,160
我用的置换算法

24
00:01:03,200     -->     00:01:06,720
然后我给进程分配的物理页面数

25
00:01:06,760     -->     00:01:07,920
这个页面的大小

26
00:01:07,960     -->     00:01:09,840
以及与我在实现我程序的时候

27
00:01:09,880     -->     00:01:11,640
我所用的方法

28
00:01:11,680     -->     00:01:14,320
比如说像前边说的 我的局部性

29
00:01:14,360     -->     00:01:16,920
跟我的实验方法有关系一样的

30
00:01:16,960     -->     00:01:18,280
这几个因素里头

31
00:01:18,320     -->     00:01:21,400
我们目前能控制的是置换算法

32
00:01:21,440     -->     00:01:23,520
我们希望通过置换算法的选择

33
00:01:23,560     -->     00:01:25,800
来影响这个缺页率

34
00:01:25,840     -->     00:01:29,040
具体的做法是这样的

35
00:01:29,080     -->     00:01:32,680
说我们的缺页率会随着分配给

36
00:01:32,720     -->     00:01:36,120
进程的物理页面数的增加而降低

37
00:01:36,160     -->     00:01:38,920
物理页面数越少 缺页率会越高

38
00:01:38,960     -->     00:01:40,640
那我们的缺页率算法的思路

39
00:01:40,680     -->     00:01:41,480
是什么样子呢

40
00:01:41,520     -->     00:01:45,400
是说我通过调节常驻集的大小

41
00:01:45,440     -->     00:01:46,880
这个调节过程当中呢

42
00:01:46,920     -->     00:01:49,240
会使得缺页率有变化

43
00:01:49,280     -->     00:01:52,160
我去观测它这个变化

44
00:01:52,200     -->     00:01:56,520
让它的缺页率保持在一定的范围里头

45
00:01:56,560     -->     00:01:59,280
那具体说起来怎么保持呢

46
00:01:59,320     -->     00:02:02,240
如果说缺页率过高 那这时候呢

47
00:02:02,280     -->     00:02:04,760
明显是我的分配给它的

48
00:02:04,800     -->     00:02:07,000
物理页面数比较少

49
00:02:07,040     -->     00:02:10,720
好 那在这我就增加它的物理页面数

50
00:02:10,760     -->     00:02:13,320
使得这条线能够回到下边来

51
00:02:13,360     -->     00:02:14,920
好 然后还有一种情况呢

52
00:02:14,960     -->     00:02:16,960
是说我往里加 那不会越加越多吗

53
00:02:17,000     -->     00:02:18,080
那缺页率会低

54
00:02:18,120     -->     00:02:19,240
低到一定程度之后

55
00:02:19,280     -->     00:02:21,760
我的并发度就会降低

56
00:02:21,800     -->     00:02:24,200
然后我的CPU的利用效率也会下降

57
00:02:24,240     -->     00:02:26,240
好 那这时候我会增加第二条

58
00:02:26,280     -->     00:02:29,720
缺页率过低的时候 我减少常驻集

59
00:02:29,760     -->     00:02:33,240
这时候呢把一些页面给置换出去

60
00:02:33,280     -->     00:02:34,920
那这样的话我的缺页率

61
00:02:34,960     -->     00:02:37,440
就会回到一个合理的范围里头

62
00:02:37,480     -->     00:02:38,760
那这是我们在这里

63
00:02:38,800     -->     00:02:42,520
缺页率置换算法它的基本思路

64
00:02:42,560     -->     00:02:46,440
那它如何来实现呢 它是这样来做的

65
00:02:46,480     -->     00:02:49,960
访存的时候我们去设置引用标志位

66
00:02:50,000     -->     00:02:51,120
这和我们前边的

67
00:02:51,160     -->     00:02:53,240
局部置换算法是一样的

68
00:02:53,280     -->     00:02:54,760
然后不同的地方是在于

69
00:02:54,800     -->     00:02:56,880
出现缺页的时候的处理

70
00:02:56,920     -->     00:02:58,080
出现缺页的时候

71
00:02:58,120     -->     00:03:00,400
我就计算上一次缺页的时间

72
00:03:00,440     -->     00:03:01,520
和当前这个时间

73
00:03:01,560     -->     00:03:02,800
也就是这一次缺页的时间

74
00:03:02,840     -->     00:03:04,320
它们之间的间隔

75
00:03:04,360     -->     00:03:06,480
根据这个间隔的大小的不同

76
00:03:06,520     -->     00:03:08,160
我来做不同的处理

77
00:03:08,200     -->     00:03:10,760
这个大小的不同实际上就是对应着

78
00:03:10,800     -->     00:03:12,240
我们刚才说到的

79
00:03:12,280     -->     00:03:16,920
缺页率置换算法里头的上界和下界

80
00:03:16,960     -->     00:03:19,560
好 在这里头我们有一个常量T

81
00:03:19,600     -->     00:03:24,120
如果说这两个间隔是大于T的

82
00:03:24,160     -->     00:03:26,320
也就是说这一段时间隔的比较长

83
00:03:26,360     -->     00:03:27,760
这表示什么意思

84
00:03:27,800     -->     00:03:31,000
这表示我这里头缺页比较少

85
00:03:31,040     -->     00:03:33,680
那对于这种情况我就会把

86
00:03:33,720     -->     00:03:36,320
在这一段时间没有引用的这些页面

87
00:03:36,360     -->     00:03:38,360
我就把它置换出去

88
00:03:38,400     -->     00:03:41,560
这样的话我就是减少常驻集的大小

89
00:03:41,600     -->     00:03:43,440
就相当于缺页率比较低

90
00:03:43,480     -->     00:03:44,800
然后我把这些不用的页面

91
00:03:44,840     -->     00:03:45,960
我就把它置换出去

92
00:03:46,000     -->     00:03:47,040
这样我可以

93
00:03:47,080     -->     00:03:49,680
把它用到更有意义的地方

94
00:03:49,720     -->     00:03:51,880
另一种情况是小

95
00:03:51,920     -->     00:03:54,320
如果说这个缺页的间隔

96
00:03:54,360     -->     00:03:55,960
小于这个时间T 那这时候我认为

97
00:03:56,000     -->     00:04:00,520
这个缺页率是比较高的 那这时候呢

98
00:04:00,560     -->     00:04:02,800
我增加它的常驻集的大小

99
00:04:02,840     -->     00:04:03,880
所谓增加怎么办呢

100
00:04:03,920     -->     00:04:06,080
就是把你缺失的那一页

101
00:04:06,120     -->     00:04:08,400
放到常驻集里头 那这样一来的话

102
00:04:08,440     -->     00:04:11,160
我们就实现了我们这里所说的

103
00:04:11,200     -->     00:04:14,040
缺页率置换算法

104
00:04:14,080     -->     00:04:15,360
那具体说起来呢

105
00:04:15,400     -->     00:04:17,160
我们还是通过一个实例

106
00:04:17,200     -->     00:04:20,320
来给出它到底是如何工作的

107
00:04:20,360     -->     00:04:23,600
在这假定这个窗口是2

108
00:04:23,640     -->     00:04:24,760
这和我们刚才说的

109
00:04:24,800     -->     00:04:27,480
工作集里的那个窗口 然后我们在

110
00:04:27,520     -->     00:04:29,800
每次访问存储单元的时候

111
00:04:29,840     -->     00:04:32,720
相当于正常访问的时候

112
00:04:32,760     -->     00:04:34,080
你就直接访问做标记

113
00:04:34,120     -->     00:04:36,560
缺页的时候我们来看它怎么处理

114
00:04:36,600     -->     00:04:39,120
那首先第一次出现缺页

115
00:04:39,160     -->     00:04:40,720
那这第一次没有以前了

116
00:04:40,760     -->     00:04:42,160
那这时候直接往里加

117
00:04:42,200     -->     00:04:44,560
然后接着往下访问

118
00:04:44,600     -->     00:04:48,160
C不出现缺页 正常访问 你做修改

119
00:04:48,200     -->     00:04:51,480
访问D也是一样的

120
00:04:51,520     -->     00:04:53,760
在访问B的时候出现了缺页

121
00:04:53,800     -->     00:04:56,800
那这个时候呢 时间间隔是3

122
00:04:56,840     -->     00:04:58,440
大于我们的2

123
00:04:58,480     -->     00:05:00,280
那这时候我们说大于2的话

124
00:05:00,320     -->     00:05:01,920
我就需要把在这一段时间里头

125
00:05:01,960     -->     00:05:04,400
没有访问过的页面把它剔除出去

126
00:05:04,440     -->     00:05:05,680
那这时候我们看

127
00:05:05,720     -->     00:05:06,800
在这里头没有访问过的

128
00:05:06,840     -->     00:05:09,160
这2里头访问的是哪

129
00:05:09,200     -->     00:05:16,280
C和D 只把C和D留下

130
00:05:16,320     -->     00:05:18,000
那这时候它就变成是

131
00:05:18,040     -->     00:05:19,960
加上你刚才缺的这页B

132
00:05:20,000     -->     00:05:21,360
就变成这个样子了

133
00:05:21,400     -->     00:05:25,560
剩下的A和E就被置换出去了

134
00:05:25,600     -->     00:05:29,600
在访问C的时候是正常的

135
00:05:29,640     -->     00:05:32,400
在访问E的时候又出现缺页

136
00:05:32,440     -->     00:05:34,720
那这个时候这个间隔是2

137
00:05:34,760     -->     00:05:37,440
那小于等于我们刚才这个值

138
00:05:37,480     -->     00:05:41,720
我直接加上 再访问C是正常的

139
00:05:41,760     -->     00:05:44,320
然后再访问E也是正常的

140
00:05:44,360     -->     00:05:47,760
再访问A的时候 它又出现缺页了

141
00:05:47,800     -->     00:05:50,240
那这个缺页的时候呢 我们再来看

142
00:05:50,280     -->     00:05:52,920
在这里头我要把哪些留下

143
00:05:52,960     -->     00:05:55,680
我在这一段时间里头访问过的

144
00:05:55,720     -->     00:06:02,960
这里头就相当于是C E A这三种

145
00:06:03,000     -->     00:06:04,320
这是目前这种情况

146
00:06:04,360     -->     00:06:05,520
那实际上在这里头呢

147
00:06:05,560     -->     00:06:08,400
再来访问D又缺页

148
00:06:08,440     -->     00:06:09,560
这两个间隔比较小

149
00:06:09,600     -->     00:06:12,240
我直接把它加进来 那到这个地方呢

150
00:06:12,280     -->     00:06:14,920
我们缺页率算法就算是说清楚了

151
00:06:14,960     -->     00:06:15,840
那实际上我们看到

152
00:06:15,880     -->     00:06:17,560
在这个执行的过程当中

153
00:06:17,600     -->     00:06:19,920
进程驻留在内存里面的

154
00:06:19,960     -->     00:06:23,080
页面数是有变化的

155
00:06:23,120     -->     00:06:24,680
那这就是我们的常驻集的大小

156
00:06:24,720     -->     00:06:26,280
在缺页率置换算法里

157
00:06:26,320     -->     00:06:27,320
它会自动做调节

158
00:06:27,360     -->     00:06:28,840
你比如说在这段时间里头

159
00:06:28,880     -->     00:06:31,800
我是有四个页面

160
00:06:31,840     -->     00:06:34,520
那分配给它的物理页面数就是四

161
00:06:34,560     -->     00:06:36,720
然后在这一段时间里头呢

162
00:06:36,760     -->     00:06:37,880
它是只有三个

163
00:06:37,920     -->     00:06:40,680
在这一段时间里呢 又是四个

164
00:06:40,720     -->     00:06:42,520
那到这变成三个

165
00:06:42,560     -->     00:06:43,880
这样的话每一个进程

166
00:06:43,920     -->     00:06:47,160
它的物理页面数是在

167
00:06:47,200     -->     00:06:49,480
整个运行过程当中动态调节的

168
00:06:49,520     -->     00:06:50,880
某种角度上来讲

169
00:06:50,920     -->     00:06:54,240
我们这个算法就是在逼近

170
00:06:54,280     -->     00:06:55,480
我们刚才前边说的工作集

171
00:06:55,520     -->     00:06:57,160
那个变化的那条曲线

172
00:06:57,200     -->     00:06:59,000
我们希望它尽可能的接近

173
00:06:59,040     -->     00:07:01,320
同时我又把这开销降下去

174
00:07:01,360     -->     00:07:03,160
那这时候缺页率算法

175
00:07:03,200     -->     00:07:05,400
和前边的工作集算法的区别在哪

176
00:07:05,440     -->     00:07:08,360
区别在于原来你去看

177
00:07:08,400     -->     00:07:09,840
我淘汰哪一个的时候

178
00:07:09,880     -->     00:07:12,120
我是在每一次访问的时候

179
00:07:12,160     -->     00:07:13,440
来做这件事情

180
00:07:13,480     -->     00:07:15,840
那这个开销太大了 现在怎么办呢

181
00:07:15,880     -->     00:07:17,000
在中间你访问的时候

182
00:07:17,040     -->     00:07:18,760
只要间隔足够大

183
00:07:18,800     -->     00:07:21,800
那这时候我就认为这是需要加进去的

184
00:07:21,840     -->     00:07:23,720
只是间隔大到一定程度之后

185
00:07:23,760     -->     00:07:25,760
我才认为那里头有你不用的

186
00:07:25,800     -->     00:07:27,200
我把它淘汰一次

187
00:07:27,240     -->     00:07:29,200
这样的话我就把置换这件事情

188
00:07:29,240     -->     00:07:31,000
放到缺页中断里头来完成

189
00:07:31,040     -->     00:07:33,760
这和我们局部置换算法又一致了

190
00:07:33,800     -->     00:07:36,160
这时候它的开销也就降下来了

191
00:07:36,200     -->     00:07:39,720
好 这是我们说到的缺页率置换算法

192
00:07:39,760     -->     00:07:39,800