术语及概念

在本章中,我们试图建立一个通用的术语来定义一个坚实的基础,用于交流 Akka 所针对的并发和分布式系统。请注意,对于这其中的许多术语,并没有一个统一的定义。我们试图给出将在 Akka 文档范围内使用的定义。

并发 vs. 并行

并发和并行是相关的概念,但有一些小的区别。并发意味着两个或多个任务正在取得进展,即使它们可能不会同时执行。例如,这可以通过时间切片来实现,其中部分任务按顺序执行,并与其他任务的部分混合。另一方面,当执行的任务可以真正同时进行时,就会出现并行。

异步 vs. 同步

如果调用者在方法返回值或引发异常之前无法取得进展,则认为方法调用是同步的。另一方面,异步调用允许调用者在有限的步骤之后继续进行,并且可以通过一些附加机制(它可能是已注册的回调、Future或消息)来通知方法的完成。

同步 API 可以使用阻塞来实现同步,但这不是必要的。CPU 密集型任务可能会产生类似于阻塞的行为。一般来说,最好使用异步 API,因为它们保证系统能够进行。Actor 本质上是异步的:Actor 可以在消息发送之后进行其他任务,而不必等待实际的传递发生。

非阻塞 vs. 阻塞

如果一个线程的延迟可以无限期地延迟其他一些线程,这就是我们讨论的阻塞。一个很好的例子是,一个线程可以使用互斥来独占使用一个资源。如果一个线程无限期地占用资源(例如意外运行无限循环),则等待该资源的其他线程将无法进行。相反,非阻塞意味着没有线程能够无限期地延迟其他线程。

非阻塞操作优先于阻塞操作,因为当系统包含阻塞操作时,系统的总体进度并不能得到很好的保证。

死锁 vs. 饥饿 vs. 活锁

当多个 Actor 在等待对方达到某个特定的状态以便能够取得进展时,就会出现死锁(Deadlock)。由于没有其他 Actor 达到某种状态(一个Catch-22问题),所有受影响的子系统都无法继续运行。死锁与阻塞密切相关,因为 Actor 线程能够无限期地延迟其他线程的进程。

在死锁的情况下,没有 Actor 可以取得进展,相反,当有 Actor 可以取得进展,但可能有一个或多个 Actor 不能取得进展时,就会发生饥饿(Starvation)。典型的场景是一个调度算法,它总是选择高优先级的任务而不是低优先级的任务。如果传入的高优先级任务的数量一直足够多,那么低优先级任务将永远不会完成。

活锁(Livelock)类似于死锁,因为没有 Actor 取得进展。不同之处在于,Actor 不会被冻结在等待他人进展的状态中,而是不断地改变自己的状态。一个示例场景是,两个 Actor 有两个相同资源可用时。他们每一个都试图获得资源,但他们也会检查对方是否也需要资源。如果资源是由另一个 Actor 请求的,他们会尝试获取该资源的另一个实例。在不幸的情况下,两个 Actor 可能会在两种资源之间“反弹(bounce)”,从不获取资源,但总是屈服于另一种资源。

竟态条件

当一组事件的顺序的假设可能被外部的非确定性(non-deterministic)因素影响时,我们称之为竟态条件(Race condition)。当多个线程具有共享可变状态时,常常会出现竟态条件,并且线程在该状态上的操作可能会交错进行,从而导致意外的行为。虽然这是一个常见的情况,但是共享状态不需要有竟态条件。例如,客户机向服务器发送无序数据包(如 UDP 数据报)P1P2。由于数据包可能通过不同的网络路由传输,因此服务器可能先接收到P2,然后接收到P1。如果消息不包含有关其发送顺序的信息,则服务器无法确定它们是以不同的顺序发送的。根据包(packets)的含义,这可能导致竟态条件。

  • 注释:Akka 提供的关于在给定的两个 Actor 之间发送的消息的唯一保证是,他们的顺序始终保持不变。详见「消息传递可靠性」。

非阻塞保证(进度条件)

如前几节所讨论的,阻塞是不可取的,原因有几个,包括死锁的危险和系统中吞吐量的降低。在下面的章节中,我们将讨论具有不同强度的各种非阻塞特性。

等待自由

如果保证每个调用都以有限的步骤完成,则方法是无等待的,即等待自由(wait-freedom)。如果一个方法是有界“无等待”的,那么步骤的数量有一个有限的上限。

根据这个定义,无等待方法永远不会被阻塞,因此不会发生死锁。此外,由于每个 Actor 都可以在有限的步骤之后(调用完成时)继续进行,因此无等待方法没有饥饿。

锁自由

锁自由(lock-freedom)比等待自由更弱。在无锁调用的情况下,某些方法以有限的步数完成可能导致无限的等待。这个定义意味着没有死锁的调用是不可能的。另一方面,某些调用以有限的步骤完成的保证不足以保证所有调用最终都完成。换句话说,锁自由不足以保证不发生饥饿。

障碍自由

障碍自由(obstruction-freedom)是本文讨论的最薄弱的非阻塞保证。如果一个方法在某个时间点之后独立执行(其他线程不执行任何步骤,例如:挂起),则该方法称为无障碍的,它以有限的步骤完成。所有锁自由对象都是无障碍的,但相反的情况通常是不正确的。

乐观并发控制(OCC)方法通常是无障碍的。OCC 方法是,每个 Actor 都试图在共享对象上执行其操作,但如果 Actor 检测到来自其他对象的冲突,则会回滚修改,并根据某些计划重试。如果有一个时间点,其中一个 Actor 是唯一的尝试者,那么操作将成功。

推荐文献

  • 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

英文原文链接Terminology, Concepts.