Concurrency, Safely

In Java the lock and the data it protects are two things joined by a convention: a field is documented as protected by a monitor, and the convention lives in a comment and in the heads of the people who wrote the class. Go has the same arrangement with a sync.Mutex beside the variable. Rust's Mutex<T> is the nearest relative of what follows, because the data sits inside the lock and you cannot reach it without taking the lock. EK9 does that, and then does what none of the three does in the compiler: it reads your program for lock-ordering cycles and refuses to compile one. This chapter is about the shape that makes that possible, the rules the compiler enforces around it, and what it leaves alone.

What exists, and what does not

The whole concurrency surface of the language is small, and none of it looks like a thread:

MutexLock of T, a lock that owns a value of type T, entered with enter(...) or tryEnter(...);
MutexKey of T, the function enter calls while it holds the lock, with the locked value as lockedItem;
the stream stage | async, which runs each stream element on a virtual thread, and | call, which runs them on the caller's thread;
Signals, whose handlers run on the signal dispatcher's thread, and the handlers of TCP and HTTP, which run on the runtime's threads.

There is no Thread, no executor, no channel, no future or promise, no atomic, no semaphore and no sleep; ek9 -h thread says so: "no Thread class or manual thread management". The last bullet is worth reading twice. Code runs concurrently because the runtime started it somewhere, and the compiler knows every place it does, which is what the rules below are built on.

One lock over one record

Here is the program every concurrency chapter writes: eight workers each make 250 deposits into one shared tally. In Java it is a synchronized method or an AtomicLong. Here the tally is a record, the record sits under one lock inside a class, and the only way in is a key.

#!ek9
defines module book.concurrency.tally

  defines constant
    workerCount <- 8
    depositsPerWorker <- 250

  defines record

    Tally
      deposits <- 0
      total <- 0

      default operator

  defines class

    Ledger
      lockedTally <- MutexLock(Tally())

      deposit()
        -> amount as Integer
        depositor <- (amount) is MutexKey of Tally as function
          lockedItem.deposits += 1
          lockedItem.total += amount
        require lockedTally.enter(depositor)

      snapshot()
        <- rtn as Tally: Tally()
        reader <- (rtn) is MutexKey of Tally as function
          rtn :=: lockedItem
        require lockedTally.enter(reader)

      default operator ?

  defines function

    work() as abstract
      <- rtn as Integer?

  defines program

    SharedTally()
      stdout <- Stdout()
      ledger <- Ledger()

      workers <- List() of work
      for id in 1 ... workerCount
        worker <- (ledger, id) is work as function
          for n in 1 ... depositsPerWorker
            ledger.deposit(id)
          rtn: id
        workers += worker

      finished <- cat workers | async | sort | collect as List of Integer
      stdout.println(`workers finished: ${finished}`)
      stdout.println(`tally: ${ledger.snapshot()}`)

It prints:

workers finished: [1, 2, 3, 4, 5, 6, 7, 8]
tally: Tally(deposits=2000, total=9000)

Eight runs in a row printed the same two lines, and a race would have shown as a smaller total. The pieces, in the order you meet them:

lockedTally <- MutexLock(Tally()) is a field with an initialiser, the only place a MutexLock may be built. deposit makes a key, a dynamic function¹ that implements MutexKey of Tally and takes amount in its capture list, and hands it to enter. While enter runs the key it holds the lock; the key sees the record as lockedItem; and when the key ends, however it ends, enter releases. There is no unlock to forget and no try/finally to write. enter returns a Boolean, and require insists it was true.

snapshot shows how a value gets out. The key captures rtn and copies into it with :=:; a copy is a new object, so nothing outside the lock holds a reference to the locked one. The reason is below.

The workers are the other half. | async takes no function: each element of the stream is a zero-argument function, and results arrive in the order the calls finish, so the pipeline sorts them; Stream Pipelines in Depth has the whole rule.

Getting a result out of a key

Inside a key you carry a result out by mutating a captured variable, and the verb that mutates is :=:, not :. A capture is a copy of the reference (Dynamic Functions and Classes has the rule), so reassigning a captured variable with : points the key's own name at another object and the caller never sees it. This version of hasFunds compiles, and is wrong:

hasFunds()
  -> amount as Integer
  <- rtn as Boolean: false
  checker <- (amount, rtn) is MutexKey of Integer as function
    rtn: lockedItem >= amount
  require lockedBalance.enter(checker)

funds for 80: false

The balance is 100 and the request is for 80, so the answer should be true. The : pointed the key's own name for rtn at another object, and the Boolean the caller holds was never touched; the compiler accepts it without comment. The fix is rtn :=: lockedItem >= amount, which changes the one object both names share. The compiler does stop the nearby mistake, assigning lockedItem itself out of the lock, with E08258 (below).

You often do not need the lock

The program above shares one tally because it was written to. Nothing requires the sharing. Each worker can build its own subtotal and return it, and the pipeline hands the results to the thread that submitted them:

WorkerTotals()
  stdout <- Stdout()

  workers <- List() of work
  for id in 1 ... workerCount
    worker <- (id) is work as function
      subtotal <- 0
      for n in 1 ... depositsPerWorker
        subtotal += id
      rtn: subtotal
    workers += worker

  subtotals <- cat workers | async | sort | collect as List of Integer
  total <- Integer()
  cat subtotals > total
  stdout.println(`subtotals: ${subtotals}`)
  stdout.println(`total: ${total}`)

subtotals: [250, 500, 750, 1000, 1250, 1500, 1750, 2000]
total: 9000

There is no lock here because there is nothing to lock: subtotal belongs to the worker that made it. This is the nearest EK9 gets to Go's channels or to message passing, and ek9 -h MutexLock recommends it ("Prefer message-passing when possible"). The chapter's rules are for when you cannot.

What the compiler refuses

Each rule below is a compile-time error with its own code, and each has a program in this chapter that triggers it.

The race (E08251)

Take the first program and remove the ledger. Each worker captures the Tally itself and writes to it:

worker <- (tally, id) is work as function
  for n in 1 ... depositsPerWorker
    tally.deposits += 1
    tally.total += id
  rtn: id
workers += worker

EK9     : Error   : E08251: 'tally' on line 31 position 12: mutation of shared state must happen inside MutexLock.enter(...) — wrap the write in a MutexKey body
             See: ek9 -h E08251
EK9     : Error   : E08251: 'tally' on line 32 position 12: mutation of shared state must happen inside MutexLock.enter(...) — wrap the write in a MutexKey body
             See: ek9 -h E08251

Two conditions meet here: the tally is shared, because the creating thread still holds it, and the code writing to it runs on another thread. The compiler's own name for the second is "a concurrent entry point": the runtime starts the code on a thread of its own. That covers the functions of a pipeline containing async (the workers and every other stage in it), an HTTP service operation (each request has its own thread), a TCP or Signals handler, and everything those call, directly or not. A write to anything another thread can reach has to be inside a key. ek9 -h E08251 is the full list of what counts as shared and what does not (an object the concurrent code makes for itself, a copy, a re-pointed local, a line to Stdout).

One further route stops the same mistake earlier. A worker declared as pure cannot write to what it captured at all:

for id in 1 ... 3
  worker <- (tally, id) is work as pure function
    tally.deposits += 1
    rtn: id
  workers += worker

EK9     : Error   : E08120: '+=' on line 25 position 25: mutating variables is not allowed when scope is marked as 'pure'
             See: ek9 -h E08120

pure is enforced: a pure function may not reassign anything but its own return, may not mutate what it was handed, and may call only pure code. It is not "no side effects", and Operators and Pragmatic Purity, in Full has the rules. For concurrency the consequence is direct: a pure worker cannot write to what it captured, so it cannot be the writer in a race. The two checks are separate; this one is E08120, not E08251.

Lock order (E08252)

Two locks are not a problem. Two locks taken in opposite orders on two paths are. This CacheService nests the log inside the cache in refresh and the cache inside the log in audit:

refresh()
  -> entry as String
  log <- lockedLog

  logIt <- (entry) is MutexKey of List of String as function
    lockedItem += `refreshed ${entry}`

  cacheIt <- (entry, log, logIt) is MutexKey of List of String as function
    lockedItem += entry
    require log.enter(logIt)

  require lockedCache.enter(cacheIt)

audit()
  -> note as String
  cache <- lockedCache

  countCache <- () is MutexKey of List of String as function
    Stdout().println(`cache holds ${length lockedItem}`)

  logAudit <- (note, cache, countCache) is MutexKey of List of String as function
    lockedItem += note
    require cache.enter(countCache)

  require lockedLog.enter(logAudit)

EK9     : Error   : E08252: 'enter' on line 32 position 24: acquiring 'errors.depth.lockordercycle::lockedCache' while holding 'errors.depth.lockordercycle::lockedLog' participates in lock-order cycle: errors.depth.lockordercycle::lockedCache → errors.depth.lockordercycle::lockedLog → errors.depth.lockordercycle::lockedCache nested enter() on a different lock identity — potential deadlock from lock-order cycle
             See: ek9 -h E08252
EK9     : Error   : E08252: 'enter' on line 19 position 22: acquiring 'errors.depth.lockordercycle::lockedLog' while holding 'errors.depth.lockordercycle::lockedCache' participates in lock-order cycle: errors.depth.lockordercycle::lockedCache → errors.depth.lockordercycle::lockedLog → errors.depth.lockordercycle::lockedCache nested enter() on a different lock identity — potential deadlock from lock-order cycle
             See: ek9 -h E08252

The compiler builds one graph of "holding this, acquiring that" edges for the whole program and finds its cycles. Both edges are reported, and each message names the whole cycle. A single direction is not an error: evict in ConsistentOrder nests the log inside the cache just as refresh does, and that program compiles and runs.²

evict()
  -> entry as String
  log <- lockedLog

  logIt <- (entry) is MutexKey of List of String as function
    lockedItem += `evicted ${entry}`

  cacheIt <- (log, logIt) is MutexKey of List of String as function
    lockedItem :=: List() of String
    require log.enter(logIt)

  require lockedCache.enter(cacheIt)

["refreshed alpha", "evicted alpha"]

The fix for a real cycle is the one ek9 -h E08252 gives. Put both lists in one record under one lock; with only one lock there is no order to get wrong:

CacheService
  lockedState <- MutexLock(CacheState())

  refresh()
    -> entry as String
    refresher <- (entry) is MutexKey of CacheState as function
      lockedItem.entries += entry
      lockedItem.log += `refreshed ${entry}`
    require lockedState.enter(refresher)

  audit()
    -> note as String
    auditor <- (note) is MutexKey of CacheState as function
      lockedItem.log += `${note}: cache holds ${length lockedItem.entries}`
    require lockedState.enter(auditor)

  report()
    <- rtn as CacheState: CacheState()
    reader <- (rtn) is MutexKey of CacheState as function
      rtn :=: lockedItem
    require lockedState.enter(reader)

  default operator ?

CacheState(entries=["alpha", "beta"], log=["refreshed alpha", "refreshed beta", "nightly: cache holds 2"])

The record is the same idea as Tally. It costs you contention, since every operation on either list now takes the same lock, and it buys a program with nothing to order.

Across a thread boundary (E08253)

A MutexLock is reentrant on one thread: code that holds it can enter it again. Reentrancy does not cross threads. A key that holds the lock and then fans out to async workers, one of which enters the same lock, makes the worker wait for a holder that is waiting for the worker:

reindex <- (lockedIndex) is work as function
  bump <- () is MutexKey of Integer as function
    lockedItem += 1
  rtn: lockedIndex.enter(bump)

holdAndFanOut <- (reindex) is MutexKey of Integer as function
  stdout <- Stdout()
  workers <- [ reindex ]
  cat workers | async | map with toLine > stdout

require lockedIndex.enter(holdAndFanOut)

EK9     : Error   : E08253: 'enter' on line 19 position 25: 'lockedIndex...lockedIndex' (cross-thread of outer 'lockedIndex...lockedIndex'): same lock acquired across a thread boundary — inner acquire blocks waiting for outer holder; MutexLock reentrancy does not cross threads
             See: ek9 -h E08253

