《存储技术基础》课件第5章

第五章计算机系统中的存储管理5.1局部性原理

5.2存储器层次结构

5.3高速缓冲存储器

5.4虚拟存储器

5.5Pentium处理器

小结

5.1局 部 性 原 理

局部性原理是指在指定时间内，程序趋于在有限的内存区域内重复访问。我们通常将局部性分为空间局部性和时间局部性。存储器层次结构建立在局部性原理的基础上，局部性原理对硬件和软件系统的设计有着极大的影响。

空间局部性(SpatialLocality)是指访问内存地址X后很可能会紧接着访问内存地址X ± i，其中i是一个很小的值，X ± i和X物理邻近，即已访问过的内存地址附近的位置很可能被连续访问。时间局部性(TemporalLocality)是指在T时刻访问过内存地址X，在T ± j时刻很可能再次访问内存地址X，其中j是一个很小的值，T ± j和T时间邻近。即已访问过的内存地址在较短的时间内还可能被多次访问。

考虑图5.1所示的代码段，在for循环体内数组v的元素按照其存储顺序被逐一访问，因此数组v有很好的空间局部性，但每个元素只被访问了一次，故其时间局部性很差。整型变量j和N在循环体内被多次访问，故其时间局部性很好。for语句代码被执行了N次，故其有较好的时间和空间局部性。图5.1for循环语句的局部性

5.2存储器层次结构

存储器层次结构(MemoryHierarchy)建立在局部性原理的基础上，由具有不同容量、成本和访问时间的存储器构成。各种存储器在性能和价格上有很大的差别，为了能达到最佳的性价比，计算机系统都采用将各种不同的存储器组合起来，形成一个存储器层次结构。在存储器层次结构中，CPU寄存器中存放着最常用的数据；Cache作为主存的缓冲区，存放着主存中的常用数据；主存又作为大容量本地磁盘的缓冲区，存放着本地磁盘上的数据；本地磁盘可作为网络上远程磁盘的缓存。这种金字塔型的层次结构的目的是使存储系统速度尽量的快，而成本又尽量的低。在图5.2所示的金字塔型存储器体系中，最高层M0是距离处理器最近的内部寄存器，内部寄存器的数量相对较少，处理器可以在一个时钟周期内快速访问它们；M1层是高速缓冲存储器，一般由静态存储器(SRAM)构成，处理器可在几个时钟周期内访问到它们；M2层是由动态存储器(DRAM)构成的主存，处理器可在几十到几百个时钟周期内访问到它们；M3层是本地磁盘，同M0、M1、M2层相比，M3层具有速度慢、容量大、价格低的特点；M4层是可通过网络访问的远程服务器上的磁盘系统。图5.2存储器层次结构

5.3高速缓冲存储器

在CPU-Cache-主存三层存储器层次结构中，高速缓冲存储器(Cache)和主存被划分为连续的数据块(block)，并以块的大小为单位在相邻层之间传输。当程序要访问主存中某个数据D时，CPU首先在Cache的相应块X中查找D，如果D在X中，那么我们说缓冲命中(CacheHit)，程序直接从Cache的X块中读取D数据，如图5.3所示；如果D不在X中，我们就说缓冲不命中(CacheMiss)，此时Cache将主存中包含D数据的块读入，如图5.4所示。图5.3缓冲命中图5.4缓冲不命中通过上述分析，我们得知，在Cache-主存这种映射机制中有四个关键问题需要解决：

(1)主存中的块如何映射到Cache中？(地址映像)

(2)若请求数据在Cache中，CPU如何寻找到Cache中的请求数据？(地址变换)

(3)当请求数据不在Cache中且Cache已满，此时需将主存中相应块调入Cache，如何替换出Cache中的块？(替换算法)

(4)当替换Cache块时，如何保持Cache中的块与主存中的对应块一致？(写策略)5.3.1直接映像

