《虚拟存储器.ppt》由会员分享，可在线阅读，更多相关《虚拟存储器.ppt（58页珍藏版）》请在三一办公上搜索。
1、2 虚拟存储器,1961年英国曼彻斯特大学Kilbrn等人提出70年代广泛地应用于大中型计算机系统中目前许多微型机也开始使用虚拟存储器是进一步完善主存-辅存存储层次，解决主存容量提出的。,虚拟存储器的特点,多个进程可以共享主存空间程序员不必做存储管理工作采用动态再定位，简化了程序的装入,目录,不同的虚拟存储管理方式 页式虚拟存储器构成 页式虚拟存储器实现中的问题,虚拟地址空间,实际地址空间,映射,压缩,不同的虚拟存储管理方式,通过增设地址映像表机构来实现程序在主存中的定位。这种定位技术是将程序分割成若干较小的段或页，用相应的映像表机构来指明程序的某段或某页是否已装入内存。段式管理 页式管理段页
2、式管理,段式管理,段为程序的逻辑单位段表，本身也是段，常驻内存，也可以在辅存，需要时调入主存。段表结构：段名、地址、装入位、段长、访问方式。段表基址寄存器：指明段表的启始地址。能使大程序分模块编制，并行编程，缩短时间便于几道程序共用已在内存内的程序和数据；各段是按其逻辑特点组合的，容易以段为单位实现存储保护。人工建立。,2.5k,主程序(0段),1k,1段,2段,3段,0,500,0,200,0,200,0,段号,段长,起址,0,1k,8k,1,500,16k,2,200,9k,3,200,30k,0,8k,9k,16k,30k,程序空间,主存储器,地址映象方法：每个程序段都从0地址开始编址，
3、长度可长可短，可以在程序执行过程中动态改变程序段的长度。地址变换方法：由用户号找到基址寄存器从基址寄存器中读出段表的起始地址把起始地址与多用户虚地址中段号相加得到段表地址把段表中给出的起始地址与段内偏移D相加就能得到主存实地址,0,段表长度,段表基址,6,As,段名,起始地址,装入位,段长,访问方式,用户号U,段号S,段内偏移D,多用户虚地址,主存实地址,4,3,2,1,0,1,n-1,As,段表基址寄存器,一个用户（一道作业）的段表,段式管理优缺点,优点程序的模块化性能好便于程序和数据的共享程序的动态链接和调度比较容易便于实现信息保护缺点地址变换所花费的时间比较长，做两次加法运算主存储器的利
4、用率往往比较低对辅存（磁盘存储器）的管理比较困难,段分配算法,首先分配：顺序扫描可用区域表，当找到第一个不小于调 入段长度的可用区时，立即分配。最佳分配：先扫描全部可用区域表，然后寻找一个可用区进行分配，使之分配后段间可用区零头最小。,举例,页式管理,页式虚拟存储器把虚拟地址空间划分成一个个固定大小的块,每块称为一页,把主存储器的地址空间也按虚拟地址空间同样的大小划分为页。页是一种逻辑上的划分，它可以由系统软件任意指定。虚拟地址空间中的页称为虚页，主存地址空间中的页称为实页。每个用户使用一个基址寄存器（在CPU内），通过用户号U可以直接找到与这个用户程序相对应的基址寄存器，从这个基址寄存器中读
5、出页表起始地址。访问这个页表地址，把得到的主存页号p与虚地址中的页内偏移直接拼接起来得到主存实地址。,页式管理,把主存空间和程序空间机械地等分成固定大小的页，按顺序编号；页表。如下图。特点：页表项简单，查找速度快；页面大小固定不利于系统的效率，有些系统可调整其大小。例：MC88200 应用程序 4kb 系统程序512kb页式管理在存储空间较大时，由于页表过大，效率降低。存储空间的保护困难。,举例,虚地址空间32位，页面大小为1kb（10位）页表地址段将达22位，32-10=22 页表的长度为4兆行(222=4096k=4M)如主存容量为8MB则页表字段为13位，每行为2+1字节 则页表容量为
6、4MB*3=12MB主存容量,0页,1页,2页,3页,页号,主存页号,0,1,2,3,用户程序,主存储器,页表,页式虚拟存储器的地址映象,Pa,装入,修改,主存页号,标志,用户号U,虚页号P,页内偏移D,页内偏移d,2,p,Pa,页表基址,页表,实页号p,页式管理的优缺点,优点主存储器的利用率比较高页表相对比较简单地址变换的速度比较快对磁盘的管理比较容易缺点程序的模块化性能不好页表很长，需要占用很大的存储空间。,段页式管理,页式：对应用程序员完全透明，由系统划分.硬件较少，地址变换速度快，调入操作简单，静态连接程序；段式：段独立，有利于程序员灵活实现段的连接、段的扩大/缩小和修改，而不影响其他
7、段，易于针对其特定类型实现保护，把共享的程序或数据单独构成一个段，从而易于实现多个用户、进程对共用段的管理，动态连接程序；特点：访存两次。段页式：把实存机械地等分成固定大小的页，程序按模块分段，每个段又分成与主存页面大小相同的页。,地址变换方法：先查段表，得到该程序段的页表起始地址和页表长度再查页表找到要访问的主存实页号最后把实页号p与页内偏移d拼接得到主存的实地址。,装入,修改,实页号,标志,用户号U,段号S,页内偏移,页内偏移,0/1,1,p,A,实页号p,虚页号P,As,装入,1,修改,0/1,页表地址,Ap,As,页式虚拟存储器构成,多用户虚地址Ns,实存地址np,实存空间,虚存总空间
8、,2nv页,2Nv页包括2u个用户，每个用户为2Nv页。,2Nr,2nr,2Nr=2nr,地址映象和变换,地址映象：是将每个虚存单元按某种规则（算法）装入（定位于）实存，即建立多用户虚地址Ns与实存地址np之间的对应关系。地址变换：是程序按照这种映象关系装入实存后，在执行时，多用户虚地址Ns如何变换成对应的是地址np。页面争用（实页冲突）：发生两个以上的虚页想要进入主存中同一个页面位置的现象。,地址变换的原则,减少实页冲突硬件少、成本低实现方便、变换速度快。由于虚存空间远远大于实存空间，因此页式虚拟存储器常采用全相联映像。,全相联映像,任何虚页可以映象装入到任何实页位置。冲突概率最低。,页面位
9、置0,页面位置1,页0,页1,页2,主存,虚存,每道程序任何虚页可映像到任何实页位置,全相联映像的页表法,页表法,nv,装入位,2u+Nv行,全相联映像的相联目录表法,相联目录表法,u+Nv,nv,2nv行相联比较,页表法与相联目录表法的比较,替换算法,页面替换发生时间：当发生页面失效时，要从磁盘中调入一页到主存。如果主存所有页面都已经被占用，必须从主存储器中淘汰掉一个不常使用的页面，以便腾出主存空间来存放新调入的页面。替换算法的确定主存的命中率 是否便于实现，软、硬件成本,页面替换算法的使用场合,虚拟存储器中，主存页面的替换，一般用软件实现Cache块替换一般用硬件实现虚拟存储器的快慢表中，
10、快表存储字的替换，用硬件实现虚拟存储器中，用户基地址寄存器的替换，用硬件实现在有些虚拟存储器中目录表的替换,替换算法（续）,随机算法（Random，RAND）：用软的或硬的随机数产生器来形成主存重要被替换页的页号。简单，易于实现没有利用历史信息命中率低，很少使用先进先出算法（First-In First-Out，FIFO）：选择最早装入主存的页作为被替换的页。配置计数器字段虽然利用历史信息，但不一定反映出程序的局部性,替换算法（续）,近期最少使用算法（Least Recently Used，LRU）：选择近期最少访问的页作为被替换的页。配有计数器字段。比较正确反映程序的局部性。优化替换算法（O
11、ptimal Replacement Algorithm，OPT）:是在时刻t找出主存中每个页将要用到时刻ti，然后选择其中ti-t最大的那一页作为替换页。理想化算法,举例1,设有一道程序，有1至5共5页，执行时的地址流为：2，3，2，1，5，2，4，5，3，2，5，2分别采用FIFO、LRU、OPT算法。,说明,命中率与地址流有关例如：一个循环程序，FIFO、LRU的命中率明显低于OPT。（下一张）颠簸现象：连续不断出现页面失效。命中率与分配给程序的主存页数有关。主存页数增加，LRU命中率提高，至少不会下降，而FIFO不一定。(P115,图4.17),举例,一个循环程序，依次使用P1，P2，
12、P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如下图所示。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去的情况，这就是“颠簸”现象。,举例2,一个程序共有5个页面组成，程序执行过程中的页地址流如下：P1,P2,P1,P5,P5,P1,P3,P4,P3,P4假设分配给这个程序的主存储器共有3个页面。给出FIFO、LRU、OPT 三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。,堆栈型替换算法的定义,对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有mn。如
13、果在任何时刻t，主存页面数集合Bt都满足关系：Bt(m)Bt(n)，则这类算法称为堆栈型替换算法。,堆栈型算法的基本特点,随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。LRU、OPT都是堆栈型算法FIFO是非堆栈型算法提出使系统性能可以更优的动态算法。由操作系统来动态调节分配给每道程序的实页数。,虚拟存储器工作的全过程,书中 P117-118,页式虚拟存储器实现中的问题,页面失效的处理页面失效会在一条指令的分析或执行过程中发出。页面失效时一种故障，不是一般的中断；注意保护现场,采用后援寄存器技术、预判技术；选择合适的替换算法；,页式虚拟存储器实现中的问题,提高虚拟存储器等效访
14、问速度的措施要求：提高命中率，加快访存时间；命中率受很多因素影响，如：地址流、页面调度策略、替换算法、页面大小、主存容量等。访存时间，解决Ns-np的转换。快表：相联目录表，慢表：页表快表-慢表存储层次的替换算法一般采用LRU法。,散列函数目的：把相联访问变成按地址访问，从而加大快表容量散列（Hashing）函数：AhH(Pv),20位左右 58位采用散列变换实现快表按地址访问避免散列冲突：采用相等比较器地址变换过程：相等比较与访问存储器同时进行,虚拟存储器举例,I BM370/168计算机的虚拟存储器快表结构及地址变换过程。虚拟地址长36位，页面大小为4KB，每个用户最多占用4K个页面，最多
15、允许16个用户，但同时上机的用户数一般不超过6个。采用了两项新的措施：采用两个相等比较器用相联寄存器组把24位用户号U压缩成3位,页式虚拟存储器实现中的问题,影响主存命中率CPU效率的某些因素程序地址流、替换算法、实页数、页面调度策略页面大小通常为1KB到4KB。,命中率H,页面大小Sp,S1,2S1,S1：某道程序的主存容量Sp：页面大小S1一定时：Sp由小增大，H逐渐增大 增达到最大值，下降。增大S1可增大Sp。,主存容量与命中率的关系,主存命中率H随着分配给该程序的主存容量S的增加而单调上升。在S比较小的时候，H提高得非常快。随着S的逐渐增，H提高的速度逐渐降低。当S增加到某一个值之后，H几乎不再提高。,页面调度方式与命中率的关系,请求式：当使用到的时候，再调入主存预取式：在程序重新开始运行之前，把上次停止运行前一段时间内用到的页面先调入到主存储器，然后才开始运行程序。可以避免在程序开始运行时，频繁发生页面失效的情况。如果调入的页面用不上，浪费了调入的时间，占用了主存资源。,
