经贸组成原理课件带音乐第七章

第七章存储系统7.1存储系统的层次结构7.2高级缓冲存储器7.3虚拟存储器7.4相联存储器7.1存储系统的层次结构1.主存和辅存的概念2.主存和辅存在操作系统的控制下，通过软硬件把主存和辅存统一成为一个整体，形成一个存储层次。这个层次拥有接近于主存的速度和辅存的容量，价格也接近于辅存的价格。3.在CPU和主存之间有高速缓冲存储器cache，这完全是由硬件来完成的。Cache－主存的速度接近于cache，而容量与价格接近于主存。

Cache的速度接近于CPU。1.三级结构的存储器系统：将高速缓缓冲存储器、主存储器和辅助（虚拟）存储器组成的统一管理、调度的一体化三级结构的存储器系统。3.三种存储器的比较

(1)高速缓存（Cache）：速度快，容量小，用于临时存放运行中的指令和少量数据；

(2)主存：速度、容量一般，用于临时存放运行中的大量程序和数；

(3)辅存：速度慢，容量大，用于永久存放大型程序软件和数据库。4.采用三级结构的目的和方法

(1)Cache-主存层次：解决CPU与主存间速度不匹配问题，使系统具有主存容量和接近于Cache速度。采用地址映像方式，以字块为基本信息单位。

(2)虚拟存储器-主存层次：解决主存容量小、运行成本高的问题，使系统具有辅存容量和接近主存速度，且造价和运行成本低。采用地址变换方式，以段、页为基本信息单位。局部性原理、一致性原则和包含性原则1.局部性原理——三级结构存储器系统运行原理基础(1)时间局部性：在较小的时间间隔内，最近被访问的指令和数据很可能再次被访问；(2)空间局部性：这些最近被访问的指令和数据往往集中在一小片存储区域中；(3)指令执行方式局部性：顺序执行较转移执行可能性大。3.一致性原则：同时存放在三类存储器中的信息，在三类存储器中必须保持同值。

2.包含性原则：处在内层的存储器的信息一定包含在各外层存储器中。即内层存储器中信息是外层存储器所存信息的一小部分的副本。

Cache：一种容量小、速度快，用静态存储器器件实现的存储器。作用：解决CPU与主存速度不匹配的问题，使系统速度接近于CPU，容量接近于主存。7.2高速缓冲存储器（cache)7.2.1cache存储器工作原理根据程序访问的局部性要设置cache.设置cache可以存放当前使用的程序和数据，提高了程序的执行速度，所以叫高速缓冲器。基本原理：将CPU最近访问的指令和数据从主存复制到Cache中，当CPU下次再使用这些信息时，可直接从快速的Cache中得到而不必访问主存，从而提高了CPU的运行效率。Cache的基本结构如图所示：1.Cache的组织形式：

(1)数据字段：保存从主存复制来的数据(2)标志字段：保存相应主存单元的地址

(3)有效位字段：用1/0表示该Cache单元的数据字段和标志字段是否有效。

2.Cache的运行原理：

(1)CPU将主存信息读入CPU的同时，也将信息写入数据字段，并将该数据所对应的主存地址也写入标志字段。(2)CPU下次访问主存时，先将该地址与标志字段内容相比较，若地址值相同，则表示数据内容即为要读的数据，可直接访问Cache，同时将有效位字段置1（命中）；否则，再访问主存，有效位字段置0。(3)利用算法如先进先出FIFO、近期最少用法LRU或优化替换法OPT将非命中的数据逐步替换掉。(4)根据局限性原理，CPU访问的绝大部分信息可直接从Cache中得到。命中与不命中：将主存地址m位与cache某块的标记相比较，当比较结果相等时，说明所需要的数在cache中，可以直接在cache和CPU中直接传送（字）。当比较结果不相等，说明需要的数据没有在cache中，就要把该数据所在的整个字块从主存一次调进来。前者称为命中，后一种情况称为不命中。设主存有2n个单元，地址码为n位，将主存分块，每块有B个字节，则共分成M=2n/B块。cache也由同样大小的块组成。在cache中，每一块都有一个标记指明它是那一块的副本，设主存地址为n位，且n=m+b,则可得出：主存的块数M=2m，块内字节数B＝2b。Cache的地址码为（c+b)位。Cache的块数为2c.块内字节数与主存相同。Cache读工作方式设计的概念命中率：CPU所要访问的信息在cache中的比率，而将所要访问的消息不在cache中的比率称为失败率。提高命中率的方法cache的容量增大。替换算法：把新的字块调入主存的过程，cache相应的位置被其他字块占有，就必须去掉旧的字块，让位给新的字块。这种替换会用到替换算法。.

