本科生毕业论文cache高速缓存与主存一致性 1.docx

本科生毕业论文cache高速缓存与主存一致性 1.docx

《本科生毕业论文cache高速缓存与主存一致性 1.docx》由会员分享，可在线阅读，更多相关《本科生毕业论文cache高速缓存与主存一致性 1.docx（16页珍藏版）》请在冰点文库上搜索。

本科生毕业论文cache高速缓存与主存一致性1

本科生毕业论文（设计）

Cache（高速缓存）与主存一致性初探

院系名称

信息工程系

姓　　名

姓名

学　　号

2008341142

专　　业

计算机科学与技术专业

指导教师

导师教授

2012年3月25日

摘　要

存储器是具有“记忆”功能的部件，它在计算机系统中占有十分重要的地位。

存储器的基本功能是存放以二进制形式表示的程序与数据。

如何设计容量大、速度快且造价低的存储器，一直是计算机发展中的关键问题，目前还没有哪一种存储器功能完全满足计算机系统对存储器的需求。

因此，计算机系统通常配备分层结构的存储系统，以满足容量、速度和造价等方面的要求。

衡量存储器有三个指标：

容量、速度和价格/位。

一般地说，速度高的存储器，每位价格也高，因此容量不能太大。

所以存储器设计的约束有容量、速度和价格。

容量似乎没有限制，不管容量多大，总要开发出应用程序来使用。

为了获得更好的性能，存储器的速度必须能够跟上CPU，即当CPU执行指令时，不想让他停下来等待指令或操作数。

价格问题也必须考虑，对于实用的系统，存储器的价格必须相对于其他部件是合理的。

因此三个指标之间需要进行权衡。

高速缓存系统中能否确保高速缓冲存储器和主存内容一致性，这个问题直接关系到整个计算机系统的性能。

这两部分的数据一致性问题产生的原因有二：

其一，由于CPU对高速缓冲存储器的写入导致它的内容更新而主存内容陈旧；其二，由于I/O处理机或多处理机系统中某一处理机修改了主存内容导致高速缓冲存储器内容陈旧。

针对不同原因，分析了写策略中七种解决方案，并就高速缓存系统采用的第二级脱片高速缓冲存储器，以及第三级脱片高速缓冲存储器结构数据一致性问题进行初步探讨。

本文通过对存储器系统Cache（高速缓存）与主存的概念进行描述和目前两者之间一致性存在的一些问题进行研究。

并分析在多处理机系统中，主存与各处理机私有Cache之间及各私有Cache之间存在的数据不一致性。

对解决不一致性的方法：

监听总线协议、基于目录的Cache一致性协议、软件控制方法等进行详细的定性分析，并指出各种方法的优缺点，供设计者参考；同时提出软件和硬件相结合的方法，能有效解决Cache的一致性问题。

关键词：

存储器；主存；缓存；一致性

Abstract

Memoryisa"memory"functioncomponents,itinacomputersystemoccupiesaveryimportantposition.Thebasicfunctionofmemoryisstoredinbinaryformofsaidprogramsanddata.Howtodesigncapacity,speedisquickandlowcostofmemory,isalwaysthekeyproblemsinthedevelopmentofthecomputer,thereisnomemoryfunctionfullymeettheneedsofthememoryofacomputersystem.Therefore,thecomputersystemusuallyequippedwithalayeredstructureofstoragesystem,tosatisfythecapacity,speedandcostrequirements.

Measurememoryhasthreeindex:

capacity,speedandprice/a.Generallyspeaking,thehighspeedofmemory,everypriceishigh,thereforecapacitycannotbetoobig.Somemorydesignconstraintscapacity,speedandprice.Thereseemstobenolimitcapacity,nomatterhowmuchcapacity,thetotaltodevelopapplicationstouse.Inordertoobtainthebetterperformance,thespeedofthememorymustbeabletokeepupwiththeCPU,andthatiswhentheCPUexecutinginstructions,don'twanthimtostopandwaitforinstructionsoroperand.Thequestionofpricemustalsoconsider,forpracticalsystem,memorypricesrelativetootherpartsmustbeisreasonable.Sothethreeindexestoweighbetween.

