七周七并发

本文为阅读《七天七并发》的笔记，记录了一些阅读时候的笔记和感受。

模型概述

随着用户数量的增加，需要我们设计出可以容纳更多人使用的并发程序。在实践之中个，有比较常用的几个模型：线程与锁模型、函数式编程、分离标识与状态、actor 模型、通信顺序进程、数据级并行、lambda 架构。每种模型都有其优势与不足，在这里我会整理其各自的使用范围，并配上自己的观点。

线程与锁模型

该模型以 Java 为例进行说明

在我们处理高并发问题的时候，第一个反应就是使用锁模型对并发变量进行控制。由于多并发条件下，非原子操作可能会使得变量赋值操作在执行时插入别的操作，导致非预期行为，如重复赋值等。我们可以通过多数编程语言自带的锁来解决问题，将设计到的变量转变为同步操作。

由于编译器的静态优化的存在，所以有时候代码的执行并不全是顺序执行的，像 JVM 的动态优化也会打乱代码的执行顺序，硬件也会打乱代码的执行顺序。

将操作转变为同步操作解决了非预期行为的出现，但这也导致了效率问题，频繁的阻塞可能会使得程序失去并发的意义。较复杂的同步问题也可能导致死锁。

悲观锁：一个线程获取锁之后，其他的线程全部停止挂起，等待获得锁的线程释放锁

乐观锁：所有的线程竞争获得锁，在竞争的时候不上锁（即认定别人不会更改），但是在修改期间会判断下别人是否更改了数据。乐观锁又分为使用版本号实现和 CAS 算法实现，版本号保证了读取和修改的值一定是相同的；CAS 算法是无锁算法，比较和替换是一个原子操作，缺点是会带来“ABA”问题，即只通过值来判断的话，无法确定是否是修改后的值与以前的值相同。

ABA 问题实例

小明在提款机，提取了 50 元，因为提款机问题，有两个线程，同时把余额从 100 变为 50

线程 1（提款机）：获取当前值 100，期望更新为 50，

线程 2（提款机）：获取当前值 100，期望更新为 50，

线程 1 成功执行，线程 2 某种原因 block 了，这时，某人给小明汇款 50

线程 3（默认）：获取当前值 50，期望更新为 100，

这时候线程 3 成功执行，余额变为 100，

线程 2 从 Block 中恢复，获取到的也是 100，compare 之后，继续更新余额为 50！！！

此时可以看到，实际余额应该为 100（100-50+50），但是实际上变为了 50（100-50+50-50）

问题分析：关键在于线程 1 和线程 2 的操作无法保证是幂等的

全局顺序模型

以哲学家进餐问题为例，我们不再按照获取某个给定的顺序执行，而是使用 hash 顺序执行，这不用维护一个全局的顺序，但是 hash 值有可能会重复。

在加锁的时候，调用某些接口可能会有多个锁同时添加导致死锁的情况发生。所以在持有锁的时候需要避免调用“外星方法”

如何解决死锁

我们没有办法从死锁的状态中脱离，除非关闭 JVM 虚拟机。对于锁，我们可以采用更为高级的锁，如超时锁，在一定时间的等待之后，自动进行退出，这虽然不能完全避免死锁，但是可以避免程序一直停顿在某个状态。这就是我们常说的活锁，为了减小活锁的几率，我们可以随机地设置锁等待的时间。

在处理链表的时候，如果对整个链表上锁将会极大地影响效率，这时候我们就可以选择使用交替锁，只锁住当前节点和下一个节点。

条件变量

在需要等待某项事件发生时，可以使用此种变量来阻塞等待。

1
2
3
4
5
6
7
8


ReentrantLock lock = new ReentrantLock();
Condition condition = lock.newCondition();
lock.lock();
try {
 while (!«条件为真»)  // 如果这里使用的是if，就会造成虚假唤醒
 condition.await();
 «使用共享资源»
} finally { lock.unlock(); }

虚假唤醒(Spurious wakeup)

虚假唤醒指的是在条件判断的时候，使用 if 而不是 while，由于唤醒和获取锁并不是连续的操作，所以直接执行后边的逻辑操作而不是判断条件，所以 while 是必须的。

原子变量

这种变量可以原子性地进行改变，java.util.concurrent.atomic 包中包含了此类方案。