cache的写操作策略

由于cache的内容只是主存部分内容的拷贝，它应当与主存内容保持一致。而CPU对cache的写入更改了cache的内容。如何与主存内容保持一致，可选用如下三种写操作策略。①写回法写回法要求：当CPU写cache命中时，只修改cache的内容，而不立即写入主存；只有当此行被换出时才写回主存。这种方法使cache真正在CPU主存之间读/写两方面都起到高速缓存作用。对一个cache行的多次写命中都在cache中快速完成，只是需要替换时才写回速度较慢的主存，减少了访问主存的次数。实现这种方法时，每个cache行必须配置一个修改位，以反映此行是否被CPU修改过。当某行被换出时，根据此行修改位是1还是0，来决定将该行内容写回主存还是简单弃去。如果CPU写cache未命中，为了包含欲写字的主存块在cache分配一行，将此块整个拷贝到cache后对其进行修改。主存的写修改操作统一地留到换出时再进行。显然，这种写cache与写主存异步进行的方式可显著减少写主存次数，但是存在不一致性的隐患。②全写法全写法要求：当写cache命中时，cache与主存同时发生写修改，因而较好地维护了cache与主存的内容的一致性。当写cache未命中时，只能直接向主存进行写入。但此时是否将修改过的主存块取到cache，有两种选择方法：一种称为WTWA法，取主存块到cache并为它分配一个行位置；另一种称WTNWA法，不取主存块到cache。全写法是写cache与主存同步进行，优点是cache中每行无需设置一个修改位，以及相应的判断逻辑。缺点是，cache对CPU向主存的写操作无高速缓冲功能，降低了cache的功效。③写一次法写一次法是基于写回法并结合全写法的写策略：写命中与写未命中的处理方法与写回法基本相同，只是第一次写命中时要同时写入主存。这是因为第一次写cache命中时，CPU要在总线上启动一个存储写周期，其他cache监听到此主存块地址及写信号后，即可拷贝该块或及时作废，以便维护系统全部cache的一致性。奔腾CPU的片内数据cache就采用了写一次法。

在一个程序执行期间，设Nc表示cache完成存取的总次数，Nm表示主存完成存取的总次数，h定义为命中率，则有h=Nc/（Nc+Nm)若tc表示命中时的cache访问时间，tm表示未命中时的主存访问时间，1-h表示未命中率，则cache/主存系统的平均访问时间ta为：ta=htc+(1-h)tm

【例】CPU执行一段程序时，cache完成存取的次数为1900次，主存完成存取的次数为100次，已知cache存取周期为50ns，主存存取周期为250ns，求cache/主存系统的效率和平均访问时间。解：h=Nc/(Nc+Nm)=1900/(1900+100)=0.95r=tm/tc=250ns/50ns=5e=1/[r+(1-r)h]=1/[5+(1-5)×0.95]=83.3%ta=tc/e=50ns/0.833=60ns7.2.2cache存储器组织

1.地址映像为了把主存块放到cache中，必须应用某种方法把主存地址定位到cache中，称做地址映射。“映射”一词的物理含义是确定位置的对应关系，并用硬件来实现。这样当CPU访问存储器时，它所给出的一个字的内存地址会自动变换成cache的地址。由于采用硬件，这个地址变换过程很快，软件人员丝毫未感觉到cache的存在。这种特性称为cache的透明性。地址映射方式有全相联方式、直接方式和组相联方式三种，下面分别介绍。假设主存储器空间被分为2m个块，字块大小为2b个字；cache存储空间被分为2c个同样大小的块。(1)直接映射方式直接映射方式也是一种多对一的映射关系，但一个主存块只能拷贝到cache的一个特定行位置上去。cache的行号i和主存的块号j有如下函数关系：

j

=imod2c

J是cache的字块号，I是主存的字块号。

显然，主存的第0块，第m块，第2m块，…，第2sm块只能映射到cache的第0行；而主存的第1块，第m+1块，第2m+1块，…，第2sm+1块只能映射到cache的第1行。下图表示直接映射方式的示意图。

直接映射方式的优点是硬件简单，成本低。缺点是每个主存块只有一个固定的行位置可存放。如果块号相距m整数倍的两个块存于同一cache行时，就要发生冲突。发生冲突时就要将原先存入的行换出去，但很可能过一段时间又要换入。频繁的置换会使cache效率下降。因此直射映射方式适合于需要大容量cache的场合，更多的行数可以减小冲突的机会。

（2）全相联映射方式全相联映像方式是最灵活但成本最高的一种方式。它允许主存中的每一字块映像到Cache的任何一个字块位置上，也允许从确实已被占满的Cache中替换出任何一个旧字块。主要问题是在访问Cache时，需要和Cache的全部标记进行“比较”才能判断出所访主存地址的内容是否已在Cache中。由于Cache速度要求高，所以全部“比较”操作都要用硬件实现，通常由“按内容寻址的”相联存储器完成。优点：灵活性好，命中率高。缺点：电路复杂、成本高。

（3）组相联映射方式全相联映射和直接映射两种方式的优缺点正好相反。从存放位置的灵活性和命中率来看，前者为优；从比较器电路简单及硬件投资表说，后者为佳，而组相联映射方式是前两种方式的折衷方案，它适度地兼顾了二者的优点又尽量避免二者的缺点，因此被普遍采用。这种方式将cache分成u组，每组v行。主存块存放到哪个组是固定的，至于存到该组哪一行是灵活的，即有如下函数关系m＝u×v组号g＝j modu

内存地址中主存s位的块号划分成两部分：低序的d位(2d＝u)用于表示cache组号，高序的s-d位作为标记(tag)与块数据一起存于此组的某行中。下图表示组相联映射的示意图。

2.

替换策略

cache工作原理要求它尽量保存最新数据。当一个新的主存块需要拷贝到cache，而允许存放此块的行位置都被其他主存块占满时，就要产生替换。替换问题与cache的组织方式紧密相关。对直接映射的cache来说，因一个主存块只有一个特定的行位置可存放，所以问题解决很简单，只要把此特定位置上的原主存块换出cache即可。对全相联和组相联cache来说，就要从允许存放新主存块的若干特定行中选取一行换出。如何选取就涉及到替换策略，又称替换算法。硬件实现的常用算法主要有以下三种：①最不经常使用(LFU)算法LFU算法认为应将一段时间内被访问次数最少的那行数据换出。为此，每行设置一个计数器。新行建立后从0开始计数，每访问一次，被访行的计数器增1。当需要替换时，对这些特定行的计数值进行比较，将计数值最小的行换出，同时将这些特定行的计数器都清零。这种算法将计数周期限定在对这些特定行两次替换之间的间隔时间内，因而不能严格反映近期访问情况。②近期最少使用(LRU)算法LRU算法将近期内长久未被访问过的行换出。为此，每行也设置一个计数器，但它们是cache每命中一次，命中行计数器清零，其它各行计数器增1。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。这种算法保护了刚拷贝到cache中的新数据行，符合cache工作原理，因而使cache有较高的命中率。对2路组相联的cache来说，LRU算法的硬件实现可以简化。因为一个主存块只能在一个特定组的两行中来做存放选择，二选一完全不需要计数器，只需一个二进制位即可。例如规定一组中的A行拷贝进新数据可将此位置“1”，B行拷贝进新数据可将此位置“0”。当需要置换时，只需检查此二进制位状态即可：为0换出A行，为1换出B行，实现了保护新行的原则。奔腾CPU内的数据cache是一个2路组相联结构，就采用这种简捷的LRU替换算法。

③随机替换随机替换策略实际上是不要什么算法，从特定的行位置中随机地选取一行换出即可。这种策略在硬件上容易实现，且速度也比前两种策略快。缺点是随意换出的数据很可能马上又要使用，从而降低命中率和cache工作效率。但这个不是随着cache容量增大而减小。研究表明，随机替换策略的功效只是稍逊于前两种策略。

7、2.3奔腾PC机是一个单CPU系统。它采用两级cache结构。安装在主板上的2级cache（L2），其容量是512KB，采用2路组相联映射方式，每行可以是32B，64B或128B。集成在CPU内的1级cache（L1），其容量是16KB，采用的也是2路组相联映射方式，每行是32B。L2的内容是32MB容量主存的子集，L1又是L2的子集，从而使L1未命中处理时间大大缩短。7.3虚拟存储器7.3.1、基本概念：虚拟存储器只是一个容量非常大的存储器的逻辑模型，不是任何实际的物理存储器，它借助于磁盘等辅助存储器来扩大主存容量，使之为更大或更多的程序所使用。

虚拟存储器指的是主存-外存层次。它以透明的方式给用户提供了一个比实际主存空间大得多的程序地址空间。此时程序的逻辑地址称为虚拟地址（虚地址），程序的逻辑地址空间称为虚拟地址空间。物理地址（实地址）由CPU地址引脚送出，它是用于访问主存的地址。设CPU地址总线的宽度为m位，那么物理地址空间的大小用2m来表示。