直接映像(Direct-MappedCache)是把主存按Cache的大小分为相等的区，每区又分为大小相等的块，主存中不同区的各块一一对应Cache的块，如图5.5所示。图5.5直接映像的地址映像因直接映像中Cache块号与主存各区内的块号一一对应，为了区分Cache的块来自主存中的哪个区，需要设置一个按地址访问的区号表存储器硬件来记录放入Cache中块的区号，即当主存中的某块映像到Cache中的对应块时，在对应的区号表存储器项中应记录其区号，以供地址变换使用。

直接映像的地址变换过程比较简单。如图5.6所示，将主存地址划分为区号、块号、块内地址三部分，将Cache地址划分为块号和块内地址两部分。用主存地址中的块号部分寻址区号表存储器，读取区号表存储器对应项所存的区号，使其与主存地址的区号部分比较。若相等，则Cache命中，直接用主存地址中块号和块内地址构成Cache地址；若不相等，则Cache不命中，进入缺块处理程序。图5.6直接映像的地址变换通过对主存地址进行划分，我们知道请求数据是主存第2区第1块内的第2个字节，如图5.7(a)所示。地址映像时，将第1块调入Cache的第1块中，在区号表第1项中记录区号2，如图5.7(b)所示。注意，区号表和Cache是对应的。图5.7直接映像的地址映像示例地址变换时，通过主存地址的块号1找到区号表的第1项，将其内容(10)2取出与主存地址的区号比较，若相等则命中，主存地址的块号和块内组合(1000000001)2地址即是Cache地址，如图5.8所示。图5.8直接映像的地址变换示例直接映像的地址变换比较简单，可以直接从主存地址中提取Cache地址，并且其区号表只需使用普通的按地址访问存储器即可。其缺点是地址映像决定了其主存中不同区的相同块号会被映像到同一个Cache块中，从而导致Cache的块冲突率比较高，即使Cache中其他块为空时也无法利用，降低了Cache的命中率和利用率。

直接映像在划分主存地址时，用内存地址的中间位来做块索引并非偶然。如果用高位来做块索引，那么连续存储器块会映像到同一个Cache块中，如图5.9所示。由局部性原理可知，这样不利于提高Cache的命中率。图5.9内存地址中间位做块索引5.3.2全相联映像

全相联映像(FullAssociativeCache)是指将主存和Cache划分成大小相等的块，主存中的任意一块都可以映像到Cache中的任意一块，如图5.10所示。

全相联映像使用相联存储器来记录主存块和Cache块的对应关系，当主存中某块调入Cache时，在相联存储器Cache对应项中记录主存块号。

全相联映像地址变换过程如图5.11所示。主存地址和Cache地址均被分为块号和块内地址两部分。用主存块号在块号表中相联比较，若相等，则Cache命中，将相联存储器对应的Cache块号与主存的块内地址部分组合起来，形成Cache地址；若均不等，则Cache不命中，进入缺块处理程序。图5.10全相联映像的地址映像图5.11全相联映像的地址变换通过对主存地址进行划分，我们知道请求数据是主存第5块、块内第2个字节，如图5.12(a)所示。全相联地址映像时，主存中的任意一块都可以映像到Cache中的任意一块。我们假设主存中的第5块映像到Cache的第2块中，即将主存第5块调入Cache第2块中，并在块号表第2项中记录主存块号5，如图5.12(b)所示。图5.12全相联映像的地址映像示例地址变换如图5.13所示，首先将主存地址块号5与块号表相联比较，匹配块号表第2项，然后将块号表序号2与主存块内地址(000000001)2组合，构成Cache地址(10000000001)2。

全相联映像中，主存中的块可以装入Cache中任意一块，只要Cache有空闲块，就不会发生块冲突，故全相联映像是三种映像中Cache利用率最高的。但其地址变换机制相对比较复杂，无法从主存地址直接提取Cache地址，并且需要使用相联存储器来提高查表速度。图5.13全相联映像的地址变换示例5.3.3组相联映像

