Deadlock/livelock/etc. prevention

[dumblob]

I saw the implementation of u64 normal_join(u64 tid) {...} in runtime.c and its use and wonder whether the HVM language (or is it HOVM language?) guarantees no deadlocks/livelocks in this case?

If so, how? If not, then this should be taken into consideration if I understood the inner workings correctly.

I'm unable to do any mathematical proofs of this, so I've turned to asking about this 😉.

[VictorTaelin]

normal_join is just a function that waits for a thread to complete its assigned reduction. So, as long as it terminates, normal_join will eventually return too. Note that once normal_join is called, the thread that called it doesn't have any more work to do.

[dumblob]

Yes, that's exactly how I understood it. Sorry I wasn't specific enough in my description.

What I meant is that there is a fixed number of threads (workers) and they get some work "over the time" (but maybe this is another misunderstanding on my side of the source code and all the work is scheduled up-front in a fixed manner without any dependency on "time" unlike e.g. in work stealing scenarios) whether each thread gets to normal_join there is a guarantee there is no more work to schedule.

[VictorTaelin]

The scheduler is very primitive see here. Each thread is only assigned a redex, and then it just waits. A task scheduler is one of the improvements we'd like to make if we manage to scale this project.

[dumblob]

Then I'd recommend a work-stealing scheduler. Ideally one optimized for micro tasks (the state of the art is still Weave - you can easily skip the binary generation and use only the generated C code as Nim is just a clever transpiler).

[VictorTaelin]

Yep, something like that is very high on my dream wishlist!