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


1
00:00:07,240 --> 00:00:11,440
下面我们来介绍反置页表

2
00:00:11,480 --> 00:00:12,920
反置页表也是一种

3
00:00:12,960 --> 00:00:15,200
为了减少页表所占用

4
00:00:15,240 --> 00:00:16,960
存储空间的一种做法

5
00:00:17,000 --> 00:00:20,640
那它是怎么做的呢

6
00:00:20,680 --> 00:00:22,480
提出反置页表的原因

7
00:00:22,520 --> 00:00:25,080
还是说我们多级页表

8
00:00:25,120 --> 00:00:28,040
它访问存储空间的次数比较多

9
00:00:28,080 --> 00:00:31,200
然后特别是在大地址空间的情况下

10
00:00:31,240 --> 00:00:32,440
那这时候呢 

11
00:00:32,480 --> 00:00:34,800
由于大地址空间和多级页表

12
00:00:34,840 --> 00:00:36,400
它和逻辑地址空间

13
00:00:36,440 --> 00:00:38,560
的大小呢有对应关系

14
00:00:38,600 --> 00:00:40,360
每一个逻辑页面

15
00:00:40,400 --> 00:00:42,280
都会对应着页表项的一项

16
00:00:42,320 --> 00:00:43,960
那这样的话我的进程数目的增加

17
00:00:44,000 --> 00:00:46,200
都会导致你页表的数目

18
00:00:46,240 --> 00:00:47,840
占用的空间增大

19
00:00:47,880 --> 00:00:50,920
好 针对这种情况呢

20
00:00:50,960 --> 00:00:53,160
反置页表和页寄存器

21
00:00:53,200 --> 00:00:55,080
是两个类似的做法

22
00:00:55,120 --> 00:00:56,720
那它们在这里头做法是

23
00:00:56,760 --> 00:01:00,280
让页表项和物理地址空间

24
00:01:00,320 --> 00:01:02,040
的大小相对应起来

25
00:01:02,080 --> 00:01:04,360
而不是说像多级页表里

26
00:01:04,400 --> 00:01:06,600
和逻辑地址空间相对应起来

27
00:01:06,640 --> 00:01:09,880
那这样的话 你的进程数目的增加

28
00:01:09,920 --> 00:01:11,840
和虚拟地址空间的增大

29
00:01:11,880 --> 00:01:15,000
都对这页表占用的空间没有影响

30
00:01:15,040 --> 00:01:19,040
下面我们来讨论页寄存器的实现

31
00:01:19,080 --> 00:01:21,160
那么在页寄存器里头呢

32
00:01:21,200 --> 00:01:23,320
它是把每一个物理帧

33
00:01:23,360 --> 00:01:25,400
和一个页寄存器相对应

34
00:01:25,440 --> 00:01:26,960
那在这个寄存器里头

35
00:01:27,000 --> 00:01:28,000
存的内容有些啥呢

36
00:01:28,040 --> 00:01:30,200
一个是 这个物理帧

37
00:01:30,240 --> 00:01:32,520
是否被某一个进程占用

38
00:01:32,560 --> 00:01:33,640
这是使用位

39
00:01:33,680 --> 00:01:38,200
第二个就是页号 占用页号

40
00:01:38,240 --> 00:01:39,160
那么在这个

41
00:01:39,200 --> 00:01:40,360
占用页号相当于

42
00:01:40,400 --> 00:01:42,840
我一个进程占用了这一页

43
00:01:42,880 --> 00:01:45,120
它的逻辑页号是多少

44
00:01:45,160 --> 00:01:46,320
那我在这里头给它保存

45
00:01:46,360 --> 00:01:47,680
那这样的话我就知道

46
00:01:47,720 --> 00:01:52,400
这个物理帧它分配给了哪一个进程

47
00:01:52,440 --> 00:01:54,280
它的逻辑地址是多少

48
00:01:54,320 --> 00:01:55,960
另外还有一个保护位

49
00:01:56,000 --> 00:01:58,520
是来约定这一页的访问方式

50
00:01:58,560 --> 00:02:03,200
你比如说可读 可写

51
00:02:03,240 --> 00:02:04,600
有了这样一种对应关系之后

52
00:02:04,640 --> 00:02:07,200
我们看它占用的存储的情况

53
00:02:07,240 --> 00:02:09,520
在这儿通过一个例子来说明

54
00:02:09,560 --> 00:02:10,760
在这个例子当中呢

55
00:02:10,800 --> 00:02:15,280
它整个系统里有16M的物理内存

56
00:02:15,320 --> 00:02:18,600
然后页面大小呢是4K

57
00:02:18,640 --> 00:02:21,160
那这时候呢16M 4K

58
00:02:21,200 --> 00:02:24,320
那这时候呢我有4096个页面

59
00:02:24,360 --> 00:02:27,120
好 那这4096个页面

60
00:02:27,160 --> 00:02:29,000
它的页寄存器占多大呢

61
00:02:29,040 --> 00:02:31,600
那在这儿是说 假定

62
00:02:31,640 --> 00:02:34,280
每一个页寄存器占8字节

