并行

为什么要并行

业务要求，性能

但是进程开销大，一般是多线程。

图像处理、服务端编程 （计算密集型，多核计算机上）

摩尔定律失效，硬件的提升不如软件的优化了

几个重要概念

同步 异步

并发 并行

临界区

阻塞 非阻塞

锁 饥饿 活锁

并行的级别

同步异步

对方法调用而言的。

并发并行

程序的执行：并发（Concurrency）和并行（Parallelism）。单核无区别；多核有区别

临界区

临界区是一种公共（共享）资源，可以被多线程访问。需要被控制，一旦临界区资源被占用，其他线程想要使用这个资源，就必须等待。以防止资源被破坏。

阻塞非阻塞

来形容多线程间的相互影响。

如果一个线程进入临界区，其他想要这个资源的线程就必须等待，导致这些线程被挂起，这就是阻塞。

非阻塞允许多个线程进入临界区。

死锁饥饿活锁

多线程中可能遇到的问题：死锁、饥饿、活锁。

对于阻塞的程序，有可能发生死锁现象。各线程分别占有了一些资源，又需要其他线程持有的资源，导致卡死。

上图，每个小车占有了一条道路，又需要另一条道路，但是另一条道路已经被其他小车占有。

死锁（DeadLock）是静态现象，cpu占用为0. 可以通过线程dump等方式排查。

活锁（LiveLock）是动态现象。

类似电梯遇人问题。两人进出电梯时面对面撞上，同时向一边避让，还是撞上；又同时往另一边靠，还是撞上。。。

A线程拿了资源a，还想要资源b；B线程拿了资源b，还想要资源a；发生了死锁。 然后比如程序有死锁检查机制，A，B线程同时释放了占有的资源。 然后A线程和B线程重新拿取资源，各拿了一个资源，又需要对方的资源；又发生死锁。 又检测到死锁释放资源。。。循环往复。

饥饿

饥饿是指某个线程因为某种原因一直无法获取到所需的资源，导致一直无法执行。比如原子操作CAS竞争一直失败。

并发级别

concurrency并发。按并发的级别分类：

并发分为（阻塞和非阻塞）。

非阻塞进一步分为（无障碍、无锁、无等待）。

阻塞级别

当一个线程进入临界区之后，其他线程必须等待。

无障碍级别

无障碍obstruction-free （最弱非阻塞）

线程自由进入临界区。（先拿系统的快照号）

有竞争时，回滚数据。（操作时发现快照号不是最新，重新获取快照号，重新读取)

无竞争时，有限步骤内完成操作。

比如读坐标(x,y),先读x再读y. 无障碍并发级别，读之前拿一下系统的快照，然后依次读取x和y；如果读取过程中，发现快照号已经改变，重新获取快照号，重新读取x和y。

无锁

无锁Lock-Free

是无障碍的

保证有一个线程可以胜出（保证有一个线程可以顺利的走下去，继而保证整体最终可以完成）

eg:

//可能会有ABA问题？
while(!atomicVar.compareAndSet(localVar, localVar+1)) {
    localVar = atomicVar.get();
}

无等待

无等待Wait-Free

无锁的

要求所有的线程都必须在有限步内完成

必然是无饥饿的。

并行度的计算

两个重要定律：Amdahl定律（阿姆达尔定律）、Gustafson定律（古斯塔夫森定律）

Amdahl定律

Amdahl定律定义了 串行系统改造为并行系统后的加速比的理论上限。

加速比=优化前系统耗时/优化后系统耗时

Gustafson定律

说明处理器个数，串行比例和加速比之间的关系