Seven Concurrency Models in Seven Weeks

Reference: Butcher, Paul. Seven concurrency models in seven weeks: when threads unravel. Pragmatic Bookshelf, 2014.

1. 概述

并发/并行(from Rob Pike)

  • 并发(concurrency)是同一时间应对(dealing with)多件事情的能力
  • 并行(parallelism)是同一时间动手做(doing)多件事情的能力

并行架构

  • 位级(bit-level)并行: 8位/32位
  • 指令级(instruction-level)并行: 流水线/乱序执行/猜测执行
  • 数据级(data)并行: SIMD架构
  • 任务级(task-level)并行: 多处理器(共享内存/分布式内存)

七个模型

  • 线程与锁
  • 函数式编程
  • Clojure之道-分离标识与状态
  • actor
  • 通信顺序进程(Communicating Sequential Processes, CSP)
  • 数据级并行
  • Lambda架构

2. 线程与锁

线程与锁模型其实是对底层硬件运行过程的形式化,这既是它最大的优点,也是它最大的缺点。

互斥和内存模型

PASS

超越内置锁

  • 内置锁的限制: (1) 一个线程因为等待内置锁而进入阻塞之后,就无法中断该线程了; (2) 尝试获取内置锁时,无法设置超时; (3) 获得内置锁,必须使用synchronized块
  • 条件变量:
    ReentrantLock lock = new ReentrantLock();
    Condition cond = lock.newCondition();

    lock.lock();
    try {
        while (!<<条件为真>>) {
            condition.await();
            <<使用共享资源>>
        }
    } finally {
        lock.unlock();
    }
  • 原子变量

站在巨人的肩膀上

  • 写入时复制: CopyOnWriteArrayList
  • 线程池大小: 对于CPU密集型的任务,线程池大小应接近于可用核数;对于IO密集型的任务,线程池可以设置得更大些
  • ForkJoinPool
  • work-stealing

总结

  • 优点: (1) 适用面广; (2) 可以被很容易地集成到大多数编程语言中
  • 缺点: (1) 没有对并行提供直接的支持; (2) 错误不容易发现; (3) 可维护性不好

3. 函数式编程

抛弃可变状态

  • 用map或mapcat对一个序列的每个元素进行映射
  • 用序列的懒惰性来处理较大的序列,甚至无穷序列
  • 用reduce将序列化化简为一个(可能比较复杂的)值
  • 用fold对reduce进行并行化

函数式并行

  • pmap可以将映射操作并行化,构造一个半懒惰的map
  • 利用partition-all可以对并行的映射操作进行批处理,以提高处理效率
  • fold使用分而治之的策略,可以将化简操作并行化
  • clojure.core.reducers包提供的类似map、类似mapcat、类似filter的函数返回的并不是序列,而是化简器reducible

函数式并发

  • future模型
  • promise模型

总结

  • 优点: 对并发和并行友好
  • 缺点: 很多人认为函数式代码比等价的命令式代码效率较低

4. Clojure之道-分离标识与状态

原子变量与持久数据结构

代理和软件事务内存

  • 代理: agent(创建原子变量)、deref(获取代理的值)、send(更新代理的值)、await(等待代理的操作全部完成)
  • send与swap!的区别是,前者会(在代理的值更新之前)立刻返回-传给send的函数将在之后的某个时间被调用
  • 代理与actor有很大差异
  • 校验器(validator)
  • 监视器(watcher)

  • 通过引用(ref)可以实现软件事务内存(Software Transactional Memory, STM)
  • 通过原子变量和代理每次仅能修改一个变量,而通过STM可以对多个变量进行并发的一致的修改,就像数据库的事务可以对多条记录进行并发的一致的修改一样
  • 引用: ref(创建引用)、deref(获取引用的值)、ref-set/alter(更新代理的值)
  • STM事务: ACI(不支持持久性,因为STM的数据在电源故障或系统崩溃的时会丢失)
  • dosync(创建事务)
  • 原子变量不具有事务性,代理具有事务性

  • 原子变量可以对一个值进行同步更新
  • 代理可以对一个值进行异步更新
  • 引用可以对多个值进行一致的、同步的更新

深入学习

  • Clojure不具备尾调用消除(tail-call elimination)的能力

总结

  • 优点: Clojure的持久数据结构将可变量的标识与状态分离开来,解决了使用锁的方案的大部分缺点
  • 缺点: (1) 不支持分布式编程; (2) 无法直接提供容错性

5. actor

消息和信箱

  • 异步地发送消息是用actor模型的重要特性之一。消息并不是发送到一个actor,而是发送到一个信箱(mailbox)。这样的设计解耦了actor之间的关系-actor都以自己的步调运行,且发送消息时不会被阻塞。
  • 虽然所有actor可以同时运行,但它们都按照信箱接受消息的顺序来依次处理消息,且仅在当前消息处理完成后才会处理下一个消息。
  • 尽管actor模型没有提供直接回复消息的机制,但是通过将发送进程的标识符包含在消息中,消息的接受者可以回复消息。
  • 在Elixir中,可以使用spawn()创建新进程、send()向进程发送消息。

错误处理和容错性

  • 使用Process.link()在两个进程之间建立双向连接,利用进程的终止通过连接进行传播,从而让一个进程捕获另一个进程的终止消息

分布式

  • OTP(Open Telecom Platform) in Elixir: GenServer、supervise
  • 节点(Node): Node.listNode.connectNode.spawn
  • 分布式词频统计

总结

  • 优点: (1) 消息传输和封装模型; (2) 天生具有容错性; (3) 对分布式编程友好
  • 缺点: (1) 死锁; (2) 信箱溢出; (3) 没有对并行提供直接支持,由于多个actor并不共享状态,仅通过消息传递来进行交流,所以不太适合实施细粒度的并行

6. 通信顺序进程

  • 与actor模型不同,CSP(Communicating Sequential Process)模型不关注发送消息的实体,而是关注发送消息时使用的通道(channel)

channel和go块

  • 一个channel就是一个线程安全的队列,任何任务只要持有channel的引用,就可以向一端添加消息,也可以从另一端删除消息
  • 默认情况下,channel是同步的(或称无缓存的),也可以创建有缓存的channel
  • go块在底层将串行化代码透明地重写成了事件驱动的形式,转换成了状态机。当从channel中读出消息或向channel中写入消息时,状态机将暂停,并释放它所占用的线程的控制权;当代码可以继续运行时,状态机进行一次状态转换,并可能在另一个线程中继续运行

多个channel与IO

  • 使用alt!宏可以处理多个channel的读和写

客户端CSP

  • ClojureScript是Clojure的一个子集,其代码可以编译成JavaScript

总结

  • 优点: 与actor模型相比,CSP模型的最大优点是灵活性
  • 缺点: (1) 没有library支持分布式和容错性(虽然也可以支持); (2) 死锁; (3) 没有提供直接的并行支持

7. 数据并行

GPGPU编程

  • General-Purpose computing on the GPU(GPGPU)
  • 流水线、多ALU(算术逻辑单元)
  • OpenCL编程

多维空间与工作组

  • 工作项是在处理元件中执行的,多个处理元件构成了计算单元,在同一个计算单元中执行的一组工作项构成工作组
  • 一个工作组中的工作项之间通过局部内存进行通信,利用同步屏障进行数据同步,保证一致性

OpenCL和OpenGL-全部在GPU上运行

PASS

总结

  • 优点: (1) 非常适用于处理大量数值数据; (2) GPU能耗指标比较低
  • 缺点: (1) 并不适用与所有问题领域,尤其是非数据问题(比如自然语言处理); (2) 内核调优、跨平台都比较困难

8. Lambda架构

  • Lambda架构使用批处理层(使用MapReduce这类批处理技术)从历史数据中对批处理视图进行预计算,这种计算效率很高但是延迟也很高;因此使用加速层(使用流处理等低延迟技术)从接收到的新数据中计算实时视图

MapReduce

PASS

批处理层

  • 数据从业务数据库向数据仓库的迁移过程就是著名的Extract、Transform、Load过程,简称ETL

加速层

  • 加速层创建的实时视图包含了最后一次生成批处理视图后产生的数据,这样就完善了Lambda架构。加速层可以是同步的或者异步的。

总结

  • 优点: 主要用于解决大规模数据的问题,非常适合于报表和分析
  • 缺点: 它的最大优点也是它的缺点,除非数据达到TB以上,否则其成本(计算成本和智力成本)将高于收益

9. 圆满结束

未涉及部分

  • Fork/Join模型和Work-Stealing算法
  • 数据流语言(比如VHDL和Verilog)
  • 反应型编程(Reactive Programming)
  • 函数式反应型编程(Functional Reactive Programming, FRP)
  • 网格计算(比如SETI@Home)
  • 元祖空间(tuple space)是分布式联想记忆(distributed associative memory)的一种形式,可用于实现进程之间的通信
Written on June 20, 2017