The performance of multiprocessor programs is highly dependent on synergy with the underlying hardware.

术语及概念

• CPU Cycle: 一般翻译为CPU时钟周期。指处理器获取并执行一个指令所耗费的时间。
  几种典型操作所占用的CPU时间片：
  a. 访问CPU中的L1 Cache，1 ~ 2个cycle；
  b. 访问L2 Cache，数十个cycle (更先进的L2，2017年，可以做到在十个cycle内完成访问)；
  c. 为了防止指令重排序而加入的内存屏障，十几个cycle；
  d. 访问主内存中的数据，一百个左右cycle。
  e. page fault, 访问主内存出错，数百万个cycle。
  f. preemption, 正在处理器中执行的线程被抢占而搁置或者移出，数亿个cycle。
• Context Switch (Preemption): 指一个处理器在运行一个线程一段时间后将线程搁置在一旁，转而去执行另一个线程。处理器这一个动作也被称为 deschedule 。
  被搁置的线程可能依旧停留在该处理器中但是暂停执行，也可能会被切出当前处理器，然后由另一个处理器继续执行。
• Interconnect: 处理器同处理器之间，以及处理器同主内存之间的通信过程。
• Main Memory: 主内存。主内存的结构是一组以 word （存储字）组成的数组，数组的索引也被称为 address （内存地址）。根据硬件平台的不同，一个word以及一个address可以是 32bit 或者 64bit。
• Cache Lines（Cache Blocks）: 在Cache中一组相邻的存储字。
• Cache Hit & Cache Miss: 当处理器想要从主内存的指定address读取word时，处理器会先尝试从速度更快的Cache中读取，如果在Cache中找到了想要读取的word，会被称为 Cache Hit；如果没有找到，则会被称为 Cache Miss。由此，可以引申出另外一个概念，既是 ‘处理器在缓存中找到想要读取word的请求次数占处理器所有尝试读取word的请求次数的比例’ ，这一比例也被称之为 Cache Hit Ratio（Hit Rate）。
• Replacement Policy: 当所有 Cache Lines 的空间都被占满，同时又需要继续缓存新的 word 进Cache时，很自然的就需要从Cache中清空一个 Cache Lines 。被清除的Cache Lines中的数据如果是被修改过的，则会将Cache Lines中的数据写回到主内存中。
  决定如何清空已经填满的 Cache Lines 的决策过程就被称为 Replacement Policy。
• Spinning: 一个处理器一直等待另一个处理器对某个存储（可能是好几个word）的修改，并不断访问查看该存储值是否被修改，该处理器的这一过程被称为 Processor Spinning。（处理器一直读取自己Cache中的值称为Local Spinning）
• Memory Barrier：内存屏障，内存屏障指令可以要求处理器核心在运行到barrier时，必须确保barrier之前的写入（write）全部生效，也就是保证指令不会被处理器乱序执行。

Interconnect

架构

Interconnect 有着多种设计架构，其中有两种基础的设计架构被广泛使用。SMP(symmetric multiprocessing) 和 NUMA(nonuniform memory access)。

SMP

在SMP架构下，处理器和主内存都部署在同一根总线（bus）上，相互之间通过广播进行通信。无论是处理器还是主内存，都拥有自己的总线控制器（bus controller）以进行消息广播的发送和接收。
SMP的优势：由于SMP的通信架构易于设计、制造、安装（说白了就是硬件成本低，IC安装使用起来也简单），是当今使用最为广泛的Interconnect通信架构。
SMP的劣势：由于SMP的各个处理器和主内存都在同一根总线上进行通信，Interconnect通信速率和吞吐量必然会受到总线的制约。总线的制约使得SMP架构很难扩展到同时支持较多数量的处理器。

NUMA

在NUMA架构下，整个主内存会被分成多个部分，每一部分称为 Local Memory。每一个 Local Memory 会同一个到多个处理器组成一个 node，每一个node内部的通信架构称为 Local Area Network。每一个处理器除了可以访问 自己node 中的Local Memory，还可以访问 其他node 中的Local Memory（图中的 Remote memory access）。
NUMA的优势：处理器访问自己node中的Local Memory时可以获得更快的通信速度。
NUMA的劣势：由于除了node内部的通信总线以外在跨node通信时还需要更多的通信线路支持，因此NUMA实现起来更加复杂，同时也需要更加精密设计的通信协议，这就带来了更高昂的硬件成本，在软件实现通信协议时要求也更高。

Cache

Cache Lines

抛开Cache访问使用的是更简单快速的硬件基础设施不谈，能够让Cache访问更高效的一部分原因是现代程序在访问主内存中的数据时的行为模式：
1. 当处理器访问了主内存中一个数据后，极可能在随后几条指令中再次访问该数据。
2. 在处理器处理一个代码片段时，除了访问主内存中的某个数据以外，极可能会在随后几条指令中再次访问该address附近其他存储address（简单来说就是如果以一个较短的CPU指令片段来看，对内存的访问会是成块的而不是孤立的）。

Replacement Policy

根据可以清除掉的 Cache Lines不同，可以将policy分成以下几种：

• fully associative: 可以自由选择所有Cache Lines中任意一个或者任意几个进行清除。
• direct mapped: 只能选择Cache Lines中的一个进行清除。
• k-way set associative: 从一个拥有k个Cache Lines的集合中清除任意数量的Cache Lines。

Coherence

有一个广为人知的术语名称：缓存一致性。

背景

对于主内存中的一份数据（Cache Lines），有可能被多个处理器同时使用，则在多个处理器中会各自缓存这一份数据对应的缓存副本。当这些处理器都仅仅是读取而不修改这些副本数据时，工作良好不会产生任何问题；但是当其中一个处理器对副本数据进行修改时，会导致其他处理器Cache中的缓存副本变为无效状态（invalidated），对于处于无效状态的缓存数据，处理器被要求在读取时必须重新从主内存中读取。
解决处于invalidated缓存数据的问题也被成为 Cache Coherence(缓存一致性)。为了解决这一问题，开发者们设计了多种缓存一致性协议，其中最著名的是 MESI（Modified-Exclusive-Shared-Invalid）。

MESI

MESI的四个字母大写既涵盖了该协议最重要的部分——缓存状态，缓存会处于四种缓存状态中的一个，在不同的状态下缓存会被要求进行特定的动作，从而形成一个简单、稳定和有效的状态机。
对四种状态的定义如下：

• Modified: 在某个缓存中的某个Cache Lines已经被修改；这个Cache Lines中的修改被要求最终必须写回到主内存；Cache Lines对应的 memory words 没有被其他处理器缓存。
• Exclusive: 在某个缓存中的某个Cache Lines没有被修改过；Cache Lines对应的 memory words 没有被其他处理器缓存。
• Shared: 在某个缓存中的某个Cache Lines没有被修改过；但是Cache Lines对应的 memory words 已经被其他处理器缓存下来。
• Invalid: 该Cache Lines中的数据是无效的。

状态跳转图：

同一个Cache Lines的副本在另外一个处理器被修改后便处于无效状态，这一限制引申出另外一个著名的问题——False Sharing。

False Sharing

在两个（甚至更多）处理器的缓存中，同时缓存了同一个Cache Lines。在处理器看来，这些缓存中的数据都是独立的，不相关的，可以任意修改自己缓存的数据。但是由于缓存一致性协议的存在，当一个处理器修改了Cache Lines中的一个存储字（Cache Lines中有多个存储字）时会导致其他处理器中的Cache Lines变为无效状态，必须重新读取（MESI协议会发送一个请求给modified数据的处理器，处理器会返回最新的数据并发送最新数据给主内存）。如果缓存中的值被频繁修改，那么就跟每次都从主内存中读取无异，缓存就没有意义了。
False Sharing产生的频率?
如果在多个线程中共享同一个字节数组会比多个线程中共享同一个双精度整数有着更高的概率出现False Sharing。
如何尽量避免False Sharing?

• 当一个对象或者字段有可能被多线程访问时，应该尽量的使其对齐和扩充（aligned & padded），让他们能够布局在不同的Cache Lines中。
• 让只读的数据尽可能的同频繁写入的数据分离。以List为例，应该尽量保证每一个Value元素都能够填充满一个Cache Lines，这样能够确保如果这个List会被频繁写入，则频繁写入的操作不会降低List遍历查询的速度和效率。
• 共享的对象尽量使用TLS（Thread-Local Storage）。比起共享在主内存中的同一个对象，访问TLS中的对象可以有着更低的Interconnect流量。
• 如果一些数据会被经常修改，同时又被一把锁保护着。那么应该尽量使锁和数据处于不同的Cache Lines中。这样当其他线程尝试获取锁时不会影响已经获得锁的处理器访问这些数据。（在同一个Cache Lines中会因为数据被频繁修改导致其他处理器中的Cache Lines失效而认为‘没有其他处理器获取到这把锁，我可以去获取’）
• 如果一些必须加锁才能够访问的数据很少会被 竞争访问，则应该尽量的将锁和数据放在同一个Cache Lines中，这样处理器在获取锁的同时就能一起将数据加载进自己的Cache中。

