在主存与Cache的地址映射中，()是指主存中的任意一块可映射到Cache内的任一块位置上。..

计算机的主－辅存层次解决了存储器的大容量和低成本之间的矛盾，但是在速度方面，计算机的主存和CPU一直有很大的差距，这个差距限制了CPU速度潜力的发挥。为了弥合这个差距，设置高速缓冲存储器（Cache）是解决存取速度的重要方法。就是在主存和CPU之间设置一个高速的容量相对较小的存储器，如果当前正在执行的程序和数据存放在这个存储器中，当程序运行时不必从主存取指令和数据，所以提高了程序的运行速度。它具有以下特点。

（1）位于CPU与主存之间。

（2）容量小，一般在几千字节到几兆字节之间。

（3）速度一般比主存快5~10倍，由快速半导体存储器制成。

Cache

Cache的功能是提高CPU数据输入输出的速率，突破所谓的“冯.诺依曼瓶颈”，即CPU与存储系统间数据传送带宽限制。高速存储器能以极高的速率进行数据的访问，但因其价格高昂，如果计算机的内存完全由这种高速存储器组成则会大大增加计算机的成本。通常在CPU和内存之间设置小容量的高速存储器Cache。Cache容量小但速度快，内存速度较低但容量大，通过优化调度算法，系统的性能会大大改善，仿佛其存储系统容量与内存相当而访问速度近似Cache。

Cache基本原理

使用Cache改善系统性能的依据是程序的局部性原理。依据局部性原理，把内存中访问概率高的内容存放在Cache中，当CPU需要读取数据时就首先在Cache中查找是否有所需内容，如果有，则直接从Cache中读取；若没有，再从内存中读取该数据，然后同时送往CPU和Cache。如果CPU需要访问的内容大多都能在Cache中找到（称为访问命中），则可以大大提高系统性能。

如果以h代表对Cache的访问命中率（“1-h”称为失效率，或者称为未命中率），t₁表示Cache的周期时间，t₂表示内存的周期时间，以读操作为例，使用“Cache+主存储器”的系统的平均周期为t₃。则：

t₃=t₁×h+t₂×（1-h）

系统的平均存储周期与命中率有很密切的关系，命中率的提高即使很小也能导致性能上的较大改善。

例如，设某计算机主存的读/写时间为100ns，有一个指令和数据合一的Cache，已知该Cache的读/写时间为10ns，取指令的命中率为98%，取数的命中率为95%。在执行某类程序时，约有1/5指令需要存/取一个操作数。假设指令流水线在任何时候都不阻塞，则设置Cache后，每条指令的平均访存时间约为：

（2%×100ns+98%×10ns）+1/5×（5%×100ns+95%×10ns）=14.7ns

映射机制

当CPU发出访存请求后，存储器地址先被送到Cache控制器以确定所需数据是否已在Cache中，若命中则直接对Cache进行访问。这个过程被称为Cache的地址映射（映像）。在Cache的地址映射中，主存和Cache将均分成容量相同的块（页）。常见的映射方法有直接映射、全相联映射和组相联映射。

（1）直接映射。直接映射方式以随机存取存储器作为Cache存储器，硬件电路较简单。直接映射是一种多对一的映射关系，但一个主存块只能够复制到Cache的一个特定位置上去。

例如，某Cache容量为16KB（即可用14位表示），每块的大小为16B（即可用4位表示），则说明其可分为1024块（可用10位表示）。则主存地址的最低4位为Cache的块内地址，然后接下来的中间10位为Cache块号。如果内存地址为1234E8F8H的话（一共32位），那么最后4位就是1000（对应十六进制数的最后一位“8”），而中间10位，则应从E8F（1110 1000 1111）中获取，得到10 1000 1111。因此，内存地址为1234E8F8H的单元装入的Cache地址为10 1000 1111 1000。

直接映射方式的优点是比较容易实现，缺点是不够灵活，有可能使Cache的存储空间得不到充分利用。例如，假设Cache有8块，则主存的第1块与第17块同时复制到Cache的第1页，即使Cache其他页面空闲，也有一个主存页不能写入Cache。

（2）全相联映射。全相联映射使用相联存储器组成的Cache存储器。在全相联映射方式中，主存的每一页可以映射到Cache的任一页。如果淘汰Cache中某一页的内容，则可调入任一主存页中的内容，因而较直接映射方式灵活。

在全相联映射方式中，主存地址不能直接提取Cache页号，而是需要将主存页标记与Cache各页的标记逐个比较，直到找到标记符合的页（访问Cache命中），或者全部比较完后仍无符合的标记（访问Cache失败）。因此这种映射方式速度很慢，失掉了高速缓存的作用，这是全相联映射方式的最大缺点。如果让主存页标记与各Cache标记同时比较，则成本又太高。全相联映像方式因比较器电路难于设计和实现，只适用于小容量Cache。