组相联映像(SetAssociativeCache)是将主存按Cache的大小分成相等的区，区内分为大小相等的组，组内又分成大小相等的块，按照组间直接相联、组内全相联的方式进行映像，这种方式实质上是前两种映像方式的折中，如图5.14所示。图5.14组相联映像的地址映像组相联映像采用一种按地址访问与按内容访问混合的存储器来存放主存块与Cache块的对应关系表，为了讲述方便，我们称这个表为区号块号表。地址映像时需要将调入Cache的主存块的区号和块号同时记录在区号块号表中，由于组间采用直接相联映像，故组号无需记录。

组相联映像的地址变换过程如图5.15所示，先依据主存地址的组号按地址查找，并锁定区号块号表对应组，之后将锁定组中的各项与主存地址区号块号部分进行相联比较。若相等，则Cache命中；反之，Cache不命中，进入缺块处理程序。图5.15组相联映像的地址变换通过对主存地址进行划分，我们知道请求数据位于主存第1区、第0组、第1块内第2个字节，如图5.16(a)所示。图5.16组相联映像的地址映像示例在地址映像时，依据组内全相联、组间直接相联的规则，主存第1区、第0组、第1块可以映像到Cache第0组、第0块或第0组、第1块，我们假设将其映像到第0组、第0块，并在区号块号表第1项中记录对应块的主存区号1和块号1，如图5.16(b)所示。

地址变换如图5.17所示，首先通过主存组号0按地址锁定区号块号表第0组，然后用主存地址区号块号部分相联比较区号块号表锁定组中各项，发现与第0组第0块匹配，最后将匹配项的块号同主存地址中组号和块内地址组合，构成Cache地址(10000000001)2。图5.17组相联映像的地址变换示例5.3.4替换算法

当Cache已满并且不命中时，需要将主存块调入Cache中，替换算法决定了应当替换掉Cache中的哪一块。替换算法应尽量找出Cache中最不可能再次被访问的块将其替换出去，从而提高命中率和访问延迟。常用的替换算法有以下几种。

1.最优置换算法OPT(OptimalReplacement)

OPT算法是一种理论上的算法，其基本思想是根据将来使用块的时间作为替换依据，替换掉Cache中最远的将来才会被访问的块。这种算法可以保证最少的缺块率，但无法完全用程序实现，故其一般用来衡量其他算法的优劣。

2.先进先出算法FIFO(First-In,First-Out)

FIFO算法根据块在Cache中的时间长短作为替换依据。FIFO算法认为是最早调入Cache中的块，其以后不再被使用的可能性比刚调入的可能性大，故总是选择在Cache中停留时间最长的块替换。在算法实现上，将进入Cache的块按照时间先后顺序排队，队首是最早进入Cache的块，队尾是最晚进入Cache的块，需要替换时，队首的块首先被替换掉。先进先出算法是一种简单并易于实现的替换算法，其缺点是较早调入的块有可能是经常被访问的块，这些块在FIFO算法下会被反复调入调出，会导致Cache的命中率较低，故在实际的系统中很少直接使用FIFO算法。FIFO还有一种异常现象(Belady’sAnomaly)，即在增加Cache块的情况下，有可能反而使缺块率增加，例如：对主存中块请求顺序为3，2，1，0，3，2，4，3，2，1，0，4，当Cache大小为3时，缺块率为9；当Cache大小增加为4时，缺块率反而变成了10，如表5.1和表5.2所示。表5.1FIFO算法(Cache块为3，×表示缺块)表5.2FIFO算法(Cache块为4，×表示缺块)

3.第二次机会算法(Second-Chance)

第二次机会算法是经改进的FIFO算法。它通过对块设置访问位来避免把经常使用的块置换出去。与FIFO相似，第二次机会算法将进入Cache的块按照时间先后顺序排队，在替换队列首部的时候同时检查其访问位，如果是0，就置换块，如果是1，则保留它，给其第二次机会。

4.最近最少使用算法LRU(Leastrecentlyused)

