接下来我们介绍虚拟存储当中的局部性原理
那我们在这里说虚拟存储是想
把原来放到内存里的这个进程地址空间的信息
把其中的一部分放到外存当中来
那要把它放到外存当中来呢
实际上这时候呢需要有一系列的准备工作
那我们首先看一下
我们在这里头如何把这个放到外存里头来
我们想达到的目标具体准确的描述出来
这是我们虚拟存储希望达到的效果
进程地址空间实际的物理内存和外存
这两个搁在一起呢
来存放地址空间的内容
这一些呢放在内存一些放到外存里头
中间呢是由操作系统来干这件事情
那我们把这个目标具体的描述出来呢
就有这样两条 第一条是说
我们只让一部分程序加载到内存当中来
这时候呢就可以让程序运行
那这是跟以前不一样的
以前我们说要想一个程序运行
我必须把整个进程加到地址空间当中
那这时候才能开始运行 只加一部分让它
怎么能让它运行起来
那这时候呢需要我们做的是说要操作系统
自动的来完成我需要加载哪一部分
而不需要程序员的参与
而在我们前面用的覆盖技术呢
这是需要程序员来参与的
另一个呢是说我们可以把一部分
内存空间当中的信息放到外存当中去
内存和外存之间做一个交换
这样做的目的是让正在运行的进程
能够有更多的空闲空间
而这一条也是需要由操作系统来做
它在内外存之间进行交换
需要讨论的问题是说我到底要把哪些东西放出去
实际上这时候我们前面说的第一个
我到底要把哪些东西放进来
这是我用到的放进来
这个地方我把哪个东西放出去呢
实际上是说我需要把不常用的放到外存当中去
这就是我们后面会说到的置换算法
那在具体讨论之前呢
我们需要来讨论程序访问的一些特征
这就是我们这里说到的局部性原理
所谓局部性原理呢是指程序在执行的过程当中
在一个较短的时间里头
它所执行的指令和指令操作数的地址
分别局限于在一定区域里头
因为通常情况下我们指令是存在代码段里的
指令所访问的操作数呢通常是存在数据段里的
这两个呢各是一个地方
那这两个各自一个地方呢
分别局限在一定区域里头
这怎么说呢 这种特征呢体现在以下几个方面
第一个呢叫时间局部性
也就是说我一条指令的连续两次执行
我一个数据的连续两次访问 通常情况下
它们都集中在一段较短的时间里头
正是因为有了这种较短的时间所以我可以把
放到内存里的这一段内容 它会频繁的访问
如果没这一条的话可能出现一种什么样的情况
就是你刚放进来内存里的这个信息
下一步要访问另一个你刚拿出去的
如果出现这种极端情况的话
你这个虚拟存储就性能大幅度下降了
好这是时间局部性
另一个呢是说空间局部性
空间局部性是指我相邻的几条指令
或者说我访问的相邻的几个数据
访问区域呢是局限在一个较小的区域里头
也就是说我相邻的访问的两条指令
相邻访问的两个数据
比如说我们在对数据进行排序的时候
那我会有循环
那这个循环呢就是你要访问这几条指令
而我排序的相邻这些数据呢
那就是你这儿要访问的数据
它们呢通常情况下是局限在一个较小的区域里头
再有一条呢是叫分支局部性
分支局部性是指什么呢 说我有一条跳转指令
这跳转指令的两次执行呢很多时候
它是会跳转到同一个地址的
这种情况在实际的例子中会是什么样的
比如说我有一个循环 循环一千次
那进到这个循环体里头
到那个循环的跳转指令的地方
判断小于你的循环次数
它就蹦回到开头 那这样的话
你从这条指令上来看
前面只要没到你的循环次数
那前面都是蹦到开头
那这样的话只有最后一次是例外
好 那这种呢我们称之为叫分支局部性
有了这几条之后我们就可以认为
我们所运行的程序它具有它所执行的指令
所访问的数据有很好的这种集中特征
它们会集中在一个局部的区域里头
那这样的话如果我们能够判断清楚
它局限在的那个区域到底是哪些
我们可以对它做很好的预测的话
那这时候我们就可以把这些内容放到内存里头来
而把那些不常用的放到外存当中
而这种经常用的放到内存里头之后
那我们的计算的程序执行的性能
就不会有大幅度下降 这也是由于这一条
我们局部性原理 那从理论上呢保证了
我们虚拟存储它是可能实现的
它具有可行性 并且呢
它实现完了之后应该能有很好的这个效果
好 那具体呢我们通过一个例子来说明
说这个局部性到底体现在什么地方
同时这种局部性
也跟我们写的程序特征是有关系的
在这儿给一个例子
说我在这里呢4K为一个页面
然后我给一个进程呢 这仅仅是个示例
分配一个页面这是用来放数据的
好 那这里头我约定一个二维数组
那1024乘1024 假定你的int是整数呢
是占四个字节为一个整数
好 那这时候呢我在这个页面
再被这个数组呢进行清零
我们看它访问的次数会是啥样的
好 清零呢 我来写我这程序的时候呢
这是一种写法 两个循环
二维数组第一维第二维
那需要大家注意的是我第一维呢
在里头这个循环是用的第一个下标
在外头这个循环是用的第二个下标
而还有一种另外的写法 我把它反过来
i j i j 这样的话在里头那个小循环里头
那我是先循环的第二位
那如果说我们在实际的存储当中
它的存储顺序和你这两个循环
实际上它在访问的时候
它的位置的分布呢是很不相同的
那我们具体看一下这两个到底会有什么样的情况
那这是呢我们看到的刚才那个
二维数组它在存储空间当中的情况
这里呢每一行代表一页
你比如说每个元素我占四个字节
1024个刚才说的4K 4K我占一页
我们用来存数据的呢 分配的页面是
物理页面是一个 那这样的话我每使用一行
蹦到下一行的时候我就会产生缺页
那对应着我们刚才前面的两种清零的办法
那第一种办法呢 我是从第一个元素
然后它并不是在这一页里的第二个
而是第二页里的第一个
一直到最后一页的第一个
然后再是 这样循环下来的
我们看它 它的访问顺序 第一页一直到1023
然后又是第0页到1023
这样的话我每一次相邻的一次访问
我都会切到下一页 那这种切换呢会导致一次缺页
那这样总共缺页次数是什么
就是1024乘1024 而我们的第二种做法呢
它的访问方式是先把这一行全部清零
然后再把第二行全部清零
如果说 你意识到背后是虚拟存储
那么这时候呢这地方的缺页次数
就变成了1024次
如果说你认为这些数据全在内存里头
那么这两种做法
我们在内存里头任何一个单元在访问的时候
它都是使用的时间是一样的
那这两种算法是没有区别的
好 如果说我们在这里头考虑到物理内存的量小
那么这时候呢这两种做法
它的区别呢就是巨大的
所以在这儿呢不同的程序
如果说你背后利用了虚拟存储
那你在这里头呢需要很小心的
去使用你的编程方法 以便于提高它的局部性
这个提高它的局部性
也有利于提高你的程序的这个性能
好 基于这样一种做法呢
我们说在这里头它可以很好的有局部性的特征
那接下来我们会说基于这种局部性的特征
我们怎么来实现我们的虚拟存储系统