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


1
00:00:07,000 --> 00:00:13,080
接下来我们介绍虚拟存储当中的局部性原理

2
00:00:13,120 --> 00:00:17,320
那我们在这里说虚拟存储是想

3
00:00:17,360 --> 00:00:22,280
把原来放到内存里的这个进程地址空间的信息

4
00:00:22,320 --> 00:00:25,840
把其中的一部分放到外存当中来

5
00:00:25,880 --> 00:00:28,080
那要把它放到外存当中来呢

6
00:00:28,120 --> 00:00:31,640
实际上这时候呢需要有一系列的准备工作

7
00:00:31,680 --> 00:00:33,240
那我们首先看一下

8
00:00:33,280 --> 00:00:37,360
我们在这里头如何把这个放到外存里头来

9
00:00:37,400 --> 00:00:40,840
我们想达到的目标具体准确的描述出来

10
00:00:40,880 --> 00:00:44,440
这是我们虚拟存储希望达到的效果

11
00:00:44,480 --> 00:00:49,320
进程地址空间实际的物理内存和外存

12
00:00:49,360 --> 00:00:50,640
这两个搁在一起呢

13
00:00:50,680 --> 00:00:52,440
来存放地址空间的内容

14
00:00:52,480 --> 00:00:54,840
这一些呢放在内存一些放到外存里头

15
00:00:54,880 --> 00:00:58,080
中间呢是由操作系统来干这件事情

16
00:00:58,120 --> 00:01:00,480
那我们把这个目标具体的描述出来呢

17
00:01:00,520 --> 00:01:02,960
就有这样两条 第一条是说

18
00:01:03,000 --> 00:01:08,560
我们只让一部分程序加载到内存当中来

19
00:01:08,600 --> 00:01:11,840
这时候呢就可以让程序运行

20
00:01:11,880 --> 00:01:13,280
那这是跟以前不一样的

21
00:01:13,320 --> 00:01:14,840
以前我们说要想一个程序运行

22
00:01:14,880 --> 00:01:17,760
我必须把整个进程加到地址空间当中

23
00:01:17,800 --> 00:01:21,160
那这时候才能开始运行 只加一部分让它

24
00:01:21,200 --> 00:01:22,640
怎么能让它运行起来

25
00:01:22,680 --> 00:01:26,120
那这时候呢需要我们做的是说要操作系统

26
00:01:26,160 --> 00:01:29,840
自动的来完成我需要加载哪一部分

27
00:01:29,880 --> 00:01:32,240
而不需要程序员的参与

28
00:01:32,280 --> 00:01:34,440
而在我们前面用的覆盖技术呢

29
00:01:34,480 --> 00:01:37,440
这是需要程序员来参与的

30
00:01:37,480 --> 00:01:40,640
另一个呢是说我们可以把一部分

31
00:01:40,680 --> 00:01:45,680
内存空间当中的信息放到外存当中去

32
00:01:45,720 --> 00:01:47,680
内存和外存之间做一个交换

33
00:01:47,720 --> 00:01:51,760
这样做的目的是让正在运行的进程

34
00:01:51,800 --> 00:01:54,160
能够有更多的空闲空间

35
00:01:54,200 --> 00:01:57,560
而这一条也是需要由操作系统来做

36
00:01:57,600 --> 00:01:59,560
它在内外存之间进行交换

37
00:01:59,600 --> 00:02:03,600
需要讨论的问题是说我到底要把哪些东西放出去

38
00:02:03,640 --> 00:02:05,400
实际上这时候我们前面说的第一个

39
00:02:05,440 --> 00:02:07,200
我到底要把哪些东西放进来

40
00:02:07,240 --> 00:02:08,960
这是我用到的放进来

41
00:02:09,000 --> 00:02:10,800
这个地方我把哪个东西放出去呢

42
00:02:10,840 --> 00:02:14,240
实际上是说我需要把不常用的放到外存当中去

43
00:02:14,280 --> 00:02:16,720
这就是我们后面会说到的置换算法

44
00:02:16,760 --> 00:02:18,320
那在具体讨论之前呢

45
00:02:18,360 --> 00:02:21,200
我们需要来讨论程序访问的一些特征

46
00:02:21,240 --> 00:02:23,920
这就是我们这里说到的局部性原理

