本章重点是页式虚拟存储器映象及地址变换过程；LRU，FIFO的替换算法；LRU的堆栈分析过程；Cache组相联地址映象和LRU块替换；虚存，Cache的性能分析，要求达到综合应用的水平。本章是重点章。要求掌握的基本概念有：LRU,FIFO ,全相联、直接映象，组相联，快表、命中率，地址变换，页式，段式，段页式管理，虚拟存储器，高速缓存等等。
一、访存的局部性原理
计算机对存储器的要求是高速度、大容量、低价格。
从大量的统计中得到的一个规律是，程序中对于存储空间90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在存储空间的其余90%的区域中。这就是通常说的局部性原理。访存的局部性规律包括两个方面：
-
1、时间局部性：如果一个存储项被访问，则可能该项会很快被再次访问。
-
2、空间局部性：如果一个存储项被访问，则该项及其邻近的项也可能很快被访问。
人们为了解决存储器容量和速度的矛盾，应用了访问局部性原理，把存储体系设计成为层次化的结构以满足使用要求。在这个层次化存储系统中，一般由寄存器、高速缓存(Cache)、主存(内存)、外存(硬盘等)组成。其中寄存器是最高层次的存储部件，容量最小，速度最快。寄存器对程序员是不透明的，对它的访问需按寄存器名访问而不是按地址。
二、存储体系构成的基本原理
由于存储体系采用了分层的结构，因此存储体系中各层次之间的数据访问如何的管理就显得相当重要。一般都把管理功能分布在各个层次上，每个层次的存储管理控制器控制这一层和与之相关一层的数据访问。层间传递数据的单位称为块或页。
命中率指命中的访问次数和总访问次数之比、失效率是失效的访问次数和总访问次数之比。命中时间包括判断是否命中所需时间和对上层存储器访存所需时间，失效时间则包括对下层存储器的访问时间和将下层存储器中数据调入上层存储器所需时间(传输时间)
存储器设计的目标是降低平均访问时间而不是单单提高命中率。也就是说层次化存储器的速度性能指标是访存的平均时间。另外还有带宽(频宽)、存储周期等指标。
平均访问时间=命中时间+失效时间×失效率
层次化存储体系必须解决的三个问题：
-
1.定位问题：数据块在较高层存储器中存放在哪个位置?怎样确定并且找到该块?这是块的标识和寻址问题。一般用查表法来映象块或页的定位、标识和寻址。
-
2.替换问题：不命中时，要从下层调入上层数据块，若上层满，则此时如何将上层中的数据置换出去?什么方法好。这就是替换策略的问题。
-
3.更新问题：在需要写访问时，何时将上层中得到的结果写到下层存储器中? 因为上层数据在经过运算后比下层的数据新，则这种写的方式就是为了解决上下层数据一致性的问题。
本章的内容就是围绕着这三个问题的解决而展开的。解决好这三个问题，层次化存储体系管理的主要问题也就解决了。
三、高速缓冲存储器(Cache)
这一节的内容就是讲述关于Cache高速缓存如何解决上述三个问题展开的内容，其他各层的管理基本上与它的解决办法类似。
高速缓存是位于CPU和主存之间的高层存储子系统。采用高速缓存的主要目的是提高存储器的平均访问速度，从而使存储器的速度也CPU的速度相匹配。
1、Cache的基本工作原理和结构
Cache通常由两部分组成，块表和快速存储器。Cache的基本结构可见教材图7.4，其工作原理是：处理机按主存地址访问存储器，存储器地址的高段通过主存-Cache地址映象机构借助查表判定该地址的存储单元是否在Cache中，如果在，则Cache命中，按Cache地址访问Cache。否则，Cache不命中，则需要访问主存，并从主存中调入相应数据块到Cache中，若Cache中已写满，则要按某种算法将Cache中的某一块替换出去，并修改有关的地址映象关系。
从这个工作原理我们可以看出，它已经涉及到了两个问题。首先是定位、然后是替换的问题。
Cache的存在对程序员是透明的。其地址变换和数据块的替换算法均由硬件实现。通常Cache被集成到CPU内以提高访问速度。
2.下面就要展开来讲述Cache中是如何进行地址映象和变换的。
因为处理机访问都是按主存地址访问的，而Cache的空间远小于主存，如何知道这一次的访问内容是不是在Cache中，在Cache中的哪一个位置呢? 这就需要地址映象，即把主存中的地址映射成Cache中的地址。让Cache中一个存储块(空间)与主存中若干块相对应，如此，访问一个主存地址时，就可以对应地知道在cache中哪一个地址了。地址映象的方法有三种：直接映象、全相联映象和组相联映象。
直接映象就是将主存地址映象到Cache中的一个指定地址。任何时候，主存中存储单元的数据只能调入到Cache中的一个位置，这是固定的，若这个位置已有数据，则产生冲突，原来的块将无条件地被替换出去。
全相联映象就是任何主存地址可映象到任何Cache地址的方式。在这种方式下，主存中存储单元的数据可调入到Cache中的任意位置。只有在Cache中的块全部装满后才会出现块冲突。
组相联映象指的是将存储空间的页面分成若干组，各组之间的直接映象，而组内各块之间则是全相联映象。
下面将三种地址映象方式进行对比。
| 直接映象 | 全相联映象 | 组相联映象 | |
| 过程 | (1)主存地址分成区号、块号、块内地址 (2)在主存地址中截取与Cache地址对就部分作为Cache地址 (3)以块号为地址访问目录表读出区号与主存地址中区号比较 (4)若相等，命中 (5)若不相等，块失效，停止Cache访问。访主存，并调块 |
(1)主存地址分成主存块号和块内地址 (2)用主存块号同目录表相联比较 (3)若相同，则取出Cache块号，Cache块号与块内地址拼接成Cache地址，访问Cache (4)若无相同的，则产生缺块、调块 |
(1)主存地址分区号、组号、块号、块内地址 (2)用组号选出一组 (3)对该组用区号+块号全相联比较 (4)或找不到，则块失效 (5)若找到一样，则将读出的Cache块号与组号和块内地址拼接形成Cache地址。 |
| 目录表 | 长：Cache大小 宽：主存地址位-Cache地址位 |
长：Cache 大小 宽：(主存块号+Cache块号)位 主存块号位参与比较 |
长：2ncbCache大小 宽：(区号+2块号)位 (区号+块号)位参与与比较 |
| 优点 | (1)硬件省，目录表小，成本低 (2)访问Cache与访问区号表同时进行 |
(1)块冲突最低 (2)Cache空间利用率最高 |
集中全相联和直接映象的优点弥补他们的缺点 |
| 缺点 | (1)块冲突概率很大 (2)Cache空间利用率很低 |
(1)映象表太长 (2)查表速度慢 |
块冲突仍大于全相联 利用率低于全相联 目录表大于直接方式 |
3.替换策略及更新主存策略
Cache从主存读取数据块时有三种方式：需要时读取、预读取和选择读取。这三种方式各有优缺点，请注意比较。课本中提到"共享的数据放在主存中比放在Cache中合适，特别是在多处理机系统中",因为共享的数据经常由别的处理过程改写，若放到cache中，则经常涉及到数据的一致性问题，因此放在主存中可保证其单一性，不致发生数据一致性错误的问题。
在层次式的存储体系中，访问某层存储器的内容时将从该层取数据块层层复制到上层存储器中，而上层的存储器容量总比下层的少，则在复制到上层时，就会发生替换掉原有数据块的问题。若被替换的块中有新写入的数据(如计算结果)则这些数据还得先写到下层存储器的相应块中，这就涉及更新策略。
在直接映象方式下，不存在块替换的算法，因为每一块的位置映象是固定的，需要哪一块数据就可直接确定地将该块数据调入上层确定位置。而其他两种映象就存在替换策略的问题，就是要选择替换到哪一个Cache块。即替换算法。
选择替换算法的依据是存储器总体性能，主要是上层存储器的访问命中率。下面将常用的几种替换算法作一比较：
| 思想 | 优点 | 缺点 | |
| 随机算法RAND | 用软的或硬的随机数产生器产生上层中要被替换的页号 | 简单、易于实现 | 没有利用上层存储器使用的"历史信息"，没有反映等程序局部性，命中率低。 |
| 先进先出FIFO | 选择最早装入上层的页作为被替换的页 | 实现方便，利用了主存历史的信息 | 不能正确反映程序局部性原理，命中率不高，可能出现一种异常现象。 |
| 近期最少使用法LRU | 选择近期最少访问的页作为被替换的页 | 比较正确反映程序局部性，利用访存的历史信息，命中率较高 | 实现较复杂 |
| 优化替换算法OPT | 将未来近期不用的页换出去 | 命中率最高，可作为衡量其他替换算法的标准 | 不现实，只是一种理想算法 |
对于块的替换策略，要掌握FIFO特别是LRU算法的替换过程，能画出其分配情况的表并作分析。
为了保持Cache中数据和主存中数据的一致性，就要对Cache和主存的数据进写操作，一般的更新策略有两种：
| 更新策略 | 思想 | 优点 | 缺点 |
| 写回法 | 是指在CPU执行写操作时，信息只写入Cache中，仅当需要替换时，才将改写过的Cache块先送回主存(写回)，然后再调块 | 有利于省去许多将中间结果写入主存的无谓开销。 | 需设修改位增加Cache的复杂性 |
| 全写法(写直达法) | 在写操作时，将数据同时写入Cache和主存 | 实现开销小、简单 | 为了写中间结果浪费了不少时间 |
另外，当写不命中时(也就是写Cache块时，这块早被人替换出去而在Cache中找不到时)是不是要把这块再取回Cache中，有两个解决方法：一是不按写分配法，就是直接写到主存里，不再把该地址对应的块调回Cache中.二是按写分配法，就是写到主存，而且把这一块从主存中调入到Cache.一般写回法用按写分配法，全写法则采用不按写分配。
4.数据Cache、指令Cache和一体化Cache
将Cache分别用来存放数据和指令，则可分成上面两种Cache，一体化Cache则既存放数据又存放指令。一般来说，分离后的Cache命中率有所提高。
5.Cache的性能分析(简单应用)
Cache的命中率对计算机速度的影响很大。实践证明，Cache的尺寸越小，地址映象方法和替换策略对命中率的影响越大。
在组的大小一定情况下，Cache的容量越大则命中率越高。
当Cache的大小确定时，组的大小或块的大小将影响不命中率，由于块的内部是全相联的，因此块越大则命中率越高。
我们知道，衡量存储系统的速度性能要以平均访存时间为指标，计算平均读访存时间的公式为：
Ta=HcTc+(1-Hc)Tm
其中Hc是指命中率，Tc是命中时访问时间，Tm为访主存时间。若是多层Cache也可按此公式推出计算方法。即上层的存储器命中时间加上不命中时访问下层存储器的时间。
四、主存储器带宽拓宽方法
前面我们学了层次存储体系中的高层存储器Cache,现在讨论主存。
存储器的主要性能指标是容量、速度和价格.存储器的速度指标包括访问时间、访存周期时间和带宽。提高主存带宽的措施主要有：
-
1.增加存储器的数据宽度。(也就是增加数据位数)
-
2.采用存储器的多体交叉技术。
存储器的多体交叉是提高其数据带宽的有效方法。这里用我自己的理解解释一下高位交叉存储器和低位交叉存储器：
| 我们知道，存储器的每个存储单元都要给定一个地址才能被访问到。并行存储器是由多个存储体组成，并行存取可以加快存取速度，但是这和编址方法有关。 比如主存空间有8个存储单元(2的3次方，设得小一些好懂些,实际上的单元数比这大得多)，那么整个存储空间地址就由一组3位二进制数组成：从000到111， 如果这个空间用两个存储体实现，有两种编址方法。 一种是"高位交叉"编址，就是把地址的码的前一位数分配给两个存储体，第一个为0，第二个为1(如果有四个存储体的话，就要分给前面的两位数，依次类推)第一个存储体里面的单元就是以这个码开始的编码：000，001，010，011 (看到第一位数都是0了吗)；第二个存储体的存储单元的四个地址是：100，101，110，111。 这样，当访问两个地址相邻存储单元的数据时，比如110和111两个单元的数据，都放在第二个存储体中，只能在这个体中存取，而第一个存储体就闲着没人访问了。而一般在存放数据时，多是将数据存放在地址连续的内存区域中的。现在可以知道了，为什么高位交叉编址的存储器适合于多机系统，就是说，因为各处理机通常访问各自所需的数据，这些数据放在不同的存储体中时，两个存储器可以同时工作，也就加快了速度。 另一种方法就是低位交叉编址。如上的例子，地址码的最后一位就是分配给存储体的地址码，第一个存储器里的存储单元就是000，010，100，110(最后一位总是0)， 第二个存储器里的存储单元就是001，011，101，111，这种方法使得相邻地址的存储单元分布在不同的存储体中，所以在访问相邻单元的数据时，多个并行存储体可以同时工作进行存取，因此比较适于单处理机内的高速数据存取。 |
增加存储器数据宽度的方法也是拓宽带宽的方法，一般采用单体多字方法。多体交叉的存储器的实际带宽比单体多字的高。
五、虚拟存储器
虚拟存储器是主存的扩展，虚拟存储器的空间大小取决于计算机的访存能力而不是实际外存的大小，实际存储空间可以小于虚拟地址空间。从程序员的角度看，外存被看作逻辑存储空间，访问的地址是一个逻辑地址(虚地址)，虚拟存储器使存储系统既具有相当于外存的容量又有接近于主存的访问速度。
虚拟存储器的访问也涉及到虚地址与实地址的映象、替换算法等，这与Cache中的类似，前面我们讲的地址映象以块为单位，而在虚拟存储器中，地址映象以页为单位。设计虚拟存储系统需考虑的指标是主存空间利用率和主存的命中率。
虚拟存储器与Cache存储器的管理方法有许多相同之处，它们都需要地址映象表和地址变换机构。但是二者也是不同的，请注意比较。
虚拟存储器的三种不同管理方式：按存储映象算法，分为段式、页式和段页式等，这些管理方式的基本原理是类似的。
段式管理：把主存按段分配的存储管理方式。它是一种模块化的存储管理方式，每个用户程序模块可分到一个段，该程序模块只能访问分配给该模块的段所对应的主存空间。段长可以任意设定，并可放大和缩小。
系统中通过一个段表指明各段在主存中的位置。段表中包括段名(段号)、段起点、装入位和段长等。段表本身也是一个段。段一般是按程序模块分的。
页式管理：是把虚拟存储空间和实际空间等分成固定大小的页，各虚拟页可装入主存中的不同实际页面位置。页式存储中，处理机逻辑地址由虚页号和页内地址两部分组成，实际地址也分为页号和页内地址两部分，由地址映象机构将虚页号转换成主存的实际页号。
页式管理用一个页表，包括页号、每页在主存中起始位置、装入位等。页表是虚拟页号与物理页号的映射表。页式管理由操作系统进行，对应用程序员的透明的。
段页式管理：是上述两种方法的结合，它将存储空间按逻辑模块分成段，每段又分成若干个页，访存通过一个段表和若干个页表进行。段的长度必须是页长的整数倍，段的起点必须是某一页的起点。
目前操作系统一般都采用段页式管理。下面将三种管理方式作一比较：
| 段式管理 | 优点 | 缺点 | |
| 地址变换过程 | 多用户(模块)地址可分成：程序号、段号、段内偏移量三部分，地址变换过程如下： (1)由程序号找到相应的段表基址寄存器，其中存有段表始址和段表长度。 (2)由段表长度与段号相比较，检查是否越界。正常转(3) (3)段表始址和段号找到其段表中相应表项，其中存有主存地址，装入位，访问位、段长、辅存地址等。 (4)检查装入位是否为"1"(在主存),为"1"转(5)，否则产生缺段中断，从辅存中调入一段到主存。 (5)由主存地址+段内偏移形成真正物理地址。 |
(1)多个程序分段编制，多个程序或并行编程，缩段编程时间； (2)各段相对独立，其修改、扩充都不会影响其他段； (3)实现虚拟存储； (4)便于共享和保护。 |
(1)分段管理主存，主存利用率不是很高，大量零头； (2)为形成一次有效地址，需多次访存，降低了访存速度； (3)分配和回收空闲区比较复杂； (4)段表中地址字段和段长字段较长，降低查表速度。 |
| 页式管理 | 用户逻辑地址分成：用户标志、用户虚页号、页内偏移三部分。过程如下： (1)由用户标志找到相应页表基址寄存器，其中有页表地址。 (2)由页表始址和页号找到页表中相应表项。 (3)检查装入位是否"1"(在主存),为'1'转(4)否则产生缺页中断。 (4)由主存块号和页内偏移形成有效地址。 |
(1)页表表项短，减少访表时间。 (2)零头较少。 (3)调入速度快。 |
(1)强制分页,页无逻辑意义，不利于存储保护和扩充。 (2)一次有效地址生成需多次访存，访存速度下降。 |
| 段页式管理 | 用户逻辑地址被分成：用户标志、段号、页号、页内偏移四部分。过程如下： (1)由用户标志找到段表基址寄存器。 (2)段表长与段号作是否越界检查。 (3)段表始址+段号找到段表中相应表项。 (4)做装入位、段长的检查。 (5)由页表始址+页号找到页表中相应表项。 (6)作装入位等检查。 (7)实页号+页内偏移形成有效地址。 |
具有段式、页式的优点 | 一次有效地址形成需3次访存，速度较慢。 |
请注意对照课本上各管理方法示意图进行理解。
页式虚拟存储器结构及其实现：主要要解决的问题是页面失效的处理及虚地址到实地址的变换速度。另外还有虚拟存储器的保护问题。
虚拟存储器中进行地址变换时，需要虚页号变换成主存中实页号的内部地址变换，这一般通过查内页表实现，若页页失效，还需通过查外页表变换地址再从外存调入页面。 所以提高页表的访问速度是提高地址变换速度的关键。根据访存的局部性原理，将一部分使用概率高页表项放在快速硬件构成的表格中，而将整个表格放在主存中，这就引出了快表和慢表的概念。查表时，快表和慢表同时进行查找。快表的存在对所有的程序员都是透明的。
·对于多道程序系统和多用户系统，虚存的保护是必不可少的。存储系统的保护分存储区域的保护和访问方式的保护。对虚拟存储器的保护方式有映象表保护法、键保护法和环式保护法等。