LRU算法将最近的过去作为不久将来的近似，用块在Cache中未被使用的时间作为替换依据，选择替换最近一段时间Cache里最久没有被使用过的块。LRU算法是一种经常被采用的块替换算法，Pentium处理器的Cache替换策略就采用了LRU算法，PentiumMMX和Intel486采用了一种改进的LRU算法—PseudoLRU(也称做Tree-LRU)。5.3.5写策略

Cache的写操作要比读操作复杂。假设CPU对Cache中某块Xc进行了写操作，那么此时Cache中的Xc块和主存中对应块Xm会出现数据不一致，为了保持Cache中的Xc块和主存中对应块Xm一致，一般情况下，可通过以下两种策略来更新主存中的Xm块。

1.直写法(Write-Through)

直写法是指在写Cahce中Xc块的同时写主存Xm块，即在写Cache时同步写主存。这种方法比较简单，但每次写操作都会引起写主存，写主存次数较多，则效率较低。

2.写回法(Write-Back)

写回法是指在写Cache中Xc块时，并不立即写主存，只有当替换算法要替换掉Xc块时，才将Xc块一次性写入主存Xm块。这种策略通过尽量推迟对主存的写操作，减少写主存的次数。写回法的Cache各块需要一个额外的脏数据位(DirtyBit)来标记Cache块是否被修改过。

5.4虚 拟 存 储 器

虚拟存储器(VirtualMemory)是计算机系统中一个十分重要的概念。虚拟存储器通常是指将主存作为辅存的缓冲区，通过硬件和操作系统等机制，实现两者数据交互。虚拟存储器机制一方面通过硬件和操作系统的配合，为每个进程提供了一个一致的逻辑地址空间，简化了存储器的管理；另一方面，由于主存中只保留了各进程的活动区域，不活动部分保存在辅存中，使得程序的并行性和主存的利用率大大提高。虚拟存储器是在20世纪60年代早期提出的，虚拟存储器的提出解决了主存过小的题，更重要的是，它使程序员从原本繁琐的编程模式中解放出来。高速缓存是在20世纪60年代末才被提出的，其目的是解决CPU和主存速度差距的问题。我们不难发现虚拟存储器和高速缓存有许多相似之处，在学习时一些概念可以类比理解，但其所使用的术语却并不相同，例如高速缓存中我们称数据为“块”，而在虚拟存储器中却称为“页”，这是由时代所造成的。5.4.1分页模型

我们可以将主存看做是一个由相等字节大小单元组成的数组，数组中的各项通过地址来索引，地址是唯一且连续的。如图5.18所示，假设一个大小为256MB的主存，其第一个字节地址为0，接下来的字节地址为1，以此类推，最后一个字节地址为228－1。这里的“地址”是物理地址，早期的PC机大都使用物理寻址，这种寻址模式无需地址变换，程序直接访问物理内存，程序的灵活性和可移植性比较差。

图5.18物理寻址图5.19虚拟寻址虚拟存储器被分为大小固定的虚页(VirtualPage)，主存被分为同等大小的页框(PageFrame)，虚拟存储器机制是将虚页映像到页框或辅存，一般采用全相连映像，并用页表(PageTable)来描述两者的对应关系。

页表存储在主存中，由操作系统负责维护。页表由页表条目(PageTableEntry,PTE)构成。在我们的模型中，每个页表条目由一个有效位和一个N位地址字段构成。N位地址字段用来索引主存中页的物理地址，在虚拟地址转换为物理地址时用来构成物理地址的一部分。有效位用来指示虚页分配情况可分为下面三种情况：

(1)虚页已分配，缓存在主存中；

(2)虚页已分配，未缓存在主存中；

(3)虚页未分配。图5.20(a)展示了一个具有8个虚页和4个页框的虚拟存储器。其中：vp1、vp2、vp3、vp5四个虚页依次被缓存在主存单元3、0、2、1中，属于第(1)种情况。虚页vp4和vp7已经分配，但未被缓存在主存中，属于第(2)种情况。虚页vp0和vp6还未被分配，属于第(3)种情况。

