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