存储结构
编辑




数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。




目录

1数据结构方面的储存结构
▪ 
分类 
▪ 
顺序存储和链接存储的基本原理 

2储存器方面的储存结构
▪ 
程序的局部性原理 
▪ 
多级存储体系的组成 

1数据结构方面的储存结构编辑
分类
顺序存储方法它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。
链接存储方法它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构，链式存储结构通常借助于程序设计语言中的指针类型来实现。
顺序存储和链接存储的基本原理
顺序存储和链接存储是数据的两种最基本的存储结构。
在顺序存储中，每个存储空间含有所存元素本身的信息，元素之间的逻辑关系是通过数组下标位置简单计算出来的线性表的顺序存储，若一个元素存储在对应数组中的下标位置为i，则它的前驱元素在对应数组中的下标位置为i-1，它的后继元素在对应数组中的下标位置为i+1。在链式存储结构中，存储结点不仅含有所存元素本身的信息，而且含有元素之间逻辑关系的信息。
数据的链式存储结构可用链接表来表示。
其中data表示值域，用来存储节点的数值部分。Pl，p2，…，Pill(1n≥1)均为指针域，每个指针域为其对应的后继元素或前驱元素所在结点(以后简称为后继结点或前驱结点)的存储位置。通过结点的指针域(又称为链域)可以访问到对应的后继结点或前驱结点，若一个结点中的某个指针域不需要指向其他结点，则令它的值为空（NULL）。
在数据的顺序存储中，由于每个元素的存储位置都可以通过简单计算得到，所以访问元素的时间都相同；而在数据的链接存储中，由于每个元素的存储位置保存在它的前驱或后继结点中，所以只有当访问到其前驱结点或后继结点后才能够按指针访问到，访问任一元素的时间与该元素结点在链式存储结构中的位置有关。
2储存器方面的储存结构编辑
储存系统的层次结构为了解决存储器速度与价格之间的矛盾，出现了存储器的层次结构。
程序的局部性原理
在某一段时间内，CPU频繁访问某一局部的存储器区域，而对此范围外的地址则较少访问的现象就是
程序的局部性原理。层次结构是基于程序的局部性原理的。对大量典型程序运行情况的统计分析得出的结论是：CPU对某些地址的访问在短时间间隔内出现集中分布的倾向。这有利于对存储器实现层次结构。
多级存储体系的组成
目前，大多采用三级存储结构。
即：Cache-主存-辅存，如下图：


3、多级存储系统的性能
考虑由Cache和主存构成的两级存储系统，其性能主要取决于Cache和贮存的存取周期以及访问它们的
次数。（存取周期为: Tc,Tm ;访问次数为: Nc,Nm）


（1）Cache的命中率 H= Nc / (Nc+Nm)
（2）CPU访存的平均时间 Ta= H * Tc+ (1-H) Tm
Cache-主存系统的效率
e= Tc / Ta
=1/H+(1-H)Tm/Tc
根据统计分析：Cache的命中率可以达到90%~98%
当Cache的容量为：32KB时，命中率为86%
64KB时，命中率为92%
128KB时，命中率为95%
256KB时，命中率为98%

词条标签：
数据结构C语言编程

微机原理与接口技术 ， 
存储器及存储器子系统 

存储器分类&存储系统的层级结构①
/*
​	开始时间：2021-04-03
​	结束时间：2021-04-07
​	字数：1.3k
​	修改日志：
​		  暂无
*/

文章目录
存储器分类&存储系统的层级结构①
知识导图
存储器的分类
按存储器的功能分类
按存取方式分类
按存取介质分类
按信息的可保存性分类
存储系统的层次结构
存储系统的追求目标
存储器的金字塔层次结构
存储层次结构
多级存储层次
三级存储系统
注释
参考资料

知识导图

存储器的分类
 存储器是计算机的重要组成部分，在计算机工作时起着重要的作用，根据不同的分类方式，可以将存储器分为以下几类：
按存储器的功能分类

