第二章在面向对象模型中引进并发 第二章在面向对象模型中引进并发 顺序面向对象模型由一组被动的对象构成，系统的执行行为是：外界激活其 某个对象的某个方法，该方法的执行中向系统中其它对象发送消息，从而激活这 些对象的方法的执行。这里的消息发送就是过程调用，即消息发送者调用消息接 受者的某个方法，必须等到消息接受者的相应方法执行完毕，才能继续执行下去， 因此，整个系统只有一个执行线程(thread)。 如何在上述的顺序面向对象模型中引进并发行为？如何实现对象的并发控 制？这是很多人都在研究的问题3,10,11,19,64,71,72,85,91,927,56。本章首先对传统的并 发系统模型作一简单描述，然后给出在面向对象模型中引入并发行为应解决的问 题和一些解决方案，最后介绍现有的一些并发面向对象模型。 2.1并发系统的一般模型 人们习惯于编写顺序程序，理由是：顺序程序的行为完全在程序设计者的控 制之下，但是，把一个程序构造成由若干个并发执行的部分组成往往会显得更加 自然，并且，这样的程序能够充分发挥一些并行体系结构的计算机系统所提供的 强大计算能力。虽然从理论上讲，一个设计良好的编译器可以发现一个顺序程序 中潜在的并行性，并产生相应的可执行并发代码，但实际上，这只对一些有限的 应用可行，对于一般的应用来说，为了描述问题领域中的并发活动，程序设计者 必须在程序中给出显式的并发描述。 在一个并发系统中，计算任务是由若干独立（异步）执行的活动相互合作完成 的。为了显式地描述这样的系统，一般要考虑三个方面的问题： (1)并发执行。 描述一个并发系统，首先要考虑采用什么样的结构来表示并发执行的单位， 以及如何让它们并发执行。在传统的基于进程的并发系统中，描述并发结构的方 式有多种，如：coroutinel4、fork/joinL25,281、cobegin/coendl29]以及task3]等，这些 并发结构在抽象级别及表达能力上各不相同，其中，有些是属于低级描述但具有 较强的表达能力，如fork/join;有些抽象级别较高但表达能力受到限制，如： cobegin/coend。另外，这些并发结构在描述进程的创建方面也各不相同，在有些结 6
第二章 在面向对象模型中引进并发 6 第二章 在面向对象模型中引进并发 顺序面向对象模型由一组被动的对象构成，系统的执行行为是：外界激活其 某个对象的某个方法，该方法的执行中向系统中其它对象发送消息，从而激活这 些对象的方法的执行。这里的消息发送就是过程调用，即消息发送者调用消息接 受者的某个方法，必须等到消息接受者的相应方法执行完毕，才能继续执行下去， 因此，整个系统只有一个执行线程(thread)。 如何在上述的顺序面向对象模型中引进并发行为？如何实现对象的并发控 制？这是很多人都在研究的问题[3,10,11,19,64,71,72,85,91,92,7,56]。本章首先对传统的并 发系统模型作一简单描述，然后给出在面向对象模型中引入并发行为应解决的问 题和一些解决方案，最后介绍现有的一些并发面向对象模型。 2.1 并发系统的一般模型 人们习惯于编写顺序程序，理由是：顺序程序的行为完全在程序设计者的控 制之下，但是，把一个程序构造成由若干个并发执行的部分组成往往会显得更加 自然，并且，这样的程序能够充分发挥一些并行体系结构的计算机系统所提供的 强大计算能力。虽然从理论上讲，一个设计良好的编译器可以发现一个顺序程序 中潜在的并行性，并产生相应的可执行并发代码，但实际上，这只对一些有限的 应用可行，对于一般的应用来说，为了描述问题领域中的并发活动，程序设计者 必须在程序中给出显式的并发描述。 在一个并发系统中，计算任务是由若干独立(异步)执行的活动相互合作完成 的。为了显式地描述这样的系统，一般要考虑三个方面的问题[6]： (1)并发执行。 描述一个并发系统，首先要考虑采用什么样的结构来表示并发执行的单位， 以及如何让它们并发执行。在传统的基于进程的并发系统中，描述并发结构的方 式有多种，如：coroutine[4]、fork/join[25,28]、cobegin/coend[29]以及task[13]等，这些 并发结构在抽象级别及表达能力上各不相同，其中，有些是属于低级描述但具有 较强的表达能力，如fork/join；有些抽象级别较高但表达能力受到限制，如： cobegin/coend。另外，这些并发结构在描述进程的创建方面也各不相同，在有些结
第二章在面向对象模型中引进并发 构中，进程是静态创建的，进程的个数是固定的：在另一些结构中，进程的创建 则是动态的，进程的个数随着系统的执行在变化。 (2)并发活动之间的通信。 在一个并发系统中，并发执行的活动之间往往需要进行交互，即，通信。在 基于进程的并发系统中，进程间的通信可以采用共享变量(shared variables)和消息 传递(message passing)两种方式，共享变量通信方式适合于具有共享内存体系结构 的计算机中，消息传递则不受共享内存的限制。在消息传递通信方式中，还存在 两种通信形式：异步消息传递(asynchronous message passing)和同步消息传递 (synchronous message passing),在异步消息传递中，消息发送者不必等待消息接受 者接收消息，而是把消息放入一个消息缓存中，消息发送者即可继续执行下去， 消息接受者适时地从消息缓存中接收消息进行处理，消息处理结果也以同样方式 送给消息发送者。在同步消息传递中，消息发送者必须等到消息接受者接收消息 后才能继续执行下去。 异步消息传递特点在于：它使得系统有较高的并行度，不足之处是：使得系 统的行为难以理解，当消息接受者接收到某个消息时，消息发送者的状态可能已 经不是发送该消息时的状态了。另外，采用异步消息传递，消息发送者还要考虑 司步问题，即何时及如何获得回答消息。同步消息传递的特点是：消息发送就隐 含了同步，不足的是使得系统的并发度降低，并且，如果处理不当易造成死锁。 异步消息传递和同步消息传递都是单向通信，为了方便地描述client/server计算 模型中的消息传递，一种较高层次的消息传递机制被引进：远程过程调用(remote procedure call或RPC),采用RPC方式进行消息传递时，消息发送者通过执行一个cal 语句来发送消息，从形式上看，call语句类似于通常的过程调用。当call语句执行时， 首先把参数传给消息接受者，然后等待消息接受者执行相应操作并返回处理结果。 远程过程调用属于一种双向通信。 (3)并发活动的同步。 在并发系统中，进行通信的并发活动间往往需要同步。较常见的同步形式是 条件同步(condition synchronization),即，一个活动的继续执行必须要等待一个条件 或事件的发生。在基于共享变量的消息传递机制中还存在另一种形式的同步：互 7
第二章 在面向对象模型中引进并发 7 构中，进程是静态创建的，进程的个数是固定的；在另一些结构中，进程的创建 则是动态的，进程的个数随着系统的执行在变化。 (2)并发活动之间的通信。 在一个并发系统中，并发执行的活动之间往往需要进行交互，即，通信。在 基于进程的并发系统中，进程间的通信可以采用共享变量(shared variables)和消息 传递(message passing)两种方式，共享变量通信方式适合于具有共享内存体系结构 的计算机中，消息传递则不受共享内存的限制。在消息传递通信方式中，还存在 两种通信形式：异步消息传递(asynchronous message passing)和同步消息传递 (synchronous message passing)，在异步消息传递中，消息发送者不必等待消息接受 者接收消息，而是把消息放入一个消息缓存中，消息发送者即可继续执行下去， 消息接受者适时地从消息缓存中接收消息进行处理，消息处理结果也以同样方式 送给消息发送者。在同步消息传递中，消息发送者必须等到消息接受者接收消息 后才能继续执行下去。 异步消息传递特点在于：它使得系统有较高的并行度，不足之处是：使得系 统的行为难以理解，当消息接受者接收到某个消息时，消息发送者的状态可能已 经不是发送该消息时的状态了。另外，采用异步消息传递，消息发送者还要考虑 同步问题，即何时及如何获得回答消息。同步消息传递的特点是：消息发送就隐 含了同步，不足的是使得系统的并发度降低，并且，如果处理不当易造成死锁。 异步消息传递和同步消息传递都是单向通信，为了方便地描述client/server计算 模型中的消息传递，一种较高层次的消息传递机制被引进：远程过程调用(remote procedure call或RPC)。采用RPC方式进行消息传递时，消息发送者通过执行一个call 语句来发送消息，从形式上看，call语句类似于通常的过程调用。当call语句执行时， 首先把参数传给消息接受者，然后等待消息接受者执行相应操作并返回处理结果。 远程过程调用属于一种双向通信。 (3)并发活动的同步。 在并发系统中，进行通信的并发活动间往往需要同步。较常见的同步形式是 条件同步(condition synchronization)，即，一个活动的继续执行必须要等待一个条件 或事件的发生。在基于共享变量的消息传递机制中还存在另一种形式的同步：互
第二章在面向对象模型中引进并发 斥(mutual exclusion),即，为了保证用于通信的共享变量不受错误的并发操作的影 响，往往要互斥地使用它们。 在传统的并发模型中，实现同步的机制有多种，其中，基于共享变量的同步 机制有：信号量(semaphoresl2]、条件临界区(conditional critical regionsl42]、管程 (monitorsl2])和路径表达式(path expressionsl[l8)等。信号量具有很强的表达能力，它 几乎可以描述各种同步问题，但它属于一种无结构的低级设施，使用不当（如：漏 掉一个P或V,或P和V颠倒了)将会产生灾难性结果：条件临界区相对来说更有结构 一些，但与信号量一样，同步控制代码分散在各个进程中，如要了解某个共享资 源的使用情况，必须要阅读整个程序：管程实现了共享资源的集中管理，它封装 了共享资源及可施于其上的操作，管程的实现保证了对其操作的互斥调用，但是， 管程在实现条件同步方面就显得不是那么有结构，必须借助于其它设施来完成， 如：条件变量上的wait和signal操作，另外，嵌套的管程调用也会引起很多问题： 路径表达式在描述操作间的并发限制上提供了比较优雅的方案，对描述并发计算 的语义起到了积极的作用。路径表达式比较适合于描述与操作历史有关的同步问 题，但在描述条件同步方面却显得无所适从，因为，一个操作是否可以执行往往 要依赖于所操作的资源的状态，而有些状态并不直接反映在操作历史中。 当用消息传递进行通信时，消息传递就隐含了一种同步，即，消息只有在发 送后才能收到，它给出了消息发送者与接收者之间的一种执行次序。消息传递机 制如果设计得好，它就能既实现进程间的通信，又能实现进程间的同步。 2.2面向对象模型的并发执行 进程是传统并发程序设计模型中的基本构件，同时它也是引起系统并发的基 本单位。而在面向对象软件系统中，对象是其基本构件，同时，对象也是产生并 发的自然单位，用面向对象模型来解决客观世界中的并发问题会显得更加自然。 要在对象模型中引进并发，首先要考虑如何让对象间的活动并发执行起来。 2.2.1异步消息传递 在面向对象模型中，对象间通过相互发送消息进行合作，共同完成系统的功 能。如果消息发送者在发送消息后不需消息处理结果，或者不立即需要处理结果， 消息发送者不必等待消息接受者接收和处理消息即可继续执行下去，只有在消息 发送者需要消息的处理结果时才等待。消息接受者对消息进行缓存，在适当的时 P
第二章 在面向对象模型中引进并发 8 斥(mutual exclusion)，即，为了保证用于通信的共享变量不受错误的并发操作的影 响，往往要互斥地使用它们。 在传统的并发模型中，实现同步的机制有多种，其中，基于共享变量的同步 机制有：信号量(semaphores[29])、条件临界区(conditional critical regions[42])、管程 (monitors[29])和路径表达式(path expressions[18])等。信号量具有很强的表达能力，它 几乎可以描述各种同步问题，但它属于一种无结构的低级设施，使用不当(如：漏 掉一个P或V，或P和V颠倒了)将会产生灾难性结果；条件临界区相对来说更有结构 一些，但与信号量一样，同步控制代码分散在各个进程中，如要了解某个共享资 源的使用情况，必须要阅读整个程序；管程实现了共享资源的集中管理，它封装 了共享资源及可施于其上的操作，管程的实现保证了对其操作的互斥调用，但是， 管程在实现条件同步方面就显得不是那么有结构，必须借助于其它设施来完成， 如：条件变量上的wait和signal操作，另外，嵌套的管程调用也会引起很多问题； 路径表达式在描述操作间的并发限制上提供了比较优雅的方案，对描述并发计算 的语义起到了积极的作用。路径表达式比较适合于描述与操作历史有关的同步问 题，但在描述条件同步方面却显得无所适从，因为，一个操作是否可以执行往往 要依赖于所操作的资源的状态，而有些状态并不直接反映在操作历史中。 当用消息传递进行通信时，消息传递就隐含了一种同步，即，消息只有在发 送后才能收到，它给出了消息发送者与接收者之间的一种执行次序。消息传递机 制如果设计得好，它就能既实现进程间的通信，又能实现进程间的同步。 2.2 面向对象模型的并发执行 进程是传统并发程序设计模型中的基本构件，同时它也是引起系统并发的基 本单位。而在面向对象软件系统中，对象是其基本构件，同时，对象也是产生并 发的自然单位，用面向对象模型来解决客观世界中的并发问题会显得更加自然。 要在对象模型中引进并发，首先要考虑如何让对象间的活动并发执行起来。 2.2.1 异步消息传递 在面向对象模型中，对象间通过相互发送消息进行合作，共同完成系统的功 能。如果消息发送者在发送消息后不需消息处理结果，或者不立即需要处理结果， 消息发送者不必等待消息接受者接收和处理消息即可继续执行下去，只有在消息 发送者需要消息的处理结果时才等待。消息接受者对消息进行缓存，在适当的时
第二章在面向对象模型中引进并发 候处理之。采用异步消息发送需要解决的两个问题是： (1)消息处理者如何返回处理结果？ (2)消息发送者如何得到处理结果？ 对于问题(1)的一般解决方案是：在消息中带有发送者的地址（标识），消息处理 者在处理完某消息后，将根据消息中的发送者标识给其发回返回值消息。关于问 题(2)的一种解决方案是把对象的消息分成两类：一类是普通消息，另一类是回答 (返回值)消息。这样往往要把一个完整的消息处理过程分成若干个子过程，其中一 个用于处理普通消息，其它的用于处理返回值消息，从而给程序设计带来麻烦。 另一种解决问题(2)的途径是：对象发送消息时，消息中带的不是发送者的地址， 而是另一个对象（发送者的代理）的地址9,91,92]，这个代理对象在消息发送时创建， 消息处理结果将送给这个对象，当消息发送者需要消息的处理结果时，将向这个 对象发送消息以获得消息处理结果，这时采用同步消息发送。 2.2.2主动对象 在面向对象模型中引进并发的另一种途径是给对象加一个自己的执行线程， 这个执行线程常被称为对象的体，有对象体的对象被称为主动对象[0,19,50]。当主 动对象创建时，它的体就立即作为单独的线程开始执行。在对象体的执行中，对 象可以接收和发送消息。 目前，关于主动对象的研究大多数是为了把进程的概念引进到面向对象模型 中来，用主动对象模拟进程；对象间消息传递采用CSP[43]或Ada3]中的同步消息传 递机制。在采用异步消息传递机制的并发面向对象模型中，系统的并发是由异步 消息发送产生，而在基于主动对象的并发面向对象模型中，系统的并发则是由创 建新对象产生的。两种模型在描述系统的并发程度上是不同，前者属于一种细粒 度(fine-grained)控制，并发程度较高，后者是一种粗粒度(coarse-.grained)并发控制， 系统的并发程度相对较低。当然，在主动对象模型中也可以采用异步消息传递， 从而提高系统的并发度，不过对于并发系统而言，并发度是一个要考虑的问题， 另一个需要考虑的问题是系统的可靠性，异步消息传递使得系统的行为难以控制， 不利于对程序的理解。关于同步和异步消息传递，论文第三章中还要讨论。 2.2.3对象内部并发 9
第二章 在面向对象模型中引进并发 9 候处理之。采用异步消息发送需要解决的两个问题是： (1)消息处理者如何返回处理结果？ (2)消息发送者如何得到处理结果？ 对于问题(1)的一般解决方案是：在消息中带有发送者的地址(标识)，消息处理 者在处理完某消息后，将根据消息中的发送者标识给其发回返回值消息。关于问 题(2)的一种解决方案是把对象的消息分成两类：一类是普通消息，另一类是回答 (返回值)消息。这样往往要把一个完整的消息处理过程分成若干个子过程，其中一 个用于处理普通消息，其它的用于处理返回值消息，从而给程序设计带来麻烦。 另一种解决问题(2)的途径是：对象发送消息时，消息中带的不是发送者的地址， 而是另一个对象(发送者的代理)的地址[19,91,92]，这个代理对象在消息发送时创建， 消息处理结果将送给这个对象，当消息发送者需要消息的处理结果时，将向这个 对象发送消息以获得消息处理结果，这时采用同步消息发送。 2.2.2 主动对象 在面向对象模型中引进并发的另一种途径是给对象加一个自己的执行线程， 这个执行线程常被称为对象的体，有对象体的对象被称为主动对象[10,19,50]。当主 动对象创建时，它的体就立即作为单独的线程开始执行。在对象体的执行中，对 象可以接收和发送消息。 目前，关于主动对象的研究大多数是为了把进程的概念引进到面向对象模型 中来，用主动对象模拟进程；对象间消息传递采用CSP[43]或Ada[13]中的同步消息传 递机制。在采用异步消息传递机制的并发面向对象模型中，系统的并发是由异步 消息发送产生，而在基于主动对象的并发面向对象模型中，系统的并发则是由创 建新对象产生的。两种模型在描述系统的并发程度上是不同，前者属于一种细粒 度(fine-grained)控制，并发程度较高，后者是一种粗粒度(coarse-grained)并发控制， 系统的并发程度相对较低。当然，在主动对象模型中也可以采用异步消息传递， 从而提高系统的并发度，不过对于并发系统而言，并发度是一个要考虑的问题， 另一个需要考虑的问题是系统的可靠性，异步消息传递使得系统的行为难以控制， 不利于对程序的理解。关于同步和异步消息传递，论文第三章中还要讨论。 2.2.3 对象内部并发
第二章在面向对象模型中引进并发 对象间存在并发，对象内部是否也允许并发？在8]中，根据对象内部是顺序 的、半并发的和并发的，对并发面向对象系统中的对象进行了分类： (I)顺序对象(sequential objects):对象以FIFO的结构顺序地从消息队列中选择 满足条件的消息进行处理，这时，对象中只有一个执行线程。如ABCL1[92]和 POOL-To]中的对象以及Ada中的task[l3]。 (2)半并发对象(quasi--concurrent objects):对象中存在多个执行线程，但在某 时刻只有一个是活动的。如管程(monitor)对象，除了一个线程可以执行外，其它线 程都因调用条件变量上的wait而被挂起。 (3)并发对象(concurrent objects):对象中同时存在多个活动线程，一个线程只 有在需要等待使用对象的局部变量（由对象的多个线程共享）或其它条件时，才被挂 起。 出于表达能力的考虑，应允许对象内部的并发，因为在现实世界中存在这样 的对象，其内部事务存在并发行为。另外，从实现的角度说，如果对象间采用同 步消息传递，当对象处理消息时又向其它对象发送消息，在等待消息处理结果时， 它就不能再接收受其它消息，特别是当对象递归（直接或间接）发送消息时，立即产 生死锁。 如果允许对象内部的并发，必须要考虑： (1)何时创建新线程。一种方案是当对象接收消息时创建新线程，一个线程处 理一个消息：另外一种方案是在对象处理一个消息的过程中创建新线程，这时， 新创建的线程承担原消息处理的一部分工作。 (2)保证对象状态的完整性。由于各活动线程可能同时使用对象的成员变量， 为了保证对象状态的完整，这些线程必须互斥地使用它们。 (3)消息接收的调度问题。由于允许对象内部并发，对象在接收消息时就可能 选取后到的满足条件的消息进行处理，这样就会使得先到的消息后处理，甚至永 远得不到处理，即出现饿死(starvation)现象。如典型的readers/writer问题，如果调 10
第二章 在面向对象模型中引进并发 10 对象间存在并发，对象内部是否也允许并发？在[89]中，根据对象内部是顺序 的、半并发的和并发的，对并发面向对象系统中的对象进行了分类： (1)顺序对象(sequential objects)：对象以FIFO的结构顺序地从消息队列中选择 满足条件的消息进行处理，这时，对象中只有一个执行线程。如ABCL/1[92]和 POOL-T[10]中的对象以及Ada中的task[13]。 (2)半并发对象(quasi-concurrent objects)：对象中存在多个执行线程，但在某一 时刻只有一个是活动的。如管程(monitor)对象，除了一个线程可以执行外，其它线 程都因调用条件变量上的wait而被挂起。 (3)并发对象(concurrent objects)：对象中同时存在多个活动线程，一个线程只 有在需要等待使用对象的局部变量(由对象的多个线程共享)或其它条件时，才被挂 起。 出于表达能力的考虑，应允许对象内部的并发，因为在现实世界中存在这样 的对象，其内部事务存在并发行为。另外，从实现的角度说，如果对象间采用同 步消息传递，当对象处理消息时又向其它对象发送消息，在等待消息处理结果时， 它就不能再接收受其它消息，特别是当对象递归(直接或间接)发送消息时，立即产 生死锁。 如果允许对象内部的并发，必须要考虑： (1)何时创建新线程。一种方案是当对象接收消息时创建新线程，一个线程处 理一个消息；另外一种方案是在对象处理一个消息的过程中创建新线程，这时， 新创建的线程承担原消息处理的一部分工作。 (2)保证对象状态的完整性。由于各活动线程可能同时使用对象的成员变量， 为了保证对象状态的完整，这些线程必须互斥地使用它们。 (3)消息接收的调度问题。由于允许对象内部并发，对象在接收消息时就可能 选取后到的满足条件的消息进行处理，这样就会使得先到的消息后处理，甚至永 远得不到处理，即出现饿死(starvation)现象。如典型的readers/writer问题，如果调