Spinning

在过去，Cache被有效使用之前，SMP、NUMA这些架构会因为Spinning出现远不如预期的性能表现。因为每次读取一个存储字，都必须消耗一定的Interconnect流量。但是在现代，有着自己Cache的处理器可以极大地降低Spinning带来的流量消耗和性能损耗。

多核多线程架构

众所周知，现代的CPU芯片基本都是多核心、多线程架构的。（如AMD ryzen 7 1700便是8核心16线程）很明显，在这种架构下，同一时间单个处理能够同时执行多个线程，为了能够最大化的利用处理器的时间片，处理器会乱序执行（out-of-order）线程中的代码块。
现代处理器由于都是多核的，因此很多时候context switch几乎不会造成什么浪费（被一个core搁置之后可以迅速被另一个core捡起来继续执行），基本上就是每执行一个指令就context switch一次。
对于现代处理器来说，它会尽最大的可能来避免访问主内存的延迟。只要一个线程要进行主内存的访问，就一定会被从处理器中切出，处理器转而去执行其他的线程。

TASLock vs TTASLock

基于上面的资料，可以轻松地解答经典的为什么TTASLock性能比TASLock性能更好的问题。

TASLock

1
2
3
4
5
6
7

public class TASLock implements Lock {
    ...
    public void lock() {
        while(state.getAndSet(true)) {} //spin
    }
    ...
}

TTASLock

1
2
3
4
5
6
7
8
9
10
11
12

public class TTASLock implements Lock {
    ...
    public void lock() {
        while(true) {
            while(state.get()) {};  //spin
            if (!state.getAndSet(true)) {
                return;
            }
        }
    }
    ...
}

这两者锁都是一样的，都是不断获取锁，获取之后加锁，然后做事情（Spin），区别在于TTAS会先尝试读取一个加锁的属性（state.get()），读取不到了才尝试加锁。
经过观察，大家发现TTASLock有着相对更好的性能表现：

原因

基于上面的资料，可以得出结论：TTASLock有着更好的性能的原因在每一个进行锁状态检查的循环，处理器都是访问Cache（state.get()内容保存在Cache中）而不需要在Interconnect架构上进行通信进而访问主内存，大大减少了访问锁状态需要消耗的CPU时间片。

硬件同步指令

在现代的CPU架构中，基本上都会提供一、两种CPU指令来提供硬件级别的同步。

CAS

compare-and-swap 指令，该种指令由于获得Intel、AMD等厂家的支持，因此也是平时使用得最多同步指令。CAS的工作原理如下：

• CAS指令有三个必要的参数：1.指令作用的内存地址 address；2.该内存地址上存储字的expected value；3.更新值 update value。
• CAS指令将会返回一个boolean来指示指令执行的结果。
• CAS指令执行时会检查address中的存储字的值是否为expected value，如果是，则将存储字的值更新为update value并返回true指示CAS指令执行成功；

CAS指令可用于原子性地更新内存中某个内存地址的值。

然而美中不足的是，CAS有一个广为人知的缺陷 —— ABA问题

ABA问题

CAS指令能够完美工作的前提是当程序检查到address中的值是expected value开始执行CAS指令，到CPU开始执行CAS指令这段时间address中的值并没有改变过。

假设我们现在读取到address的值是a, 然后立即使用CAS指令更新address，我们预期只有在address的值没有变化的情况下才会被更新为update value。然而事实并不一定如此，在读取到address的值为a，到CAS指令执行期间，address的值可能经历了这样一个过程 a -> b -> a，程序上并不能感受到这样一个过程的变化，导致虽然address中的值发生过变化，但是依旧被更新为update value。这可能会导致程序出现一些不可预期的错误。

LL/SC

load-linked 和 store-conditional 指令，这两个指令必须在同一个线程中配对使用。 LL指令 从一个内存address中读取其值a，然后 SC指令 向address中写入一个新的值。如果在LL/SC指令执行期间address的值a没有变化过，则这一次LL/SC指令执行成功，否则执行失败。LL/SC指令很明显可以避免ABA问题。

但是由于LL/SC指令限制了一个线程在指令配对区间内可以做的事情（Context Switch、load/store 内存指令），导致了LL/SC指令难以成为最主流的硬件同步指令方案。