虚拟存储器的作用：解决主存容量小、运行成本高的问题，使系统具有辅存容量和接近主存速度。

基本原理：根据局限性原理，在一小段程序运行时间内CPU只会用到一小部分指令和数据，只需将这部分指令和数据调入主存，CPU直接从主存中读取；当需要更多的指令和数据时再随时从辅助存储器读取并调入主存。

主存-外存层次和cache-主存层次用的地址变换映射方法和替换策略是相同的，都基于程序局部性原理。它们遵循的原则是：①把程序中最近常用的部分驻留在高速的存储器中。②一旦这部分变得不常用了，把它们送回到低速的存储器中。③这种换入换出是由硬件或操作系统完成的，对用户是透明的。④力图使存储系统的性能接近高速存储器，价格接近低速存储器。两种存储系统的主要区别在于：

在虚拟存储器中未命中的性能损失要远大于cache系统中未命中的损失。主存-外存层次的基本信息传送单位主存-外存层次的基本信息传送单位可采用几种不同的方案：段、页或段页。段是按照程序的逻辑结构划分成的多个相对独立部分，作为独立的逻辑单位。例如过程、子程序。优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译、管理、修改和保护,也便于多道程序共享；某些类型的段具有动态可变长度,允许自由调度以便有效利用主存空间。缺点是因为段的长度各不相同，起点和终点不定，给主存空间分配带来麻烦，而且容易在段间留下许多空余的零碎存储空间，造成浪费。

页是主存物理空间中划分出来的等长的固定区域。优点是页面的起点和终点地址是固定的,方便造页表,新页调入主存也很容易掌握，比段式空间浪费小。缺点是处理、保护和共享都不及段式来得方便。段页式管理采用分段和分页结合的方法。程序按模块分段，段内再分页，进入主存以页为基本信息传送单位，用段表和页表进行两级定位管理。

7.3.2页式虚拟存储器：页式存储管理是将主存以页为信息单位进行分配和管理。在页式虚拟存储系统中，把虚拟空间分成页，称为逻辑页或虚页；主存空间也分成同样大小的页，称为物理页或实页。1.页:人为地将虚拟的逻辑空间和主存实际的物理空间等量(2n)划分为若干个基本信息单位。虚拟地址由虚页号和页内地址给出；而实地址由实页号和页内地址给出。2.页表:驻留在主存中的一个特定的区域，用于实现由逻辑地址到实际地址的变换。

3.地址变换：

(1)由逻辑地址中的虚页号与页表基地址寄存器的内容相加得到该虚页所对于的实页号；(2)由该表项的实页号与逻辑地址中的页内地址的内容拼接，即得到在主存中的实际地址。页式存储管理的空间浪费比段式管理要小得多，新页调入主存容易掌握，只要有空白页面就可。可能造成浪费的是程序最后一页的零头，是不能利用的页内空间。页式管理系统的缺点正好和段式管理系统相反，由于页不是逻辑上独立的实体，所以处理、保护和共享都不及段式来得方便。由于若访问存储器时，要先查页表在命中时要先访问主存去查页表，再访问主存才能取得数据，若没有命中则要页面替换、页面修改，访问主存的次数就更多了，因此要建立一个快表。这个由硬件组成的快表叫转换旁路缓冲器。虚页号同时查找快表和慢表，在快表中有虚页号时，慢表的查找会作废。若快表中没有则要浪费一个访存时间来查慢表。

7.3.3段页式虚拟存储器：段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。在这种方式中，把程序按逻辑单位分段以后，再把每段分成固定大小的页。例A（p125-11)：主存容量为4MB，虚存容量为1GB，则虚拟地址和物理地址各为多少位？如页面大小为4KB，则页表长度是多少？解：主存4MB=222B所以物理地址（主存地址）为22位虚存1GB=230B所以虚地址为30位页大小4KB=212B所以：页内地址段位数由4KB=212B，故为12位。7.3.3、段式存储管理

