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