Cachesystemcanensurecachememoryandmainmemorycontentsconsistency,thedirectlyrelatedtotheentirecomputersystemperformance.Thetwopartsofthedataconsistencyissuesoftworeasons:

first,becauseoftheCPUcachememorywriteledtoitscontentstoupdatethememoryandout-of-datecontents;Second,becauseofI/Oprocessorormulti-processorsystemsofaprocessormodifiedthemainmemorycontentsleadtocachecontentobsolete.Accordingtodifferentreasons,analyzesthestrategyofwrittensevenkindsofsolutions,andthecachesystemUSES2totakeoffthepieceofcache,andthethirdclasstotakeoffthepieceofcachestructuredataconsistencyproblemforapreliminarydiscussion.

ThisarticlethroughtothememorysystemCache（Cache）andtheconceptofmainstoragedescribebetweenconsistencyandatpresenttherearesomeproblems.Andanalysisinmultiprocessorsystem,mainmemorywiththeprocessorCachebetweentheprivateandprivateCacheofinconsistencybetweendata.Tosolvetheinconsistencymethod:

surveillancebusagreement,theCachedirectorybasedonconsistencyagreement,softwarecontrolmethodofdetailedqualitativeanalysis,andpointsouttheadvantagesanddisadvantagesofeachmethodfordesigners;SomesoftwareandhardwarethemethodofcombiningtheCachecaneffectivelyresolvetheconsistencyoftheproblem.

KeyWords:

Memory,Themainmemory,Cache,Theconsistency

目　录

1引　言

高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片（SRAM）组成，容量比较小但速度比主存高得多，接近于CPU的速度。

在计算机存储系统的层次结构中，是介于中央处理器和主存储器之间的高速小容量存储器。

它和主存储器一起构成一级的存储器。

高速缓冲存储器和主存储器之间信息的调度和传送是由硬件自动进行的。

高速缓冲存储器的容量一般只有主存储器的几百分之一，但它的存取速度能与中央处理器相匹配。

根据程序局部性原理，正在使用的主存储器某一单元邻近的那些单元将被用到的可能性很大。

因而，当中央处理器存取主存储器某一单元时，计算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单元内。

于是，中央处理器就可以直接对高速缓冲存储器进行存取。

在整个处理过程中，如果中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替，计算机系统处理速度就能显著提高。

当然，计算机存储系统中，高速缓冲存储器系统的引入虽然为计算机系统处理数据的速度带来了显著地提高，但是随之而来的Cache（高速缓存）与主存间数据一致性问题也是日益凸显出来。

存储器中的一致性问题，是伴随着存储器结构的概念而提出的，又一直是困扰着计算机设计者的一个重要问题，也是很多从事计算机体系结构研究的人们所共同面对的一个热门研究课题。

特别是近年来出现的多处理系统，超并行机系统，超大规模计算机系统等采用DSM（DistributedSharedMemory）-分布式共享存储器技术的大型系统中，都采用了多级Cache的存储器层次结构。

在Cache的数据一致性问题上，就更显突出了。

如在DSM多处理机系统结构中，相邻层之间和同一层之内可能会出现数据不一致性。

通过存储器的共享数据，进程在同一算法下并行工作。

为了减少内存访问延时和内存总线的拥塞，要求Cache与每个处理器相关。

这样同一数据在不同的Cache中有多个副本。

当处理机对共享存储器某个单元在其本地Cache中的拷贝要进行维护时，只要对该单元的本地拷贝进行修改，这就有可能引起存储器的全局不一致性等等。

所以如何在维护一致性情况下又保证处理机代价最小是这本论文讨论的主要问题。

本文将在对计算机存储系统存储进行介绍的前提下，对高速缓存系统中Cache（高速缓存）与主存这两部分的数据一致性问题产生的各种原因进行充分的分析和研究，并针对不同的原因，给予适当各种维护策略下的保证一致性的可行方案。

2研究的背景和意义

2.1研究的背景

存储器是具有“记忆”功能的部件，它在计算机系统中占有十分重要的地位。

存储器的基本功能是存放以二进制形式表示的程序与数据。

如何设计容量大、速度快且造价低的存储器，一直是计算机发展中的关键问题，目前还没有哪一种存储器功能完全满足计算机系统对存储器的需求。

