Virtual Memory


对虚拟存储器管理方式和Cache的知识需要了解逻辑地址、线性地址、物理地址的相关概念,若不清楚详见Logical Address?Linear Address?Virtual Address?


虚拟存储器

虚拟存储器通过增设地址映像机构来实现程序在主存中的定位。将程序分割成若干个,用相应的映像表指明该程序的某段或某页是否已装入主存。若已装入,同时指明其在主存中的起始地址;若未装入,就去辅存(磁盘)中调段或页,将其装入主存后再在映像表中建立好程序空间和实存空间的地址映像关系。
程序执行时先查映像表,将程序(虚)地址变成实(主存)地址后再访问。

段式管理

原理:程序是模块化的,一个程序总可以分解为多个在逻辑上相对独立的模块,每一个模块就是单独的一个,段的起点以0相对编址。当某个段由辅存调入主存,系统赋予该段一个基址,由基址+单元在段内的相对位移就可以形成主存中的实际地址。主存是按段分配的存储管理方式。

段表:每个在主存中的程序都有一个段(映像表)表来存放该程序各段在主存中的状况。段表本身也是一个段,一般在主存,也可以在辅存,需要时再调入主存。

段表项:段表中每一项(行),描述该道程序一个段的基本情况。

段表基址寄存器:主存中有N道程序,可设N个段表寄存器。对于每个程序,由基号(程序号)指出使用哪一个段表基址寄存器,然后段表基址寄存器中的段表基址字段指向程序在主存的起始地址,段表长度字段指明该程序所用段表的行(段)数。

段式管理的地址转换过程如下图:

对图中一些信息做一点解释:

  • 图示的段表基址寄存器,是由N个段表基址寄存器构成,每一行都是一个寄存器。
  • 图示的段表,其段名若就是程序每个段的序号,则可以省略。
  • 图示的段表中装入位为1表示已装入主存,访问方式在一般情况下,为空也不能省略。
  • 由图可知,段式管理下,虚地址被分为三各部分:基号(程序号),段号,段内位移
  • 由图可知段式管理的地址转化流程为:虚地址->段基址寄存器->段表-(段起始地址+虚地址中段内位移)->主存地址

页式管理

原理:把主存和程序空间都机械的分成固定大小的页,按页顺序编号。这样主存地址就由实页号np和页内位移nr两个字段组成。(划重点,待会会将其与段式管理比较)

页表页表项页表基址寄存器类比段式管理

页式管理的地址转换过程(最基础的一种)如下图:

下面对该图进行一些解释:

  • 在页表中,因为页式存储中程序的起点必处于一个页面的起点,用户程序中每一个虚地址就由虚拟页号N’v字段和页内位移Nr字段组成。
  • 虚存和主存的页面大小一致,因此页表中只需记录虚拟页号N’v主存页号nv的对应关系,不用保存页内位移。而且虚页号与页表行号对应,页表中不需要专门的虚页号字段。
  • 因为虚地址中的页内位移就是实地址中的页内位移,因此页式管理只需要将主存实页号页内位移拼起来就得到了主存地址。(回到刚刚划重点的地方,因为主存地址就由这两个字段组成,因此拼接起来就是主存地址了;而段式管理中,是通过基址+段内偏移的运算,计算出主存地址。)
  • 由页式和段式的图可以看出,段式管理实际上用了两个加法器,而页式只用了一个,这也是页式比段式存储更快一点的原因。
  • 同样,页表也存在于主存中。

地址的映像和变换

虚存一般比实际主存空间大很多,即N'v > nv,因此虚地址空间映射到实地址空间必然会进行压缩,其示意图如下:

而且,页式存储器一般都采用全相联映像:让每一道程序的任何虚页可以映射到任何实页位置,如下图所示:

由于主存中装入位为1的行最多只有2^nv行,使得页表中绝大部分实页号字段和其他字段都成为无用的空间,大大降低了页表空间的利用率,因此,有两种方式来提高页表的空间利用率。

  1. 目录表法

该方法是把页表压缩成只存放已装入主存的虚页,如图:

需要注意的是,该表与上面的页表有所不同,该表是通过虚地址的基号字段和用户虚页号一起,去相联比较页表中是否有满足的项。(而普通的是通过页表基地址+用户虚页号直接得到表中位置)。但该方式查表速度慢,造价较贵,一般不使用目录表来存储全部虚页号和实页号的对应关系,但它可以用来提高地址变换速度。

  1. 辅存实地址

将页表中装入位为0的行用实页号字段存放该程序此虚页在辅存中的实地址,以便掉页时实现用户虚页号到辅存实地址的变换。这种方法在辅存实地址位数与用户虚页号位数相差太大时就很难利用。

页面替换算法

当主存装满时,这时又有新的指令或数据(不在主存),这是页面就会失效,需要从辅存中调页替换。

随机算法(RAND):采用软或硬件随机数产生器产生要被替换页的页号
先进先出算法(FIFO):选择最早装入主存的页作为被替换页
近期最少使用算法(LRU):选择近期最少访问的页作为被替换页

主存页面表:每一行用于记录主存中各页的使用情况,该表整个系统只有一个。注意:不是页表!不是页表!不是页表!

页式虚拟存储器工作全过程

快表(TLB)

为了减少访存次数,往往把页表中最活跃的几个页表项复制到高速缓存中,这种在高速缓存中的页表项组成的页表就称位快表。这样,在地址转换中,同时查页表和快表,若在快表中查到,则停止查找页表;若快表中没有查到,则在页表中查,查到后访存并将此虚页号与实页号的对应关系送入快表。这里也需要用替换算法替换快表中已不用的内容。

快表其实可以看成一个目录表,其与慢表(页表)的内部地址变换如下图:

为了提高快表的命中率和查表速度,可以用散列方法实现按内容查找,然后找到对应表项还需要与虚页号Nv对比,一致则形成nv继续后续操作,否则出现了散列冲突,得去慢表中查找。

在IBM370/168中,为了减少散列冲突,快表中每个地址单元中存放多对虚页号与实页号的映像关系,用两套相等电路比较,只有都不相符,才是不命中,再去慢表中获得nv。另外,该虚拟存储器的页表基址寄存器是一个相联寄存器,其行数并不是计算机允许的最大用户数,而是计算机上同时运行的用户的最大个数(比如最多允许2^24个用户,但实际同时存在的用户最多只有六个)。这样大大减少了查询时间,使获取nv更快。

两级页表和多级页表

一级页表所占内存连续空间太大,因此,提出了两级页表甚至多级页表的概念。

两级页表分为页目录表页表,页目录表中每一行称为页目录项,用于记录每一个页表所在的内存的初始位置;页表中的页表项,则和一级页表一样,用于记录nv等信息。这时候,页表就相当于被离散化,就能够提高内存空间利用率。

段页式管理

原理:把主存等分为固定的页,程序按模块分段,每个段又分成与主存页面大小相同的页。每到程序通过一个段表和相应的一组页表定位。

段页式管理的定位映像机构及其地址的变化过程如下图:

其中通过段表得到的就是线性地址,然后线性地址经过页式管理变为主存地址。

-------------Thanks for Reading-------------

本文标题:Virtual Memory

文章作者:asKylin

发布时间:2020年05月22日 - 09:05

最后更新:2020年06月30日 - 15:06

原始链接:http://askylin.top/2020/05/22/ComputerStorage/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。