主存储器：即内存，与CPU直接交换数据。
辅助存储器：即外存，电脑硬盘，一般存储长期保存的数据。
高速缓冲存储器(Cache)：内存和外存之间数据交换的媒介，弥补了内存的存储容量小和外存存储速度慢的缺点。

按存取方式分类


随机存储器（Random Access Memory ，RAM）
CPU可以对存储器内的数据随机的随去，不受其存储位置的影响。主要作主存或高速缓冲存储器使用。


只读存储器（Read Only Memory，ROM）
与随机存储器类似，但是只能从中读取数据，而不能修改其中的信息。断电后其中的数据也不会丢失。


顺序存储器（Sequential Access Memory，SAM）
只能按照一定顺序读取其中的信息，代表为磁带。


直接存储器（Direct Access Memory，DAM）
介于随机存储器和顺序存储器之间，对其进行信息读写时，先是直接定位至某一大范围内（类似RAM），再在其中进行顺序检索，确定准确的地址（类似SAM），进行信息的读写。


按存取介质分类
（主要是存储材料不同，了解即可。）

磁芯存储器
半导体存储器
磁表面存储器
光存储器

按信息的可保存性分类

易失性存储器：断电后存储信息即消失的存储器，内存，半导体RAM
非易失性存储器：断电后存储信息仍然保留的存储器，外存，ROM，磁芯存储器，磁表面存储器，光盘

存储系统的层次结构
 存储器是存储系统的组成单元，由于各种存储器的存储容量、存储速度和成本不同，为了提高利用率，适应不同的使用环境，通常将不同的存储器组合起来使用，形成一个统一的存储系统。
存储系统的追求目标

尽快的存储速度
尽大的存储空间
尽低的存储成本

存储器的金字塔层次结构

在上述金字塔形存储器结构中，越靠近顶层，存储器的存储速度越快，存储容量越小，存储单位成本越大。反之，越靠近底层，存储器的存储速度越慢，存储容量越大，存储单位成本越小。
存储层次结构
根据上面所要求的存储系统所追求的目标和存储器的金字塔模型，可以构成几种存储层次。
多级存储层次
多级缓冲存储类似于金字塔模型，CPU位于金字塔模型的顶部，层次结构图为：

其中，Mn 的存储容量最大，存储速度最慢，单位存储成本最低，一直到M1 存储容量减小，存储速度增大，单位存储成本增大。整个存储系统中，存储速度接近M1，存储容量接近或等于Mn，单位存储成本接近Mn ；其中最常用的数据存储在M1 中，最少使用的在Mn 中。
三级存储系统
由高速缓冲存储器，主存储器，辅助存储器构成的三级存储系统。
可以分为两个层次③：


高速缓存和主存间：Cache-主存存储层次（Cache存储系统）



主存和辅存之间：主存-辅存存储层次（虚拟存储系统）




Cache存储系统解决了主存存储速度不足的问题②。增加Cache后，对于CPU来说，主存的数据传输速度已经达到了CPU的运算速度。
虚拟存储系统解决了主存储器存储空间不足的问题。增加辅存，即外存或硬盘，增加了主存的存储容量，数据的传输速度不会降低，单位存储成本接近于辅存的成本。
注释
①　对于这部分内容主要是对存储系统的概括，基于存储器的综合性描述。
② 主存即内存，其速度相对于外存已经很快了，但是还赶不上CPU的运算速度，所以这里的速度不足是相对而言的。
③ 图示摘自参考书 P126-图5-2
参考资料
[1]蒋本珊.计算机组成原理.4版.北京：清华大学，2019.

在一个计算机系统中，对存储器的容量、速度和价格这三个基本性能指标都有一定的要求。存储容量应确保各种应用的需要；存储器速度应尽量与CPU的速度相匹 配并支持I／O操作；存储器的价格应比较合理。然而，这三者经常是互相矛盾的。例如存储器的速度越快，则每位的价格就越高；存储器的容量越大，则存储器的 速度就越慢。按照目前的技术水平，仅仅采用一种技术组成单一的存储器是不可能同时满足这些要求的。只有采用由多级存储器组成的存储体系，把几种存储技术结 合起来，才能较好地解决存储器大容量、高速度和低成本这三者之间的矛盾。

