存储系统是指计算机中由存放程序和数据的各种存储设备、控制部件及管理信息调度的设备（硬件）和算法（软件）所组成的系统。

存储系统是计算机的重要组成部分之一。存储系统提供写入和读出计算机工作需要的信息（程序和数据）的能力，实现计算机的信息记忆功能。现代计算机系统中常采用寄存器、高速缓存、主存、外存的多级存储体系结构。

计算机存储系统的核心是存储器，存储器是计算机中必不可少、用来存储程序和数据的记忆设备。

内部存储器（简称内存）主要存储计算机当前工作需要的程序和数据，包括高速缓冲存储器（Cache，简称缓存）和主存储器。目前构成内存的主要是半导体存储器。外部存储器（简称外存）主要有磁性存储器、光存储器和半导体存储器三种实现方式，存储介质有硬磁盘、光盘、磁带和移动存储器等。

现代计算机系统多级存储体系结构如图6-1，其中越顶端的越靠近CPU，存储器的速度越快、容量越小、每位的价格越高。采用这种组织方式能较好地解决存储容量、速度和成本的矛盾，提供一个在价格、容量上逻辑等价于最便宜的那一层存储器，而访问速度接近于存储系统中最快的那层存储器。

计算机的外部存储系统如果从1956年IBM制造出第一块硬盘算起，发展至今已经有半个多世纪了。在这半个多世纪里，存储介质和存储系统都取得了很大的发展和进步。

早期的数据存储一般以磁盘阵列等设备为外设，围绕服务器通过直连的方式进行存储。而近年来，随着网络技术的发展，服务器的数据读取范围也得到了很大拓展，逐渐实现了现在的网络存储。相较于传统存储来说，网络存储的优势更加突出，其不但安装便捷、成本低廉，并且还能够大规模的拓展存储设备，从而有效满足了海量数据存储对存储空间的需求。不过网络存储对网络资源的消耗极大，这是一项难题，为此，后来又逐渐出现了SAN存储架构。

目前传统存储系统主要的3种架构，包括DAS、NAS和SAN。

1.DAS（Direct-AttachedStorage，直连式存储）

顾名思义，这是一种通过总线适配器直接将硬盘等存储介质连接到主机上的存储方式，在存储设备和主机之间通常没有任何网络设备的参与。可以说DAS是最原始、最基本的存储架构方式，在个人电脑、服务器上也最为常见。DAS的优势在于架构简单、成本低廉、读写效率高等；缺点是容量有限、难于共享，从而容易形成“信息孤岛”。

2.NAS（Network-AttachedStorage，网络存储系统）

NAS是一种提供文件级别访问接口的网络存储系统，通常采用NFS、SMB/CIFS等网络文件共享协议进行文件存取。NAS支持多客户端同时访问，为服务器提供了大容量的集中式存储，从而也方便了服务期间的数据共享。

3.SAN（StorageAreaNetwork，存储区域网络）

通过光纤交换机等高速网络设备在服务器和磁盘阵列等存储设备间搭设专门的存储网络，从而提供高性能的存储系统。

SAN与NAS的区别，在于其提供块（Block）级别的访问接口，一般并不同时提供一个文件系统。通常情况下，服务器需要通过SCSI等访问协议将SAN存储映射为本地磁盘、在其上创建文件系统后进行使用。目前主流的企业级NAS或SAN存储产品一般都可以提供TB级的存储容量，高端的存储产品也可以提供高达几个PB的存储容量。

大数据导致了数据量的爆发式增长，传统的集中式存储（如NAS或SAN）在容量和性能上都无法较好地满足大数据的需求。因此，具有优秀的可扩展能力的分布式存储成为大数据存储的主流架构方式。分布式存储多采用普通的硬件设备作为基础设施，因此，单位容量的存储成本也得到大大降低。另外，分布式存储在性能、维护性和容灾性等方面也具有不同程度的优势。

分布式存储系统需要解决的关键技术问题包括诸如可扩展性、数据冗余、数据一致性、全局命名空间缓存等，从架构上来讲，大体上可以将分布式存储分为C/S（Client Server）架构和P2P（Peer-to-Peer）架构两种。当然，也有一些分布式存储中会同时存在这两种架构方式。

分布式存储面临的另外一个共同问题，就是如何组织和管理成员结点，以及如何建立数据与结点之间的映射关系。成员结点的动态增加或者离开，在分布式系统中基本上可以算是一种常态。

EricBrewer于2000年提出的分布式系统设计的CAP理论指出，一个分布式系统不可能同时保证一致性、可用性和分区容忍性（Partitiontolerance）这3个要素。因此，任何一个分布式存储系统也只能根据其具体的业务特征和具体需求，最大地优化其中的两个要素。当然，除了一致性、可用性和分区容忍性这3个维度，一个分布式存储系统往往会根据具体业务的不同，在特性设计上有不同的取舍，比如，是否需要缓存模块、是否支持通用的文件系统接口等。

云存储是由第三方运营商提供的在线存储系统，比如面向个人用户的在线网盘和面向企业的文件、块或对象存储系统等。云存储的运营商负责数据中心的部署、运营和维护等工作，将数据存储包装成为服务的形式提供给客户。云存储作为云计算的延伸和重要组件之一，提供了“按需分配、按量计费”的数据存储服务。因此，云存储的用户不需要搭建自己的数据中心和基础架构，也不需要关心底层存储系统的管理和维护等工作，并可以根据其业务需求动态地扩大或减小其对存储容量的需求。

云存储通过运营商来集中、统一地部署和管理存储系统，降低了数据存储的成本，从而也降低了大数据行业的准入门槛，为中小型企业进军大数据行业提供了可能性。比如，著名的在线文件存储服务提供商Dropbox，就是基于AWS（AmazonWeb Services）提供的在线存储系统S3创立起来的。在云存储兴起之前，创办类似于Dropbox这样的初创公司几乎不太可能。

云存储背后使用的存储系统其实多采用分布式架构，而云存储因其更多新的应用场景，在设计上也遇到了新的问题和需求。比如，云存储在管理系统和访问接口上大都需要解决如何支持多租户的访问方式，而多租户环境下就无可避免地要解决诸如安全、性能隔离等一系列问题。另外，云存储和云计算一样，都需要解决的一个共同难题就是关于信任（Trust）的问题——如何从技术上保证企业的业务数据放在第三方存储服务提供平台上的隐私和安全，的确是一个必须解决的技术挑战。

将存储作为服务的形式提供给用户，云存储在访问接口上一般都会秉承简洁易用的特性。比如，亚马逊的S3存储通过标准的HTTP协议、简单的REST接口进行存取数据，用户分别通过Get、Put、Delete等HTTP方法进行数据块的获取、存放和删除等操作。出于操作简便方面的考虑，亚马逊S3服务并不提供修改或者重命名等操作；同时，亚马逊S3服务也并不提供复杂的数据目录结构而仅仅提供非常简单的层级关系；用户可以创建一个自己的数据桶（bucket），而所有的数据则直接存储在这个bucket中。另外，云存储还要解决用户分享的问题。亚马逊S3存储中的数据直接通过唯一的URL进行访问和标识，因此，只要其他用户经过授权便可以通过数据的URL进行访问。

存储虚拟化是云存储的一个重要技术基础，是通过抽象和封装底层存储系统的物理特性，将多个互相隔离的存储系统统一化为一个抽象的资源池的技术。通过存储虚拟化技术，云存储可以实现很多新的特性。比如，用户数据在逻辑上的隔离、存储空间的精简配置等。

存储系统的层次化结构可以分为5级:寄存器组、高速缓存Cache、主存、虚拟存储器和外部存储器。其中，寄存器组总是在CPU内部，程序员可通过寄存器名访问，无总线操作，访问速度最快；其余4级均在CPU外部，Cache和主存构成内存储系统，程序员通过总线寻址访问存储单元，访问速度较寄存器差；虚拟存储器对程序员而言是透明的 ；外部存储系统容量大，需通过I/O接口与CPU交换数据，访问速度最慢。

高速缓冲存储器（Cache）的原始意义是指存取速度比一般随机存取存储器（RAM）更快的一种RAM，一般而言，它不像系统主存那样使用动态随机存储器（DRAM）技术，而是使用昂贵但较快速的静态随机存储器（SRAM）技术。

高速缓冲存储器是介于主存与CPU之间的一级存储器，由静态存储芯片（SRAM）组成，容量较小但速度比主存快得多，其最重要的指标是它的命中率。高速缓冲存储器与主存储器之间信息的调度和传送是由硬件自动进行的。

组成结构

高速缓冲存储器主要由以下三大部分组成：

工作原理

高速缓冲存储器通常由高速存储器、联想存储器、置换逻辑电路和相应的控制线路组成。在有高速缓冲存储器的计算机系统中，处理器存取主存储器的地址划分为行号、列号和组内地址三个字段。于是，主存储器就在逻辑上划分为若干行：每行划分为若干的存储单元组；每组包含几个或几十个字。高速存储器也相应地划分为行和列的存储单元组。二者的列数相同，组的大小也相同，但高速存储器的行数却比主存储器的行数少得多。

联想存储器用于地址联想，有与高速存储器相同行数和列数的存储单元。当主存储器某一列某一行存储单元组调入高速存储器同一列某一空着的存储单元组时，与联想存储器对应位置的存储单元就记录调入的存储单元组在主存储器中的行号。

当处理器存取主存储器时，硬件首先自动对存取地址的列号字段进行译码，以便将联想存储器该列的全部行号与存取主存储器地址的行号字段进行比较。若有相同的，表明要存取的主存储器单元已在高速存储器中，称为命中，硬件就将存取主存储器的地址映射为高速存储器的地址并执行存取操作；若都不相同，则表明该单元不在高速存储器中，称为失效，硬件将执行存取主存储器操作并自动将该单元所在的那一主存储器单元组调入高速存储器相同列中空着的存储单元组中，同时将该组在主存储器中的行号存入联想存储器对应位置的单元内。

当出现失效而高速存储器对应列中没有空的位置时，便淘汰该列中的某一组以腾出位置存放新调入的组，这称为置换。确定替换的规则称为置换算法，常用的置换算法有最近最久未使用算法（LRU）、先进先出法（FIFO）和随机法（RAND）等。置换逻辑电路就是执行这个功能的。另外，当执行写主存储器操作时，为保持主存储器和高速存储器内容的一致性，对命中和失效分别进行处理。

地址映像与转换

地址映像是指某一数据在主存中的地址与在缓存中的地址两者之间的对应关系。下面介绍三种地址映像方式：

1.全相联方式

全相联方式的地址映像规则是：主存储器中的任意一块可以映像到Cache中的任意一块。其基本实现思路是：1）主存与缓存分成相同大小的数据块；2）主存的某一数据块可以装入缓存的任意一块空间中。

目录表存放在联想存储器中，包括三个部分：数据块在主存的块地址、存入缓存后的块地址及有效位（也称装入位）。由于是全相联方式，因此目录表的容量应当与缓存的块数相同。

全相联方式的优点是命中率比较高，Cache存储空间利用空间率高；缺点是访问相关存储器时，每次都要与全部内容比较，速度低且成本高，因而应用少。

2.直接相联方式

直接相联方式的地址映像规则是主存储器中某一块只能映像到Cache的一个特定的块中。其基本实现思路是：

1）主存与缓存分成相同大小的数据块；

2）主存容量应是缓存容量的整数倍，将主存空间按缓存的容量分成区，主存中每一区的块数与缓存的总块数相等；

3）主存中某区的一块存入缓存时只能存入缓存中块号相同的位置。

主存中各区内相同块号的数据块都可以分别调入缓存中块号相同的地址中，但同时只能有一个区的块存入缓存。由于主、缓存的块号及块内地址两个字段完全相同，因此，目录登记时，只记录调入块的区号即可。目录表存放在高速小容量存储器中，包括两个字段：数据块在主存的区号和有效位。目录表的容量与缓存的块数相同。

直接相联方式的优点是地址映像方式简单，数据访问时，只需检查区号是否相等即可，因而可以得到比较快的访问速度，且硬件设备简单；缺点是置换操作频繁，命中率比较低。

3.组相联映像方式

组相联映像方式的地址映像规则是主存储器中某一块只能存入缓存的同组号的任一块中。其基本实现思路是：

1）主存和缓存按同样大小划分成块；

2）主存和缓存按同样大小划分成组：

3）主存容量是缓存容量的整数倍，将主存空间按缓存区的大小分成区，主存中每一区的组数与缓存的组数相同;

4）当主存的数据调入缓存时，主存与缓存的组号应相等，也就是各区中的某一块只能存入缓存的同组号的空间内，但组内各块之间可任意存放，即从主存的组到缓存的组之间采用直接映像方式：在两个对应的组内部采用全相联映像方式。

主存地址与缓存地址的转换由两部分构成：组地址采用的是直接映像方式，按地址进行访问；而块地址采用的是全相联方式，按内容访问。

组相联映像方式的优点是块的冲突概率比较低，块的利用率大幅度提高，块的失效率明显降低：而缺点是实现难度和造价要比直接映像方式高。

