Notes on Concurrency

General
1

This post summarizes parts of a conversation that occurred on Discord. I am not the author of any of the commentary. I am posting it here because I liked the discussion and I don't want it lost in unsearchable Discord history.

Patterns of Composition

I've thought about this a lot over the years and the conclusion I reached is that there's two patterns of composition for two concurrent operations a and b :

  • exclusive choice, where exactly one of a or b happens and it's whichever is ready to happen first

  • product, where both happen and if one fails the other is cancelled and synchronizable events with non-cooperative threads work perfectly for the former but the latter is better served by cooperative concurrency.

Discussion

  1. i always thought that the advantage of synchronizable events is that they graceful handle cancellation in a way that some other concurrency systems dont; i remember playing with channels in ocaml's eio and getting into situations where "racing" two channels picks one but the cancellation request to the other fails to prevent it from consuming a message
  2. the problem is that there's no way to combine two events into a compound event that preserves the exclusive-or guarantee of sync
  3. isn't that what choice-evt is? but it requires your operations to be events all the way down which can be difficult to do
  4. by "compound event" I mean combining two events into a single event where syncing on it syncs on both input events, not exactly one of them, so like (zip-event f e1 e2) applicative functor composition
  5. sync events are bad at doing this?
  6. yes. they cannot do it correctly.

Example

Suppose there are lock objects that count as synchronizable events, and syncing on them acquires the lock. then consider this operation:

(sync (zip-evt list lock1 lock2)
      lock3)

It is possible that this code acquires lock1 , then acquires lock3 and selects the lock3 events as the result of sync .... and the "negative acknowledgment" event for lock1 never fires. So the code could silently acquire lock1 without realizing it.

The issue is that exactly one of these two things happens:

  • lock1 gets acquired
  • the nack for lock1 becomes ready

Just because lock1 is ready, doesn't mean lock2 is ready. there's no way to tell lock1 to "wait" until lock2 is also ready. the only thing zip-evt can do is try to sync on both, then use its own nack to manually undo the lock acquisition if one lock gets acquired but the other doesn't. this isn't particularly composable, since the event interface doesn't expose a general way to "undo" an event that's already happened. It only guarantees that only one event can happen at once.

There's a variant of concurrent ML that lets you make events with transactions and rollback semantics, but it's much more complex and not as fast.

Misc

Suggestion: see a join calculus tutorial for exploration of the space.

Conclusion

Question: what does that mean for a casual sync user?

Answer: it means you shouldn't try to make your own custom events which try to wait on multiple sub-events to all complete. and it means that you should be wary of replace-evt. If you want to wait on multiple things to happen asynchronously, you should probably use delay/thread for each subtask, then just force the subtasks serially. and you should give up on optimal cancellation.

4 Likes
2

Further commentary, also not mine:

A nack event passed to the guard proc of a nack-guard-evt is guaranteed to become ready for synchronization if the event returned by nack-guard-evt is abandoned. What's not guaranteed is that a composition of events will behave as you expect upon abandonment. For example:

(define sema (make-semaphore 1))
(let loop ()
  (sync
   (replace-evt ;; 1
    sema
    (lambda (_)
      (handle-evt ;; 2
       (system-idle-evt)
       (lambda (_)
         (begin0 'a
           (semaphore-post sema))))))
   (wrap-evt always-evt (λ (_) 'b))) ;; 3
  (if (semaphore-try-wait? sema)
      (semaphore-post sema)
      (error "deadlock"))
  (loop))

This code can deadlock because, when 1 is selected for synchronization, the semaphore is decremented and the sync recurs with 2 and 3 (as opposed to 1 and 3 on the first iteration). When 3 is selected on that retry, sema remains decremented so the next iteration will deadlock.

2 Likes