ek9 -h E08253 names three thread boundaries, TCP accept, Signals registration and | async, and the alternative, | call, which stays on the same thread where reentrancy is legal. The usual fix is to do the locked work before the boundary and pass a copy across it.

The dining philosophers (E08255)

Two locks of the same type, handed in by the caller, are the textbook ring deadlock, because the order depends on the arguments and not on the source. Here dine takes two forks and holds one while it takes the other; somewhere else a caller can pass them the other way round:

dine()
  ->
    leftFork as Fork
    rightFork as Fork

  eat <- () is MutexKey of Integer as function
    lockedItem += 1

  holdLeft <- (rightFork, eat) is MutexKey of Integer as function
    require rightFork.lock().enter(eat)

  require leftFork.lock().enter(holdLeft)

EK9     : Error   : E08255: 'enter' on line 25 position 33: nesting 'rightFork...forkLock' inside 'leftFork...forkLock' — same-type locks, caller-supplied, no provable acquisition order: two locks of the same type are nested but no consistent acquisition order can be statically proven — under some interleaving this will deadlock; protect the state under ONE lock over an owning record (and if the state is durable or shared across instances, a mutex cannot protect it — that is a transaction concern)
             See: ek9 -h E08255

The compiler refuses it outright. There is no ordered-acquire helper and no lock-ranking annotation to reach for: the compiler's answer is the same as before, one lock over an owning record.

Where a lock may live

The remaining rules say where a lock can exist, so that every enter can be traced to a lock the analysis can name. Four shapes are refused, and each refusal is one line:

locks <- List() of MutexLock of Integer

EK9     : Error   : E08254: 'List' on line 7 position 15: 'MutexLock of Integer' as type argument to 'List of type T': MutexLock cannot appear in a generic type parameter — move the lock to a class or component field
             See: ek9 -h E08254

lockedCount <- MutexLock(0)

EK9     : Error   : E08256: 'MutexLock' on line 7 position 21: MutexLock construction is only allowed as a field initialiser on a class or component
             See: ek9 -h E08256

names <- List() of String
lockedNames as MutexLock of List of String: MutexLock(names)

EK9     : Error   : E08257: 'MutexLock' on line 8 position 50: MutexLock(...) argument must be a fresh value — a literal or a constructor call (MutexLock(List() of Item) builds an empty payload; MutexLock(String(existing)) copies, but only for a type with a copy constructor - List and Dict have none); not a reference to existing state
             See: ek9 -h E08257

leak <- (escaped) is MutexKey of List of String as function
  escaped := lockedItem

EK9     : Error   : E08258: ':=' on line 12 position 18: data inside a MutexLock must be purely contained — assigning 'lockedItem' creates an external reference; use ':=:' (copy), ':~:' (merge), or ':^:' (replace) instead
             See: ek9 -h E08258

A lock may not be a type argument, so there is no list or dictionary of locks and no lock per key; it may not be built outside a field initialiser; its payload must be a fresh value, not a name for state something else holds; and the locked value cannot be assigned out of the key. The last two are what keep a reference to the payload from existing outside the lock. The per-key pattern a Java programmer reaches for, a ConcurrentHashMap of locks, is the one pattern those rules make impossible; the philosophy behind that is that a lock the compiler cannot name is a lock it cannot order.

What the compiler does not try to do

The compiler enforces its rules on the shapes it accepts. The deadlock check covers in-process lock-order cycles and cross-thread use of the same lock, on the shapes EK9 accepts, and nothing more: it does not try to prove anything about atomicity across separate enter calls, livelock, starvation or fairness, or hazards that live outside the process, such as a database or a message queue. The data-race rule is a separate check, E08251, and is the one above: it refuses a write to shared state outside a key where it can see one.

The first of those is the one that catches people, because it looks like it should be covered. Each enter is atomic; two of them in a row are not. This account checks that funds exist in one enter and takes them in another:

#!ek9
defines module book.concurrency.checkthenact

  defines constant
    withdrawal <- 80

  defines class

    Account
      lockedBalance <- MutexLock(100)

      hasFunds()
        -> amount as Integer
        <- rtn as Boolean: false
        checker <- (amount, rtn) is MutexKey of Integer as function
          rtn :=: lockedItem >= amount
        require lockedBalance.enter(checker)

      take()
        -> amount as Integer
        taker <- (amount) is MutexKey of Integer as function
          lockedItem :=: lockedItem - amount
        require lockedBalance.enter(taker)

      takeIfFunds()
        -> amount as Integer
        <- rtn as Boolean: false
        taker <- (amount, rtn) is MutexKey of Integer as function
          if lockedItem >= amount
            lockedItem :=: lockedItem - amount
            rtn :=: true
        require lockedBalance.enter(taker)

      balance()
        <- rtn as Integer: Integer()
        reader <- (rtn) is MutexKey of Integer as function
          rtn :=: lockedItem
        require lockedBalance.enter(reader)

      default operator ?

  defines program

    CheckThenAct()
      stdout <- Stdout()

      split <- Account()
      firstSeesFunds <- split.hasFunds(withdrawal)
      secondSeesFunds <- split.hasFunds(withdrawal)
      stdout.println(`both saw enough: ${firstSeesFunds and secondSeesFunds}`)
      split.take(withdrawal)
      split.take(withdrawal)
      stdout.println(`check and take apart: ${split.balance()}`)

      together <- Account()
      firstTaken <- together.takeIfFunds(withdrawal)
      secondTaken <- together.takeIfFunds(withdrawal)
      stdout.println(`check and take together: ${together.balance()}, taken ${firstTaken} then ${secondTaken}`)

both saw enough: true
check and take apart: -60
check and take together: 20, taken true then false

Both customers saw enough, both took 80, and the balance is -60. The program makes the bad interleaving happen on purpose, on one thread, so that it is reproducible; with real threads it happens when two of them land between the check and the take, which is the unlucky interleaving and not the usual one. No lock is misused, no cycle exists and the compiler is right to say nothing. The second account is the fix: takeIfFunds checks and takes inside one key, and the second customer is refused.

The cost

You cannot share a variable. Anything two threads both write has to live in a MutexLock, inside a class, behind methods that make keys; the key syntax is heavier than a synchronized block, and a result has to be copied out with :=:. You cannot keep a map of locks, build one where you need it, or hand a lock to whichever helper is convenient; the rule that the compiler can name every lock excludes some designs a Java or Go programmer would reach for first. And the fix the compiler offers for almost every refusal, one lock over a record, serialises operations that might have run in parallel. EK9 does not hide that cost. What it buys is that the failures you have read about, the unprotected counter, the two-lock cycle, the ring of philosophers, are errors at compile time and not intermittent faults in production.

A design note. I would rather refuse a program that is correct than accept one I cannot read in thirty seconds. If you have to think hard to convince yourself that a pattern of locking is safe, then it is only safe on the day you thought about it, and code under maintenance for years does not keep the argument that justified it. So the compiler does not ask for the argument. It asks for a shape where the answer is visible: one lock over one record, and a worker that returns its result. - Steve

Where this stops

The checks are an analysis of the shapes above, and where they stop is stated, not hidden: the two-call atomicity gap, the liveness hazards and the distributed ones are yours. Nothing here says a program is correct. It says that, in the shapes the compiler analyses, it found no lock-order cycle, no same lock entered across a thread, and no write to shared state outside a lock. A Web Service, Step by Step uses these rules on a repository behind a service, where every request is a concurrent entry point, and Networking: TCP and UDP meets the handlers that start the other threads.

The capture list (amount) and the is MutexKey of Tally as function form are covered in Dynamic Functions and Classes; for this chapter, a key is a function body that is handed lockedItem and the values in its capture list. ↩
The two locks in ConsistentOrder are declared with their type spelled out, lockedCache as MutexLock of List of String: MutexLock(List() of String), because <- cannot infer a lock over a generic payload (E04050). ↩