内存（Memory)）又被称为内存储器或主存储器，由半导体器件制成，是计算机的重要部件之一，是CPU能直接寻址的存储空间， 其特点是存取速率快。计算机中所有程序的运行都是在内存中进行的， 因此内存的性能对计算机的影响非常大。内存的作用是暂时存放CPU中的运算数据以及与硬盘等外部存储器交换的数据。只要计算机在运行中， CPU就会把需要运算的数据调到内存中进行运算， 当运算完成后CPU再将结果传送出来。

我们平常使用的程序， 如Windows操作系统、打字软件、游戏软件等， 一般都是安装在硬盘等外存上的，但仅此是不能使用其功能的，必须把它们调入内存中运行，才能真正使用其功能，我们平时输入一段文字，或玩一个游戏，其实都是在内存中进行的。就好比在一个书房里，存放书籍的书架和书柜相当于电脑的外存，而我们工作的办公桌就是内存。通常我们把要永久保存的、大量的数据存储在外存上，而把一些临时的或少量的数据和程序放在内存中，当然，内存的性能会直接影响电脑的运行速度。

内存包括只读存储器（ROM）和随机存储器（RAM）两类。

只读存储器（ROM）

只读存储器即ROM（ReadOnly Memory)）。在制造ROM的时候，信息（数据或程序）就被存入并永久保存。这些信息只能读出，不能写入，即使机器停电，数据也不会丢失。ROM一般用于存放计算机的基本程序和数据， 如BIOS ROM。其物理外形一般是双列直插式（DIP）的集成块。

随机存储器（RAM）

随机存储器即RAM（Random Access Memory） ， 表示既可以从中读取数据， 也可以写入数据。当机器电源关闭时， 存于其中的数据就会丢失。我们通常购买或升级的内存条（SIMM）就是用作电脑的内存， 它是将RAM集成块集中在一起的一小块电路板， 插在计算机中的内存插槽上， 以减少RAM集成块占用的空间。

最后介绍物理存储器和存储地址空间这两个概念。它们是两个不同的概念，但因为两者间有十分密切的关系，且都使用B、KB、MB及GB来度量其容量大小，因此容易产生认识上的混淆。物理存储器是指实际存在的具体存储器芯片。如主板上装插的内存条和装载有系统的BIOS的ROM芯片， 显示卡上的显示RAM芯片和装载显示BIOS的ROM芯片， 以及各种适配卡上的RAM芯片和ROM芯片都是物理存储器。存储地址空间是指对存储器编码（编码地址）的范围。所谓编码，就是对每一个物理存储单元（一个字节）分配一个号码，通常叫作“编址”。分配一个号码给一个存储单元的目的是为了便于找到它，完成数据的读写，这就是所谓的“寻址”，因此有人也把存储地址空间称为寻址空间。

存储地址空间的大小和物理存储器的大小并不一定相等。举个例子来说明这个问题：某层楼共有17个房间，其编号为801~817。这17个房间是物理的，而其地址空间采用了三位编码，其范围是800~899共100个地址，可见地址空间是大于实际房间数量的。对于386以上档次的微机，其地址总线为32位，因此地址空间可达2B，即4GB。

非易失性存储（NVM）

近年来出现的非易失性存储（Non-Volatile memory，NVM）以其高集成度、低能耗、非易失性、字节寻址等特性得到了广泛关注。学术界和工业界已经开发了一些新型非易失存储介质和技术， 例如磁存储器（Magnetic RAM，MRAM） 、自旋磁存储器（Spin Transfer TorqueRAM，STT-RAM）、相变存储器（Phase Change Memory， PCM） 、阻变存储器（Resistive RAM，RRAM）、铁电存储器（Ferroelectric RAM， FeRAM）等。表中列举了几种主流新型存储器件的主要参数，从表中可以看出，非易失性存储在集成度、读速度方面具有较好的表现，是构建潜在新型存储器件的候选对象。但是非易失性存储也有几个明显的缺点：1）具有较大的写延时，其写延时比相应的存储介质大1个数量级，并且写延时大于读延时，即读写不一致；2）虽然非易失性存储的读操作比写操作快，但是仍然比传统存储介质的读操作慢；3）非易失性存储的写寿命有限，在连续写的情况下，存储单元很快会失效。