因此，计算机系统通常配备分层结构的存储系统，以满足容量、速度和造价等方面的要求。

衡量存储器有三个指标：

容量、速度和价格/位。

一般地说，速度高的存储器，每位价格也高，因此容量不能太大。

所以存储器设计的约束有容量、速度和价格。

容量似乎没有限制，不管容量多大，总要开发出应用程序来使用。

为了获得更好的性能，存储器的速度必须能够跟上CPU，即当CPU执行指令时，不想让他停下来等待指令或操作数。

价格问题也必须考虑，对于实用的系统，存储器的价格必须相对于其他部件是合理的。

因此三个指标之间需要进行权衡。

2.1.1主-辅存存储层次

由于计算机主存容量相对于程序员所需要的容量来说总是太小，程序与数据从辅存调入主存是由程序员自己安排的，程序员必须花费很大精力和时间把大程序预先分成块，确定好这些程序块在辅存中的位置和装入主存的地址，而且还要预先安排好程序运行时各块如何和何时调入调出，因此存在存储空间的分配问题。

操作系统的形成和发展使得程序员尽可能摆脱主、辅存之间的地址定位，同时形成了支持这些功能的“辅助硬件”，通过软件、硬件的结合，把主存和辅存统一成了一个整体，如图2-1所示。

这时，由主存、辅存形成了一个存储层次，即存储系统。

从整体看，其速度接近于主存的速度，其容量则接近于辅存的容量，而每位的平均价格也接近于廉价的慢速的辅存平均价格。

这种系统不断发展和完善，就逐步形成了现在广泛使用的虚拟存储系统。

在系统中，应用程序员可用机器指令地址码对整个程序统一编址，如同程序员具有对应这个地址码宽度的全部虚存空间一样。

该空间可以比主存实际空间大得多，以致可以存得下整个程序。

这种指令地址码称为虚地址（虚存地址、虚拟地址）或逻辑地址，其对应的存储容量称为虚存容量或虚存空间；而把实际主存的地址称为物理地址、实（存）地址，其对应的存储容量称为主存容量、实存容量或实（主）存空间。

图2-1主-辅存存储层次

2.1.2CACHE-主存存储层次

当用虚地址访问主存时，机器自动地把它经辅助软件、硬件变换成主存实地址。

察看这个地址所对应的单元内容是否已经装入主存，如果在主存就进行访问，如果不在主存内就经辅助软件、硬件把它所在的那块程序和数据由辅存调入主存，而后进行访问。

这些操作都不必由程序员来安排，也就是说，对应用程员员是透明的。

主-辅存层次解决了存储器大容量要求和低成本之间的矛盾。

在速度方面，计算机的主存和CPU直保持了大约一个数量级的差距。

显然这个差距限制了CPU速度潜力的发挥。

为了弥合这个差距，仅采用一种工艺的单一存储器是行不通的，必须进一步从计算机系统结构和组织上去研究。

设置高速缓冲存储器（Cache）是解决存取速度的重要方法。

在CPU和主存中间设置高速缓冲存储器，构成高速缓存（Cache）-主存层次，要求Cache在速度上能跟得上CPU的要求。

Cache-主存间的地址映象和调度吸取了比它较早出现的主-辅存存储层次的技术，不同的是因其速度要求高，不是由软、硬件结合而完全由硬件来实现，如图2-2所示。

图2-2Cache-主存存储层次

2.1.3存储器分层结构

从CPU的角度看，Cache-主存层次的速度接近于Cache，容量与每位价格接近于主存，因此，解决了速度与成本之间的矛盾。

综上所述，计算机的存储系统是采用了存储器的分层结构，而不只是依赖单一的存储部件或技术。

图2-3给出了一个通用分层结构，图中从上到下出现情况如下：

1>每位的价格降低；

2>容量增大；

3>存取时间增大；

4>CPU存取存储器的频度降低。

图2-3存储器分层结构

因此，较小、较贵、较快的存储器可作为较大、较便宜、较慢的存储器的补充。

这个结构成功的关键是最后一项，即存取频度降低。

如果能够根据以上的1>到3>项来组织存储器，而且数据和指令能够根据4>分布在存储器中，很显然，这个方案在保证给定的性能水平的情况下能降低总体价格。

下面用一个简单的例子来说明这一点。

假设CPU能够存取二级的存储器，第1级包含1000个字并有1微秒的存取时间，第2级包含1000000个字并有10微秒的存取时间。

假设要存取的一个字在第1级，那么CPU能直接存取它；假设它在第2级，则这个字首先传到第1级，然后再由CPU存取它。

为了简化，不考虑CPU确定这个字在第1级还是在第2级所需的时间。

图2-4表示了平均总存取时间和在第1级中存取字所需的时间占总的百分比的函数关系。

可见，第1级存取百分比高时，平均总的存取时间接近于第1级的存取时间。

此例说明了这种策略工作的原理。

如果条件1>到4>都满足，则它能工作。

图2-4简单的两级存储性能

条件4>有效的基础是访问局部性原理。

在程序执行过程中，处理器访问存储器中的指令和数据倾向于成块进行。

程序通常包含许多迭代循环的子程序，一旦进入了一个循环或子程序，则需重复访问一小组指令。

同样，对于表和数组的操作，包含存取一块块的数据字。

在一长段时间内，使用的块是变化的，而在一小段时间内，处理器主要访问存储器中的固定块。

因此，通过分层结构组织数据，有可能使存取较低层的存取时间百分比低于存取高层的百分比。

根据上面给出的二级例子，让第2级的存储器包含所有程序的指令和数据，当前的块临时放在第1级，第1级某些块回不时地交换回第2级。

然而，多数是对第1级中的指令和数据的访问。

这个原理可以应用到两级以上的存储器。

考虑如图2-3所示的分层结构，最快、最小和最贵的存储器是处理器的内部存储器。

通常一个处理器包含几十个寄存器，虽然有些机器包含几百个寄存器。

向下跳二层是主存储器。

主存储器通常用一个速度更快、容量更小的高速缓存来扩充。

高速缓存是透明的，它在主存和处理器寄存器之间传送数据以提高性能。

2.2研究的意义

高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片（SRAM）组成，容量比较小但速度比主存高得多，接近于CPU的速度。

在计算机存储系统的层次结构中，介于中央处理器和主存储器之间的高速小容量存储器。

它和主存储器一起构成一级的存储器。

高速缓冲存储器和主存储器之间信息的调度和传送是由硬件自动进行的。

高速缓冲存储器的容量一般只有主存储器的几百分之一，但它的存取速度能与中央处理器相匹配。

根据程序局部性原理，正在使用的主存储器某一单元邻近的那些单元将被用到的可能性很大。

因而，当中央处理器存取主存储器某一单元时，计算机硬件就自动地将包括该单元在内的那一组单元内容调入高速缓冲存储器，中央处理器即将存取的主存储器单元很可能就在刚刚调入到高速缓冲存储器的那一组单元内。

于是，中央处理器就可以直接对高速缓冲存储器进行存取。

在整个处理过程中，如果中央处理器绝大多数存取主存储器的操作能为存取高速缓冲存储器所代替，计算机系统处理速度就能显著提高。

在由主存和高速缓存组成的存储器层次结构中，主存是多处理机共享，而高速缓存是每个处理机私有的。

主存和高速缓存都以块为单位进行划分，以映射的方式来检索。

映射的方法有直接映射、组关联映射、区段关联映射和全相联映射。

在主存和高速缓存之间，是以块为单位进行搬送。

主存中保存有各高速缓存的副本，高速缓存的目录中，存放相应主存的块号及一些标志。

通过对目录的检索来寻找高速缓存中的数据。

当处理机发出一个访问主存地址时，如果包含这个地址在内的模块在高速缓存中，则称之为命中，该高速缓存可以使用。

如果不在高速缓存中，则称之为未命中（或Cache失效），这时，必须把这个模块从主存搬到高速缓存中，叫做块搬送。

如果高速缓存已满，则必须按一定的置换算法挑出一个模块搬出高速缓存到主存，这叫置换。

置换算法有FIFO算法，URL算法等。

计算机高速缓存系统的发展为计算机设计者提出了一个重要课题：

数据在Cache（高速缓冲存储器）和主存之间交换时必须满足数据一致的要求，随着多任务系统的采用，数据一致性问题越来越突出，以往关于这方面的著述具有了很大的局限性，例如，对于486以上机种出现的第二级托片Cache、第三级托片Cache如何保存数据一致的问题尚未见于专门的论述。

为了探索更适合于当前计算机发展的趋势，必须适时追溯数据一致性问题出现和发展的历史轨迹，步入多任务系统的解决方案。

因此高速缓存系统中能否确保高速缓冲存储器和主存内容一致性，这个问题直接关系到整个计算机系统的性能。

对于计算机整体性能的提升有十分重要的意义。

3数据一致性问题的提出

高速缓存是旨在改善存储器平均响应时间的小型快速存储器，它在系统中位于微处理器和主存之间，使得系统从CPU看具有Cache的速度，主存的容量。

图3-1为一高速缓冲存储器系统框图，它将微处理器频繁向主存请求的代码和数据予以拷贝。

图3-1高速缓存框图

Cachc的操作与存储器一样具有读/写两种模式，其中读操作主要局限在不命中时更新Cache内容，只影响存储系统工作速度。

写操作不仅工作时间比读操作长，而且更新主存内容，直接影响机器性能，据李学干、苏东庄在《计算机系统结构》一书中借典型程序的统计可知，所有访存中约有10%~34%甚至更多的是写操作。

写操作是直接导致数据一致性问题产生的原因。

在一个系统中，同一个数据的多个拷贝可以同时存在，如果一个拷贝改变了而其它的没变，那么两组不同的数据便与主存的同一地址有关。

Cache必须包含一个更新系统以防止老数据（陈旧数据）被使用，即解决一致性问题。

分析产生数据一致性问题的原因主要有三个：

1>同样一个数据可能既存于Cache中，也存于主存中，这样可能前者己更新，后者未更新，造成数据丢失。

2>在有DMA系统或多处理器系统中，有多个部件可以访问主存，这时可能其中有些部件是直接访问主存，也可能每个DMA部件和每个处理器配一个Cache，这样主存的一块区域可能对应于多个Cache中的各1个块区，产生主存中的数据被某个总线主控部件更新过，而某个Cache中的内容未更新，造成Cache中数据过时。

3>当主存中同时有多道程序运行时，Cache中均有相应的数据副本与每道程序相对应；对于共享数据，每道程序都有各自的Cache数据与主存数据相一致。

当某道更新了其相应的Cache数据和主存数据，而其它程序的Cache数据也有此页内容.则其内容不会改变（例如写直达法约束）。

这道程序再次读到的内容就会因是原先的内容而出错。

写策略是Cache使用的保证数据一致性的方法，保持系统主存更新，处理陈旧数据。

高速缓存一致性是指要求同一个信息项与后继存储器层次上的副本是一致的。

如果在高速缓存中的一个字被修改过，那么在所有更高层上该字的副本也必须立即或最后加以修改。

对于多处理机系统的存储器层次结构，相邻层之间和同层之间可能会出现数据不一致性。

比如某个处理机修改了该处理机的Cache的某个数据，则该数据块可能在别的处理机上有相同的拷贝，由于该数据块得到了最新的修改，所以如果其它相同的拷贝不及时得到修改的话，被其它处理机访问以后，可能出现错误。

这也就是所谓的Cache不一致性。

我们用图3-2一致性定义图来直观的表示：

图3-2一致性定义图

但是这种只对本地拷贝进行修改的方法就可能导致存储器的全局不一致性，也就是这些拷贝并不一致。

如何能够让处理器访问不会出错，并且维护一致性的代价最小是研究高速缓存一致性和同步机制的主要研究课题。

4基于不同原因的写策略解决方案

4.1基于原因1的解决办法

原因1导致的数据一致性问题是建立在Cache内容与主存内容一一对应基础上，不能相关更新造成的数据丢失，解决方法首先解决Cache与主存的相关动作。

4.1.1写直达

它利用Cache-主存贮层次在处理机和主存之间的直接通路，每当处理机写入Cache的同时，也通过此通路直接写入主存。

从而主存随时跟踪Cache的最新版本，也就不会有主存将数据丢失的问题但缺点也显而易见，它把开销花费在每次写Cache时就有对主存的