计算机结构

计算机可分为两种结构

冯诺依曼结构
哈佛结构

冯诺依曼结构提出计算机由运算器、控制器、存储器、输入设备、输出设备5个部分组成。

冯诺依曼结构特点是指令存储和数据存储合并在一起的存储结构，指令和数据统一编址，使用同一条总线传输，CPU读取指令和数据的操作是互斥的，同一时间只能做一件事，只能分时复用，无法并行，速度慢，CPU吞吐量低。

哈佛结构特点是指令存储和数据存储分开的存储结构，指令和数据独立独立编址，使用两条独立的总线传输，CPU读取指令和数据操作可以并行，速度快，CPU吞吐量高。

因为cpu速度快，而总线速度慢。冯诺依曼结构中，数据存储器和指令存储器使用同一总线，总线繁忙，cpu需要停下来等待总线读取数据。在哈佛结构中，数据存储器和指令存储器使用不同总线，减少了cpu停止工作等待数据读取的时间，因此提升了效率。

冯诺依曼结构由于指令和数据共用总线，速度慢、效率低、吞吐量低，但因为指令存储区域和数据存储区域大小可以动态调整，存储器利用率高，适用场景更通用，所以也便宜。

哈佛结构由于指令和数据分开存储，速度快、效率高、吞吐量大，但不能灵活调整存储区，适用比较做单一的功能，针对不同的功能要做单独的设计，成本也提高了。

冯诺依曼瓶颈

指令和数据存储在一起，导致指令读取和数据处理不能同时进行，而CPU运算速度远远超过主存储器读写的速度，CPU就会浪费时间等待主存数据读写，CPU吞吐量低。

解决瓶颈途径之一：

CPU访问主存数据具有时间局部性和空间局部性特点，在CPU和主存储器之间增加缓存，缓存的命中率很高，大大减少访问主存的次数。

同时CPU缓存采用哈佛结构，指令和数据分开存储，以提高存储量。

数据访问的时间局部性：如果一项信息最近被访问，那么近期很可能被再次访问。产生这个效果的典型原因是代码存在大量循环操作。

数据访问的空间局部性：将来马上要用到的信息，很可能与正在使用的信息，在空间存储位置上是临近的

所以当访问主存中某一个数据的时候，把这个数据相邻的数据都放入缓存中，可以大大减少CPU访问主存消耗的时间。

CPU缓存和内存为什么要分块？

CPU访问主存数据具有时间和空间局部性的特点。

时间局部性：如果一个数据被访问了，那么近期很可能被再次访问。产生这个效果的典型原因是代码存在大量循环操作。

空间局部性：访问内存上的一个数据，这个数据邻近位置的数据，最近也很大可能会被访问

所以应该把该数据邻近的位置的数据都一起读入缓存中，这样可以减少CPU访问主存的次数，CPU直接访问缓存的速度是很快的，这样CPU的吞吐量就提高了。

虚拟内存机制，也是建立了主存和外存之间的缓存关系，也是利用数据访问的局部性原理，把暂时不用的数据放到访问速度更慢的外存，需要频繁使用的数据按页交换到访问速度更快的主存中。这样内存中可以运行更多的进程。

缓存行

为了便于CPU缓存和主存交换数据，CPU缓存和主存都被划分位长度相等的块，缓存块又称为缓存行，大小为2的次方，CPU缓存从主存读入数据一次读一整块，向主存更新数据，也是一次写入一整块。

伪共享

多个CPU同时读写主存上某个连续区域的不同变量时，会各自把该该主存块拷贝一份放入自己的CPU缓存中，多个线程在访问缓存行内的不同变量时，由缓存一致性协议可知该缓存行会失效，多个CPU之间互相等待对方先把缓存行写入主存，自己再从主存读入最新的数据块，表现为缓存频繁未命中，CPU演变为直接与主存交互，CPU访问主存速度很慢，CPU吞吐量因此降低。

伪共享的解决：字节填充

保证不同的CPU处理的数据位于不同的缓存行中，就不会引发缓存行的频繁失效。

java里定义类的成员变量时，可以倾向于把不变的遍历放在一起（一组位置），易变的变量放在一起，使它们尽量不在同一个缓存行，这样每次对象的易变变量变化时，不会引起不变的属性所在缓存行失效，从而提高缓存命中率，避免频繁从主存读取数据，提高CPU吞吐量。

Jdk6中可以通过添加填充变量进行字节填充来解决伪共享，示例如下：

public class PaddingObject{
	public volatile long value = 0L;  // 实际数据
	public long p1, p2, p3, p4, p5, p6; // 填充
}

想象PaddingObject里本来只有一个value属性，现在有多个线程需要读写一个PaddingObject数组（修改数组每一项里的value），由于数组的存储空间在内存中是连续的，根据CPU访问数据的空间局部性特点，CPU在访问数组某个元素的时候，会把该元素所在的内存块整个拷贝到CPU缓存中，这个内存块包含了数组中一些相邻的元素，多个线程同时修改数组中相邻的一些元素时，这个缓存行会频繁失效，CPU缓存命中率低，如果数组的每一个元素位于不同的内存块，也就可以位于不同的缓存行，多线程就不会竞争同一个缓存行

Jdk7中有的版本用上述方式无效，添加的无用变量会被优化去除，需要使用继承的方式组织优化，示例如下：

abstract class AbstractPaddingObject{
    protected long p1, p2, p3, p4, p5, p6;// 填充
}

public class PaddingObject extends AbstractPaddingObject{
    public volatile long value = 0L;    // 实际数据
}

Jdk8开始提供了@sun.misc.Contended 注解进行字节填充，不用再手动声明无用的变量了，同时要开启 JVM 参数：-XX:-RestrictContended=false

字节填充会增大目标对象的体积，是用空间换时间。

伪共享应用场景

数组优于链表

从伪共享的角度，数据和链表的区别，不仅是结构上的区别，在缓存命中率上是完全不一样的，因为数组的存储空间连续，缓存命中率更高，链表的缓存命中率低，访问速度慢。

快速排序优于堆排序

堆排序访问数据时，也不是访问连续内存空间的数据，所以堆排序和快速排序虽然都有相近的时间复杂度，但是常用的还是快速排序

二维数组横向遍历优于竖向遍历

横向遍历二维数组，比竖向遍历缓存命中率要高，因为数组在内存中的存储是每行每行的连续存储，先按行遍历再按列遍历，会访问内存空间连续的数据，先按列遍历再按行遍历访问的不是内存存储空间连续的数据，数据不在同一块，缓存的命中率低

二维数组维数短的写在外层更优

二维数组，维数短的写在外层，缓存命中率更高，因为会减少跨缓存块访问数据，集中在一个缓存块上访问数据，如果长的一维写在外层，访问二维数组元素时，访问数据的内存地址跨度可能超过一个内存块长度，就要频繁的交换CPU缓存，缓存命中率低

Ricky.L的随笔

Java并发-伪共享