磁盘是最常用的外部存储器，它是将圆形的磁性盘片装在一个方型的密封盒子里，这样做的目的是为了防止磁盘表面划伤，导致数据丢失。存放在磁盘上的数据信息可长期保存且可以反复使用。磁盘有软磁盘和硬磁盘之分，当前软磁盘已经基本被淘汰了，计算机广泛使用的是硬磁盘，我们可以把它比喻成是电脑储存数据和信息的大仓库。

硬磁盘的种类和构成

硬磁盘的种类主要包括SCSI、IDE以及现在流行的SATA等。任何一种硬磁盘的生产都有一定的标准，随着相应标准的升级，硬磁盘生产技术也在升级， 比如SCSI标准已经经历了SCSI-1、SCSI-2及SCSI-3，而目前我们经常在网站服务器看到的Ultra l-160就是基于SCSI-3标准的。IDE遵循的是ATA标准， 而目前流行的SATA，是ATA标准的升级版本。IDE是并口设备， 而SATA是串口， SATA的发展是为了替换IDE。

一般说来，无论是哪种硬磁盘，都是由盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等组成。

硬磁盘结构如图2-6所示。所有的盘片都固定在一个旋转轴上，这个轴即盘片主轴。而所有盘片之间是绝对平行的，在每个盘片的存储面上都有一个磁头，磁头与盘片之间的距离比头发丝的直径还小。所有的磁头连在一个磁头控制器上，由磁头控制器负责各个磁头的运动。磁头可沿盘片的半径方向作径向移动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。而盘片以数千转每分钟到上万转每分钟的速度高速旋转，这样磁头就能对盘片上的指定位置进行数据的读写操作。

硬磁盘的工作原理

1.盘面

硬磁盘的盘片一般用铝合金材料做基片，高速硬磁盘也可能用玻璃做基片。硬磁盘的每一个盘片都有两个盘面（Side）， 即上、下盘面， 一般每个盘面都会利用， 都可以存储数据，成为有效盘面，也有极个别的硬磁盘盘面数为单数。每一个这样的有效盘面都有一个盘面号，按顺序从上至下、从0开始依次编号。在硬磁盘系统中，盘面号又叫磁头号，因为每一个有效盘面都有一个对应的读写磁头。硬磁盘的盘片组的盘片有2~14片不等，通常有2~3个盘片，故盘面号（磁头号）为0~3或0~5。

2.磁道

磁盘在低级格式化时被划分成许多同心圆， 这些同心圆轨迹叫做磁道（Track） ， 信息以脉冲串的形式记录在这些轨迹中。磁道由外向内、从0开始顺序编号。硬磁盘的每一个盘面有300~1024个磁道，新式大容量硬磁盘每面的磁道数更多。每条磁道并不是连续记录数据，而是被划分成一段段的圆弧，这些圆弧的角速度一样，但由于径向长度不一样，所以线速度也不一样，外圈的线速度较内圈的线速度大，即同样的转速下，外圈在同样时间段里，划过的圆弧长度要比内圈划过的圆弧长度大。每段圆弧叫做一个扇区，扇区从1开始编号，每个扇区中的数据作为一个单元同时读出或写入。磁道是看不见的，只是盘面上以特殊形式磁化了的一些磁化区，在磁盘格式化时就已规划完毕。

3.柱面

所有盘面上的同一磁道构成一个圆柱， 通常称作柱面（Cylinder），每个圆柱上的磁头由上而下、从0开始编号。数据的读/写按柱面进行，即磁头读/写数据时首先在同一柱面内从0磁头开始进行操作，依次向下在同一柱面的不同盘面即磁头上进行操作，只有在同一柱面所有的磁头全部读/写完毕后，磁头才转移到下一柱面（同心圆的再往里的柱面），因为选取磁头只需通过电子切换即可，而选取柱面则必须通过机械切换，电子切换时磁头向邻近磁道移动的速度比机械切换时快得多，因此数据的读/写按柱面进行，而不按盘面进行，从而提高硬磁盘的读/写效率。

一块硬磁盘驱动器的柱面数（或每个盘面的磁道数）既取决于每条磁道的宽窄（同样，也与磁头的大小有关），也取决于定位机构所决定的磁道间步距的大小。

4.扇区

操作系统以扇区（Sector）形式将信息存储在硬磁盘上，每个扇区包括两个主要部分：扇区标识符和存储数据的数据段（通常为512B）。

扇区标识符，又称为扇区头标，包括组成扇区三维地址的三个数字：1）盘面号：扇区所在的磁头（或盘面）2）柱面号：磁道，确定磁头的径向方向：3）扇区号：在磁道上的位置，也叫块号，确定了数据在盘片圆圈上的位置。

