一、影响并行编程的硬件特性

1.1 CPU流水线（Pipelined CPUs）

CPU流水线，是CPU填充接下来将要执行的指令的地方。

现代CPU每个核心都有多条流水线。例如，ARM Cortex-A73架构就是3发射设计。这样就意味着，串行编写的程序代码，在实际执行过程中，往往是乱序执行的。

CPU采用了预测分支技术，可以在程序执行到关键点位置之前，预测一个结果，并将接下来的指令提前填充到流水线中。如果预测成功，程序的执行效率非常高。但是如果预测失败，流水线中的指令就必须替换为正确的指令。这就构成了很大的一笔性能开销。

gcc编译过程中，如果使用了-O2或者-O3选项，都会将实际代码的顺序打乱，以提高实际执行速度。

现代CPU的计算速度发展很快，导致即使是内存IO也成为耗时操作。即使CPU的L1～L3缓存容量越来越大，但对于常见的操作，例如链表遍历，仍然作用有限。

使用锁结构或者其他方案，可以将一组指令绑定成不可分割的操作，也就是原子化。然而，原子化的指令组合内部，也有可能存在流水线冲刷的可能性。如果每条线程都要冲刷流水线，那性能开销就大了。

内存屏障，就是为了防止顺序指令被错误地乱序执行。因此，它的存在绝对会对程序性能造成影响。

在多核CPU系统中，如果一条线程修改了一个数据结构，而另一个线程同时也在修改它，此时会发生缓存不命中。而CPU的控制机制将会保证这两步操作顺序执行，降低性能。

考虑一个八核CPU。

线程A运行在核1上，修改了一个数据结构。CPU的控制机制会将该数据结构标记为脏。当运行在核7上的线程B请求修改同一个数据结构时，发现已经存入的数据被标记为脏：

无论是向本地磁盘，还是向网络请求数据，IO操作都会对程序性能构成很大的影响。

POSIX提供了fork()等API可以创建进程。但是进程过于重量级，而且消息传递比较麻烦。

因此，作为线程库，pthread的使用更为广泛。

pthread的详细教程可以参考man手册和Multithreaded Programming Guide。

pthread库中提供一种mutex锁。这把锁，只能有一个线程同时持有，其他竞争线程只能被阻塞进入休眠状态。

spin锁和mutex锁类似，只能有一个线程同时持有。但是，没有得到锁的线程不会休眠，而是进入轮询状态。

自旋锁适用于锁每次持有时间较短的情况。

对于多读少写的数据结构，pthread提供一种读写锁rwlock。rwlock允许线程并发读取数据，但只能有一个线程修改数据。修改期间，无法读取数据。

也即是说r锁之间不会排斥，但会排斥w锁；而w锁之间是相互排斥的。

自旋锁是Linux内核中的一种锁机制。和读写锁类似，适用于多读少些的数据结构。不同的是，r锁和w锁不会互斥。也就是读写可以同时执行。如果读取动作执行在修改之前，可能会重新读取，取决于是否注册通知事件。而读取动作执行在修改之后的，可以立即拿到正确的数据。

gcc编译器还提供了原子化访问内存的原语。具体可以看文档：6.52 Built-in Functions for Memory Model Aware Atomic Operations

风险指针（Hazardous Pointer）是一种无锁结构（Lock-free）。

它的思想起源于多线程gc机制。每一个线程维护一组风险指针，其中指向的是全局公共变量。gc机制会扫描所有线程的风险指针，如果有某个公共变量不存在于任何一个线程的风险指针中，那就会被回收。

并行算法的一个重要的设计指标就是“可拓展性”（Scalability），也就是尽量保证并发线程和程序性能正相关。

然而，真实情况并非那样美好。如果算法需要频繁地访问公共变量，那么很多线程就会阻塞在锁的获取上。线程越多，被阻塞的就越多，性能就会越差。

解决这个问题，可以从这几个方向考虑：