47
00:02:23,960 --> 00:02:27,920
所谓局部性原理呢是指程序在执行的过程当中

48
00:02:27,960 --> 00:02:29,600
在一个较短的时间里头

49
00:02:29,640 --> 00:02:33,880
它所执行的指令和指令操作数的地址

50
00:02:33,920 --> 00:02:36,640
分别局限于在一定区域里头

51
00:02:36,680 --> 00:02:40,040
因为通常情况下我们指令是存在代码段里的

52
00:02:40,080 --> 00:02:44,040
指令所访问的操作数呢通常是存在数据段里的

53
00:02:44,080 --> 00:02:45,480
这两个呢各是一个地方

54
00:02:45,520 --> 00:02:46,960
那这两个各自一个地方呢

55
00:02:47,000 --> 00:02:49,200
分别局限在一定区域里头

56
00:02:49,240 --> 00:02:52,840
这怎么说呢 这种特征呢体现在以下几个方面

57
00:02:52,880 --> 00:02:55,440
第一个呢叫时间局部性

58
00:02:55,480 --> 00:02:59,400
也就是说我一条指令的连续两次执行

59
00:02:59,440 --> 00:03:03,520
我一个数据的连续两次访问 通常情况下

60
00:03:03,560 --> 00:03:06,760
它们都集中在一段较短的时间里头

61
00:03:06,800 --> 00:03:10,840
正是因为有了这种较短的时间所以我可以把

62
00:03:10,880 --> 00:03:14,400
放到内存里的这一段内容 它会频繁的访问

63
00:03:14,440 --> 00:03:17,120
如果没这一条的话可能出现一种什么样的情况

64
00:03:17,160 --> 00:03:19,480
就是你刚放进来内存里的这个信息

65
00:03:19,520 --> 00:03:22,200
下一步要访问另一个你刚拿出去的

66
00:03:22,240 --> 00:03:24,360
如果出现这种极端情况的话

67
00:03:24,400 --> 00:03:28,880
你这个虚拟存储就性能大幅度下降了

68
00:03:28,920 --> 00:03:30,800
好这是时间局部性

69
00:03:30,840 --> 00:03:33,080
另一个呢是说空间局部性

70
00:03:33,120 --> 00:03:37,360
空间局部性是指我相邻的几条指令

71
00:03:37,400 --> 00:03:41,960
或者说我访问的相邻的几个数据

72
00:03:42,000 --> 00:03:46,520
访问区域呢是局限在一个较小的区域里头

73
00:03:46,560 --> 00:03:48,800
也就是说我相邻的访问的两条指令

74
00:03:48,840 --> 00:03:50,720
相邻访问的两个数据

75
00:03:50,760 --> 00:03:54,240
比如说我们在对数据进行排序的时候

76
00:03:54,280 --> 00:03:55,560
那我会有循环

77
00:03:55,600 --> 00:03:58,240
那这个循环呢就是你要访问这几条指令

78
00:03:58,280 --> 00:04:00,400
而我排序的相邻这些数据呢

79
00:04:00,440 --> 00:04:02,160
那就是你这儿要访问的数据

80
00:04:02,200 --> 00:04:07,360
它们呢通常情况下是局限在一个较小的区域里头

81
00:04:07,400 --> 00:04:10,400
再有一条呢是叫分支局部性

82
00:04:10,440 --> 00:04:13,920
分支局部性是指什么呢 说我有一条跳转指令

83
00:04:13,960 --> 00:04:16,360
这跳转指令的两次执行呢很多时候

84
00:04:16,400 --> 00:04:19,400
它是会跳转到同一个地址的

85
00:04:19,440 --> 00:04:22,040
这种情况在实际的例子中会是什么样的

86
00:04:22,080 --> 00:04:24,320
比如说我有一个循环 循环一千次

87
00:04:24,360 --> 00:04:25,680
那进到这个循环体里头

88
00:04:25,720 --> 00:04:27,640
到那个循环的跳转指令的地方

89
00:04:27,680 --> 00:04:30,600
  判断小于你的循环次数

90
00:04:30,640 --> 00:04:32,400
它就蹦回到开头 那这样的话

91
00:04:32,440 --> 00:04:33,720
你从这条指令上来看

92
00:04:33,760 --> 00:04:36,680
前面只要没到你的循环次数

