Skip to content

Instantly share code, notes, and snippets.

@michelf
Last active December 10, 2020 14:12
Show Gist options
  • Save michelf/bb2d61f994306b61e5c26e076e4a2418 to your computer and use it in GitHub Desktop.
Save michelf/bb2d61f994306b61e5c26e076e4a2418 to your computer and use it in GitHub Desktop.
Interlocking in A Hierarchy of Actors

A Hierarchy of Actors

This is an attempt to define an Actor system where some actors can make synchronous calls to others. It tries to keep blocking on the margins — where it is more tolerable — and to not allow anything that could cause deadlocks.

There are two basic rules to add to the current actor pitch:

  • Actors can have a parent actor chosen when initializing the actor.
  • A child actor can call synchronously methods of its parent actor.

A typical application could look like this. The Main thread actor has child task actors, which can have subtasks:

       Main
  +-----^-----+
  |           |
Task A      Task B
          +---^----+
          |        |
      Subtask C  Subtask D

@interlockable

A hierarchy is created by giving the @interlockable attribute to a let property of an actor class that is used as the parent:

actor class ChildTask {
   @interlockable let parent: SomeParentTask // also an actor class
}

The type of the property must be an actor class, but it can be optional, and it can be weak or unowned. It must also be a let to guaranty it'll never change after initialization: this also ensures there'll be no cycle. You can only use @interlockable inside an actor class.

interlock

The @interlockable property is blessed by the compiler to permit special calls. Since the parent is an actor, you normally have to use:

    await parent.method()

to call anything on it. You should still use it most of the time to avoid blocking. But since this property is @interlockable, you can also use:

    interlock parent.method()

which will "lock" the self during the call, preventing new partial tasks of this to be interleaved. This avoids the creation of a suspension point and ensures the state of our ChildTask will not change during the call. Because there's no suspension point allowed, interlock may only be used to call synchronous methods on the parent actor. It is also not possible to have both interlock and await in the same expression.

Since interlock enables synchronous access, you can use it to mutate properties and subscripts of the parent, or pass them as inout to other functions. This is allowed:

    interlock parent.someCounter += 1
    interlock self.mutatingMethod(&parent.someCounter)

The parent of an actor becomes a place where children can share common state.

When to Use

interlock should be used sparingly when you need to avoid a suspension point. For instance, an actor could purchase an item from its parent like this:

func buyFromParent(item: Item) {
    let price = await parent.price(for: item)
    guard let funds >= price else {
       throw SomeError.insufficientFunds
    }
    interlock try parent.purchase(item, at: price) // no suspension point here
    funds -= price // skipped when the purchase fails
}

Because interlock guaranties no interleaving of other partial tasks on this actor, you can deduct the funds after a successful purchase. Without interlock, you'd have to code more defensively so the last two lines can handle the case where multiple calls to buyFromParent are in flight:

func buyFromParent(item: Item) {
    let price = await parent.price(for: item)
    guard let funds >= price else {
       throw SomeError.insufficientFunds
    }
    funds -= price // take the funds here so interleaved tasks know they are not available
    do {
       await try parent.purchase(item, at: price) // suspension point here
    } catch {
       funds += price // put back the money in the funds
    }
}

While this defensive coding protects an invariant where funds >= 0, it can lead to racy results. If your actor has funds to purchase only one item but tries to purchase two, and if the first purchase throws for some reason, the second purchase might also fail due to insufficient funds if by chance it is executed in the time window where the funds have been temporarily removed. This race does not exist with interlock.

Blocking-Free Where it Counts the Most

In a UI application, blocking the main thread will cause the UI to become unresponsive, so blocking should to be avoided. Since the Main actor sits at the top of the hierarchy, it has no parent and can never lock itself while calling another actor.

Deadlock-Free

Locking is often known to cause deadlocks. This occurs when creating a cycle: A blocks waiting for B while B blocks waiting for A; both are waiting on each other and will wait forever. The cycle can have more participants, but the result is the same. Deadlocks often depends on timing and can be hard to reproduce.

With the interlockable hierarchy there is no cycle possible. An actor can only interlock with its parent, and the parent can interlock with its own parent, but a parent can never interlock with a child or another arbitrary actor. If we were to allow parents to interlock with their children, cycles could be formed. So we're not allowing that.

This is also why async methods cannot be called within interlock. A cycle would be formed if a child is locked while calling a parent and that parent decides to call an async method on the same child: it would wait forever for the child to unlock.

Inconsequential Suspension Points

Note that when we say interlock locks the actor, it must only suspend running partial tasks of this particular actor. If multiple actors are running on the same thread or queue, the executor must be able to to continue running their partial tasks. An interlocking implementation that blocks the thread is problematic unless you can guaranty only one actor is using the thread. How this is implemented is decided by the executor.

One way this could be implemented would be this equivalence:

    interlock parent.method()
    // same thing as:
    self.suspendRunningPartialTasks = true
    await parent.method()
    self.suspendRunningPartialTasks = false

where the executor honors the suspendRunningPartialTasks flag of an actor by not running its queued partial tasks.

With this implementation, interlock might still create a suspension point, but this suspension point has no consequence on the actor state since it does not allow interleaving. From the actor's point of view, it's as if there was no suspension point.

init & deinit

It is not clear to me a the moment if the initializer and deinitializer of an actor class are running within the actor's execution context or not. Assuming they runs from the actor's execution context, the usual rules for interlock apply.

However, if they do not run from the actor's execution context, then we may need to prevent an interlock during init and deinit which will necessitate a new set of rules.

Complex Interlockable Graphs

To prevent deadlocks, all you need is to ensure there is no locking cycle. A tree is obviously cycle-free, but more arbitrary graphs can be free of cycles too. Something like this:

       Main
  +-----^-----+
  |           |
Task A      Task B      Database
          +---^----+ +-----^
          |        | |
      Subtask C  Subtask D

Or like this (since this is a directed graph):

       Main
  +-----^-----+------------+ 
  |           |            |  
Task A      Task B      Database
          +---^----+ +-----^                    
          |        | |
      Subtask C  Subtask D

Actors are guarantied to be free of cycles because the @interlockable forces the property to be a let. You can't express a cycle with only let properties.

This latest graph is interesting though: Subtask D has two paths to Main. Because it's hard to guaranty a locking order in those circumstances, and also to avoid the need for recursive locks, interlock does not permit synchronous access to both parents at the same time. This is allowed inside Subtask D:

    let record = interlock databaseActor.records[1234]
    interlock taskBActor.fetched.append(record)
    // one interlocked actor at a time

And this is not:

    interlock taskBActor.fetchedRecords.append(databaseActor.records[1234])
    // error: can only interlock with one actor at a time

Alternatives Considered

No interlock keyword

We could allow synchronous access to the parent directly with no keyword:

    parent.someCounter += 1

This looks like a synchronous call, and that's effectively what it is. But it also hides the cost that our actor is locking itself while calling another actor.

wait instead of interlock

This reads well and somewhat mimics the well known wait() multithreading primitive:

    wait parent.someCounter += 1

But it's too close to await for confort in regard to meaning, pronunciation, and spelling. wait is also a commonly used identifier so it'd create confusion and ambiguities.

Get rid of @interlockable as it's not actually needed!

Did I mention you can't create a cycle with only let references?

We could get rid of the @interlockable attribute and allow interlock to work with any let property of an actor.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment