计算机存储器系统

存储器是用来存放程序和数据的部件，它是一个记忆装置，也是计算机能够实现“存储程序控制”的基础。在计算机系统中，规模较大的存储器往往分成若干级，称为存储器系统。

传统的存储器系统一般分为高速缓冲存储器(Cache)、主存、辅存三级。采用分级存储体系的主要目的是为了解决存储容量、成本和速度之间的矛盾问题。

1. 主存可由 CPU 直接访问，存取速度快，但容量较小，一般用来存放当前正在执行的程序和数据；
2. 辅存在主机外部，它的存储容量大，价格较低，但存取速度较慢，一般用来存放暂时不参与运行的程序和数据；
3. Cache 介于 CPU 和主存之间，存取速度比主存更快，但容量更小，用来存放当前最急需处理的程序和数据，使访问存储器的速度能与 CPU 的速度相匹配。

在CPU运行时，所访问的数据会趋向于一个较小的局部空间地址内，包括下面两个方面:

1. 时间局部性：如果一个数据项正在被访问，那么在近期它很可能会被再次访问，即在相邻的时间里会访问同一个数据项。
2. 空间局部性：在最近的将来会用到的数据的地址和现在正在访问的数据地址很可能是相近的，即相邻的空间地址会被连续访问。

存储器中数据常用的存取方式有顺序存取、直接存取、随机存取和相联存取四种。

1. 顺序存取：存储器的数据以记录的形式进行组织。对数据的访问必须按特定的线性顺序进行。磁带存储器采用顺序存取的方式。
2. 直接存取：与顺序存取相似，直接存取也使用一个共享的读写装置对所有的数据进行访问。但是，每个数据块都拥有唯一的地址标识，读写装置可以直接移动到目的数据块所在位置进行访问。存取时间也是可变的。磁盘存储器采用直接存取的方式。
3. 随机存取：存储器的每一个可寻址单元都具有自己唯一的地址和读写装置，系统可以在相同的时间内对任意一个存储单元的数据进行访问，而与先前的访问序列无关。主存储器采用随机存取的方式。
4. 相联存取：相联存取也是一种随机存取的形式，但是选择某一单元进行读写是取决于其内容而不是其地址。与普通的随机存取方式一样，每个单元都有自己的读写装置，读写时间也是一个常数。使用相联存取方式，可以对所有的存储单元的特定位进行比较，选择 符合条件的单元进行访问。为了提高地址映射的速度，Cache 采取相联存取的方式。

主存储器

根据工艺和技术不同，主存可分为随机存取存储器(Random Access Memory，RAM)和只读存储器(Read Only Memory，ROM)。

1. RAM 既可以写入也可以读出，但断电后信息无法保存。RAM 又可分为 DRAM(Dynamic RAM，动态 RAM) 和 SRAM(Static RAM，静态 RAM)两种，DRAM 的信息会随时间逐渐消失，因此需要定时对其进行刷新维持信息不丢失；SRAM 在不断电的情况下信息能够一直保持而不会丢失。 DRAM 的密度大于 SRAM 且更加便宜，但 SRAM 速度快，电路简单(不需要刷新电路)， 然而容量小，价格高。
2. ROM 可以看作 RAM 的一种特殊形式，其特点是：存储器的内容只能随机读出而不能写入。这类存储器常用来存放那些不需要改变的信息。即使断电，写入的内容也不会丢失，所以又称为固定存储器。ROM 一般用于存放系统程序 BIOS(Basic Input Output System，基本输入输出系统)。

辅助存储器

硬盘存储器在硬盘中，信息分布呈以下层次：记录面、圆柱面、磁道和扇区，如图所示。

一台硬盘驱动器中有多个磁盘片，每个盘片有正反两个记录面。每个记录面对应一个磁头。磁头一致地沿记录面径向移动，单个磁头不能单独地移动。每个记录面有多个同心圆，每个同心圆是一个磁道，每个同心圆又被划分为多个扇区，数据就被存放在一个个扇区中。一个盘组中，各记录面上相同位置的各磁道构成一个柱面。

