本文主要是介绍并行计算--并发构造纵览，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并行计算 -- 并发构造纵览
作者简介：
孙奇辉 , 现任某电信公司软件工程师。 对面向对象分析和设计，函数式编程，并行计算等有浓厚兴趣。
Blog: http://blog.csdn.net/sunqihui ;
E-mail: qihui.sun@gmail.com ;
QQ:103561996;
MSN:sunqihui@msn.com 。
版本： 2010-10-22 。
目录
并发构造纵览
一、多线程 Multi-Threading并发模型
二、并发的设计目标和空间
三、有利于构造并发的几种理论模型
1、 Actors(动作者 /角色 )
2、 CSP(Communicating sequential processes)
3、 CCS(Calculus of Communicating Systems)
4、 Petri-net（ Petri 网）
5、 Pi-calculus(π演算 )
6、 Join-calculus（ Join演算）
7、 Functional Programming（函数式编程）
四、并发构造实现时的问题
五、软件事务内存 STM
六、持久化数据结 Persistent Data Structure
七、消息传递 Message-Passing
Actors模型
八、数据流 Dataflow
九、元组空间 Tuplespace
十、参考
本文是从 Ted Leung （ Jython 的主要开发者之一）的一次演讲《 A Survey of Concurrency Constructs 》中翻译整理而来，并补充了相关解释以飨读者，开阔视野。
文中简述了当今世界各主要的语言级并发构造， 并扼要点评了它们的特色和存在的问题，此文希望能激发国内广大程序员对并行 / 并发技术的兴趣，为其并发思想库添砖加瓦。有少许并发编程经验的读者会更利于理解此文。
以下提到的每一种编程模型或并发构造如果详述的话，都能写成一本书或册子，限于篇幅，本文并没有展开详述。如果想 掌握 这些概念和技术，需要更多的学习和一定时间的练习。
今天的程序员，对自己工作用的或家里的机器，装有几个核应该都很清楚了，但是对于并发编程，能够说清楚的，恐怕不多。大多数可能只听说过多线程，很少有（至少在我工作的这多年接触的程序员中）亲手编写过并发程序的。咱们的纵览就从多线程开始吧。
一、多线程 Multi-Threading 并发模型
多线程是最常见的语言级并发构造，例如在 Java 、 C# 等主流语言中都存在。多线程会涉及到对共享状态（即面向对象中的实例字段等）的并发修改，为了确保同步，常常会用到锁和互斥。举个简单的 Java 多线程例子：
public class Account {
private double balance = 1000.0 ;
public double getBalance() {
return balance ;
}
public void deposit( double amount) {
this . balance += amount;
}
public void withdraw( double amount) {
this . balance -= amount;
}
public static void main(String[] args) {
final Account someoneAccount = new Account();
Thread depositSalary = new Thread( new Runnable() {
public void run() {
someoneAccount.deposit( 1600.0 );
}
});
Thread withdrawInsurance = new Thread( new Runnable() {
public void run() {
someoneAccount.withdraw( 300.0 );
}
});
depositSalary.start ();
withdrawInsurance.start ();
try {
Thread.sleep (1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System. out .println(someoneAccount.getBalance()); // 这儿一定是 2300 吗？
}
}
或许我们期待这个程序的输出永远为 2300 ，因为不论是先存薪水还是先交保险，余额应该是 2300 。熟悉 Java 多线程读者可能已经知道，其实存在这种可能，存薪水线程开始取得的余额是 1000 ，而交保险线程开始取得的的余额也是 1000 ！这样它们并发地在 1000 上操作，所以最终的余额可能是它们任一操作的结果：可能是 2600 （账号拥有者会感到高兴），也可能是 700 （账号拥有者会愤怒了）。于是，简单的解决办法是为 deposit 和 withdraw 方法加上 synchronized ，即 Java 的内置锁，但是如果为了正确性，到处用 synchronized 方法，不断影响性能，而且可能会导致死锁、活锁等情况（更多介绍请参阅《 Java 并发编程实践》）。
多线程存在以下的缺点：
手动地 lock 和 unlock ；
Lock 顺序是个大问题，容易造成死锁；
锁不是组合的。
随着 GPGPU 的出现，线程的概念也越来越复杂了，在 CUDA,OpenCL 、 DirectCompute 中，线程的意义存在微妙的差异。
要克服多线程的这些缺点，需要更好的并发编程模型和并发构造。多线程也常是其它并发构造的基础，好的并发构造，应该超越目前的多线程构造，需要考虑如下的设计目标和空间：
二、并发的设计目标和空间
互斥：对于临界区的访问需要互斥；
串行 / 排序：对于并发的修改需要某种形式的串行化和排序；
内在的 / 隐式的 vs 显式的：隐式的并发（下文讲的数据流即是隐式的）与显式的并发的取舍；
细 / 中 / 粗粒度：构造并发任务的粒度，支持的级别；
可组合能力：多种并发构造的组合能力。
因而，好的并发解决方案应该有能力：
减少潜在的错误；
容易识别并发性：任务并行或数据并行；
可伸缩地运行于今天和未来的并行硬件上。
计算机科学发展至今，发展起来了许多有利于构造并发的理论，这些理论除了在科研和教育领域有实践外，在商业上的大型机和高性能计算领域也有较长的成功实现的历史。下面扼要地简介下这几种理论模型。
三、有利于构造并发的几种理论模型
1 、 Actors( 动作者 / 角色 )
在 计算机科学 中，动作者模型是一种 并行 计算 模型。 “ 动作者 ” 是一种程序上的抽象概念，被视为并行计算的 基本单元：当一个动作者接收到一则消息，它可以做出一些决策、建立更多的参与者、传送更多的消息、决定要如何应答接下来的消息。动作者模式在 1973 年 于 Carl Hewitt 、 Peter Bishop 及 Richard Steiger 的论文中提出。
一个动作者是一个计算实体，对收到的消息作出响应，它能并发地
发送有限数量的消息到另一个动作者
创建有限数量的新动作者
指派用于下一个收到的消息的行为
动作者模型作为消息传递模式，能够异步通信和像控制结构样使用，从通信解耦发送者是动作者模型的基本优势。更多介绍参见 http://en.wikipedia.org/wiki/Actor_model 。
2 、 CSP(Communicating sequential processes)
在计算机科学中，通信顺序进程用来描述并发系统中的交互模式。它是并发数学理论例如进程代数或进程演算家族中的一员。 CSP 首先被 C. A. R. Hoare , 于 1978 年的论文中描述。如其名所示， CSP 允许组件进程彼此独立地通过消息传递交互来描述系统。然而其名称中的“顺序”有点不正确，因为现代 CSP 允许组件进程定义为顺序的，也可以由多个基本进程并行地组合。不同进程间的关系，及每个进程与其环境通信的方式，可用各种进程代数操作来描述。用进程代数的方式，非常复杂的进程描述也能容易地由几个基本元素构造。更多介绍参见 http://en.wikipedia.org/wiki/Communicating_sequential_processes 。
3 、 CCS(Calculus of Communicating Systems)
通信系统演算（ CCS ）是一种进程演算，由 Robin Milner 约于 1980 引入。它的动作模拟两个参与者间不可见的通信。其形式语言包括描述动作和范围限定间的并行组合和选择。 CCS 可用于评估系统属性的正确性，例如死锁和活锁。更多介绍参见 http://en.wikipedia.org/wiki/Calculus_of_Communicating_Systems 。
4 、 Petri-net （ Petri 网）
Petri-net( 也叫 place/transition net 或 P/T net ), 是几种用于描述分布式系统的数学建模语言之一。一个 Petri 网是有向双向图，其节点表示转换（也即可发生事件，由条形所示）和位置（也即条件，由圆形所示）。有向的箭头描述了哪个位置是哪个转换的前置和 / 或后置条件。 Petri-net 由 Carl Adam Petri 发明于 1939 年。更多介绍参见 http://en.wikipedia.org/wiki/Petri_net 。
5 、 Pi-calculus( π演算 )
在理论计算机科学中，π演算是一种进程演算，起源于 Robin Milner , Joachim Parrow and David Walker 在 CCS 进程演算上的后续工作。π演算的目的是能够描述并发计算，其配置可以在计算期间变化。π演算属于进程演算家族，即描述和分析并发计算性质的数学形式。事实上，π演算像 λ 演算，定义了极小的范畴，以至于没包含基本原语，例如数字，布尔和常用控制结构等等。更多介绍参见 http://en.wikipedia.org/wiki/Pi-calculus 。
6 、 Join-calculus （ Join 演算）
Join 演算是一种进程演算，由法国计算机科学和控制国家研究所开发。 Join 演算提供了设计分布式编程语言的形式基础，并且有意避免了其它进程中的通信构造，例如 rendezvous -- 它在分布式设置里难于实现。尽管有此限制， Join 演算有与完全的π演算一样的表达能力。用 Join 演算编码π演算，反之亦然，已经被论证过了。更多介绍参见 http://en.wikipedia.org/wiki/Join-calculus 。
7 、 Functional Programming （函数式编程）
在计算机科学中，函数式编程是一种编程范型，其把计算作为求值数学函数对待，并且避免状态和可变数据。其强调应用函数，相对于命令式编程风格强调改变状态。函数式编程的根基在于 lambda 演算，开发于 1930s 的用于考察函数定义，函数应用和递归的形式系统。
实践中，数学函数与命令式编程中的“函数”间的差异在于命令式函数能有副作用，其改变已经计算过的值。因而命令式编程中的函数缺乏引用透明性，即同样的表达式在不同的时间可能导致不同的值，依赖于执行程序的状态。相对地，函数式编程中，函数的输出值仅依赖于其输入参数。更多介绍参见 http://en.wikipedia.org/wiki/Functional_programming 。
四、并发构造实现时的问题
实现高效的并发构造，各具体的模型需要考虑以下几种开销：
线程（线程通常是其它并发构造的基础）创建和销毁的开销，当今支持较好并发的语言基本上提供了轻量级或基于事件的线程；
消息发送的开销，在一些优化的并发 VM 上，底层可能会通过共享内存的方式在多核心机器上传递只读的消息；
上下文 / 线程切换的开销；
锁获取 / 释放的开销。
除了传统的基于锁和互斥的多线程模型外，目前得到实践检验，在一些并发功能突出的语言中应用的并发编程模型还有：
Transactional Memory （事务内存）
Persistent Data Structures （持久化数据结构，通常与 STM 结合使用）
Actors( 动作者 / 角色 )
Dataflow( 数据流 )
Tuplespaces( 元组空间 )
以下分别简述这几种并发构造的历史、特点和不足。了解 Clojure 、 Erlang 、 F# 或 Scala 等并发功能突出的语言的读者会较容易理解下文；以下的例子和图示展示了这些并发构造的精华。
五、软件事务内存 STM
历史：
最初的 STM 论文出现在 1995 年；
这一想法早在 1986 年就出现了， Tom Knight 提到了硬件事务内存；
第一次出现于编程语言，是在 Concurrent Haskell 2005 。
STM 的特点：
在内存中的数据项上使用事务；
在 begin/end 块里包装代码；
指明手动中止或重试的操作；
手动中止时可指明可选的执行路径。
Clojure 语言 (http://clojure.org) 中的 STM 支持数据库事务 ACID 中的 ACI ，即原子性、一致性、隔离性，因为它是内存中的事务，所以没提供数据的持久性存储（例如像数据库样保存在硬盘上）。以下为 Clojure 中的一个例子：
(defn deposit [account amount] ; 定义了一个存款函数，对账号存指定金额
(dosync ; 启用 STM
(let [owner (account :owner) ; 绑定账号
balance-ref (account :balance-ref)] ; 绑定指向账号的引用
(do ; 执行
(alter balance-ref + amount) ; 修改账号余额
(println “depositing” amount (account :owner))))))) ; 打印结果
Clojure 是 JVM 上的一种现代的 LISP 方言。熟悉 LISP 的读者应该能明白以上代码的意思。各行后面有简短的注释（ Clojure 中的注释以 ; 号开始）。
STM 设计空间涉及的算法 / 策略：
事务的粒度，字 word 或块 block 级的粒度
锁 vs 乐观并发；
冲突检测，积极或延迟检测；
竟争管理。
STM 不足和要注意的 :
非事务的代码访问 STM 中的引用；
不可中止的操作，如 I/O ；
STM 开销：读写屏障消除；
哪儿放置事务边界较合适；
仍然需要条件变量，问题的排序很重要。
当编程语言中的 STM 实现有：
Haskell/GHC
使用 logs 和 aborts txns
Clojure STM –via Refs
基于 ML Refs 限制改变，但 ML Refs 没有自动并发语义；
只为 Refs 聚合；
用 MVCC( 多版本并发控制 ) 实现；
持久化数据结构启用 MVCC 可分离读取者和写入者（读取者不等待）。
六、持久化数据结 Persistent Data Structure
历史：
初始形成于约 1981 ；
Sarnoff 形式化于 1986 ；
由 Clojure 流行开来；
PDS 的特点：
当 update 的时候，前一版本的数据仍然可用，保持数据的功能性，会保持对应的可变版本的 big-O 效率；
在 Clojure,PDS 与 STM 组合一起，受写时复制（ copy on write ）激发，有 Hash-map,vector,sorted map 等。
可用的数据结构：
Lists, Vectors, Maps
hash list based on VLists
VDList - deque s based on VLists
red-black trees
Real Time Queues and Deques
deques, output-restricted deques
binary random access lists
binomial heaps
skew binary random access lists
skew binomial heaps
catenable lists
heaps with efficient merging
ca tenable deques
PDS 不足：
不完整的模型，它不能解决所有并发问题；
面向函数式编程。
七、消息传递 Message-Passing
Actors 模型
历史：
由 Carl Hewitt 发明于 MIT （ 1973 ）， 形式模型，编程语言，硬件，由 Scheme 延续；
近来由 Erlang 中兴起来， Erlang 的模型不是明确地派生于 Actors 。
Actors 模型思考：
Actor 的消息队列的分布式服务；
多个 actor 协作， 重新使用事务？
Actors 仍会死锁和饥饿；
程序员定义粒度，得选择什么是一个 actor 。
支持 Actor 模型的编程语言有：
Scala Actors 和 Lift Actors
Erlang
CLR,F# / Axum
Actor 变种：
Kamaelia
消息发到命名的信箱
协作语言连接发件箱和收件箱
信箱大小可控制
Clojure Agents （动作者 / 代理）
为松 耦合的情况设计
代码/ 动作发到agents
当到达agents 时代码会被排队
Agents 框架保证串行
Agents 的状态对读取操作总是可用（不像actors ）
不支持透明的分布式
能在‘开放世界’里操作—actors 响应特定集合的消息
以下为 Actors 的一个简短示意图；再下面是 Scala 语言 (http://www.scala-lang.org) 的一个例子，代码后面也有简短注释。
object account extends Actor { // 单例对象账号继承于 Actor 类
private var balance = 0 // 声明和初始化私有变量 -- 余额
def act() { // 覆写 act() 方法
loop { // 循环处理 Actor 的消息队列
react { // 动作代码，接收消息并处理
case Withdraw(amount) => // 尝试模式匹配，取款类
balance -= amount // 匹配上，则减少余额
sender ! Balance(balance) // 并向发送者响应消息 -- 当前余额
case Deposit(amount) => // 尝试模式匹配，存款类
balance += amount // 匹配上，则增加余额
sender ! Balance(balance) // 并向发送者响应消息 -- 当前余额
case BalanceRequest => // 尝试模式匹配，余额请求类
sender ! Balance(balance) // 匹配上，向发送者响应消息 -- 当前余额
case TerminateRequest => // 尝试模式匹配，终止请求类，忽略此消息
}
}
}
八、数据流 Dataflow
历史：
Bill Ackman 的博士论文于 MIT(1984) ；
函数式语言中声明式并发；
在 1980 和 90 年代得到研究；
内在的并发，导致实现困难；
研究者对声明式并发的兴趣在慢慢地回归。
特色：
数据流变量，创建变量，绑定值，读取值或者阻塞；
轻量级线程；
数据流式的流 stream ，即其尾部是未绑定的数据流变量的列表；
确定性计算。
变种：
Futures( 期货 )
起源于 Multilisp
积极 / 试探的求值
实现质量问题
I-Structures
Id,ph(Parallel Haskell)
单次赋值数组
不能再绑定值，无 stream
Dataflow 的不足：
不能处理非确定性问题，例如服务器端，需要 port 实现 -- 像 actor 的构造。
以下的例子取自于 Scala 语言的开源项目 Akka- （ http://akkasource.org ），其模拟了 Oz 语言（ http://www.mozart-oz.org ）中的数据流并发 :
// Test5 简述：
// 1 、创建 3 个数据流变量 x 、 y 和 z ，其值此时是未绑定的
// 2 、创建 main 线程并启动，绑定 x 的值 1 （通过 << 运算符）
// 3 、获取（通过 () 调用函数）并比较 x 与 y 的值， z 会绑定其中的较大者；注意，此时 y 是 // 未绑定的 , 于是 main 线程会暂停执行，直到 y 的值可用（即其它线程给 y 绑定值）！
// 4 、然后，启动另一个线程 setY, 睡眠 5 秒后给 y 绑定值 2— 这会通知等候 y 值的 main 线程， // -- 于是比较的代码继续运行， z 被绑定为值 2 ！
// 5 、最后，关闭 3 个数据流变量和退出线程。
// 重要的是，无论 main 与 setY 哪个先启动或后启动， z 的值始终会是期望的较大者 2 ！跟 // 上面的 actor 例子一样，都是无锁 (lock-free) 即能保证在并发访问下得到期望的结果。
object Test5 extends Application {
import DataFlow._
val x, y, z = new DataFlowVariable[Int]
val main = thread {
println("Thread 'main'")
x << 1
println("'x' set to: " + x())
println("Waiting for 'y' to be set...")
if (x() > y()) {
z << x
println("'z' set to 'x': " + z())
} else {
z << y
println("'z' set to 'y': " + z())
}
x.shutdown
y.shutdown
z.shutdown
v.shutdown
}
object Test5 extends Application {
val setY = thread {
println("Thread 'setY', sleeping...")
Thread.sleep(5000)
y << 2
println("'y' set to: " + y())
}
// shut down the threads
main ! 'exit
setY ! 'exit
System.exit(0)
}
// 这个例子就不解释了，有兴趣的读者可以查阅 http://github.com/jboner/scala-dataflow
object Test4 extends Application {
import DataFlow._
def ints(n: Int, max: Int, stream: DataFlowStream[Int]): Unit = if (n != max) {
println("Generating int: " + n)
stream <<< n
ints(n + 1, max, stream)
}
def sum(s: Int, in: DataFlowStream[Int], out: DataFlowStream[Int]): Unit = {
println("Calculating: " + s)
out <<< s
sum(in() + s, in, out)
}
def printSum(stream: DataFlowStream[Int]): Unit = {
println("Result: " + stream())
printSum(stream)
}
val producer = new DataFlowStream[Int]
val consumer = new DataFlowStream[Int]
thread { ints(0, 1000, producer) }
thread { sum(0, producer, consumer) }
thread { printSum(consumer) }
}
九、元组空间 Tuplespace
历史：
起源于 Linda(1984) ；
流行于 Jini 。
模型特色：
三种操作
Write() (out)
Take() (in)
Read()
空间解耦
时间 解耦
读取者和写入者 解耦
数据内容通过模式匹配可编址
能够模拟
像 continuations( 延续 ) 的 Actor
CSP
Message Passing
Semaphores
示意图如下：
问题或不足之处：
较低的层次；
空间有较高的延迟 — 空间是竟争点 / 热点；
可伸缩性；
相对于并发多用于分布式。
元组空间的进一步介绍，请参阅
《 Concurrent Programming with Ruby and Tuple Spaces 》
http://www.slideshare.net/luccastera/concurrent-programming-with-ruby-and-tuple-spaces
十、参考
http://assets.en.oreilly.com/1/event/27/A%20Survey%20of%20Concurrency%20Constructs%20Presentation.pdf
这篇关于并行计算--并发构造纵览的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
