术语,概念

这一章我们将尝试建立通用的术语,对Akka面向的并发、分布式系统等提供一个坚实的讨论基础。请注意,这里的很多术语都没有统一的定义。我们只是希望在Akka文档的范围内给出可用的定义。

并发 vs. 并行

并发和并行是相关的定义,有一些微小的不同。并发 指的是两个或多个任务都有进展,即使他们没有被同时执行。例如可以这样实现:划分出时间片,几个任务交叉执行,尽管时间片的执行是线性的。并行 则是指可以真正同时执行。

异步 vs. 同步

一个方法调用是 同步 的,当调用者不能继续处理,除非方法返回一个值或抛出一个异常。另一方面,一个 异步 调用允许调用者在调用方法的有限步后能够继续执行,并且该方法的结束可以被额外的机制通知到(也许是一个注册的回调callback,一个Future或一个消息)。

一个同步的API也许会使用阻塞实现同步性,但也不是必须的。一个CPU极为密集的任务也会导致类似阻塞的行为。通常推荐使用非阻塞API,因为它们能确保系统继续处理。Actor本质上是异步的:一个Actor可以在发送消息后继续处理,而不需要等待消息确实被送达。

非阻塞 vs. 阻塞

如果一个线程的延迟会导致其它一些线程无限期的延迟,我们称之为 阻塞。一个很好的例子是资源可以被线程通过互斥锁独占。如果这个线程无限期地占有这个资源(例如不小心进入死循环),其他等待这个资源的线程就无法处理了。相反地,非阻塞 意味着没有线程可以无限期的阻塞其他线程。

相比阻塞操作,我们推荐非阻塞的操作,因为很明显这样系统不会因为阻塞操作而不再继续处理。

死锁 vs. 饥饿 vs. 活锁

当多个参与者互相等待别人达到某个特殊的状态才能继续处理的时候,死锁 出现了。因为如果一些参与者不达到特定状态,所有的参与者都不能执行(就像《第二十二条军规》描述的那样),所有相关子系统都停顿了。死锁和阻塞息息相关,因为阻塞使得一个参与者线程可以无限期地推迟其他线程的处理。

在死锁中,没有参与者可以处理,然而相对的 饥饿 可能发生,当有些参与者可以不断地处理,而另一些可能不行。一个典型的场景是一个幼稚的调度算法——总是选择高优先级的任务。如果高优先级的任务数量一直足够多,则低优先级的任务永远不会被完成。

活锁 和死锁类似,没有参与者可以处理。区别在于与进程进入等待其他进程处理的“冻结”状态不同,参与者不断地变换他们的状态。一个示例场景是两个参与者和两个特殊的资源。他们分别试图获取资源,并且检查是不是另一个参与者也需要这个资源。如果该资源被另一个参与者请求,则它们试图获取另一个资源。在一个很不幸的情况下,也许两个参与者会不停的在两个资源上“跳跃”,永远在谦让而不使用资源。

竞态条件

当一组事件的顺序假设可能被外部不确定因素影响,我们称之为 竞态条件。竞态条件经常在多个线程共享一个可变状态时出现,一个线程对这个状态的操作可能被交织从而导致意外的行为。尽管这是常见的情况,但是共享状态并不一定会导致竞态条件。例如一个客户端向服务器发送无序的包(例如UDP数据包)P1P2。由于包可能经过不同的网络路由器传送,所以服务器可能先收到P2,后收到P1。如果消息中没有包含发送顺序的相关信息的话,服务器是不可能确定包是否是按照发送顺序接收的。根据包的内容这可能会导致竞态条件。

注意

对两个actor之间的消息发送,Akka唯一提供的保证是消息的发送顺序是被保留的。详见 消息传送可靠性Message Delivery Reliability

非阻塞担保(进展条件)

就像前几个章节描述的,阻塞是不受欢迎的,因为它有可能导致死锁并降低系统的吞吐量。在下面几节,我们将从不同深度讨论各种无阻塞特性。

无等待(Wait-freedom)

如果一个方法的调用可以保证在有限步骤内完成,则称该方法是 无等待 的。如果方法是 有界无等待 的,则方法的执行步数有一个确定的上界。

从这个定义可以得出无等待的方法永远不会阻塞,因此死锁是不可能发生的。此外,因为每个参与者都可以经过有限步后继续执行(当调用完成),所以无等待方法也不会出现饥饿的情况。

无锁(Lock-freedom)

无锁 是比 无等待 更弱的特性。在无锁调用的情况下,无限地经常有一些方法在有限步骤内完成。这个定义暗示着对无锁调用是不可能出现死锁的。另一方面,部分方法调用 在有限步骤内 结束,不足以保证所有调用最终完成。换句话说,无锁不足以保证不会出现饥饿。

无阻碍(Obstruction-freedom)

无阻碍 是这里讨论的最弱的无阻塞保证。对一个方法,当在某一个它独自执行的时间点(其他线程不在执行,例如都挂起了),之后它在有限步后能够结束,我们称之为 无阻碍。所有无锁的对象都是无阻碍的,但反之一般不成立。

乐观并发模型OCC(Optimistic concurrency control ) 的方法通常是无阻碍的。OCC的做法是,每一位参与者都试图在共享对象上执行操作,但是如果参与者检测到来自其他参与者的冲突,它回滚修改,并根据调度再次尝试。如果在某一个时间点,其中一个参与者,是唯一一个尝试修改的点,则其操作就会成功。

推荐文献

  • The Art of Multiprocessor Programming, M. Herlihy and N Shavit, 2008. ISBN 978-0123705914 (注:中文译《多处理器编程的艺术》
  • Java Concurrency in Practice, B. Goetz, T. Peierls, J. Bloch, J. Bowbeer, D. Holmes and D. Lea, 2006. ISBN 978-0321349606(注:中文译《Java并发编程实战》