Java 中的volatile 关键字可以使得代码执行顺序不会再改变，但是不能保证操作是原子的，所以尽量使用 atomic 包中的方法。

基于 AQS（AbstractQueuedSynchronizer）的锁

有一个 state 变量，初始值为 0，获得锁，state++，释放锁，state–，锁会记录当前持有的线程。

某个线程 A 拥有锁的时候，其余的线程 B 去尝试请求，会对 state 进行 CAS(0,1)操作，由于 state>0，所以失败几次后就会将线程 B 放入等待队列之中。

如果线程 A 使用完资源，释放锁，这时候 state==0，A 线程会去唤醒等待队列中第一个线程，即刚刚进入等待队列的 B 线程，B 线程被唤醒之后回去检查这个 status 的值，尝试 CAS(0,1)，这时候有线程 C 来请求资源

非公平锁

C 与 B 进行竞争，如果 C 先尝试对这个 status 进行 CAS(0,1)操作，并成功改变了 status 的值，那么线程 B 无法获取锁，再次挂起，最终 C 抢到了锁。（如果 B 先对这个 status 进行 CAS(0,1)操作，则 B 可能先获得锁，C 进入队列进行等待）

公平锁

C 发现有线程在等待队列，直接将自己进入等待队列并挂起,B 获取锁。

线程池

对于每一个任务直接分配一个线程是不合理的，当过多的请求分配过来的时候，虽然创建一个线程的花费很低但数量多了以后就不可以忽略；随着处理数远远低于请求数之后，不停增长的数量会拖垮系统。这时候，池化的概念就可以用于创建线程。

线程池设置经验

CPU 密集型任务：大小接近于可用核数

IO 密集型任务：可以设置的更大一些

生产-消费者模型

需要使用阻塞队列，因为非阻塞队列尽管性能更好，但是由于生产者和消费者的速度不同，会导致队列越来越大。

毒丸（poison pill）是一个特殊的对象，其作用在于让消费者退出无限循环

对于线程，不是开得越多越好，如果多个线程同时使用一个共享资源，那么消费者可能需要更多的时间去等待和竞争锁，造成性能下降。针对这个问题，Java 提供了 ConcurrentHashMap，其使用了锁分段（lock striping）来改善这个问题

锁分段类似分区的概念，系统预分配一些锁，之后将数据分成多个段，使用不同的锁来锁住不同区域的数据，减少对同个锁的竞争

写入时复制

Java 提供了现成的方案 CopyOnWriteArrayList，其不是为原来的副本做深拷贝，而是在其修改的时候，自动使用旧值。

锁的优缺点

优点

正确使用的时候，效率很高，可控制的粒度可以从小到大

缺点

不易 debug，难以测试，很多 bug 需要进行长时间的压测才会暴露

函数式编程

该模型以 Clojure 为例进行说明

在 Java 这样的语言之中，为了编写简单，很多背后的 API 进行了封装，即使是一个简单的变量，背后可能会有隐藏的可变状态。

在 Clojure 中，可以使用天生支持并发的 map 等达到并行的操作。其中有较为常用的 future、promise 模型，与 JavaScript 不同，Clojure 可以使其并行运行。

分离标识与状态

该模型以 Clojure 为例进行说明

引用和代理

原子性变量

软件事务内存

软件事务内存（Software Transactional Memory）STM

Clojure 特有，无太多借鉴性。

Actor

该模型以 Elixir 为例进行说明

其使用进程进行并发编程，对于错误处理，其不是进行防御式编程，而是使用任其崩溃策略，反而可以避免许多问题

其“进程”间的连接是双向的，也可以传递错误，如果“进程”被转化为系统进程，其连接的“进程”异常终止时，系统进程不会终止，而是会收到 exit 消息。

actor 模型优劣势

优势

消息传输和封装

容错

分布式编程

缺点

仍会碰到死锁，或者其特有的问题，例如 mailbox 溢出

类似于线程与锁模型，对并行没有提供直接支持，需要使用并发技术来构造并行的方案，会引入不确定性，所以不太适合细粒度的并行

Scala 中的 akka 库是很好的工具

通信顺序进程（Communicating Sequential Processe，CSP）

通过 Clojure 进行调用 golang 的组件，调用 golang 特有的 channel，进行 go 的并发操作