简绘为：
通用寄存器(CPU内) ---> 高速缓存（常在cpu内）-->主存 ---> 虚拟存储器(硬盘) 

 最内层是CPU中的通用寄存器，很多运算可直接在CPU的通用寄存器中进行，减少了CPU与主存的数据交换，很好地解决了速度匹配的问题，但通用寄存器的数量是有限的一般在几个到几百个之间，如Pentium CPU中有8个32位的通用寄存器。 

高速缓冲存储器（Cache）设置在CPU和主存之间，可以放在CPU 内部或外部。其作用也是解决主存与CPU的速度匹配问题。Cache一般是由高速SRAM组成，其速度要比主存高1到2个数量级。由主存与Cache构成 的“主存－Cache存储层次，从CPU来看，有接近于Cache的速度与主存的容量，并有接近于主存的每位价格。通常，Cache还分为一级Cache 和二级Cache。 

但是，以上两层仅解决了速度匹配问题，存储器的容量仍受到内存容量的制约。因此，在多级存在储结构中又增设了辅助存储器（由磁盘构成）和大容量 （又称海量）存储器（由磁带构成）。随着操作系统和硬件技术的完善，主存之间的信息传送均可由操作系统中的存储管理部件和相应的硬件自动完成，从而构成了 主存一辅存的价格，从而弥补了主存容量不足的问题。 


多级存储结构构成的存储体系是一个整体。从CPU看来，这个整体的速度接近于Cache和寄存器的操作速度、容量是辅存（或海量存储器）的容量，每位价格接近于辅存的位价格。从而较好地解决了存储器中速度、容量、价格三者之间的矛盾，满足了计算机系统的应用需要。 

随着半导体工艺水平的发展和计算机技术的进步，存储器多级结构的构成可能会有所调整，但由多级半导体存储器芯片集成度的提高，主存容量可能会达到 几百兆字节或更高，但由于系统软件和应用软件的发展，主存的容量总是满足不了应用的需求，只要这一现状仍然存在，由主存――辅存为主体的多级存储体系也就 会长期存在下去。 

更详细的资料可以参考
http://www.open.ha.cn/qiu/dag/main4.htm#/qiu/dag/4/4_1/index.htm

摘要

计算机系统对存储器的容量、速度和价格这三个基本性能指标都有一定的要求。存储容量应确保各种应用的需要，存储器速度应尽量与CPU的速度相匹配并支持I/O操作，存储器的价格应比较合理。但是存储器的速度越快，则每位的价格就越高；存储器的容量越大，则存储器的速度就越慢。按照目前的技术水平，仅仅采用一种技术组成单一的存储器是不可能同时满足这些要求的。因此让少量的昂贵存储器辅以大量较便宜的存储器，构成多级存储器体系，才能较好地解决存储器大容量、高速度和低成本这三者间的矛盾。

 

正文

CPU需要快速轻松地存取大量数据才能实现最优性能。如果CPU无法获得所需要的数据，则只能停下来等待这些数据，访存操作约占CPU时间的70%，运行速度为每秒数十亿赫兹的现代CPU可以处理大量的数据，然而，能够匹配每秒数十亿赫兹的CPU的存储器非常昂贵——而这些大量昂贵存储器的费用远非人们可以负担。半导体存储器速度快，但价格高，容量不宜做得很大，因此仅用作与CPU频繁交流信息的内存储器。磁盘存储器价格较便宜，可以把容量做得很大，但存取速度较慢，因此用作存取次数较少，且需存放大量程序、原始数据和运行结果的外存储器。计算机在执行某项任务时，仅将与此有关的程序和原始数据从磁盘上调入容量较小的内存，通过CPU与内存进行高速的数据处理，然后将最终结果通过内存再写入磁盘。这样的配置价格适中，综合存取速度则较快。

