Read Section 3.4

Encompasses lectures 30, 31, 32

3.4 Describes the classic bank withdraw problem, where you have a condition before updating a value.

(define (withdraw amount)
  (if (>= balance amount)
    (begin
      (set! balance (- balance amount))
       balance)
    "Insufficient funds"))

If two processes that operate independenly (or two requests) interleave these if checks and set! calls, even in the same process, the if check can be true while the (- balance amount) is happening, but before the set!.

The obvious, but incredibly slow solution would be to introduce a lock, and require only one transaction happen at a time.

Alternatively, you could have some other logic that works regardless of order. The book describes a concept of a ‘serializer’, which uses a builtin parallel-execute which means only one of the defined functions can execute at a time. This is reminiscint of the actor model, and it works well if you have only one piece of shared data (like, one bank account).

However…

Multiple Shared Resources

Suppose you had to find the difference between two accounts for some reason, or add balance from one account to another. To do that, we’d have to expose the serializer somehow, and ‘hold locks’ on both accounts while we compute something.

To implement parallel-execute we need a mutex (TIL stands for “Mutual Exclusion”).

Acquire calls to a mutex must be done atomically. If the code was actually something like:

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

.. this falls into the same problem as before, where the condition check to (car cell) can be interleaved by two processes at the same time, meaning two different processes could try to acquire the same lock. The actual implementation of test-and-set! depends on the architecture, and ideally uses a hardware syscall. If not, we can use time-slicing, which requires that calls to acquire (or related concurrent code) are done by cycling through each process and giving them an opportunity to acquire.

One issue that happens here is what if two processes actually try to acquire at the same time. Some mechanism to resolve that (called an arbiter) is then needed, which is typically some sort of hardware device. There are different ways that arbiters resolve the situation, but the obvious one is round-robin or time-slicing (just closer to hardware, so its faster). There is no guarantee of the amount of time this might take, because which process acquires the lock is still a version of the two generals problem.

If improperly implemented, one can run into deadlocks, or incorrect state. More complex software paradigms (like the Actor System) forgoes some performance in favor of processing one request at a time. A more primitive version of that might assign unique identifiers to each acquire, so that when serializers/semaphores are checking who to allow, it can compare the ID.