Structure and Interpretation of Computer Programs (60 page)

(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) withdraw)
            ((eq? m 'deposit) deposit)
            ((eq? m 'balance) balance)
            ((eq? m 'serializer) balance-serializer)
            (else (error "Unknown request -- MAKE-ACCOUNT"
                         m))))
    dispatch))

We can use this to do serialized deposits and withdrawals. However,
unlike our earlier serialized account, it is now the responsibility of
each user of bank-account objects to explicitly manage the
serialization, for example as follows:
⁴³

(define (deposit account amount)
  (let ((s (account 'serializer))
        (d (account 'deposit)))
    ((s d) amount)))

Exporting the serializer in this way gives us enough flexibility to
implement a serialized exchange program. We simply
serialize the original
exchange
procedure with the serializers for both accounts:

(define (serialized-exchange account1 account2)
  (let ((serializer1 (account1 'serializer))
        (serializer2 (account2 'serializer)))
    ((serializer1 (serializer2 exchange))
     account1
     account2)))

Exercise 3.43.
  Suppose that the balances in three accounts start out as $10, $20,
and $30, and that multiple processes run, exchanging the balances in
the accounts. Argue that if the processes are run sequentially,
after any number of concurrent exchanges, the account balances should be
$10, $20, and $30 in some order.
Draw a timing diagram like the one in figure 
3.29
to
show how this condition can be violated if the exchanges are
implemented using the first version of the account-exchange program in
this section. On the other hand, argue that even with this
exchange
program, the sum of the balances in the accounts will be
preserved. Draw a timing diagram to show how even this condition would
be violated if we did not serialize the transactions
on individual accounts.

Exercise 3.44.
  
Consider the problem of transferring an amount from one account to
another. Ben Bitdiddle claims that this can be accomplished with the
following procedure, even if there are multiple people concurrently
transferring money among multiple accounts, using any account
mechanism that serializes deposit and withdrawal transactions, for
example, the version of
make-account
in the text above.

(define (transfer from-account to-account amount)
  ((from-account 'withdraw) amount)
  ((to-account 'deposit) amount))

Louis Reasoner claims that there is a problem here, and that we need
to use a more sophisticated method, such as the one required for
dealing with the exchange problem. Is Louis right? If not, what is
the essential difference between the transfer problem and the exchange
problem? (You should assume that the balance in
from-account
is at least
amount
.)

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.

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.
⁴⁷

Exercise 3.46.
  Suppose that we implement
test-and-set!
using an ordinary
procedure as shown in the text, without attempting to make the operation
atomic. Draw a timing diagram like the one in
figure 
3.29
to demonstrate how the mutex
implementation can fail by allowing two processes to acquire the mutex
at the same time.

Exercise 3.47.
  
A semaphore (of size
n
) is a generalization of a mutex. Like a
mutex, a semaphore supports acquire and release operations, but it is
more general in that up to
n
processes can acquire it
concurrently. Additional processes that attempt to acquire the
semaphore must wait for release operations. Give implementations of
semaphores

a. in terms of mutexes

b. in terms of atomic
test-and-set!
operations.

Now that we have seen how to implement serializers, we can see
that account exchanging still has a problem, even with the
serialized-exchange
procedure above.
Imagine that Peter attempts to exchange
a
1
with
a
2 while Paul concurrently attempts to exchange
a
2
with
a
1. Suppose that Peter's process reaches the point where
it has entered a serialized procedure protecting
a
1 and, just
after that, Paul's process enters a serialized procedure protecting
a
2. Now Peter cannot proceed (to enter a serialized procedure
protecting
a
2) until Paul exits the serialized procedure
protecting
a
2. Similarly, Paul cannot proceed until Peter exits
the serialized procedure protecting
a
1. Each process is stalled
forever, waiting for the other. This situation is called a
deadlock
. Deadlock is always a danger in systems that provide
concurrent access to multiple shared resources.

One way to avoid the deadlock in this situation is to give each
account a unique identification number and rewrite
serialized-exchange
so
that a process will always attempt to enter a procedure protecting the
lowest-numbered account first. Although this method works well for
the exchange problem, there are other situations that require more
sophisticated deadlock-avoidance techniques, or where deadlock cannot
be avoided at all. (See exercises 
3.48
and 
3.49
.)
⁴⁸

Exercise 3.48.
  
Explain in detail why the deadlock-avoidance method described above,
(i.e., the accounts are numbered, and each process attempts to acquire
the smaller-numbered account first) avoids deadlock in the exchange
problem. Rewrite
serialized-exchange
to incorporate this idea.
(You will
also need to modify
make-account
so that each account is created
with a number, which can be accessed by sending an appropriate
message.)

Exercise 3.49.
  Give a scenario where the deadlock-avoidance mechanism described
above does not work. (Hint: In the exchange problem, each process
knows in advance which accounts it will need to get access to. Consider a
situation where a process must get access to some shared resources before it
can know which additional shared resources it will require.)

We've seen how programming concurrent systems requires controlling the
ordering of events when different processes access shared
state, and we've seen how to achieve this control through judicious
use of serializers. But the problems of concurrency
lie deeper than this, because, from a fundamental point of view, it's
not always clear what is meant by “shared state.”

Mechanisms such as
test-and-set!
require processes to examine a
global shared flag at arbitrary times. This is problematic and
inefficient to implement in modern high-speed processors, where
due to optimization techniques such as pipelining and cached memory,
the contents of memory
may not be in a consistent state at every instant. In contemporary
multiprocessing systems, therefore, the serializer paradigm is being
supplanted by new approaches to concurrency control.
⁴⁹

The problematic aspects of shared state also arise
in large, distributed systems. For
instance, imagine a
distributed banking system where individual branch banks maintain
local values for bank balances and periodically compare these with
values maintained by other branches. In such a system the value of
“the account balance” would be undetermined, except right after
synchronization.
If Peter deposits money in an account he holds
jointly with Paul, when should we say that the account balance has
changed – when the balance in the local branch changes, or not until
after the synchronization?
And if Paul accesses the account from a
different branch, what are the reasonable constraints to place on the
banking system such that the behavior is “correct”?
The only thing that might matter for
correctness is the behavior observed by Peter and Paul individually
and the “state” of the account immediately after synchronization.
Questions about the
“real” account balance or the order of events between synchronizations
may be irrelevant or meaningless.
⁵⁰