CPU寄存器位于CPU执行单元中，很多运算可直接在CPU寄存器中进行，减少了CPU与主存的数据交换，很好地解决了速度匹配的问题。寄存器的工作方式很简单，只有找到相关的位、读取这些位这样的两步操作；并且寄存器设在CPU内部，因而寄存器是访问速度最快的存储器，访问时间只需几纳秒。CPU寄存器数量有限，通常只有几个到几十个，并且寄存器的位数远小于内存的位数，这意味着高性能、高成本、高耗电的设计可以用在寄存器上，而不能用在内存上。因此CPU寄存器的性能、集成度和价格都很高。

高速缓冲存储器用来改善主存储器与中央处理器的速度匹配问题。它采用速度很快、价格更高的半导体静态存储器，甚至与微处理器做在一起，存放当前使用最频繁的指令和数据。当CPU从内存中读取指令与数据时，将同时访问高速缓存与主存。如果所需内容在高速缓存中，就能立即获取；如没有，再从主存中读取。高速缓存中的内容是根据实际情况及时更换的。这样，通过增加少量成本即可获得很高的速度。所以有效地利用Cache可以大大提高计算机的整体性能。设想有两台计算机，配有相同的内存和硬盘，一台有32KB的Cache，另一台没有Cache，虽然多出来32KB的Cache与内存、硬盘的容量相比微不足道，但由于局部性原理，有Cache的计算机明显会快很多。高速存储器即使容量只能做得很小也能显著提升计算机的性能，这也是存储器体系的意义所在。

内存作为CPU外的芯片，与CPU通过地址和数据总线相连。内存暂时存放CPU中的运算数据以及与硬盘等外部存储器交换的数据，是与CPU进行沟通的桥梁。计算机中所有程序的运行都在内存中进行，因此内存的性能对计算机的影响非常大。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也就决定了计算机的稳定运行。但是内存的工作方式复杂很多：首先要找到数据的指针，将指针送往MMU，由MMU将虚拟的内存地址翻译成实际的物理地址，并将物理地址送往内存控制器，由内存控制器找出该地址在哪一根内存插槽上，再确定数据在哪一个内存块上，才能从该块读取数据。数据要先送回内存控制器，再送回CPU，然后开始使用。内存的工作流程比寄存器多出许多步，每一步都会产生延迟，累积起来就使得内存比寄存器慢数十倍。

但是，以上几层仅解决了速度匹配问题，存储器的容量仍受制约。因此，在存储器体系中就需要辅助存储器，从而弥补主存容量不足的问题。硬盘等辅助存储器位于设备总线上，并不直接和CPU相连，而是由驱动程序操作设备总线控制器去访问。寄存器、Cache和内存中的数据掉电丢失，因此它们被称为易失性存储器；与之相对的，硬盘是一种非易失性存储器，它由磁性介质和磁头组成，访问硬盘时存在机械运动，磁头要移动，磁性介质要旋转，机械运动的速度很难提高到电子的速度，所以访问速度很受限制，典型访问时间是几毫秒，是寄存器的数百倍。但使用磁盘作为外存，不仅价格便宜，可以把存储容量做得很大，而且在断电时它所存放的信息也不丢失，可以长久保存，且复制、携带都很方便。

 

总结

现代的信息处理对存储系统的要求很高，存储器体系的好坏影响到整机效率，因此存储体系的性能在计算机中的地位日趋重要。“CPU寄存器-高速缓冲存储器-主存储器-辅助存储器”这样的多级存储结构构成的存储体系是一个整体。从CPU看来，这个整体的速度接近于Cache和寄存器的操作速度、容量是辅存的容量，每位价格接近于辅存的位价格，从而较好地解决了存储器中速度、容量、价格三者之间的矛盾，既满足了计算机系统的应用需要，又得到了较高的性能价格比，意义重大而深远。

 

参考资料

[1] 屠立德,王丹,金雪云.《操作系统基础》.清华大学出版社，2014.01

[2] Behrouz A. Forouzan,Firouz Mosharraf.《计算机科学导论》.机械工业出版社,2009.01

[3] 唐朔飞,《计算机组成原理(第2版)》.高等教育出版社,2008.01

[4] 闫莉,牛箴.计算机存储体系分析.哈尔滨工程高等专科学校学报,第11卷第1期,2000.06

[5] Mike Ash.Why Registers Are Fast and RAM Is Slow.2013.10