93
00:04:36,720 --> 00:04:38,560
那前面都是蹦到开头

94
00:04:38,600 --> 00:04:40,880
那这样的话只有最后一次是例外

95
00:04:40,920 --> 00:04:44,200
好 那这种呢我们称之为叫分支局部性

96
00:04:44,240 --> 00:04:47,200
有了这几条之后我们就可以认为

97
00:04:47,240 --> 00:04:51,280
我们所运行的程序它具有它所执行的指令

98
00:04:51,320 --> 00:04:55,280
所访问的数据有很好的这种集中特征

99
00:04:55,320 --> 00:04:58,640
它们会集中在一个局部的区域里头

100
00:04:58,680 --> 00:05:01,200
那这样的话如果我们能够判断清楚

101
00:05:01,240 --> 00:05:03,640
它局限在的那个区域到底是哪些

102
00:05:03,680 --> 00:05:05,760
我们可以对它做很好的预测的话

103
00:05:05,800 --> 00:05:09,560
那这时候我们就可以把这些内容放到内存里头来

104
00:05:09,600 --> 00:05:11,960
而把那些不常用的放到外存当中

105
00:05:12,000 --> 00:05:15,120
而这种经常用的放到内存里头之后

106
00:05:15,160 --> 00:05:18,200
那我们的计算的程序执行的性能

107
00:05:18,240 --> 00:05:22,120
就不会有大幅度下降 这也是由于这一条

108
00:05:22,160 --> 00:05:25,360
我们局部性原理 那从理论上呢保证了

109
00:05:25,400 --> 00:05:30,240
我们虚拟存储它是可能实现的

110
00:05:30,280 --> 00:05:32,000
它具有可行性 并且呢

111
00:05:32,040 --> 00:05:36,320
它实现完了之后应该能有很好的这个效果

112
00:05:36,360 --> 00:05:40,760
好 那具体呢我们通过一个例子来说明

113
00:05:40,800 --> 00:05:42,800
说这个局部性到底体现在什么地方

114
00:05:42,840 --> 00:05:43,840
同时这种局部性

115
00:05:43,880 --> 00:05:47,440
也跟我们写的程序特征是有关系的

116
00:05:47,480 --> 00:05:48,800
在这儿给一个例子

117
00:05:48,840 --> 00:05:51,600
说我在这里呢4K为一个页面

118
00:05:51,640 --> 00:05:55,040
然后我给一个进程呢 这仅仅是个示例

119
00:05:55,080 --> 00:05:57,720
分配一个页面这是用来放数据的

120
00:05:57,760 --> 00:06:00,600
好 那这里头我约定一个二维数组

121
00:06:00,640 --> 00:06:04,120
那1024乘1024 假定你的int是整数呢

122
00:06:04,160 --> 00:06:07,040
是占四个字节为一个整数

123
00:06:07,080 --> 00:06:09,240
好 那这时候呢我在这个页面

124
00:06:09,280 --> 00:06:11,600
再被这个数组呢进行清零

125
00:06:11,640 --> 00:06:14,560
我们看它访问的次数会是啥样的

126
00:06:14,600 --> 00:06:17,200
好 清零呢 我来写我这程序的时候呢

127
00:06:17,240 --> 00:06:19,320
这是一种写法 两个循环

128
00:06:19,360 --> 00:06:21,800
二维数组第一维第二维

129
00:06:21,840 --> 00:06:24,520
那需要大家注意的是我第一维呢

130
00:06:24,560 --> 00:06:27,920
在里头这个循环是用的第一个下标

131
00:06:27,960 --> 00:06:31,000
在外头这个循环是用的第二个下标

132
00:06:31,040 --> 00:06:34,880
而还有一种另外的写法 我把它反过来

133
00:06:34,920 --> 00:06:39,080
i j i j 这样的话在里头那个小循环里头

134
00:06:39,120 --> 00:06:41,480
那我是先循环的第二位

135
00:06:41,520 --> 00:06:44,600
那如果说我们在实际的存储当中

136
00:06:44,640 --> 00:06:47,240
它的存储顺序和你这两个循环

137
00:06:47,280 --> 00:06:48,520
实际上它在访问的时候

138
00:06:48,560 --> 00:06:51,560
它的位置的分布呢是很不相同的

139
00:06:51,600 --> 00:06:55,760
那我们具体看一下这两个到底会有什么样的情况

140
00:06:55,800 --> 00:06:59,000
那这是呢我们看到的刚才那个

141
00:06:59,040 --> 00:07:02,520
二维数组它在存储空间当中的情况

142
00:07:02,560 --> 00:07:05,960
这里呢每一行代表一页

143
00:07:06,000 --> 00:07:08,880
你比如说每个元素我占四个字节

144
00:07:08,920 --> 00:07:13,080
1024个刚才说的4K 4K我占一页

145
00:07:13,120 --> 00:07:17,160
我们用来存数据的呢 分配的页面是

146
00:07:17,200 --> 00:07:20,480
物理页面是一个 那这样的话我每使用一行

147
00:07:20,520 --> 00:07:22,960
蹦到下一行的时候我就会产生缺页

148
00:07:23,000 --> 00:07:27,200
那对应着我们刚才前面的两种清零的办法

149
00:07:27,240 --> 00:07:30,920
那第一种办法呢 我是从第一个元素

150
00:07:30,960 --> 00:07:34,000
然后它并不是在这一页里的第二个

151
00:07:34,040 --> 00:07:35,320
而是第二页里的第一个

152
00:07:35,360 --> 00:07:36,720
一直到最后一页的第一个

153
00:07:36,760 --> 00:07:38,720
然后再是 这样循环下来的

154
00:07:38,760 --> 00:07:44,760
我们看它 它的访问顺序 第一页一直到1023

155
00:07:44,800 --> 00:07:48,080
然后又是第0页到1023

156
00:07:48,120 --> 00:07:50,960
这样的话我每一次相邻的一次访问

157
00:07:51,000 --> 00:07:56,360
我都会切到下一页 那这种切换呢会导致一次缺页

158
00:07:56,400 --> 00:07:58,680
那这样总共缺页次数是什么

159
00:07:58,720 --> 00:08:04,880
就是1024乘1024 而我们的第二种做法呢

160
00:08:04,920 --> 00:08:08,200
它的访问方式是先把这一行全部清零

161
00:08:08,240 --> 00:08:10,880
然后再把第二行全部清零

162
00:08:10,920 --> 00:08:14,400
如果说 你意识到背后是虚拟存储

163
00:08:14,440 --> 00:08:18,240
那么这时候呢这地方的缺页次数

164
00:08:18,280 --> 00:08:20,560
就变成了1024次

165
00:08:20,600 --> 00:08:23,760
如果说你认为这些数据全在内存里头

166
00:08:23,800 --> 00:08:25,440
那么这两种做法

167
00:08:25,480 --> 00:08:28,600
我们在内存里头任何一个单元在访问的时候

168
00:08:28,640 --> 00:08:32,400
它都是使用的时间是一样的

169
00:08:32,440 --> 00:08:34,280
那这两种算法是没有区别的

170
00:08:34,320 --> 00:08:41,040
好 如果说我们在这里头考虑到物理内存的量小

171
00:08:41,080 --> 00:08:42,960
那么这时候呢这两种做法

172
00:08:43,000 --> 00:08:45,720
它的区别呢就是巨大的

173
00:08:45,760 --> 00:08:47,760
所以在这儿呢不同的程序

174
00:08:47,800 --> 00:08:50,440
如果说你背后利用了虚拟存储

175
00:08:50,480 --> 00:08:52,720
那你在这里头呢需要很小心的

176
00:08:52,760 --> 00:08:57,440
去使用你的编程方法 以便于提高它的局部性

177
00:08:57,480 --> 00:08:58,720
这个提高它的局部性

178
00:08:58,760 --> 00:09:02,840
也有利于提高你的程序的这个性能

179
00:09:02,880 --> 00:09:04,520
好 基于这样一种做法呢

180
00:09:04,560 --> 00:09:09,560
我们说在这里头它可以很好的有局部性的特征

181
00:09:09,600 --> 00:09:13,040
那接下来我们会说基于这种局部性的特征

182
00:09:13,080 --> 00:09:17,640
我们怎么来实现我们的虚拟存储系统

183
00:09:17,680 --> 00:09:23,160


184
00:09:23,200 --> 00:09:23,800


185
00:09:23,840 --> 00:09:24,440


186
00:09:24,480 --> 00:09:25,160


187
00:09:25,200 --> 00:09:25,240