第四章 存储体系

4.2.2 页式虚拟存储器的构成

1.地址的影响和变换

页式虚拟存储器是采用页式存储和管理的主存——辅存层次,它将主存程序空间都按相同大小机械的分页,并让程序的起点总在页的起点上。

程序员用指令地址码Ni来编写每道程序,Ni由用户虚页号Nv'和页内地址Nr组成。

主存地址则分成实页号nv与页内位移nr两部分,其中nrNr总是一样,大多数虚拟存储器中每个用户程序空间与与实际主存空间大的多,一般Nv'>nv

虚拟存储器系统总的多用户虚地址Ns就由用户标志号u,用户的虚页号Nv`及页内地址Nr三部分构成,总的虚存空间是:

可将uNv'合并成多用户虚页号Nv

地址的映像是每个虚存单元按某种算法(规则)装入(定位于)实主存,建立起多用户虚地址Ns与实(主)地址np之间的对应关系。

地址的变换是指程序按照这种映像关系装入实存后,在执行中,如何将多用户虚地址Ns变换成对应的实地址np。

虚实地址对应关系及空间的压缩

虚实地址对应关系及空间的压缩

由于是把大的虚拟空间压缩到小的虚拟空间,主存的每一个页面位置可能对应多个虚页,对应多少个虚页与采用的映像方式有关,这就可以发生页面冲突,只能让主存在该页页面位置先装入其中一页,待其退出之后再装入另一个,执行效率下降。

因此,映像方式的选择应考虑能否尽量减少实页冲突概率,同时考虑硬件是否少,成本是否低,实现是否方便,地址变换速度手否够快等。

由于虚存空间大于实存空间,页式虚拟存储器一般都采用让每道程序的任何虚拟页可以映像装入任何实页位置的全相联映像。

仅当一个任务要求同时调入主存的页数超出2nv时,才会出现冲突,因此,全相联映像的实页冲突效率最低。

全相联映象

全相联映象

全相联映像用表作为地址影响表,故称为页表法。

整个多用户虚存空间可对应2u个用户(程序),但主存最多同时只能对其中N个用户(程序)开放,由基号b标识的N道程序中的每一道都有一个最大为2Nv'行的页表。

而主存总工只有2nv个实页位置,因此,N道程序页表的全部行中,装入位为1的最多有2nv行,由于,使得绝大部分实页字段无法使用,造成页表空间利用率降低。

  • 解决方法1

若辅存实地址的位数与用户虚页号字段位数差别不大,可采用将装入位为0的行用实页号nv字段存放该程序此虚页在辅存中的实地址,以便掉页时实现用户虚页号到辅存实地址的转换。

  • 解决方法2

把页表压缩成只存放已装入主存的那些虚页(用基号b和Nv'标识)与实页位置(nv)的对应关系,该表最多为2nv行,称为相联目录表法,采用按内容访问的相联存储器构成。

目录表法

目录表法

按内容访问的相联存储器不同于按地址访问的随机存储器。

随机存储器一个存储周期只能按给出的一个地址访问存储单元。

相联存储器在一个周期中能将给定的Nv同时与目录表全部2nv个单元对应的虚页号字段内容比较,进行相联查找。

查到表示已装入,该单元存放的实页号nv就是虚页存放位置。读出并拼接上Nr就是访实存地址np

未查到表示未装入,去辅存装入。

其他字段可提供访问方式保护、其他工作,无需设置装入位。

目录表行数为2nv,比页表少,但主存页数2nv还是很大的,用2nv行相联存储器,造价高,查表速度慢,所以虚拟存储器不直接存储(按目录表),但它可以调高地址变换速度。

要把一道程序的虚页调入主存,需给出在辅存中的实际地址,为提高效率,一般按信息块编址,块大小等于页面大小,磁盘辅存实(块)地址Nvd格式:

Nvd格式

Nvd格式

将多用户虚页号Nv变成辅存实(块)地址Nvd用类似查找页表方式为每道程序(用户)设置一个存放用户虚页号Nv'与辅存实(块)地址Nvd映像关系的表,用于外部地址变换,称之为外页表。

Nv'nv关系用于内部地址变换的页表称为内页表。

每个用户的外页表也是2Nv'行,每行用装入位字段表示内容是否有效,为1时,有效,是该信息块(页面)在辅存(磁盘)中的实际位置。

外页表内容在程序装入辅存时就填好。

由于虚拟存储器页面失效率一般低于1%,调用外页表进行虚地址到辅存地址变换机会少,辅存调页速度低,因此,外页表常存于辅存,某道程序初始运行时,才把外页表内容转录到内页表的实页地址字段。

查外页表速度要求低,可用软件时间以节省成本,程序/进程切换时所需时间比调页时间短,发生页面丢失,不必让处理机等待,而是程序换道。

虚地址到辅存实地址的变换

虚地址到辅存实地址的变换

2.页面替换算法

当处理机要用到的指令或数据不在主存中时,导致页面失效,去辅存调入主存,存在虚存空间比主存大,出现主存满页面失效,这时辅存一页调入主存会放生冲突。

冲突只有强制腾出主存某个页才能接纳由辅存调来的新页,那个页被替换,是替换算法要解决的问题。

替换算法的确定主要看命中率,便于实现以及成本。

随机算法(Random,RAND)是用软的或硬的随机数产生器,产生主存中要被替换的页号,算法简单,易于实现,无历史信息,反应不了程序局限性,主存命中率低,已不采用。

先进先出算法(First In First Out,FIFO)选择最早装入主存的页作为被替换的页,算法实现方便,只要在操作系统为主存管理所设置的主存页面表中给每个实页配一个计数器字段。

一页装入主存时,该页计数器清零,其他已装入主存页计数器都加1,需替换时,计数器最大的页的页号就是最先进入主存而现在准备替换掉的页号,虽然利用了主存使用的历史信息,但不一定能正确地发宁程序的局部性,因为最先进入的页可能是使用最频繁的页。

近期最少使用算法(Least Recently Used,LRU),选择近期最少访问的页作为被替换页,能比较正确地放映程序局部性。但算法实现比较困难,需要为每个实页都配一个字长很长的计数器,所以用变形,近期最久未访问的页作为被替换页,多少变有无。

主存页面表,每行用来记录主存各页的使用状况,存于主存,整个操作系统只有一个,页号顺序,可省去,用相对于主存页面表起点的行数表示。

程序占用页/段,由程序号,段页号指明,实现近期最久未使用算法,开始时,使用位0,被访问过的页,由硬件置使用位为1,由于全相联映像,调入页可进入主存页任一占用位为0的实页位置,装入就将该实页占用位置为1,只有占用位都是1又发生页面失效时,只替换使用位为0的页。

若使用位全为1,则无法替换。

  • 解决方法1

使用位全为1时,硬件强制置0,从概念上看,近期最少使用的“期”是从上次使用位全为0到这次使用位全为0的这段时期,这个时期的成端是随机的,所以叫随机期法。

  • 解决方法2

定期置全部使用位为0,给每个实页再配一个未使用过计数器Hs(历史位),定期地每隔△t时间扫描所有使用位,凡使用位为0的,Hs+1并让使用位持续为0,对于使用位为1的,将其Hs的使用位都清零,Hs值最大的就是被替换的页。

使用位反应了一个△t时期内的页面使用情况,Hs则反应多个△t期内页面的使用情况。

此方法比近期最少使用法所耗费的计数器硬件少,由于页面失效后调页时间长加上程序换道,主页表的修改可软硬结合地实现。

可在主存页面表中增设修改位,以记录主存是否修改过,未改写过,不操作,改写过,写入辅存再替换。

近期最少使用和近期最久未用两种算法都是LRU法,与FIFO法一样,都是根据页面使用的“历史”情况来预估未来的页面使用情况,

根据未来实际使用情况将未来的近期不用页替换出去,一定会有最高的命中率,这种算法称为优化替换算法(Optimal,OPT),在时刻t找出主存中每个页都要用到的时刻ti,然后选择其中ti+t最大的一页替换。

OPT是一种理想算法,可以被用来作为评价其他替换算法好坏的标准。

替换算法一边通过典型的页地址流模拟替换过程,再根据命中率高低来评价好坏,影响因素:替换算法的选择、地址流、页面大小、主存容量。

什么是堆栈型替换算法呢? 设A是长度为L的任意一个页面地址流,t为已处理过t-1个页面的时间点,n为分配给该地址流的主存页面数,Bt(n)表示在t时间点、在n页的主存中的页面集合,Lt表示到t时间点已遇到过的地址流中相异页的页数。如果替换算法具有下列包含性质:

dzsf

则此替换算法属堆栈型的替换算法。

LRU、OPT是堆栈型算法,FIFO不是。

用堆栈处理技术对地址流进行模拟处理时,主存在t时间点的状况用堆栈St表示。St是Lt个不同页面号在堆栈中的有序集,St(1)是t时间点的St的栈顶项,St(2)是t时间点的St的次栈顶项,依次类推。按照堆栈型算法具有的包含性质,必有

dzxz

结论1 命中率与所选用替换算法有关,LRU由于FIFO,命中率也与页地址流有关。

结论2 命中率与分配给程序的主存页数有关。(FIFO不一定)

结论3 堆栈型算法有随分配给该道程序实页数n增加,命中率H会单调上升这一贴点,可以对LRU改进,提出使系统性能更优的动态算法。

根据各道程序运行中的主存页面失效率,由操作系统动态分配各道程序实页数。使整个系统总的主存命中率和主存利用率得到提高。此算法为页面失效频率(PEF)算法。

3.虚拟存储器工作的全过程

页式虚拟存贮器工作的全过程

页式虚拟存贮器工作的全过程

与本文相关的文章
版权声明
转载保留版权: 大D综合研究院 | 《《计算机系统结构》读书笔记(九)》
本文链接地址:https://www.dadclab.com/archives/3104.jiecao
本文版权采取:BY-NC-SA 协议进行授权,除特别标注,本站所有文章均为原创。
转载须知:如果您需要转载本文,请将版权信息,版权授权方式,以及本文的链接地址注明,多谢合作。
本文被贴上了: , , , , , 标签