段式存储管理是将主存按段作为信息单位进行分配和管理。1.段:也称程序段，是指按程序的逻辑结构划分的多个独立的程序单位（例如过程、子程序、数据表、阵列等）。各段经过段间连接而形成规模较大的程序。因此，段构成了主存-辅存之间传送的基本信息单元。段由段名或段号表示，其长度取决于组成程序段的指令条数或组成数据段数据个数。2.逻辑地址:经过连接而组成的程序所占地址空间。程序员按逻辑空间编制程序，机器指令的地址码，即逻辑地址（虚拟地址）是由段号和段内地址组成。3.段表:驻留在主存中的一个特定的段，也可存放在辅存中。用于指明各段在主存中位置，用于实现由逻辑地址到实际地址的变换。段表在主存中的起始地址保存在段表基地址寄存器中。4.地址变换：将一个字（指令或数据）的逻辑地址转换为在主存中的实际地址的过程。(1)由逻辑地址中的段号与段表基地址寄存器内容相加得到段始地址；(2)检查该表项中的装入位是否为1，若为1，则表该段已调入内存；若为0，则将该段从辅存中调入主存。(3)段始地址与逻辑地址中的段内地址的内容相加，即得到在主存中的实际地址。段式管理系统的优点是段的分界与程序的自然分界相对应；段的逻辑独立性使它易于编译，管理，修改和保护，也便于多道程序共享。其缺点是容易在段间留下许多空余的零碎存储空间不好利用，造成浪费。7.3.4段页式虚拟存储器

段页式虚拟存储器是段式虚拟存储器和页式虚拟存储器的结合。它把程序按逻辑单位分段以后，再把每段分成固定大小的页。程序对主存的调入调出是按页面进行的，但它又可以按段实现共享和保护，兼备页式和段式的优点。缺点是在映象过程中需要多次查表。在段页式虚拟存储系统中，每道程序是通过一个段表和一组页表来进行定位的。段表中的每个表目对应一个段，每个表目有一个指向该段的页表起始地址及该段的控制保护信息。由页表指明该段各页在主存中的位置以及是否已装入、已修改等状态信息。如果有多个用户在机器上运行，多道程序的每一道需要一个基号,由它指明该道程序的段表起始地址。如果有多个用户在机器上运行，即称为多道程序，多道程序的每一道(每个用户)需要一个基号(用户标识号)，可由它指明该道程序的段表起始地址(存放在基址寄存器中)。这样，虚拟地址应包括基号、段号、页号、页内地址。格式如下：每道程序可由若干段组成，而每段又由若干页组成，由段表指明该段页表的起始地址，由页表指明该段各页在主存中的位置以及是否已装入等控制信息。

【例6】假设有三道程序(用户标志号为A，B，C)，其基址寄存器内容分别为SA，SB，SC，逻辑地址到物理地址的变换过程见下图：

在主存中，每道程序都有一张段表，A程序有4段，C程序有3段。每段应有一张页表，段表的每行就表示相应页表的起始位置，而页表内的每行即为相应的物理页号。请说明虚实地址变换过程。

【解】

地址变换过程如下：①根据基号C执行SC加1（段号）操作，得到段表相应行地址，其内容为页表的起始地址ｂ。②执行b+2（页号），得到物理页号的地址，其内容即为物理页10。③物理页号与页内地址拼接即得物理地址。如计算机只有一个基址寄存器，基号可不要，多道程序切换时，操作系统修改基址寄存器内容。

假如该计算机只有一个基址寄存器，那么基号可以不要，在多道程序切换时，则操作系统修改基址寄存器内容。

另外上述每一张表的每一行都要设置一个有效位。我们在上面讨论时假设相应行的有效位均为“1”，否则表示相应的表还未建立，访问失败，发出中断请求启动操作系统建表。可以看出，段页式虚拟存储系统由虚拟地址向实主存地址的变换至少需查两次表(段表与页表)。段、页表构成表层次。当然，表层次不只段页式有，页表也会有，这是因为整个页表是连续存储的。当一个页表的大小超过一个页面的大小时，页表就可能分成几个页，分存于几个不连续的主存页面中，然后，将这些页表的起始地址又放入一个新页表中。这样，就形成了二级页表层次。一个大的程序可能需要多级页表层次。对于多级表层次，在程序运行时，除了第一级页表需驻留在主存之外，整个页表中只需有一部分是在主存中，大部份可存于外存，需要时再由第一级页表调入，从而可减少每道程序占用的主存空间。

7.4相联存储器

1.相联存储器的基本原理相联存储器是指其中任一存储项内容作为地址来存取的存储器。选用来寻址存储器的子段叫做关键字。存放在相联存储器中的项可以看成具有KEY，DATA这样的格式。其中KEY是地址，DATA是被读写信息。相联存储器的基本原理是把存储单元所存内容的某一部分作为检索项(即关键字项)，去检索该存储器，并将存储器中与该检索项符合的存储单元内容进行读出或写入。2.相联存储器的组成相联存储器由存储体、检索寄存器、屏蔽寄存器、符合寄存器、比较线路、代码寄存器、控制线路等组成框图请看演示

检索寄存器：用来存放检索字，其位数和相联存储器的存储单元位数相