（3）组相联映射。组相联映射是直接映射和全相联映射的折中方案。它将Cache中的块再分成组，通过直接映射方式决定组号，通过全相联映射的方式决定Cache中的块号。在组相联映射方式中，主存中一个组内的块数与Cache的分组数相同。

例如：容量为64块的Cache采用组相联方式映像，每块大小为128个字，每4块为一组。若主存容量为4096块，且以字编址，那么主存地址应该为多少位？主存区号（组号）为多少位？这样的题目，首先根据主存与Cache块的容量需一致，即每个内存块的大小也是128个字，因此共有128×4096个字（2¹⁹个字），即主存地址需要19位。因为Cache分为16组，所以主存需要分为4096/16=256组，即2⁸组，因此主存组号需8位。

在组相联映射中，由于Cache中每组有若干可供选择的页，因而它在映像定位方面较直接映像方式灵活；每组页数有限，因此付出的代价不是很大，可以根据设计目标选择组内页数。

淘汰算法

当Cache产生了一次访问未命中之后，相应的数据应同时读入CPU和Cache。但是当Cache已存满数据后，新数据必须淘汰Cache中的某些旧数据。最常用的淘汰算法有随机淘汰法、先进先出法（First In and First Out, FIFO）和近期最少使用淘汰法（Least Recently Used, LRU）。其中平均命中率最高的是LRU算法。

写操作

因为需要保证缓存在Cache中的数据与内存中的内容一致，相对读操作而言，Cache的写操作比较复杂，常用的有以下几种方法。

（1）写直达（write through）。当要写Cache时，数据同时写回内存，有时也称为写通。

（2）写回（write back）。CPU修改Cache的某一行后，相应的数据并不立即写入内存单元，而是当该行从Cache中被淘汰时，才把数据写回到内存中。

（3）标记法。对Cache中的每一个数据设置一个有效位。当数据进入Cache后，有效位置1；而当CPU要对该数据进行修改时，数据只需写入内存并同时将该有效位清0。当要从Cache中读取数据时需要测试其有效位：若为1则直接从Cache中取数，否则从内存中取数。

地址映射

如前所述，当一个任务被加载到内存后，它的各个连续的逻辑页面，被分散地存放在若干个不连续的物理页面当中。在这种情形下，为了保证程序能够正确地运行，需要把程序中使用的逻辑地址转换为内存访问时的物理地址，也就是地址映射。

那么如何将一个逻辑地址映射为相应的物理地址呢？在页式存储管理当中，连续的逻辑地址空间被划分为一个个的逻辑页面，这些逻辑页面被装入到不同的物理页面当中。也就是说，系统是以页面为单位来进行处理的，而不是以一个个的字节为单位。因此，地址映射的基本思路是：

.逻辑地址分析：对于给定的一个逻辑地址，找到它所在的逻辑页面，以及它在页面内的偏移地址；

.页表查找：根据逻辑页面号，从页表中找到它所对应的物理页面号；

.物理地址合成：根据物理页面号及页内偏移地址，确定最终的物理地址。

逻辑地址分析

由于页面的大小一般都是2的整数次幂，因此，人们可以很方便地进行逻辑地址的分析。具体来说，对于给定的一个逻辑地址，可以直接把它的高位部分作为逻辑页面号，把它的低位部分作为页内偏移地址。例如，假设页面的大小是4KB，即2¹²，逻辑地址为32位。那么在一个逻辑地址当中，最低的12位就是页内偏移地址，而剩下的20位就是逻辑页面号。

下图是逻辑地址分析的一个例子，在这个例子中，逻辑地址用十六进制形式表示。假设页面的大小为1KB，逻辑地址为0x3BAD。在这种情形下，首先把这个十六进制的地址展开为二进制的形式。然后，由于页面的大小为1KB，即2的10次方，所以这个逻辑地址的最低10位，就表示页内偏移地址，而剩下的最高6位，就表示逻辑页面号。因此，该地址的逻辑页面号是0x0E，页内偏移地址是0x03AD。

逻辑地址分析的例子

如果逻辑地址不是用十六进制，而是用十进制的形式来表示，那么有两种做法：一是先把它转换为十六进制的形式，然后重复刚才的步骤。二是采用如下的计算方法：

逻辑页面号=逻辑地址／页面大小

页内偏移量=逻辑地址%页面大小

用页面大小去除逻辑地址，得到的商就是逻辑页面号；得到的余数就是页内偏移地址。例如，假设页面的大小为2KB，现在要计算逻辑地址7145的逻辑页面号和页内偏移地址。用2048去除7145，得到的商是3，余数是1001。所以这个逻辑地址的逻辑页面号是3，页内偏移地址是1001。实际上，这个算法和刚才的十六进制的方法是完全等价的。从二进制运算的角度来看，一个是右移操作，一个是除法操作。把一个整数右移N位等价于把它除以2^N。

页表查找

对于给定的一个逻辑地址，如果知道其逻辑页面号，就可以去查找页表，从中找到相应的物理页面号。

在具体实现上，页表通常是保存在内核的地址空间中，因为它是操作系统的一个数据结构。另外，为了能够访问页表的内容，在硬件上要增加一对寄存器。一个是页表基地址寄存器，用来指向页表的起始地址；另一个是页表长度寄存器，用来指示页表的大小，即对于当前任务，它总共包含有多少个页面。操作系统在进行任务切换的时候，会去更新这两个寄存器当中的内容。

物理地址合成

对于给定的一个逻辑地址，如果已经知道了它所对应的物理页面号和页内偏移地址，可以采用简单的叠加算法，计算出最终的物理地址。假设物理页面号为f，页内偏移地址为offset，每个页面的大小为2ⁿ，那么相应的物理地址为：f×2ⁿ+offset。

下图是页式存储管理当中的地址映射机制，也是以上各个步骤的一个综合。假设在程序的运行过程中，需要去访问某个内存单元，因此就给出了这个内存单元的逻辑地址。如前所述，这个逻辑地址由两部分组成，一是逻辑页面号，二是页内偏移地址。这个分析工作是由硬件自动来完成的，对用户是透明的。在页表基地址寄存器当中，存放的是当前任务的页表首地址。将这个首地址与逻辑页面号相加，就找到相应的页表项。里面存放的是这个逻辑页面所对应的物理页面号。将这个物理页面号取出来，与页内偏移地址进行组合，从而得到最终的物理地址。然后就可以用这个物理地址去访问内存。

页式存储管理中的地址映射

现有的这种地址映射方案，虽然能够实现从逻辑地址到物理地址的转换，但它有一个很大的问题。当程序运行时需要去访问某个内存单元，例如，去读写内存当中的一个数据，或是去内存取一条指令，需要访问2次内存。第一次是去访问页表，取出物理页面号；第二次才是真正去访问数据或指令。也就是说，内存的访问效率只有50%。这样，就会降低获取数据的存取速度，进而影响到整个系统的使用效率。为了解决这个问题，人们又引入了快表的概念。它的基本思路来源于对程序运行过程的一个观察结果。对于绝大多数的程序，它们在运行时倾向于集中地访问一小部分的页面。因此，对于它们的页表来说，在一定时间内，只有一小部分的页表项会被经常地访问，而其他的页表项则很少使用。根据这个观察结果，人们在MMU中增加了一种特殊的快速查找硬件：TLB（Translation Lookaside Buffer），或者叫关联存储器，用来存放那些最常用的页表项。这种硬件设备能够把逻辑页面号直接映射为相应的物理页面号，不需要再去访问内存当中的页表，这样就缩短了页表的查找时间。

在TLB方式下，地址映射的过程略有不同。当一个逻辑地址到来时，它首先会到TLB当中去查找，看这个逻辑页面号所在的页表项是否包含在TLB当中，这个查找的速度是非常快的，因为它是以并行的方式进行。如果能够找到的话，就直接从TLB中把相应的物理页面号取出来，与页内偏移地址拼接成最终的物理地址。如果在TLB中没有找到该逻辑页面，那只能采用通常的地址映射方法，去访问内存当中的页表。接下来，硬件还会在TLB当中寻找一个空闲单元，如果没有空闲单元，就把某一个页表项驱逐出来，然后把刚刚访问过的这个页表项添加到TLB当中。这样，如果下次再来访问这个页面，就可以在TLB中找到它。

页式存储管理方案的优点是：

（1）没有外碎片，而且内碎片的大小不会超过页面的大小。这是因为系统是以页面来作为内存分配的基本单位，每一个页面都能够用上，不会浪费。只是在任务的某一些页面当中，可能没有装满，里面有一些内碎片。

（2）程序不必连续存放，它可以分散地存放在内存的不同位置，从而提高了内存利用率。

（3）便于管理。

页式存储管理方案的缺点主要有：

（1）程序必须全部装入内存，才能够运行。如果一个程序的规模大于当前的空闲空间的总和，那么它就无法运行。

（2）操作系统必须为每一个任务都维护一张页表，开销比较大。简单的页表结构已经不能满足要求，必须设计出更为复杂的结构，如多级页表结构、哈希页表结构、反置页表等。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5