Exercise 3.45 · 习题

Exercise 3.45: Louis Reasoner thinks our
bank-account system is unnecessarily complex and error-prone now that deposits
and withdrawals aren’t automatically serialized. He suggests that
make-account-and-serializer should have exported the serializer (for use
by such procedures as serialized-exchange) in addition to (rather than
instead of) using it to serialize accounts and deposits as make-account
did. He proposes to redefine accounts as follows:

(define
(make-account-and-serializer balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((balance-serializer
(make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw)
(balance-serializer withdraw))
((eq? m 'deposit)
(balance-serializer deposit))
((eq? m 'balance)
balance)
((eq? m 'serializer)
balance-serializer)
(else (error "Unknown request:
MAKE-ACCOUNT"
m))))
dispatch))

Then deposits are handled as with the original make-account:

(define (deposit account amount)
((account 'deposit) amount))

Explain what is wrong with Louis’s reasoning. In particular, consider what
happens when serialized-exchange is called.

Implementing serializers

We implement serializers in terms of a more primitive synchronization mechanism
called a
mutex. A mutex is an object that supports two
operations—the mutex can be
acquired, and the mutex can be

released. Once a mutex has been acquired, no other acquire
operations on that mutex may proceed until the mutex is released. In our implementation, each
serializer has an associated mutex. Given a procedure p, the serializer
returns a procedure that acquires the mutex, runs p, and then releases
the mutex. This ensures that only one of the procedures produced by the
serializer can be running at once, which is precisely the serialization
property that we need to guarantee.

(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))

The mutex is a mutable object (here we’ll use a one-element list, which we’ll
refer to as a
cell) that can hold the value true or false. When the
value is false, the mutex is available to be acquired. When the value is true,
the mutex is unavailable, and any process that attempts to acquire the mutex
must wait.

Our mutex constructor make-mutex begins by initializing the cell
contents to false. To acquire the mutex, we test the cell. If the mutex is
available, we set the cell contents to true and proceed. Otherwise, we wait in
a loop, attempting to acquire over and over again, until we find that the mutex
is available. To release the
mutex, we set the cell contents to false.

(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-mutex 'acquire))) ; retry
((eq? m 'release) (clear! cell))))
the-mutex))
(define (clear! cell) (set-car! cell false))

Test-and-set! tests the cell and returns the result of the test. In
addition, if the test was false, test-and-set! sets the cell contents to
true before returning false. We can express this behavior as the following
procedure:

(define (test-and-set! cell)
(if (car cell)
true
(begin (set-car! cell true)
false)))

However, this implementation of test-and-set! does not suffice as it
stands. There is a crucial subtlety here, which is the essential place where
concurrency control enters the system: The test-and-set! operation must
be performed
atomically. That is, we must guarantee that, once a
process has tested the cell and found it to be false, the cell contents will
actually be set to true before any other process can test the cell. If we do
not make this guarantee, then the mutex can fail in a way similar to the
bank-account failure in Figure 3.29. (See Exercise 3.46.)

The actual implementation of test-and-set! depends on the details of how

our system runs concurrent processes. For example, we might be executing

concurrent processes on a sequential processor using a time-slicing mechanism

that cycles through the processes, permitting each process to run for a short

time before interrupting it and moving on to the next process. In that case,

test-and-set! can work by disabling time slicing during the testing and

setting. Alternatively, multiprocessing computers provide

instructions that support atomic operations directly in

hardware.

练习 3.45：Louis Reasoner 认为，既然存款和取款不再自动串行化，我们的银行账户系统如今变得不必要地复杂且容易出错。他建议 make-account-and-serializer 应当在使用串行器对账户存取款进行串行化的同时（而非取代），也将串行器导出（供 serialized-exchange 等过程使用）。他提议按如下方式重新定义账户：

(define
(make-account-and-serializer balance)
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance
(- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(let ((balance-serializer
(make-serializer)))
(define (dispatch m)
(cond ((eq? m 'withdraw)
(balance-serializer withdraw))
((eq? m 'deposit)
(balance-serializer deposit))
((eq? m 'balance)
balance)
((eq? m 'serializer)
balance-serializer)
(else (error "Unknown request:
MAKE-ACCOUNT"
m))))
dispatch))

然后按照原来的 make-account 方式处理存款：

(define (deposit account amount)
((account 'deposit) amount))

请解释 Louis 的推理有何错误。请特别考虑调用 serialized-exchange 时会发生什么。

实现串行器

我们用一种更基本的同步机制来实现串行器，这种机制称为互斥体 (mutex)。互斥体是一个支持两种操作的对象——互斥体可以被获取 (acquired)，也可以被释放 (released)。一旦某个互斥体被获取，对该互斥体的任何其他获取操作都必须等到它被释放后才能继续。在我们的实现中，每个串行器都有一个关联的互斥体。给定一个过程 p，串行器返回一个过程，该过程先获取互斥体，再运行 p，然后释放互斥体。这保证了由同一串行器产生的过程每次只有一个在运行，而这正是我们所需要的串行化性质。

(define (make-serializer)
(let ((mutex (make-mutex)))
(lambda (p)
(define (serialized-p . args)
(mutex 'acquire)
(let ((val (apply p args)))
(mutex 'release)
val))
serialized-p)))

互斥体是一个可变对象（这里我们用一个单元素的表来表示，称之为单元格 (cell)），它可以持有值 true 或 false。当值为 false 时，互斥体可被获取；当值为 true 时，互斥体不可用，任何试图获取该互斥体的进程都必须等待。

互斥体的构造函数 make-mutex 首先将单元格内容初始化为 false。要获取互斥体，我们检测单元格：若互斥体可用，则将单元格内容设为 true 并继续；否则在循环中反复尝试获取，直到发现互斥体可用为止。要释放互斥体，将单元格内容设为 false。

(define (make-mutex)
(let ((cell (list false)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-mutex 'acquire))) ; retry
((eq? m 'release) (clear! cell))))
the-mutex))
(define (clear! cell) (set-car! cell false))

Test-and-set! 检测单元格并返回检测结果。此外，若检测结果为 false，test-and-set! 在返回 false 之前将单元格内容设为 true。我们可以用以下过程表达这一行为：

(define (test-and-set! cell)
(if (car cell)
true
(begin (set-car! cell true)
false)))

然而，这一 test-and-set! 的实现本身并不充分。这里有一个关键的细节，也是并发控制进入系统的核心之处：test-and-set! 操作必须原子地 (atomically) 执行。也就是说，我们必须保证，一旦某个进程检测到单元格为 false，在任何其他进程检测该单元格之前，单元格内容会实际被设为 true。若不能做出这一保证，互斥体可能以类似图 3.29 中银行账户失效的方式失效（见练习 3.46）。

test-and-set! 的实际实现取决于我们的系统运行并发进程的具体方式。例如，我们可能在一台顺序处理器上通过时间片 (time-slicing) 机制执行并发进程，该机制循环遍历各进程，允许每个进程运行一小段时间后中断，再切换到下一个进程。在这种情况下，test-and-set! 可以通过在检测和设置期间禁用时间片来实现。另一种方式是，多处理器计算机直接在硬件层面提供支持原子操作的指令。