当CPU要读取的页在主存中时，我们说页命中，反之就是不命中，我们也常称之为缺页。假设CPU首先要读取vp3页内的数据，通过页表索引到主存中的vp3，且vp3页命中。紧接着CPU要访问vp4页内数据，页表有效位为0，故vp4不在主存中，操作系统触发缺页异常。此时操作系统需将vp4页调入主存中，但主存此时已满，需要替换出其中一页。在此我们假设替换出vp1，如果vp1已被修改，则需要将vp1写回辅存中，接着操作系统将vp4从辅存中缓存到主存第3单元的位置，同时更新页表条目1和4，更新后的页表如图5.20(b)所示。

从图5.20(a)中我们还可看到，连续的页表条目1、2、3分别对应主存中不连续的页框3、0、2。在虚拟存储器机制中，连续的虚页通过全相连方式可映射到任意的主存页框，其好处是使得进程在需要连续的地址空间时，操作系统没有必要分配连续的实际物理主存空间。图5.20页表在实际情况中，操作系统的每个进程都有一个独立的页表，虚拟存储器机制使得多个虚页可以映像到同一个物理页框上，为进程间的数据共享提供了便利。两个虚页映像到同一个页框示例如图5.21所示。图中，进程x虚页映像用“实线”表示；进程y虚页映像用“虚线”表示。

最后，页表条目的字段构成远比上述模型中的一个有效位和一个n位地址字段复杂得多。因此在实际情况下，通过在页表条目中设置更多的字段，来控制页的读写权限和访问权限等，对进程数据起到保护作用。图5.21两个虚页映像到同一个页框示例5.4.2地址翻译

虚拟存储器的地址翻译通过硬件和操作系统相互协作来完成。如图5.22所示，处理器将虚拟地址交给处理器中的MMU单元，MMU负责虚拟地址到物理地址的转换工作。在MMU查找主存中的页表时，若页命中，则通过页表项构造物理地址，CPU取得物理地址后访问主存中的数据。若页不命中，即页表项有效位为零时，MMU触发缺页异常，操作系统进入缺页异常处理程序。缺页异常处理程序决定将请求页调入主存，在主存已满时，缺页异常处理程序还需确定主存中的哪个页面需要首先换出，换出时要检查这个页面是否被更新过，如果更新过则需将页面写入辅存，然后再将请求页调入主存，同时更新页表项。图5.22虚拟存储器机制虚拟地址到物理地址的映射是全相连方式，一般将虚拟地址分为虚页号和页偏移两部分，如图5.23所示，①表示处理器中的控制寄存器CR3指向当前页表，②表示虚拟地址通过虚页号索引页表，找到对应的页表项，③表示当页表有效位为1时，将页表条目中的物理页号同虚拟地址中的页偏移组合形成物理地址。当有效位为0时，则进行缺页异常处理。图5.23虚拟地址到物理地址的变换若要通过虚拟地址取得数据需经过两次主存访问。第一次访问主存中的页表，取得页表项，构成物理地址；第二次通过物理地址访问主存，取得请求数据。若要加快数据的读取速度，就需要减少对主存的访问次数，实际中的系统会使用一个较小的高速缓存——快表(TranslationLookasideBuffer,TLB)，来缓存部分页表项，它将把主存的访问次数由两次减少到一次。

快表的结构与页表类似，依据程序的局部性原理，快表缓存着最近一段时间经常用到的页表项，我们可以认为它是一个微型页表。快表中页表项与页表中页表项的映射关系同Cache映像方式类似，可相互参考。下面我们以图5.24来解释整个读操作的过程：

(1)处理器将虚拟地址交给处理器中的MMU单元，MMU查找快表中缓存的页表项。

①若快表项命中，则通过页表项物理地址字段构造物理地址；

②若快表项未命中，则查找主存中的页表，将相应页表项调入快表，通过页表项物理地址字段构造物理地址。

(2)当物理地址构造完成后，则通过物理地址查看请求数据是否在缓存中。

①若在缓存中，直接从缓存中取得请求数据；

