3.4.2 Mechanisms for Controlling Concurrency

We’ve seen that the difficulty in dealing with concurrent processes is rooted

in the need to consider the interleaving of the order of events in the

different processes. For example, suppose we have two processes, one with

three ordered events (

a

,

b

,

c

) and one with three ordered events

(

x

,

y

,

z

). If the two processes run concurrently, with no

constraints on how their execution is interleaved, then there are 20 different

possible orderings for the events that are consistent with the individual

orderings for the two processes:

我们已经看到，处理并发计算过程的困难根植于需要考虑不同计算过程中事件顺序的交错。例如，假设我们有两个计算过程，一个含有三个有序事件（a、b、c），另一个含有三个有序事件（x、y、z）。如果这两个计算过程并发运行，对它们的执行如何交错没有任何约束，那么与两个计算过程各自内部顺序一致的事件排列共有 20 种：

As programmers designing this system, we would have to consider the effects of

each of these 20 orderings and check that each behavior is acceptable. Such an

approach rapidly becomes unwieldy as the numbers of processes and events

increase.

作为设计这一系统的程序员，我们必须考虑这 20 种排列各自产生的效果，并确认每种行为都是可接受的。随着计算过程数和事件数的增加，这种方法很快就会变得难以应对。

A more practical approach to the design of concurrent systems is to devise

general mechanisms that allow us to constrain the interleaving of concurrent

processes so that we can be sure that the program behavior is correct. Many

mechanisms have been developed for this purpose. In this section, we describe

one of them, the

serializer.

Subheading: Serializing access to shared state

设计并发系统更为实用的方法，是设计通用机制，使我们能够约束并发计算过程的交错，从而确保程序行为的“正确”性。为此目的已开发出许多机制。本节介绍其中之一：串行化器 (serializer)。

子标题：对共享状态的串行化访问

Serialization implements the following idea: Processes will execute

concurrently, but there will be certain collections of procedures that cannot

be executed concurrently. More precisely, serialization creates distinguished

sets of procedures such that only one execution of a procedure in each

serialized set is permitted to happen at a time. If some procedure in the set

is being executed, then a process that attempts to execute any procedure in the

set will be forced to wait until the first execution has finished.

串行化实现了如下思想：各计算过程将并发执行，但存在某些过程的集合不允许并发执行。更精确地说，串行化创建若干特定的过程集合，规定在每个串行化集合中，每次只允许一个过程的一次执行发生。如果集合中某个过程正在执行，那么任何试图执行该集合中任意过程的计算过程，都将被迫等待，直到第一次执行完成为止。

We can use serialization to control access to shared variables. For example,

if we want to update a shared variable based on the previous value of that

variable, we put the access to the previous value of the variable and the

assignment of the new value to the variable in the same procedure. We then

ensure that no other procedure that assigns to the variable can run

concurrently with this procedure by serializing all of these procedures with

the same serializer. This guarantees that the value of the variable cannot be

changed between an access and the corresponding assignment.

Subheading: Serializers in Scheme

我们可以利用串行化来控制对共享变量的访问。例如，若要根据某个共享变量的当前值来更新它，可以将读取该变量当前值与将新值赋给该变量这两步操作放在同一个过程中，然后用同一个串行化器对所有可能对该变量赋值的过程进行串行化，从而确保没有其他赋值过程能与此过程并发运行。这保证了在一次读取与相应赋值之间，变量的值不会被改变。

子标题：Scheme 中的串行化器

To make the above mechanism more concrete, suppose that we have extended Scheme

to include a procedure called parallel-execute:

为使上述机制更加具体，假设我们已扩展了 Scheme，加入了一个名为 parallel-execute 的过程：

Each ⟨p⟩ must be a procedure of no arguments. Parallel-execute

creates a separate process for each ⟨p⟩, which applies

⟨p⟩ (to no arguments). These processes all run

concurrently.

As an example of how this is used, consider

每个 ⟨p⟩ 必须是一个无参数的过程。parallel-execute 为每个 ⟨p⟩ 创建一个独立的计算过程，并调用该 ⟨p⟩（不传入任何参数）。这些计算过程全部并发运行。作为其用法的示例，考虑下面的代码：

This creates two concurrent processes—P

1, which sets x to

x times x, and P

2, which increments x. After

execution is complete, x will be left with one of five possible values,

depending on the interleaving of the events of P

1 and P

2:

这将创建两个并发的计算过程——P₁ 将 x 设置为 x 乘以 x，P₂ 将 x 加一。执行完成后，x 将取五种可能值之一，具体取决于 P₁ 和 P₂ 各事件的交错方式：

We can constrain the concurrency by using serialized procedures, which are

created by

serializers. Serializers are constructed by

make-serializer, whose implementation is given below. A serializer

takes a procedure as argument and returns a serialized procedure that behaves

like the original procedure. All calls to a given serializer return serialized

procedures in the same set.

Thus, in contrast to the example above, executing

我们可以通过使用串行化过程来约束并发性，这些串行化过程由串行化器创建。串行化器由 make-serializer 构造，其实现见下文。串行化器以一个过程为参数，返回一个与原过程行为相同的串行化过程。对同一个串行化器的所有调用，均返回属于同一集合的串行化过程。因此，与上例不同，执行以下代码时：

can produce only two possible values for x, 101 or 121. The other

possibilities are eliminated, because the execution of P

1 and P

2

cannot be interleaved.

x 只能产生两种可能的值：101 或 121。其他可能性被排除，因为 P₁ 和 P₂ 的执行不再能够交错进行。

Here is a version of the make-account procedure from

3.1.1, where the deposits and withdrawals have been serialized:

下面是 3.1.1 节中 make-account 过程的一个版本，其中存款和取款操作已被串行化：

With this implementation, two processes cannot be withdrawing from or

depositing into a single account concurrently. This eliminates the source of

the error illustrated in Figure 3.29, where Peter changes the account

balance between the times when Paul accesses the balance to compute the new

value and when Paul actually performs the assignment. On the other hand, each

account has its own serializer, so that deposits and withdrawals for different

accounts can proceed concurrently.

有了这一实现，两个计算过程就不能同时对同一账户进行取款或存款。这消除了图 3.29 中所示错误的根源——Paul 在读取余额以计算新值和实际执行赋值之间，Peter 改变了账户余额。另一方面，每个账户都有自己的串行化器，因此对不同账户的存款和取款操作可以并发进行。