当要存入一个较大的文件时，若一条磁道存不完，就需要存放在几条磁道上。这时，应首先将一个文件尽可能地存放在同一柱面中。如果仍存放不完，再存入相邻的柱面内。

读取数据时，磁头首先要寻找到对应的磁道，这个过程称之为寻道，寻道所消耗的时间称为寻道时间，然后等待磁盘进行周期旋转，旋转到指定的扇区，才能读取到对应的数据，因此，会产生寻道时间和等待时间。公式为：

存取时间=寻道时间+等待时间(平均定位时间+转动延迟)

为了更好地读写数据，磁盘会用到以下调度算法：

1. 先来先服务FCFS：根据进程请求访问磁盘的先后顺序进行调度。
2. 最短寻道时间优先SSTF：请求访问的磁道与当前磁道最近的进程优先调度，使得每次的寻道时间最短。会产生“饥饿”现象，即远处进程可能永远无法访问。
3. 扫描算法SCAN：又称“电梯算法”，磁头在磁盘上双向移动，其会选择离磁头当前所在磁道最近的请求访问的磁道，并且与磁头移动方向一致，磁头永远都是从里向外或者从外向里一直移动完才掉头，与电梯类似。
4. 单向扫描调度算法CSCAN：与SCAN不同的是，其只做单向移动，即只能从里向外或者从外向里。

Cache 存储器

Cache 通常采用相联存储器(ContentAddressable Memory，CAM)。CAM 是一种基于数据内容进行访问的存储设备。当对其写入数据时，CAM 能够自动选择一个未用的空单元进行存储；当要读出数据时，不是给出其存储单元的地址，而是直接给出该数据或者该数据的一部分内容，CAM 对所有存储单元中的数据同时进行比较，并标记符合条件的所有数据以供读取。由于比较是同时、并行进行的，所以，这种基于数据内容进行读写的机制，其速度比基于地址进行读写的方式要快很多。

当 CPU 发出访存请求后，存储器地址先被送到 Cache 控制器以确定所需数据是否已在 Cache 中，若命中则直接对 Cache 进行访问。这个过程称为 Cache 的地址映射。在 Cache 的地址映射中，主存和 Cache 将均分成容量相同的块(页)。常见的映射方法有直接映像、全相联映像和组相联映像。

直接映像以随机存取存储器作为 Cache 存储器，硬件电路较简单。在进行映射时，主存地址被分成三个部分，从高到低依次为：区号(7位)、页号(4位)以及页内地址(19位)。

在直接映像方式中，将 Cache 存储器等分成块，主存也等分成块，每个主存页只能复制到某一固定的 Cache 页中，如图所示。直接映像方式的优点是比较容易实现，缺点是不够灵活，有可能使 Cache 的存储空间 得不到充分利用。

全相联映像使用相联存储器组成的 Cache 存储器。存储器同等分块并编号，主存的每一页可以映像到 Cache 的任一页。如果淘汰 Cache 中某一页的内容，则可调入任一主存页的内容，因而较直接映像方式灵活，但地址变换复杂速度较慢。主存地址分为两个部分，分别为地址部分(主存页标记 11 位)和数据部分(页内地址 19 位)。数据部分用于存放数据，而地址部分则存放该数据的存储器地址。

组相联映像(页组映像)介于直接映像和全相联映像之间，主存与 Cache 都分组，主存中一个组内的页数与 Cache 的分组数相同，如图所示。组间采用直接映像，即主存中组号与 Cache 中组号相同的组才能命中，但是组内全相联映像，即组号相同的两个组内的所有块可以任意调换。

当 Cache 已存满数据后，新数据必须替换 Cache 中的某些旧数据。最常用的替换算法有以下几种：

• 随机替换算法：用随机数发生器产生一个要替换的块号，直接替换掉；
• 先进先出(First In and First Out，FIFO)算法：把最先进入 Cache 块的数据替换掉；
• 近期最少使用(Least Recently Used，LRU)算法：把近期最少使用的 Cache 块替换掉；
• 优化替换算法：先执行一次程序，统计 Cache 的替换情况，再下次执行程序时依此替换。