②若不在缓存中，则需访问主存，将所需数据调入缓存，然后取得请求数据。图5.24加入快表和数据Cache后系统的虚拟存储器机制5.4.3小系统举例

我们先假设了一个小系统，通过对其进行分析，来综合理解虚拟存储器机制。小系统的具体参数：虚拟地址为8位，物理地址为7位，页大小为4字节，高速缓存大小共8字节(分为4块、每块2字节)，快表分为4组(每组2个页表项)，主存按字节寻址，假设每次访问1个字节。

虚拟地址和物理地址的格式划分分别如图5.25和图5.26所示。页大小为4字节，故虚拟地址低2位为页偏移，高6位为虚页号；物理地址低2位为页偏移，高5位为物理页号。图5.25虚拟地址的划分图5.26物理地址的划分快表分为4组，每组2个页表项，以类似组相联的方式映像页表，用虚页号的低2位作为其组号，用虚页号剩余4位作为标记，区分同一组里不同的项，如图5.27所示。

页表共64(26)个表项，存放在主存中，通过虚拟地址虚页号部分来索引，如图5.28所示。图5.27快表和页表的划分图5.28小系统页表高速缓存采用全相联映像，共4块，每块2字节。物理地址的低1位作为块内地址，高6位作为块号，如图5.29所示。

下面我们来分析比较两种简单的读操作情况：

(1)快表命中，数据Cache命中；

(2)快表不命中，页表命中，数据Cache命中。图5.29高速缓存地址的划分首先分析第一种情况。我们假设CPU要读取0x15处的一个字节，如图5.30所示。图5.30小系统举例① MMU从虚拟地址中取得虚页号000101，划分为标记0001和组号01，通过标记和组号来查找匹配快表表项，与第1组第二表项匹配成功，即快表命中，将对应的物理页号00011返回给MMU。

② MMU将取得的物理页号00011同虚拟地址中页偏移01组合起来，形成物理地址0001101。

③高速缓存从物理地址0001101中取得块号000110，同块号表相联比较，发现块号表第2项与之匹配，即高速缓存命中。组合块号表第2项和物理地址的块内地址部分构成Cache地址，最终取得目标字节0xFF。接着分析第二种情况。即当快表不命中时，我们假设CPU要读取0x05处的一个字节，页表如图5.28所示，其过程如下：

① MMU从虚拟地址中取得虚页号000001，划分为标记0000和组号01，通过标记和组号查找匹配快表表项，发现匹配不成功，即快表不命中。

② MMU通过虚页号000001索引内存中的页表，取得物理页号00110，同虚拟地址中页偏移01组合起来，形成物理地址0011001。

③高速缓存从物理地址0011001中取得块号001100，同块号表相联比较，发现块号表第3项与之匹配，即高速缓存命中。组合块号表第3项和物理地址的块内地址部分构成Cache地址，最终取得目标字节0xEA。当快表不命中，MMU查找页表，对应的页表项有效位字段为零时，还需从辅存中调入页面；若数据Cache不命中，则还需要进行相关的调块操作。

写操作与读操作类似。虚拟内存读取的整个流程如图5.31所示，不再具体分情况讨论，请读者自己思考。图5.31虚拟内存读取流程图

5.5Pentium处理器

1. L1Cache

PentiumL1Cache内部可分为数据Cache和指令Cache两部分，每部分的大小为8KB，分128组，每组2块，2路组相连映像方式，块大小为32字节。数据Cache采用了一种MESI协议，M表示当前缓存块中的数据修改过

；E表示当前缓存块中的数据未被修改过，和主存中一致；S表示当前缓存块中的数据与其他缓存共享；I表示所请求的块不在当前缓存块中。数据Cache各块需要额外的两位来存储MESI状态。指令Cache只有S和I两种状态，故只需要1位二进制来存储。替换算法先采用了LRU算法。

PentiumMMX处理器的数据Cache和指令Cache扩展到了16KB，并采用4路组相连映像方式。替换算法采用了PseudoLRU算法。

2. L2Cache

L2Cache的大小从512KB到1MB不等，块大小32字节，采用