63
00:02:34,320 --> 00:02:38,200
那4096乘8是32K字节

64
00:02:38,240 --> 00:02:39,520
那这32K字节

65
00:02:39,560 --> 00:02:42,520
和16M物理内存比较起来呢

66
00:02:42,560 --> 00:02:46,360
占到的比例是0.2%

67
00:02:46,400 --> 00:02:49,800
那这个比例相对来说还是比较小的

68
00:02:49,840 --> 00:02:54,840
那这时候 它和虚拟内存的大小

69
00:02:54,880 --> 00:02:56,040
就没有关系了

70
00:02:56,080 --> 00:02:57,840
那这时候我在里创建多少个进程

71
00:02:57,880 --> 00:03:00,080
它只是每一个物理页面

72
00:03:00,120 --> 00:03:02,720
和一个页寄存器相对应

73
00:03:02,760 --> 00:03:05,880
那这是它占用存储的情况

74
00:03:05,920 --> 00:03:07,920
那具体说起来这样的话

75
00:03:07,960 --> 00:03:09,880
这种方法它的好处是说

76
00:03:09,920 --> 00:03:12,840
我跟物理内存相比较起来

77
00:03:12,880 --> 00:03:14,800
它占用的空间比较小

78
00:03:14,840 --> 00:03:16,960
而且和逻辑地址空间没关系

79
00:03:17,000 --> 00:03:18,840
但是它也有很大的麻烦

80
00:03:18,880 --> 00:03:20,240
它的麻烦是什么

81
00:03:20,280 --> 00:03:22,200
在多级页表里头

82
00:03:22,240 --> 00:03:25,920
我们这个信息查询呢

83
00:03:25,960 --> 00:03:27,760
我是从逻辑页号到物理页号

84
00:03:27,800 --> 00:03:31,840
利用下标查里头的内容

85
00:03:31,880 --> 00:03:34,040
我就可以找到它的页帧号

86
00:03:34,080 --> 00:03:38,320
而现在呢我排序的办法呢是页帧号

87
00:03:38,360 --> 00:03:42,160
我要从 找的是里头的逻辑页号

88
00:03:42,200 --> 00:03:43,680
是否是我想找的那个

89
00:03:43,720 --> 00:03:44,440
那这样的话 

90
00:03:44,480 --> 00:03:46,680
就要在页寄存器里头进行搜索

91
00:03:46,720 --> 00:03:49,360
那这个搜索是会比较困难的

92
00:03:49,400 --> 00:03:50,440
下面我们来讨论

93
00:03:50,480 --> 00:03:53,600
页寄存器机制的地址转换

94
00:03:53,640 --> 00:03:56,120
CPU生成的是逻辑地址

95
00:03:56,160 --> 00:03:58,040
那在页寄存器机制下

96
00:03:58,080 --> 00:04:01,240
它所对应的物理地址是多少呢

97
00:04:01,280 --> 00:04:02,360
那么这个多少呢

98
00:04:02,400 --> 00:04:04,840
是把逻辑地址做Hash

99
00:04:04,880 --> 00:04:06,800
Hash的原因是这样

100
00:04:06,840 --> 00:04:08,520
我可以减少搜索范围

101
00:04:08,560 --> 00:04:11,480
然后呢如果说有冲突

102
00:04:11,520 --> 00:04:13,560
Hash之后的值 它可能是

103
00:04:13,600 --> 00:04:15,600
两个不同的逻辑地址

104
00:04:15,640 --> 00:04:17,520
对应到同一个Hash值上

105
00:04:17,560 --> 00:04:19,760
那这种情况下Hash值相同

106
00:04:19,800 --> 00:04:21,440
那这时候我就会产生冲突

107
00:04:21,480 --> 00:04:23,320
这种冲突是需要解决的

108
00:04:23,360 --> 00:04:24,880
好 这时候呢

109
00:04:24,920 --> 00:04:28,560
我们可以利用快表来和

110
00:04:28,600 --> 00:04:32,200
这个页寄存器机制搁到一起来用

111
00:04:32,240 --> 00:04:33,680
那么这时候的做法什么呢

112
00:04:33,720 --> 00:04:35,600
逻辑地址进行Hash

113
00:04:35,640 --> 00:04:38,760
然后在快表当中去查找相应的页表项

114
00:04:38,800 --> 00:04:41,560
如果说查找的过程当中出现冲突

115
00:04:41,600 --> 00:04:45,520
这时 我就需要遍历所有的冲突链表

116
00:04:45,560 --> 00:04:47,120
好 如果说查找不到

117
00:04:47,160 --> 00:04:50,080
那么这时候呢它就会出现异常

118
00:04:50,120 --> 00:04:51,600
好 那么在这里头

119
00:04:51,640 --> 00:04:53,560
它也有一个问题

120
00:04:53,600 --> 00:04:56,040
和我们前面的快表是一样的

121
00:04:56,080 --> 00:04:58,400
由于快表它的容量有限

122
00:04:58,440 --> 00:05:01,000
这时候呢快表的功耗又很大

123
00:05:01,040 --> 00:05:03,560
这对于我们页寄存器机制

124
00:05:03,600 --> 00:05:05,040
还是有很大影响的

125
00:05:05,080 --> 00:05:07,320
比如说在这里说到StrongARM上的

126
00:05:07,360 --> 00:05:09,920
快表的功耗占到27%

127
00:05:09,960 --> 00:05:11,680
这是不可以忽视的

128
00:05:11,720 --> 00:05:14,120
好 接下来我们说反置页表

129
00:05:14,160 --> 00:05:16,880
反置页表和页寄存器的做法的区别是

130
00:05:16,920 --> 00:05:20,280
在于它把进程ID也考虑进来了

131
00:05:20,320 --> 00:05:23,000
那它和页寄存器做法一样的

132
00:05:23,040 --> 00:05:25,000
它需要进行Hash

133
00:05:25,040 --> 00:05:26,840
不同的地方是把进程标识

134
00:05:26,880 --> 00:05:28,840
也加在里头一块做Hash

135
00:05:28,880 --> 00:05:31,840
Hash完的结果呢也可能会有冲突

136
00:05:31,880 --> 00:05:33,720
那也需要解决冲突

137
00:05:33,760 --> 00:05:35,080
那Hash完的结果呢

138
00:05:35,120 --> 00:05:39,160
它是以页帧号来作为排序的

139
00:05:39,200 --> 00:05:43,280
那我在这儿找到的结果是说

140
00:05:43,320 --> 00:05:46,920
我需要到相应的页表项里去核对

141
00:05:46,960 --> 00:05:49,520
Hash之前的结果和之后的

142
00:05:49,560 --> 00:05:53,200
里头的进程ID和逻辑号是否一致

143
00:05:53,240 --> 00:05:55,560
如果一致呢这就是我要找的那一项

144
00:05:55,600 --> 00:05:58,520
我就可以得到相应的物理页号了

145
00:05:58,560 --> 00:05:59,640
如果不一样

146
00:05:59,680 --> 00:06:02,480
那这时候呢它就会产生冲突

147
00:06:02,520 --> 00:06:04,600
那么对于冲突情况呢

148
00:06:04,640 --> 00:06:08,320
我们以这个例子来说

149
00:06:08,360 --> 00:06:12,840
一个逻辑地址加上它的进程ID

150
00:06:12,880 --> 00:06:15,920
那我首先做Hash

151
00:06:15,960 --> 00:06:18,600
Hash完的结果是在这儿

152
00:06:18,640 --> 00:06:22,960
到相应的反置页表当中进行查找

153
00:06:23,000 --> 00:06:26,640
看进程ID和逻辑页号

154
00:06:26,680 --> 00:06:28,640
是不是跟Hash之前的一样

155
00:06:28,680 --> 00:06:30,480
如果不一样那就是说明有冲突

156
00:06:30,520 --> 00:06:32,240
这时候告诉你下一项在哪

157
00:06:32,280 --> 00:06:36,120
这地方是有冲突

158
00:06:36,160 --> 00:06:37,200
好 告诉你下一项

159
00:06:37,240 --> 00:06:40,240
然后我再到下一项里头进行核对

160
00:06:40,280 --> 00:06:42,400
这时候呢这两者跟那儿是一样的

161
00:06:42,440 --> 00:06:43,560
 好 那么这时候呢

162
00:06:43,600 --> 00:06:46,200
我要找这个地方 

163
00:06:46,240 --> 00:06:51,680
它的序号就是我的页帧号，

164
00:06:51,720 --> 00:06:55,560
好 页帧号和页内偏移合到一起

165
00:06:55,600 --> 00:07:00,280
那就得到它的物理页号和页内偏移

166
00:07:00,320 --> 00:07:05,200
那到目前为止呢我们介绍了三种做法

167
00:07:05,240 --> 00:07:09,600
来缓解或者是解决页表所带来的麻烦

168
00:07:09,640 --> 00:07:14,480
一种是快表 它是通过缓存的机制

169
00:07:14,520 --> 00:07:18,360
来减少对物理内存 对页表的访问

170
00:07:18,400 --> 00:07:20,000
第二种是多级页表

171
00:07:20,040 --> 00:07:21,520
多级页表的做法呢

172
00:07:21,560 --> 00:07:25,600
通过多级来减少页表的大小

173
00:07:25,640 --> 00:07:29,520
反置页表是另一种减少页表大小的做法

174
00:07:29,560 --> 00:07:32,360
这几种做法呢都可以有效的解决

175
00:07:32,400 --> 00:07:37,160
或者是缓解我们引入页表所带来的麻烦

176
00:07:37,200 --> 00:07:39,520
那在这些麻烦解决掉之后

177
00:07:39,560 --> 00:07:41,440
我们现在用到计算机

178
00:07:41,480 --> 00:07:45,840
都是采用这种页表的机制来进行转换的

179
00:07:45,880 --> 00:07:50,680
那这是呢 我们说到的这个页存储机制

180
00:07:50,720 --> 00:07:50,760