参考 Lockfree Algorithms，Is Parallel Programming Hard, And, If So, What Can You Do About It?（中文版名称《深入理解并行编程》）。

最近在看《实战 Java 高并发程序设计》，遇到一些问题，所以简单记录一下。上面两个参考资料都非常不错，由于时间有限，并没有全部看完，有些地方也不能完全看懂。第二个参考资料偏 C++，如果要看 Java 相关的书，或许可以看看《The Art of Multiprocessor Programming》。

阻塞算法（Blocking Algorithms）：被阻塞/中断/终止的线程可能会无限期的阻止整个系统向前推进。使用锁的算法都是阻塞算法，因为当持有锁的线程被阻塞/中断/终止时，其他线程无法向前推进。以及存在死锁问题。

非阻塞算法：被阻塞/中断/终止的线程不会阻止当前线程向前推进，包括无障碍（Obstruction-freedom）、无锁（Lock-freedom）和无等待（Wait-freedom）。无障碍：线程只有在没有遇到其他线程竞争时，才能向前推进，也就是说存在活锁。无锁：必然有一个线程可以向前推进。无等待：所有线程都可以向前推进。

概念比较抽象，可以想下经典的例子，对于无锁来说典型的就是 CAS + 循环。那么为什么说这样是无锁的？对于多个并行执行的线程，必然会有一个线程 CAS 成功（当然其他线程都会 CAS 失败，并且会存在饥饿现象，即某个线程可能会一直自旋），所以说这样是无锁的。

常见的误区是认为，无锁算法一定比基于互斥锁的算法更快。实际上，以上术语只是关于系统向前推进的保证，和性能无关。参考资料中有一句话，我不太理解，但还是先放这里：

So blocking is at least as fast as lockfree, while it can be faster (when it happened so that the fastest known algorithm is at least partially blocking).

这也是《实战 Java 高并发程序设计》中犯的错误，书中提到以下代码使用 AtomicInteger 比锁有更好的性能。给出的例子是，使用单个 AtomicInteger 变量作为多个线程共享的计数器。简单的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class AtomicIntegerDemo {
    private static final AtomicInteger i = new AtomicInteger();

    public static class AddThread implements Runnable {
        public void run() {
            for (int k = 0; k < 10000000; k++) {
                i.incrementAndGet();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] ts = new Thread[10];
        for (int k = 0; k < 10; k++) {
            ts[k] = new Thread(new AddThread());
        }
        long s = System.nanoTime();
        for (int k = 0; k < 10; k++) {
            ts[k].start();
        }
        for (int k = 0; k < 10; k++) {
            ts[k].join();
        }
        long e = System.nanoTime();
        System.out.println((e - s) / 1000000.);
    }
}

在我的机器上测试，以上程序执行时间在 1900 ms 左右。如果使用锁呢？以下程序执行时间只有十几毫秒，性能相差 100 倍。为什么无锁反而更慢呢？因为使用 AtomicInteger 会在循环中多次执行 CAS 操作，而使用锁只会执行很少的加锁/解锁操作。并且，CAS 竞争单个变量，在多处理器的情况下，会频繁地使缓存失效（由于缓存一致性），所以在多处理器上执行反而会更慢，毫无扩展性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

public class AtomicIntegerDemo {
    private static int i = 0;

    public static class AddThread implements Runnable {
        public void run() {
            synchronized (AtomicIntegerDemo.class) {
                for (int k = 0; k < 10000000; k++) {
                    i++;
                }
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Thread[] ts = new Thread[10];
        for (int k = 0; k < 10; k++) {
            ts[k] = new Thread(new AddThread());
        }
        long s = System.nanoTime();
        for (int k = 0; k < 10; k++) {
            ts[k].start();
        }
        for (int k = 0; k < 10; k++) {
            ts[k].join();
        }
        long e = System.nanoTime();
        System.out.println((e - s) / 1000000.);
    }
}

我们使用 start /affinity 1 java geym.conc.ch4.atomic.AtomicIntegerDemo 命令设置程序的 CPU 亲和性，测试 AtomicInteger 代码在单核上的耗时，得到大约 500 ms 的输出，毕竟使用的是同一个 CPU 缓存，性能更高在意料之中。那么，如果设置使用锁的代码亲和单个 CPU，得到的结果依然是十几毫秒，毕竟加锁就是严格串行的，无法利用多核 CPU 的资源，即使在单核上执行也不会影响多少性能。

那么，如果要使用无锁算法，更好的做法是什么？使用 LongAdder，时间大概在 200 多毫秒，因为该类会将累加操作拆分到多个变量中，然后合并得到累加结果，所以比 AtomicInteger 更快。将单个变量拆分为数组时，需要注意伪共享（False sharing）问题，数组元素类型在源代码中声明为如下形式：

1

@jdk.internal.vm.annotation.Contended static final class Cell

使用 @Contended 注解，JVM 会在字段周围进行填充，从而使数组元素位于不同的缓存行中。可以看看这篇文章，对使用/不使用 @Contended 的程序做了基准测试，并且使用 Linux 的 perf 命令进行性能监控，查看两者缓存命中次数的差别，还是非常不错的。

参考 What Volatile Means in Java，Memory Models，Consistency model。另外，stack overflow 的讨论或许有用。

Java 中的 volatile 可以保证可见性、有序性。可见性：线程 A 写入 volatile 变量，线程 B 读取该 volatile 变量可以读到最新值，并且在线程 A 写入 volatile 变量之前对 A 可见的变量值，在线程 B 读取该 volatile 变量之后对 B 也可见。有序性：禁止（编译器/CPU）对 volatile 变量相关的指令进行重排优化。虽然 Java 并发编程实战中提到 volatile 不能保证原子性，但是对 long/double 类型的 volatile 变量的简单赋值操作是原子的，我所说的简单赋值是指不依赖变量当前值的赋值操作。

问题

在《深入理解 Java 虚拟机》第 12 章中有提到 volatile 相关的汇编代码，简单的示例如下。书中提到 lock addl 相当于一个内存屏障，阻止跨内存屏障的指令重排，同时还会将当前处理器的缓存写入内存，以及使其他处理器的缓存失效，从而禁止指令重排。

1
2
3
4
5
6
7

private static boolean a;
private volatile static boolean b;

public static void foo() {
    a = true;
    b = true;
}

1
2
3
4
5

0x000002271ed4378c: movabs $0x711dec880,%r10 ; {oop(a 'java/lang/Class'{0x0000000711dec880} = 'Test')}
0x000002271ed43796: movb $0x1,0x70(%r10)
0x000002271ed4379b: movb $0x1,0x71(%r10)
0x000002271ed437a0: lock addl $0x0,-0x40(%rsp) ;*putstatic b {reexecute=0 rethrow=0 return_oop=0}
; - Test::foo@5 (line 8)

最初，我有个疑问，就是赋值语句之后的内存屏障无法禁止屏障之前的指令重排，例如此处的两个赋值语句 a=true 和 b=true 是否可能重排。询问 Jeremy（JSR-133 的作者之一）之后，他告诉我：

It is possible for processors to do that in general, but x86 doesn’t, so you don’t need a barrier there. Search for “total store order” if you’re curious.

然后，我查找和 TSO 相关的内容时，又一次找到 Russ Cox 的博客，以下内容部分来自该博客。

概念

顺序一致性（Sequential Consistency）：单个处理器按照程序顺序执行（不重排指令），多个处理器按照某种顺序交错执行，这样的多处理器就是顺序一致的。

大多数指令集架构不提供顺序一致的内存模型，因为更强的一致性通常意味着更少的优化（更低的性能）。x86 使用 Total Store Order（TSO）内存模型：所有处理器都连接到单个共享内存，但是每个处理器有一个本地的写入队列，写入操作排队写入共享内存，读取操作会优先读取本地写入队列中的值（如果有的话）。ARM/POWER 的内存模型更加宽松：每个处理器从自己的内存完整副本中读取和写入，读取可以延迟到写入之后，并且每个写入都独立地传播到其他处理器，在写入传播时允许重新排序。

测试

Litmus Test（石蕊测试）：初始时 x=0,y=0（共享变量），rn 表示私有存储（例如，寄存器或者局部变量），不考虑编译器重排指令。

以下程序是否可以看到 r1=1,r2=0？顺序一致性和 x86 中不可以，ARM/POWER 中可以。

1
2
3
4
5
6

// Thread1
x = 1
y = 1
// Thread2
r1 = y
r2 = x

以下程序是否可以看到 r1=0,r2=0？顺序一致性中不可以，x86 和 ARM/POWER 中可以。

1
2
3
4
5
6

// Thread1
x = 1
r1 = y
// Thread2
y = 1
r2 = x

其他

区分 consistency 和 coherency：consistency 表示多个处理器对所有内存位置的操作的总顺序达成一致，coherency 表示多个处理器对相同内存位置的操作的总顺序达成一致。

JMM 为程序中所有操作定义了一个偏序关系，称为 Happens-Before。操作 A Happens-Before 操作 B 的含义是：如果操作 A 先于操作 B 发生，那么执行操作 B 的线程能够看到操作 A 的结果。如果两个操作没有 Happens-Before 关系，那么 JVM/CPU 可以对它们任意地重新排序。

参考 Reflections on Trusting Trust，Running the “Reflections on Trusting Trust” Compiler。

The moral is obvious. You can’t trust code that you did not totally create yourself. (Especially code from companies that employ people like me.) No amount of source-level verification or scrutiny will protect you from using untrusted code.

步骤一

如何编写一个自我复制程序（Quine）？使用 Java 编写的代码如下，还是有点难的。最开始想直接打印，但是打印语句需要包含完整的程序，而完整的程序又包含打印语句，是一个循环依赖的过程。要把循环解开，就只能在字符串中包含基本的行，经过特殊处理得到正确的输出，最简单的方式是使用占位符。似乎不能使用转义字符，因为反斜杠在字符串中也需要转义，所以根本没办法打印出相同的行。更短的示例可以参考 Quine Programs。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = """
public class Main {
    public static void main(String[] args) {
        char n = 10;
        String t = new String(new char[]{'"', '"', '"'});
        String s = %s;
        System.out.printf(s, t + n + s + t);
    }
}
""";
        System.out.printf(s, t + n + s + t);
    }
}

步骤二

如何构建一个自编译的编译器（即由要编译的语言编写的编译器），是一个先有鸡还是先有蛋的问题，解决方案是引导（Bootstrapping）。简单来说，首先使用机器支持的语言编写编译器 A 的源代码，编译器 A 可以编译目标语言的子集。然后使用目标语言的子集编写编译器 B 的源代码，经过编译器 A 编译得到编译器 B 的二进制文件。之后就可以不断重复，得到支持完整目标语言的编译器。

1
2

if (c == 'v') return 11; // 旧编译器可以识别
if (c == 'v') return '\v'; // 新编译器才能识别

论文提到的例子是，在目标语言中添加 \v 符号，表示垂直制表符。由于旧编译器不识别该符号，所以使用垂直制表符的 ASCII 码 11 扩展旧编译器的源代码，旧编译器编译扩展后的源代码得到新编译器，新编译器就能够识别 \v 符号。

步骤三

修改编译器，以匹配指定模式，如果匹配则错误地编译源代码，这是特洛伊木马（Trojan horse）。可以在编译器中插入指定的匹配模式（后门，backdoor），使其匹配 login 命令的源代码。如果用户使用该编译器编译 login 命令，则命令会被错误编译，从而可以使用指定的密码登录系统的任意用户。

最关键的是，如果再添加一个针对编译器自身的匹配模式，在识别到当前正在编译编译器时，将特洛伊木马插入到新编译器中，则可以实现类似步骤二中的“学习”过程。也就是说，即使编译器 B 的源代码是正确的，使用包含以上两个匹配模式的编译器 A 编译，得到的编译器 B 的二进制文件依然包含两个特洛伊木马。最终，编译器 B 仍会错误地编译 login 命令，而编译器 B 的源代码却是正确的。

论文提到，将特洛伊木马插入到新编译器中，使用的是步骤一的自我复制程序。我看半天才理解这句话，可以这么想，特洛伊木马需要获取自身的代码，然后插入到新编译器的特定位置，类似自我复制需要输出自身的代码。