本节书摘来自华章出版社《计算机存储与外设》一书中的第1章，第1节，作者Computer Organization and Architecture: Themes and Variations［英］艾伦·克莱门茨（Alan Clements） 著，沈 立 肖晓强 王苏峰 译，更多章节内容可以访问云栖社区“华章计算机”公众号查看。
第1章
Computer Organization and Architecture: Themes and Variations
Cache存储器和虚拟存储器
任何足够先进的技术都与魔法无异。
——Arthur C. Clark
名字有什么关系？我们把玫瑰叫成别的名字，闻起来还是一样的芬芳。
——莎士比亚，《罗密欧与朱丽叶》
存储层次（Memory Hierarchy）
Cache存储器（Cache Memory）使得计算机看似拥有了比实际更多的快速存储器。存储器应该具有非易失性（non-volatile）、廉价、快速、功耗低的特点。在现实世界中，每种存储技术都有其自身的特点，其中有些特点是相互矛盾的。例如，速度快的存储器往往昂贵，而速度慢的存储器往往便宜。存储系统使用了几种不同的技术，每种技术都发挥着不同的作用。总而言之，这些技术使整个存储系统表现为快速、非易失性、低成本。可以把各种存储技术分为不同的层，从而形成存储层次。
图1-1描述了典型的金字塔结构存储层次。在顶端的存储器速度最快（具有最短的访问时间），金字塔底部的存储器速度最慢。使用金字塔来表示存储层次的原因是，顶层的存储器的容量要小于底层的存储器容量。
片上的寄存器（register）是计算机中最快的存储器，它保存着处理器所需的工作数据。寄存器的访问速度快，这使得load/store寄存器–寄存器型体系结构十分流行。寄存器是以与CPU相同的方法制备的，与CPU的时钟频率相同，且与CPU其他部分之间的数据通路都较短。此外，片上寄存器可以直接被CPU访问，而访问其他的外部存储器都需要一个过程，包括存储器管理、地址翻译以及复杂的数据缓冲和控制机制。因此，寄存器速度很快。但是，CPU只有少量寄存器可以用来存储工作数据和状态信息。寄存器不能存放程序。
存储器层次结构中，在寄存器的下方就是Cache，更准确地说是一级Cache。Cache的大小一般比主存小几个数量级，但真实程序的性质和数据的分布使得典型应用在95%以上的时间内只使用较小的指令和数据集合。历史上Cache曾经位于主板上，但芯片技术的进步使得人们可以在处理器芯片上实现大部分的Cache。
图1-1显示了两级Cache存储器。如果被访问的数据不在一级Cache中，将访问下一级的存储层次，即二级Cache。并不是所有的系统都有两级Cache，有的系统还有三级Cache。
如果数据不在Cache中，它必须从计算机的主存储器来获得，主存在图1-1中是Cache的下一级存储器。现代个人计算机和工作站大都使用DRAM来实现随机访问的主存储器。今天的个人计算机可以使用1GB～48GB的DRAM。
主存是易失性的存储器，因此程序和数据需要保存在非易失性存储器中。最便宜的存储机制之一是硬盘，它以磁信号的形式将数据保存在旋转的盘片上。一个硬盘可以存储超过4TB的数据。然而，硬盘的访问时间为5ms左右，虽然按照人的标准来说这已经很快了，但还是比主存慢106倍。今天，机械硬盘被更快、更可靠的固态硬盘（SSD）代替。这些技术将在第3章中讨论。
因为主存通常不能容纳处理器所需的所有程序和数据，计算机采用了一种被称为虚拟存储器（virtual memory）的存储器管理系统，其中主存中仅包括当前要使用的数据，那些不使用的数据仍然保存在硬盘上。当处理器需要的数据不在主存中时，操作系统开始介入并使主存和磁盘之间交换一个页（page）的数据，其典型大小为4KB～64KB。虚拟存储器系统允许用户运行比主存大得多的程序，且不会导致系统性能的显著下降。即由512MB的DRAM和100GB硬盘构成的虚拟存储系统的性能与具有100GB的DRAM的存储系统性能相当。虚拟存储器还提供了一种保护数据的手段。
存储层次的下一个层次是光存储，由CD、DVD或者蓝光光盘构成。光盘存储器将数据以凹痕的方式记录在塑料盘片上的螺旋轨迹中，并使用激光根据凹痕处是否有反光来读取数据。光盘的读取速度比硬盘的速度要慢，这主要是因为CD或DVD盘片的转速与硬盘片旋转速度相比差距太大。
图1-1中至少有一个数据是不准确的：光存储器的速度比磁记录存储器的速度慢，但其容量并不比后者大。CD通常可以容纳650MB的数据，而蓝光光盘可以存储25GB的数据。几年前，该容量还相对较大，但硬盘技术的进步如此引人注目，在10年的时间中，硬盘的容量已经从100MB发展到超过4TB（从108B增加为4×1012B，即容量增加了4×104倍。今天的硬盘能够存储比光盘更多的数据，在图1-1中光盘是因为速度慢而不是容量大才位于硬盘的下一个层次。
图1-1中光存储器的下面为磁带（magnetic tape）或磁带存储器（cartridge storage）。这些存储技术通过很长的磁带而不是旋转的磁盘来记录数据。磁带可以容纳大量的数据，但是它们的访问时间在几分钟甚至几小时的量级，所以它们只能作为后备存储器或者用于文档备份存储。
磁带的下一级是互联网（Internet）和云存储（cloud storage），它们可以提供远程分布式存储。数据存储在计算机外部，通常位于第三方提供的虚拟服务器中；即用户通过购买存储服务，通过互联网和WWW来存储信息。用户不需要知道数据到底存在哪里。重要的是，如何在灾难降临时保证数据的安全性。此外，只要连接到因特网，数据就可从任何地方访问。
在第1章和第2章中深入讨论存储系统技术之前，需要讨论存储器是如何与计算机系统关联的。如果访问CPU内寄存器的时间小于1ns，访问CD驱动器的时间超过200ms，虽然完成的任务都是数据访问，也需要花大量的精力来管理这种由多种不同存储设备构成的系统。
本章介绍相对较小的Cache，与相对更大和更慢的存储器相结合，并使整个组合的系统看起来像一个又大又快的存储器。奇妙吧！本章然后介绍虚拟存储器对地址的管理，这使得用户不必关心数据在存储器中如何存储，允许用户在不同的存储区域中同时运行若干程序，且在计算机需要数据的时候自动从磁盘加载它。
本章包括Cache和虚拟存储系统，是因为它们完成相同的任务。两者都使用少量快速存储器，将它们与大容量的慢速存储器相结合，使得整个存储系统好似大容量的快速存储器。两种技术都涉及从计算机地址映射到数据在存储器中的实际位置。Cache和虚拟存储器之间的区别主要体现在速度和控制机制上。Cache操作需要ns量级，由硬件自动管理，而虚拟存储器操作需要ms量级，由操作系统管理。
下面来看看Cache和虚拟存储器在系统中的作用。假设计算机执行下列操作：
这些指令从内存读取操作数time。CPU所要做的就是将time的地址放到地址总线上，然后读取数据。原理上，该过程再简单不过了。图1-2展示了可以执行此代码的系统。计算机给出的操作数地址（此例中为time）是一个逻辑地址。将这个地址传给快速的Cache，在那里试图访问数据。如果数据在Cache中，就从Cache中获取数据。否则，如果数据在较慢的主存储器中，该数据将从主存交给计算机和Cache。该过程由硬件实现，并对用户和操作系统来说是不可见的。
有时，数据也不在主存储器中；它在硬盘上。当数据在磁盘上，虚拟存储器机制将其从磁盘拷贝到主存储器。它当然也被拷贝到了Cache。从磁盘传输到主存储器的数据可以存放到主存储器的任意位置。这就需要存储器管理单元（memory management unit，MMU）将来自计算机的逻辑地址（logical address，即计算机认为数据所在的地方）转换为物理地址（physical address，即操作系统把该数据存放在存储器中的地址）。虚拟存储器管理是操作系统完成的主要任务之一，需要存储器管理单元的专用硬件与操作系统密切合作。
下面将讨论图1-1中给出的存储层次的相关特性，然后介绍Cache是如何加快计算机操作的。本章的部分内容将介绍影响Cache性能的因素，以及如何通过优化Cache硬件和应用软件来提高系统速度。
本章的后半部分关注虚拟存储器以及如何从处理器给出的数据逻辑地址（或虚拟地址）映射到存储器中对应的数据物理地址。
1.1 Cache存储器概述
在冯·诺依曼计算机中，存放程序和数据的主存储器应该尽可能快地满足CPU的要求。如果存储器不能在当前周期向CPU提供所需访问的数据或指令，存储器必须返回一个信号通知CPU等待。CPU通过在机器周期中插入空闲（idle）或等待（wait）指令来阻止其执行下一个操作。在等待状态，CPU将停止正常操作，因此慢速存储器将严重降低其性能。在本节中，将介绍Cache如何显著提高处理器的性能，而不会带来太大的开销。图1-3再次展示了存储器的层次结构，并以时钟周期的形式给出了各层的延迟。
20世纪90年代早期，在各种期刊上常常可以看到这样的评论，“如果只是要CPU以更快的速度等待，则制造与使用高速CPU是没有意义的。”解决该困境的一个方案是使用更快的存储器以跟上CPU的速度。这听起来可能很容易做到，因为CPU和存储器的技术是相关的，它们都采用相同的设计和制造工艺。人们很容易认为一个具有5ns周期的CPU需要存储器的访存时间也达到5ns。这种想当然的认知存在两个缺陷。首先，历史上处理器速度的增长率已远远超过了DRAM速度的增加，这在过去的20年中已经是事实。第二，CPU的机器周期时间（即处理器执行一个读或写操作来访问外部存储器所需的时间）为5ns，但其时钟周期可能只有2.5ns，此时每个CPU的机器周期包括两个时钟周期。假设CPU在这5ns的机器周期时间中，将花费一个时钟周期来执行管理任务。处理器将需要在一个时钟周期内获得数据，该时间包括从数据地址可用到来自存储器的数据被锁定所需的时间。所以，要跟上CPU的存储器访问时间是2.5ns。因此，这需要存储器的访问时间远低于其服务的处理器的机器周期时间。
尽管现代技术确实可以制造访问时间小于5ns的存储部件，但该设备的高昂成本使得其难以在大容量存储系统中应用。在20世纪90年代中期，个人计算机和工作站的大规模生产，为控制成本，要求使用已经测试过的主流存储部件（例如，64Mb DRAM的访问时间为50ns）。
Cache并不神秘，它只是一个可由处理器快速访问的高速存储器。奇妙之处在于系统只拥有少量高速存储器（例如，某系统有256KB的Cache和512MB的DRAM），并且希望处理器在95%的时间内都访问Cache而不是DRAM。
Cache可以通过日常生活中诸如日记、地址簿，或iPhone中的电话号码簿等类似物来理解。电话号码黄页中包含成千上万的电话号码，但没有人会真正带上一本。人们通常在号码簿中只记录约100个电话号码。虽然这些号码可能少于电话号码清单总数的0.0001%，但下一个电话来自号码簿的概率是很高的，就像人们经常会给朋友打电话一样。
Cache的工作方式与上述电话号码簿的工作原理相同，它将经常访问的信息放入Cache而不是放入相对较慢的主存储器。与号码簿不同，计算机不能提前知道哪些数据是最可能需要的。与人们将数据划分为重要类别的做法不同，计算机的Cache根据学习原理（learning principle）来操作。Cache通过在实践中学习什么样的数据是最经常需要使用的数据，然后将它们保存在Cache中。
理想情况下，由于基于DRAM的存储器的速度越来越快，对复杂和昂贵的Cache系统的需求应该消失。在20世纪70年代，我曾阐述了这个观点。时间证明我错了。图1-4显示了在过去20年中存储器和微处理器性能的发展趋势。存储器每年约增速7%。处理器速度在这段时间内提升更快，每年增加55%左右的性能。由于处理器和存储器之间的性能差距已经扩大，Cache存储系统今天的作用比其刚发明时的作用要重要得多。
Wulf和McKee讨论了存储器和处理器性能变化具有不同速度带来的影响。他们认为DRAM速度滞后于处理器的速度将最终被证明是限制计算机性能的条件。他们认为，处理时间是执行内部操作的时间加上访问外部存储器的时间的总和，因此，存储器访问时间部分将主宰处理时间。进一步提升处理性能将毫无意义。他们创造了“碰到存储墙（hitting the memory wall）”的概念，表明在传统微处理器系统设计中存在限制。
Cache高速缓存本来没有什么内在价值。总线用来分布数据；硬盘用来存储大量的数据。Cache的作用仅仅是隐藏了存储器延迟。如果存储器足够快，就可以不需要Cache。
1.1.1 Cache存储器的结构
Cache存储器系统的一般结构如图1-5所示。Cache存储体与处理器的地址总线和数据总线相连，并与更大容量的主存储器并行工作。Cache中的数据在主存储器（即DRAM）中也存在副本。
访问的局部性原理
回到前面的电话号码簿例子，向电话号码簿中添加一个朋友的号码并不会从电话号码黄页中删除他的号码。考虑计算机访问某个存储器位置。各个给定的存储位置被访问的概率是不同的，因为有些地方比其他地方更容易被访问。由于程序和其数据结构的性质，处理器所需的数据往往在存储器中聚集在一起。例如，堆栈经常被访问，某些函数与其他函数相比经常被调用。这种现象被称为访问的局部性（locality of reference），这使Cache的使用成为可能。
一些地址被称为出现了空间局部性（spatial locality），这是因为它们聚集在相同的存储器区域内（例如，数据结构）。程序员和编译器会针对空间局部性进行特殊考虑。假设某程序包括变量P、Q和R，其中P是整数，R是由8个整数组成的数组，Q是另一个整数。另外，假设P和R经常被访问而Q很少被访问。如果数据的声明顺序为P、R和Q，则这两个经常访问的变量在存储器中是相邻的，可以被缓存在一起。
一些地址被称为出现了时间局部性（temporal locality），这是因为它们在短时间内被多次访问（例如，在一个循环体内的位置）。某循环，例如：
将在一段时间内有规律地访问相同的变量。
局部性原理仅仅是种指导，而不能成为定律。某些程序同时表现出时间局部性和空间局部性，而有些程序没有。若程序要访问一个非常大的矩阵且数据分布是随机的，此时可能不会表现出空间局部性。某按照地理位置列表的邮购消费者数据库可能具有较好的空间局部性，这是因为一些团体由需要频繁服务的用户组成。一个简单的具有时间局部性和空间局部性的例子是产生内积的例子：
计算机连续访问a0，a1，a2，a3，…，就会表现出空间局部性，因为这些连续的元素在内存中是相邻的。元素ai和bi在空间中存放的位置可能相距很远，但它们从访问时间上看是相邻的，因为ai和bi几乎在相同的时间被访问。
Cache使用Cache控制器（cache controller）来确定CPU要访问的操作数是否在Cache中，是否需要从主存储器中调取。当给Cache控制器一个地址后，控制器返回一个信号（hit或miss）确定Cache是否命中。命中（hit）表明数据当前位于Cache中，失效（miss）表示数据不在Cache中，需要从主存储器中调取。
现代高性能系统具有多个级别的Cache：一级Cache、二级Cache和三级Cache。一级Cache是容量最小但速度最快的Cache。如果数据不在一级Cache中，就在二级Cache中查找。如果数据也不在那儿，则在三级Cache中查找。多级Cache的性价比较好，因为它们在不增加最快Cache的容量的情况下提供了更好的性能。后续章节中将讨论多级Cache。
