3.4 Concurrency: Time Is of the Essence⁠

• The power of stateful computational objects comes at a price: the loss of referential transparency.
• This gives rise to a thicket of questions about sameness and change, and we had to create a more intricate evaluation model.
• The central issue is that by introducing assignment we are forced to admit time in the computational model.
• We can go further in structuring the model to match the world: in the physical world, we perceive simultaneous changes.
• We want computational processes executing concurrently.
• Writing programs this way forces us to avoid inessential timing constraints, making the program more modular.
• It can also provide a speed advantage on multicore computers.
• The complexities introduced by assignment become even more problematic in the presence of concurrency.

# 3.4.1 The Nature of Time in Concurrent Systems⁠

• On the surface, time is straightforward: it is an ordering.
• Two events either occur in one order, or the other, or simultaneously.
• Consider (set! balance (- balance amount)). There are three steps: accessing the value of balance, computing the new balance, and setting balance to this value.
• Two such expressions executed concurrently on the same balance variable could have their three steps interleaved.
• The general problem is that, when concurrent processes share a state variable, they may try to change it at the same time.

To quote some graffiti seen on a Cambridge building wall: “Time is a device that was invented to keep everything from happening at once.” (Footnote 3.35)

# Correct behavior of concurrent programs

• We already know we have to be careful about order with set!.
• With concurrent programs we must be especially careful.
• A very stringent restriction to ensure correctness: disallow changing more than one state variable at a time.
• A less stringent restriction: to ensure that the system produces the same result as if the processes had run sequentially in some order (we don’t specify a particular order).
• Concurrent programs are inherently nondeterministic, because we don’t what order of execution its result is equivalent to, so there is a set of possible values it could take.

# 3.4.2 Mechanisms for Controlling Concurrency⁠

• If one process has three ordered events $(a,b,c)$ and another, running concurrently, has three ordered events $(x,y,z)\htmlClass{math-punctuation}{\text{,}}$ then there are twenty ways of interleaving them.
• The programmer would have to consider the results in all twenty cases to be confident in the program.
• A better approach is to use mechanisms to constrain interleaving to ensure correct behavior.

# Serializing access to shared state

• Serialization groups procedures into sets such and prevents multiple procedures in the same set from executing concurrently.
• We can use this to control access to shared variables.
• Before, assignments based on a state variables current value were problematic. We could solve this with the set {get-value, set-value!, and swap-value!} where the latter is defined like so:

(define (swap-value! f)
  (set-value! (f (get-value))))

# Serializers in Scheme

• Suppose we have a procedure parallel-execute that takes a variable number of arguments that are procedures of no arguments, and executes them all concurrently.
• We construct serializers with (make-serializer).
• A serializer takes a procedure as its argument and returns a serialized procedure that behaves like the original.
• Calls to the same serializer return procedures in the same set.

# Complexity of using multiple shared resources

• Serializers are powerful, and easy to use for one resource.
• Things get much more difficult with multiple shared resources.
• Suppose we want to swap the balances in two bank accounts:

(define (exchange acc1 acc2)
  (let ((diff (- (acc1 'balance) (acc2 'balance))))
    ((acc1 'withdraw) diff)
    ((acc2 'deposit) diff)))

• Serializing deposits and withdrawals themselves is not enough to ensure correctness.
• The exchange comprises four individually serialized steps, and these may interleave with a concurrent process.
• One solution is to expose the serializer from make-account, and use that to serialize the entire exchanging procedure.
• We would have to manually serialize deposits, but this would give us the flexibility to serialize the exchanging procedure.

# Implementing serializers

• Serializers are implemented in terms of the primitive mutex.
• A mutex can be acquired and it can be released.
• Once acquired, no other acquire operations can proceed until the mutex is released.
• Each serializer has an associated mutex.
• A serialized procedure (created with (s proc) where s is a serializer) does the following when it is run:
  • acquire the mutex,
  • run the procedure proc,
  • release the mutex.
• The mutex is a mutable object, represented by a cell (a one-element list). It holds a boolean value, indicating whether or not it is currently locked.
• To acquire the mutex, we test the cell. We wait until it is false, then we set it to true and proceed.
• To release the mutex, we set its contents to false.

# Deadlock

• Even with a proper implementation of mutexes and serializers, we still have a problem with the account exchanging procedure.
• We serialize the whole procedure with both accounts so that an account may only participate in one exchange at a time.
• There are two mutexes, so it is possible for something to happen in between acquiring the first and the second.
• If we exchange a1 with a2 and concurrently do the reverse exchange, it is possible for the first process to lock a1 and the second process to lock a2.
• Now both need to lock the other, but they can’t. This situation is called deadlock.
• In this case, we can fix the problem by locking accounts in a particular order based on a unique identifier.
• In some cases, it is not possible to avoid deadlock, and we simply have to “back out” and try again.

# Concurrency, time, and communication

• Concurrency can be tricky because it’s not always clear what is meant by “shared state.”
• It also becomes more complicated in large, distributed systems.
• The notion of time in concurrency control must be intimately linked to communication.
• There are some parallels with the theory of relativity.