什么是内存（一）：存储器层次结构

参考教材：http://www.cnblogs.com/yaoxiaowen/p/7805661.html

一 前置知识：

物理内存 Physical memory 是通过物理内存条而获得内存；
虚拟内存，将硬盘的一块区域划分作为内存。

二 冯·诺依曼体系：

冯·诺依曼体系结构有如下特点：

1. 计算机处理的数据和指令一律用二进制表示
2. 指令和数据不加区分混合存储在同一个存储器中；
3. 顺序执行程序的每一条指令；
4. 计算机硬件由运算器、控制器、存储器、输入设备和输出设备五大部分构成

冯·诺依曼体系结构的计算机必须实现的功能：

1. 把需要的程序和数据送至计算机
2. 必须具有长期记忆程序、数据、中间结果及最终运算结果的能力
3. 能够完成各种算数、逻辑运算和数据传送等数据加工处理的能力
4. 能够根据需要控制程序走向，并能根据指令控制机器的各部分协调操作

5. 能够按照要求将处理结果输出给用户

   
   冯诺依曼.png
   

   概括来说，冯诺依曼体系有几个要点：

6. 把程序当成数据来看待，程序和该程序要处理的数据采用相同的处理方式
7. 计算机的数制采用二进制
8. 计算机应该按照程序顺序执行

也就是说，所谓计算机，就是大个的计算器，输入内容运算出结果。

三 存储设备

在冯诺依曼体系中，存储设备是必不可少的。理想中的存储设备，应该：

1. 稳定，断电后不丢数据；
2. 容量大；
3. 读写速度快
4. 价格便宜
5. 体积小

但是完全符合这5点的存储器还没发明出来，所以在目前的计算机体系中才出现了不同的存储器，如内存、硬盘、光盘等。

3.1 硬盘

硬盘就是磁盘，好处是稳定、断电不丢数据、容量大、价格便宜。
CPU 来进行运算的，一秒可以执行十几亿次，相比硬盘速度太快了。所以，CPU 和 硬盘不能直接通信，必须加一个中间层，这就是内存条。这个内存条就是硬件内存。

memory.png

L5（硬盘） 和 L4（内存条） 之间查了几十万倍，L3 和 L0 之间，每级缓存的速度大概差10倍

3.2 RAM / ROM / 总线

首先，他们都属于存储器，存储器分为两类：

1. 易失性（volatile）存储器:包括内存，SRAM / DRAM等，特点是读写速度很快，没电后数据会丢失、价格贵、存储量小。
2. 非易失性（nonvolatile）存储器: 硬盘，速度慢/但是没电后不会丢失数据

• RAM（Random-Access Memory）:随机访问存储器，易失性存储器。也可以分为两类：SRAM（Static Random-Access Memory）静态存储器，+ + DRAM（Dynamic Random-Access Memory）动态存储器，并且SRAM的读写速度比DRAM更快，价格也更便宜。
• 闪存（Flash Memory）：非易失性存储器。如SD卡/SSD
  淘宝上 8G 内存条，598
  256G SSD（固态硬盘，Solid State Drives）,读取速度普遍可以达到400M/s,写入写入速度也可以达到130M/s，300左右
  1T机械硬盘，300左右

像 L0 寄存器，每个寄存器只能存储一个字长的内容，但是CPU读取寄存器耗费的时钟周期为0个，这是最快的速度。

3.3 如何把硬盘 / 内存条 串起来通信？

计算机.png

上图中存在三条主线，系统总线 / 存储器总线（通常叫内存总线） / IO总线。在主板上，那就是一排排的32/64根并行的导线。这些导线用来连接CPU / 内存 / 硬盘以及外围设备。（这32/64位计算机，其实就是指的就是内存总线）

CPU 要通过 I/O 桥（就是主板的南桥/北桥）与外围设备相连，因为CPU的主频太高了，它的时钟周期一秒内几亿次，外围设备的时钟周期比较慢，所以它们不能直接通信。

3.4 不管中间怎么加缓存，数据从硬盘到内存的速度就是那么慢，那么这些缓存的意义是什么？

读盘.png

1. CPU 通过将命令、逻辑块号和目的存储器地址写到与磁盘相关联的存储器映射地址，发起一个碰盘读

   
   step2.png

2. 磁盘控制器读扇区，并执行到主存的DMA传送（把相关程序和数据加载到内存）

   
   step3.png
3. 当DMA传送完成时，磁盘控制器用中断的方式通知CPU

磁盘的速度和内存之间差了几十万倍，并且CPU是以光速进行的，所以这段时间对于CPU来说实在是太长了。
因此，CPU 在第一步发起一个磁盘读的信号后，在第二步和第三步的时候根本不参与，会切换到另外一个线程工作。等到第三步，通过中断，硬盘主动发信号给CPU，通知CPU需要的数据已经加载到内存，CPU可以将线程切换回来，接着执行这个线程的任务。

对于一个进程/应用来说，它都有一个入口。（虽然不一定需要我们直接写 main 函数）入口函数内部就是我们的任务代码，任务代码执行完了这个应用 / 进程也就结束了。

但是有些程序，如一个app，你打开了这个app，不做任何操作。这个界面会一直存在，也不会消失。这是为什么呢？因为这个app进程肯定也有一个main入口，main里面的任务执行完了，就应该结束了。而一个程序的代码/指令数肯定是有限的，但该app在我们不主动退出的情况下，却不会结束。
所以，这个app的入口main，其实是这样的：

int main(){
  boolean flag = true;
  while(flag){
    // 我们执行的代码
  }
}

并且不仅如此，在一个程序的内部，也有大量的for，while等循环语句。那么当我们把这些相关的指令送到了内存，或更高一级的缓存时，那么 CPU 在执行这些指令时，存储速度自然就快很多。

在执行一个程序时，启动阶段比较慢，因为需要从磁盘读取数据（而CPU这个阶段也没浪费闲置，它会线程切换执行其他任务），但是数据被送往内存之后，它执行就会快很多，并且伴随着执行过程，还可能更快，因为这些数据，有可能被一级一级的向上送，从L4，送到L3，L2，L1

四 局部性原理（Principle of locality）

局部性原理对于硬件和软件系统的设计和性能都有着非常重要的影响。对于我们理解存储器的层次结构也必不可少。

程序倾向于引用临近于与其他最近引用过的数据项的数据项。或者最近引用过的数据项本身。这种倾向性，我们称之为局部性原理。它通常有以下两种形式：

• 时间局部性（temporal locality）:被引用过一次的存储器位置的内容在未来会被多次引用
• 空间局部性（spatial locality）: 如果一个存储器位置的内容被引用，那么它附近的位置也有很大概率会被引用。

一般而言，有良好局部性的程序比局部性差的程序运行更快。现代计算机系统的各个层次，从硬件到操作系统、再到应用系统，它们的设计都利用了局部性。

int sum1(int array[N]){
  int i, sum = 0;
  for(i = 0;i<N;i++){
    sum += array[i];
  }
  return sum;
}

在这个程序中，变量sum, i 在每次循环迭代时被引用一次，因此对于sum和i来说，具有较好的时间局部性。
对于变量 array 来说，它是一个 int 类型数组，循环时按顺序访问 array, 因此一个C数组在内存中占用连续的内存空间。因而具有较好的空间局部性。

int sum(int array[M][N]){
  int i, j , sum = 0;
  for(i = 0; i<M;i++){
    for(j=0;j<N;j++){
      sum += array[j][i];
    }
  }
  return sum;
}

这是一个空间局部性很差的程序。假设这个数组是 array[3][4], 因为 C 数组在内存中是按行顺序来存放的。所以sum2 对每个数组元素的访问顺序变成了这样：0,4,8,1,5,9 ... 7,11。所以它的空间局部性很差。

但是幸运的是，一般情况下，软件编程天然就是符合局部性原理的。

假设一个CPU需要读取一个值，int var, 而 var 在 L4 主存上，那么该值会被依次向上送，L4 > L3 > L2, 但是这个传递过程并不只是单纯的只传递 var 四个字节的内容，而是把 var 所在的内存块(block),依次向上传递，为什么要传递 block? 因为根据局部性原理，我们认为，与 var 值相邻的值，未来也会被引用。

存储器的层次结构，数据进行传送时，是以 block（块）为单位传送的。在整个层次结构上，越往上，block越小而已。

五、存储器层次结构中的缓存

存储器归根到底就是一个缓存思想，其实并不复杂：

我们做 app 开发时，对于app活动页面等，都是后台发给我们的url，我们下载后才显示在app上，这时我们总要使用 Glide / Picasso 等图片缓存框架把下载好的图片缓存在手机上。下次打开这个app时，如果这个图片的连接没有变，我们直接加载本地缓存。

cache.png

存储器层次结构中基本的缓存原理：

1. 存储器层次结构的中心思想：

• 位于k层的更快更小的存储设备作为位于 k+1 层的更大更慢的存储设备的缓存；
• 数据总是以块为传送单元（transfer unit）在第K层和第K+1 层之间来回考虑的；
• 任何一对相邻的层次之间传送的块大小是固定的，即每一级缓存块大小是固定的。但是其它的层次对之间可以有不同的块大小。
• 当程序需要第 k + 1层的某个数据对象时，他首先会在当前存储在第k层的一个块中查找。如果找到，这就是命中缓存。如果第k层中没有缓存数据对象，那么就是缓存不命中。当缓存不命中时，第K层的缓存从第K+1层缓存中取出包含d的那个块，如果第k层的缓存已经满了，可能会覆盖现存的一个块。（覆盖策略可见 LRU 算法）

六 volatile 关键字

在 java 和 C 当中，有一个 volatile 关键字（其他语言估计也有），它的作用就是在多线程时保证变量的内存可见性。

上面的金字塔图，是对于一个单核CPU而言的，对于一个四核三级缓存的CPU，它的缓存结构是这样的：

cache4.png

我们可以看到 L3 是四个核所共有的，但是L2 L1 是每个核私有的，如果我有一个变量，这个变量会被两个线程同时读取，这两个线程在两个核上并行执行，因为我们的缓存原理，这个变量可能分别会在两个核的L2 或 L1 缓存，这样读取速度最快，但是该 var 值可能就分别被这两个核分别修改成不同的值，最后将值写到 L3 或 L4 主存，此时就会发生 bug。

所以 volatile 关键字就是预防这种情况，对于被 volatile 修饰的变量，每次CPU 读取时，都至少从 L3 读取，并且 CPU 计算结束后，也立即回写到L３中，这样读写速度虽然慢了一点，但是避免了该值在每个 core 的私有缓存中单独操作而其他核不知道。