扇区头标中还包括一个字段，其中有一个标识扇区是否能可靠存储数据的标记。有些硬磁盘控制器在扇区头标中还记录有指示字，可在原扇区出错时指引磁盘转到替换扇区或磁道。最后， 扇区头标以循环冗余校验（CRC）值作为结束， 以供控制器检验扇区头标的读出情况，确保准确无误。

扇区的数据段用于存储数据信息， 包括数据和保护数据的纠错码（ECC）。在初始准备期间， 计算机将512个虚拟信息字节（实际数据的存放位置）和与这些虚拟信息字节相应的ECC数字填入这个部分。

堆栈是C语言程序运行时的一个记录调用路径和参数的空间：包括函数调用框架、传递参数、保存返回地址及提供局部变量空间。

堆栈相关基础知识

1.堆栈相关寄存器

1）esp：堆栈栈顶指针；

2）ebp：基址指针（ebp在C语言中用作记录当前函数调用基址）；

3）cs:eip指向下一条指令的地址，分两种情况；

（1）顺序执行：总是指向地址连续的下一条指令；

（2）跳转/分支：执行这样的指令的时候，cs:eip的值会根据程序需要被修改；

4)call：将当前cs:eip的值压入栈顶，cs:eip指向被调用函数的入口地址；

5) ret：从栈顶弹出原来保存在这里的cs:eip的值， 放入cs:eip中；

6)iret：从栈顶弹出原来保存在这里的cs:eip及flags的值，放入cs:eip及标志寄存器中。

2.堆栈操作

1） push：栈顶指针减少4个字节（32位）：

2）pop：栈顶指针增加4个字节（32位）。

函数调用过程中堆栈的使用过程

函数调用过程中对堆栈的操作情况如图3所示，一个主函数调用了一个子函数，调用过程的具体步骤描述如下：

所谓局部性原理， 是指CPU访问存储器时， 无论是存取指令还是存取数据， 所访问的存储单元都聚集在一个较小的连续区域中。

局部性通常有两种形式：

时间局部性（temporal locality）：如果一个信息项正在被访问， 那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。

空间局部性（spatial locality）：在最近将要用到的信息很可能与现在正在使用的信息在空间地址上是临近的。

现代计算机系统的各个层次，从硬件到操作系统，再到应用程序，它们的设计都利用了局部性原理。在硬件层，局部性原理允许计算机设计者通过引入小而快速的高速缓冲存储器来保存最近被引用的指令和数据项，从而提高对主存的访问速度。在操作系统级，局部性原理允许系统使用主存作为虚拟地址空间最近被引用的高速缓存，局部性原理也允许系统利用主存来缓存磁盘文件系统中最近被使用的磁盘块等。局部性原理在应用程序的设计中也扮演着重要的角色， 例如， Web浏览器将最近被引用的文档放在本地磁盘上， 利用的就是时间局部性。大量的Web服务器将最近被请求的文档放在前端磁盘高速缓存中， 这些缓存能满足用户对这些文档的请求，而不需要服务器的任何干涉。

下面用三个例子来说明程序对数据引用的局部性。

例1：

int sumvec(int v[N])

{

int i=0，sum=0;

for(int i=0; i

{

sum+=v[i];

}

return sum;

}

上述代码中，变量sum在每次循环迭代中被引用一次，具有时间局部性。对于数组v的元素，按照它们存储在存储器中的顺序，被依次读取，因此具有空间局部性，但是每个数组元素只被访问一次， 所以不具有时间局部性。可见， sumvec函数对数据的访问既有空间局部性，也有时间局部性。

例2：

int sumarrayros(int v[M][N])

{

int i=0;j=0;sum=0;

for(i=0;i

for(j=0;j

{

sum+=v[i] [j]；

}

return sum;

}

上述代码中，数组v的元素都是按照步长1来访问的，因此具有很好的空间局部性（数组元素是按照行顺序存储的）。

例3：

int sum array ros(int v[M][N])

{

inti=0;j=0;sum=0;

for(j=0;j

for(i=0;i

{

sum+=v[i][j];

}

return sum;

}

上述代码中，数组v的元素都是按照步长N来访问的，因此其空间局部性很差。综上，可以得到如下结论：

1)重复引用同一个变量的程序有良好的时间局部性；

2)对于具有步长为k的引用模式的程序，步长越小，空间局部性越好。在存储器中以大步长跳来跳去的程序，空间局部性会很差；

3)对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。