`
zj419zj
  • 浏览: 12899 次
最近访客 更多访客>>
社区版块
存档分类
最新评论

并行计算--并发构造纵览

 
阅读更多

并行计算--并发构造纵览
2010年10月22日
  作者简介:
  孙奇辉,现任某电信公司软件工程师。对面向对象分析和设计,函数式编程,并行计算等有浓厚兴趣。        E-mail:qihui.sun@gmail.com ;           QQ:103561996; 版本:2010-10-22。 目录 本文是从Ted Leung (Jython的主要开发者之一)的一次演讲《A Survey of Concurrency Constructs》中翻译整理而来,并补充了相关解释以飨读者,开阔视野。
  文中简述了当今世界各主要的语言级并发构造,并扼要点评了它们的特色和存在的问题,此文希望能激发国内广大程序员对并行/并发技术的兴趣,为其并发思想库添砖加瓦。有少许并发编程经验的读者会更利于理解此文。
  以下提到的每一种编程模型或并发构造如果详述的话,都能写成一本书或册子,限于篇幅,本文并没有展开详述。如果想掌握这些概念和技术,需要更多的学习和一定时间的练习。
  今天的程序员,对自己工作用的或家里的机器,装有几个核应该都很清楚了,但是对于并发编程,能够说清楚的,恐怕不多。大多数可能只听说过多线程,很少有(至少在我工作的这多年接触的程序员中)亲手编写过并发程序的。咱们的纵览就从多线程开始吧。 多线程是最常见的语言级并发构造,例如在Java、C#等主流语言中都存在。多线程会涉及到对共享状态(即面向对象中的实例字段等)的并发修改,为了确保同步,常常会用到锁和互斥。举个简单的Java多线程例子:
  publicclass Account {
  privatedoublebalance = 1000.0;
  publicdouble getBalance() {
  returnbalance;
  }
  publicvoid deposit(double amount) {
  this.balance += amount;
  }
  publicvoid withdraw(double amount) {
  this.balance -= amount;
  }
  publicstaticvoid main(String[] args) {
  final Account someoneAccount = new Account();
  Thread depositSalary = new Thread(new Runnable() {
  publicvoid run() {
  someoneAccount.deposit(1600.0);
  }
  });
  Thread withdrawInsurance = new Thread(new Runnable() {
  publicvoid 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 显式的:隐式的并发(下文讲的数据流即是隐式的)与显式的并发的取舍;
  细/中/粗粒度:构造并发任务的粒度,支持的级别;
  可组合能力:多种并发构造的组合能力。
  因而,好的并发解决方案应该有能力:
  减少潜在的错误;
  容易识别并发性:任务并行或数据并行;
  可伸缩地运行于今天和未来的并行硬件上。
  计算机科学发展至今,发展起来了许多有利于构造并发的理论,这些理论除了在科研和教育领域有实践外,在商业上的大型机和高性能计算领域也有较长的成功实现的历史。下面扼要地简介下这几种理论模型。          在计算机科学中,动作者模型是一种并行计算模型。"动作者"是一种程序上的抽象概念,被视为并行计算的基本单元:当一个动作者接收到一则消息,它可以做出一些决策、建立更多的参与者、传送更多的消息、决定要如何应答接下来的消息。动作者模式在1973年于Carl Hewitt、Peter Bishop及Richard Steiger的论文中提出。
  一个动作者是一个计算实体,对收到的消息作出响应,它能并发地
  发送有限数量的消息到另一个动作者
  创建有限数量的新动作者
  指派用于下一个收到的消息的行为
  动作者模型作为消息传递模式,能够异步通信和像控制结构样使用,从通信解耦发送者是动作者模型的基本优势。更多介绍参见http://en.wikipedia.org/wiki/Actor_model。          在计算机科学中,通信顺序进程用来描述并发系统中的交互模式。它是并发数学理论例如进程代数或进程演算家族中的一员。CSP首先被C. A. R. Hoare ,于1978年的论文中描述。如其名所示,CSP允许组件进程彼此独立地通过消息传递交互来描述系统。然而其名称中的"顺序"有点不正确,因为现代CSP允许组件进程定义为顺序的,也可以由多个基本进程并行地组合。不同进程间的关系,及每个进程与其环境通信的方式,可用各种进程代数操作来描述。用进程代数的方式,非常复杂的进程描述也能容易地由几个基本元素构造。更多介绍参见http://en.wikipedia.org/wiki/Communicating_sequent ial_processes。          通信系统演算(CCS)是一种进程演算,由Robin Milner约于1980引入。它的动作模拟两个参与者间不可见的通信。其形式语言包括描述动作和范围限定间的并行组合和选择。CCS可用于评估系统属性的正确性,例如死锁和活锁。更多介绍参见http://en.wikipedia.org/wiki/Calculus_of_Communica ting_Systems。           Petri-net(也叫place/transition net 或P/T net ),是几种用于描述分布式系统的数学建模语言之一。一个Petri网是有向双向图,其节点表示转换(也即可发生事件,由条形所示)和位置(也即条件,由圆形所示)。有向的箭头描述了哪个位置是哪个转换的前置和/或后置条件。Petri-net由Carl Adam Petri发明于1939年。更多介绍参见http://en.wikipedia.org/wiki/Petri_net。          在理论计算机科学中,π演算是一种进程演算,起源于Robin Milner , Joachim Parrow and David Walker在CCS进程演算上的后续工作。π演算的目的是能够描述并发计算,其配置可以在计算期间变化。π演算属于进程演算家族,即描述和分析并发计算性质的数学形式。事实上,π演算像λ演算,定义了极小的范畴,以至于没包含基本原语,例如数字,布尔和常用控制结构等等。更多介绍参见http://en.wikipedia.org/wiki/Pi-calculus。           Join演算是一种进程演算,由法国计算机科学和控制国家研究所开发。Join演算提供了设计分布式编程语言的形式基础,并且有意避免了其它进程中的通信构造,例如rendezvous --它在分布式设置里难于实现。尽管有此限制,Join演算有与完全的π演算一样的表达能力。用Join演算编码π演算,反之亦然,已经被论证过了。更多介绍参见http://en.wikipedia.org/wiki/Join-calculus。 在计算机科学中,函数式编程是一种编程范型,其把计算作为求值数学函数对待,并且避免状态和可变数据。其强调应用函数,相对于命令式编程风格强调改变状态。函数式编程的根基在于lambda演算,开发于1930s的用于考察函数定义,函数应用和递归的形式系统。
  实践中,数学函数与命令式编程中的"函数"间的差异在于命令式函数能有副作用,其改变已经计算过的值。因而命令式编程中的函数缺乏引用透明性,即同样的表达式在不同的时间可能导致不同的值,依赖于执行程序的状态。相对地,函数式编程中,函数的输出值仅依赖于其输入参数。更多介绍参见http://en.wikipedia.org/wiki/Functional_programmin g。          实现高效的并发构造,各具体的模型需要考虑以下几种开销:
  线程(线程通常是其它并发构造的基础)创建和销毁的开销,当今支持较好并发的语言基本上提供了轻量级或基于事件的线程;
  消息发送的开销,在一些优化的并发VM上,底层可能会通过共享内存的方式在多核心机器上传递只读的消息;
  上下文/线程切换的开销;
  锁获取/释放的开销。
  除了传统的基于锁和互斥的多线程模型外,目前得到实践检验,在一些并发功能突出的语言中应用的并发编程模型还有:
  Transactional Memory (事务内存)
  Persistent Data Structures(持久化数据结构,通常与STM结合使用)
  Actors(动作者/角色)
  Dataflow(数据流)
  Tuplespaces(元组空间)
  以下分别简述这几种并发构造的历史、特点和不足。了解Clojure、Erlang、F# 或Scala等并发功能突出的语言的读者会较容易理解下文;以下的例子和图示展示了这些并发构造的精华。 历史:
  最初的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 (accountwner)                      ;绑定账号
  balance-ref (account :balance-ref)] ;绑定指向账号的引用
  (do                                                                 ;执行
  (alter balance-ref + amount)             ;修改账号余额
  (println "depositing" amount (accountwner))))))) ;打印结果
  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可分离读取者和写入者(读取者不等待)。
  历史:
  初始形成于约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 - deques 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
  catenable deques
  PDS不足:
  不完整的模型,它不能解决所有并发问题;
  面向函数式编程。          历史:
  由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 =>                         //尝试模式匹配,终止请求类,忽略此消息
  }
  }
  }          历史:
  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(通过 y()) {
  z
  问题或不足之处:
  较低的层次;
  空间有较高的延迟-空间是竟争点/热点;
  可伸缩性;
  相对于并发多用于分布式。
  元组空间的进一步介绍,请参阅
  《Concurrent Programming with Ruby and Tuple Spaces》
  http://www.slideshare.net/luccastera/concurrent-pr ogramming-with-ruby-and-tuple-spaces
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics