3.4.1 The Nature of Time in Concurrent Systems

On the surface, time seems straightforward. It is an ordering imposed on

events. For any events A and B, either A occurs before B,

A and B are simultaneous, or A occurs after B. For instance,

returning to the bank account example, suppose that Peter withdraws $10 and

Paul withdraws $25 from a joint account that initially contains$100, leaving

$65 in the account. Depending on the order of the two withdrawals, the

sequence of balances in the account is either $100 →$90 → $65 or$100 → $75

→ $65. In a computer implementation of the banking system, this changing

sequence of balances could be modeled by successive assignments to a variable

balance.

表面上，时间似乎是直观的：它是施加在事件之上的一种顺序关系。对于任意事件 A 与 B，要么 A 发生在 B 之前，要么 A 与 B 同时发生，要么 A 发生在 B 之后。例如，回到银行账户的例子：假设 Peter 取款 10 美元，Paul 取款 25 美元，两人共享一个初始余额为 100 美元的账户，最终账户余额为 65 美元。根据两次取款的顺序不同，账户余额的变化序列要么是 $100 →$90 → $65，要么是$100 → $75 →$65。在银行系统的计算机实现中，这一不断变化的余额序列可以用对变量 balance 的连续赋值来建模。

In complex situations, however, such a view can be problematic. Suppose that

Peter and Paul, and other people besides, are accessing the same bank account

through a network of banking machines distributed all over the world. The

actual sequence of balances in the account will depend critically on the

detailed timing of the accesses and the details of the communication among the

machines.

然而，在复杂的情形下，这种观点可能会引发问题。假设 Peter、Paul 以及其他人，通过遍布全球的银行机器网络访问同一个银行账户。账户余额的实际变化序列将严格依赖于各次访问的精确时序，以及各机器之间通信的细节。

This indeterminacy in the order of events can pose serious problems in the

design of concurrent systems. For instance, suppose that the withdrawals made

by Peter and Paul are implemented as two separate processes sharing a common

variable balance, each process specified by the procedure given in

3.1.1:

事件顺序的这种不确定性，在并发系统的设计中可能造成严重问题。例如，假设 Peter 和 Paul 的取款操作被实现为两个独立的计算过程，它们共享公共变量 balance，每个计算过程由 3.1.1 节中给出的过程来描述：

If the two processes operate independently, then Peter might test the

balance and attempt to withdraw a legitimate amount. However, Paul

might withdraw some funds in between the time that Peter checks the

balance and the time Peter completes the withdrawal, thus invalidating

Peter’s test.

Things can be worse still. Consider the expression

如果两个计算过程独立运行，那么 Peter 可能检查余额并尝试取出一个合法金额。然而，Paul 可能在 Peter 检查余额之后、Peter 完成取款之前取走了一些钱，从而使 Peter 的检查结果失效。情况还可能更糟。考虑下面这个表达式：

executed as part of each withdrawal process. This consists of three steps: (1)

accessing the value of the balance variable; (2) computing the new

balance; (3) setting balance to this new value. If Peter and Paul’s

withdrawals execute this statement concurrently, then the two withdrawals might

interleave the order in which they access balance and set it to the new

value.

该语句作为每个取款计算过程的一部分被执行，包含三个步骤：（1）读取变量 balance 的当前值；（2）计算新的余额；（3）将 balance 设置为新值。如果 Peter 和 Paul 的取款操作并发地执行这条语句，那么两次取款对 balance 的读取和设置操作的顺序可能会交错进行。

The timing diagram in Figure 3.29 depicts an order of events where

balance starts at 100, Peter withdraws 10, Paul withdraws 25, and yet

the final value of balance is 75. As shown in the diagram, the reason

for this anomaly is that Paul’s assignment of 75 to balance is made

under the assumption that the value of balance to be decremented is 100.

That assumption, however, became invalid when Peter changed balance to

90. This is a catastrophic failure for the banking system, because the total

amount of money in the system is not conserved. Before the transactions, the

total amount of money was $100. Afterwards, Peter has$10, Paul has $25, and

the bank has $75.

图 3.29 的时序图描绘了一种事件顺序：balance 初始为 100，Peter 取款 10，Paul 取款 25，而 balance 的最终值却是 75。如图所示，出现这一异常的原因在于：Paul 将 balance 赋值为 75 时，是基于 balance 待减少的值为 100 这一假设。然而，当 Peter 将 balance 改为 90 之后，这一假设便已不再成立。这对银行系统而言是灾难性的错误，因为系统中的资金总量并未得到守恒。交易前，资金总量为 100 美元；交易后，Peter 拥有 10 美元，Paul 拥有 25 美元，银行账户中有 75 美元。

Figure 3.29: Timing diagram showing how interleaving the order of events in two banking withdrawals can lead to an incorrect final balance.

图 3.29：时序图，展示了两次银行取款中事件顺序的交错如何导致错误的最终余额。

The general phenomenon illustrated here is that several processes may share a

common state variable. What makes this complicated is that more than one

process may be trying to manipulate the shared state at the same time. For the

bank account example, during each transaction, each customer should be able to

act as if the other customers did not exist. When a customer changes the

balance in a way that depends on the balance, he must be able to assume that,

just before the moment of change, the balance is still what he thought it was.

Subheading: Correct behavior of concurrent programs

这里所说明的一般现象是：多个计算过程可能共享同一个公共状态变量。使情况变得复杂的，是多个计算过程可能同时试图操纵这一共享状态。在银行账户的例子中，每次交易期间，每位客户都应能像其他客户不存在一样独立地进行操作。当某位客户以依赖于余额的方式改变余额时，他必须能够假定：就在改变的那一刻之前，余额仍然是他所预期的值。

