An example: Two coroutines share a channel `c`. Th...

# coroutines

[Ulrik Rasmussen]

An example: Two coroutines share a channel c. The first coroutine calls c.send(i) followed by `c.receive()`; the second does val i = c.receive(), then checks if i is even and only then does c.send(i+1). The first coroutine will block forever on`c.receive()` if it sent an odd i in the beginning. It should be possible to reliably detect this situation under the assumption that no other coroutines know c, and detecting (asynchronously) that the dispatcher is out of work. Preferably I would like to be able to do this in the first coroutine, i.e. effectively doing c.receiveOrThrowOnDeadlock().

[uli]

What exactly do you want to detect? I.e. how would you know you are dead locked? You could sure use a timeout. But that’s cheating and might fail under load.
Just saw your previous post.

[Ulrik Rasmussen]

I want to detect the situation where progress is guaranteed not to be made. Edit: I see, yes, that was the missing context :)

[uli]

Refering to your previous post, the question remains, what could be the definition of `idle`in an asynchronous setting?
If coroutine (b) is suspended on receive and (a) calls send, would coroutine (b) still be considered idle before it is resumed at some later point in time?

[Ulrik Rasmussen]

That's a good question, and I still have a fairly hazy idea of the intrinsics of the coroutines library, so that's where I am not sure. I would assume that for an unbuffered channel, calling c.send() from (a) will either (1) cause the continuation of (b) to be dispatched before (a) suspends; or directly continue executing the continuation of (b). In either case, the worker thread is either still active and/or the list of work is non-empty. In the case where (a) calls c.receive() and suspends, I think the work thread will become idle for the first time because there is no more work to be done. If a coroutine could be activated in that situation, e.g. via a select query, then it could possibly query the state of the channels and conclude that there is a deadlock.

[Ulrik Rasmussen]

The context for this is that I am using coroutines to implement actors, which in turn model nodes in a network that participate in a protocol. For testing my implementation, I want to apply randomized testing, e.g. using kotest. The problem is that the correct behavior in many test cases will be for a node to simply ignore an incoming invalid message, but in order to end the test case I need to ensure that no further progress will be made. Relying on timeouts makes it impossible to apply randomized testing because the test suite would take days to finish, mostly just by idling.

[uli]

If you have no external events (network, timer) you could probably implement a dispatcher that throws when no coroutines are running or are ready to run. The argument would be, that if no coroutine is running or ready to run then nothing can trigger any event that would cause a coroutine to be resumed in the future

[uli]

On the other hand, if a coroutine could be resumed by timer, network request callback (even any IO) you can not know whether you are waiting or dead.

[Ulrik Rasmussen]

Yes, that's a good point. This only works when you can guarantee that all resources are confined to a single, or known set of, dispatchers.

[Ulrik Rasmussen]

I guess my use case is even simpler than general deadlock detection. I merely need to detect quiescence of the dispatcher. The ability to dispatch computations with a priority would even suffice for this, as I would just schedule a task with the lowest priority. This only runs when all actors have finished processing and can then check that all conditions are as expected. I don't know if there is a way of even doing that though, but it seems like a simpler thing to implement.