子标题：并发程序的“正确”行为

The above example typifies the subtle bugs that can creep into concurrent

programs. The root of this complexity lies in the assignments to variables

that are shared among the different processes. We already know that we must be

careful in writing programs that use set!, because the results of a

computation depend on the order in which the assignments occur. With concurrent processes we must be especially careful

about assignments, because we may not be able to control the order of the

assignments made by the different processes. If several such changes might be

made concurrently (as with two depositors accessing a joint account) we need

some way to ensure that our system behaves correctly. For example, in the case

of withdrawals from a joint bank account, we must ensure that money is

conserved. To make concurrent programs behave correctly, we may have to place

some restrictions on concurrent execution.

上述例子典型地说明了并发程序中可能潜入的隐蔽错误。这种复杂性的根源在于对不同计算过程之间共享变量的赋值操作。我们已经知道，在编写使用 set! 的程序时必须小心，因为计算结果依赖于赋值发生的顺序。对于并发的计算过程，我们必须格外关注赋值问题，因为我们可能无法控制不同计算过程所进行的赋值操作的顺序。如果可能有若干此类修改同时发生（如两位存款人同时访问一个联名账户），我们就需要某种方式来确保系统行为的“正确”性。例如，在从联名银行账户取款的情形中，我们必须确保资金守恒。为了使并发程序的行为“正确”，我们可能不得不对并发执行施加某些限制。

One possible restriction on concurrency would stipulate that no two operations

that change any shared state variables can occur at the same time. This is an

extremely stringent requirement. For distributed banking, it would require the

system designer to ensure that only one transaction could proceed at a time.

This would be both inefficient and overly conservative. Figure 3.30

shows Peter and Paul sharing a bank account, where Paul has a private account

as well. The diagram illustrates two withdrawals from the shared account (one

by Peter and one by Paul) and a deposit to Paul’s private account. The two withdrawals from the

shared account must not be concurrent (since both access and update the same

account), and Paul’s deposit and withdrawal must not be concurrent (since both

access and update the amount in Paul’s wallet). But there should be no problem

permitting Paul’s deposit to his private account to proceed concurrently with

Peter’s withdrawal from the shared account.

对并发性施加的一种可能限制是：规定任何改变共享状态变量的两个操作都不能同时发生。这是一项极为严格的要求。对于分布式银行系统而言，这将要求系统设计者确保每次只有一笔交易能够进行，既低效又过于保守。图 3.30 展示了 Peter 和 Paul 共享一个银行账户的情形，其中 Paul 还有一个私人账户。图中说明了两次从共享账户的取款（一次由 Peter 发起，一次由 Paul 发起）以及向 Paul 私人账户的一次存款。从共享账户发起的两次取款不能并发（因为两者都访问并更新同一账户），Paul 的存款和取款也不能并发（因为两者都访问并更新 Paul 钱包中的金额）。但 Paul 向私人账户存款与 Peter 从共享账户取款并发进行，则不应存在任何问题。

Figure 3.30: Concurrent deposits and withdrawals from a joint account in Bank1 and a private account in Bank2.

图 3.30：从 Bank1 的联名账户和 Bank2 的私人账户并发存取款的示意图。

A less stringent restriction on concurrency would ensure that a concurrent

system produces the same result as if the processes had run sequentially in

some order. There are two important aspects to this requirement. First, it

does not require the processes to actually run sequentially, but only to

produce results that are the same as if they had run sequentially. For

the example in Figure 3.30, the designer of the bank account system can

safely allow Paul’s deposit and Peter’s withdrawal to happen concurrently,

because the net result will be the same as if the two operations had happened

sequentially. Second, there may be more than one possible “correct” result

produced by a concurrent program, because we require only that the result be

the same as for some sequential order. For example, suppose that Peter

and Paul’s joint account starts out with $100, and Peter deposits$40 while

Paul concurrently withdraws half the money in the account. Then sequential

execution could result in the account balance being either $70 or$90 (see

Exercise 3.38).

对并发性施加一种较宽松的限制，可以确保并发系统产生的结果与各计算过程按某种顺序顺序执行时相同。这一要求有两个重要方面。第一，它并不要求各计算过程真正顺序执行，只要求产生的结果与顺序执行时相同即可。对于图 3.30 中的例子，银行账户系统的设计者可以安全地允许 Paul 的存款和 Peter 的取款并发进行，因为最终结果与两个操作顺序执行时相同。第二，并发程序产生的“正确”结果可能不止一种，因为我们只要求结果与某种顺序执行的结果相同即可。例如，假设 Peter 和 Paul 的联名账户初始余额为 100 美元，Peter 存入 40 美元的同时 Paul 取出账户中一半的钱。那么顺序执行的结果可能使账户余额为 70 美元或 90 美元（见练习 3.38）。

There are still weaker requirements for correct execution of concurrent

programs. A program for simulating diffusion (say, the flow of heat in an

object) might consist of a large number of processes, each one representing a

small volume of space, that update their values concurrently. Each process

repeatedly changes its value to the average of its own value and its neighbors’

values. This algorithm converges to the right answer independent of the order

in which the operations are done; there is no need for any restrictions on

concurrent use of the shared values.

对于并发程序“正确”执行的要求还可以更弱。一个模拟扩散过程（例如物体中的热流）的程序，可能由大量计算过程组成，每个计算过程代表一小块空间体积，并发地更新各自的值。每个计算过程反复将自身的值替换为其自身与邻居值的平均值。这一算法收敛到“正确”答案，与操作执行的顺序无关；无需对共享值的并发使用施加任何限制。