I've got versions working for both of them, but I'm still a bit confused why sleeping for 1ms (a backoff) after failing to get the mutexes, is necessary in the async version but not in the threads version.
Here are the full files on rust playground, with the 1ms backoff included in both, although actually the sync version fails to complete in rust playground, but does complete for me locally. When I run it locally the sync version completes in ~91.8 seconds without the 1ms backoff (on line 39), and completes in 4.2 seconds with the 1ms backoff. The async version completes for me locally in 1.8 seconds.
async dining philosophers (the backoff is line 79)
sync/threads dining philosophers (the backoff is line 39)
I'd like to understand better some of these questions:
why the async version will not complete at all without the 1ms backoff? but the sync/threads version can complete without the backoff?
why the sync version goes so much faster with the 1ms backoff?
why the async version is even faster than the sync version?
how would one theoretically make it even faster? are there better backoffs to choose than 1ms?
thanks for any help!
edit: fixed the rust playground links which were mixed up
Rust async is, in part, a kind of cooperative multitasking system. If you want some other participant to take an action (in this case, releasing a lock), you have to yield/suspend (in implementation terms: at some point have your task return Poll::Pending) to let their code run that action. Depending on the implementation of the executor and of the mutex, it may or may not be necessary in practice to do so, but it is always incorrect to write a loop that never yields.
(Note that an .await by itself never suspends. Only awaiting a future that itself suspends suspends your future/task; you cannot introduce a yield point by writing (async {}).await.)
In practice, what you should do is use lock() instead of try_lock() for left_fork, so that instead of repeatedly failing, you wait (while you are holding zero locks) until the lock is available, then try_lock() (so as not to possibly deadlock) the right fork. This way, the lock() on the left fork is how you yield, and your task is not wasting CPU time on waking up and trying again repeatedly while any other task holds the lock. Then the only time it is appropriate to sleep is after you have failed to obtain a right fork (and released the left fork!).
Note that I don’t mean this to be any particular perspective on the dining philosophers problem; rather, I'm trying to explain how to write correct and efficient async code, based on minimal changes to your example.
In cooperative multi-tasking, you need to actually explicitly yield to give other threads an opportunity. Also a helpful and funny side-note that (async {}).await wouldn't do the trick.
And makes sense that using lock().await for the first lock would be a natural place to yield. Indeed when I adjust my async code to use .lock on the first lock, and then try_lock on the second, it can complete even without the sleep backoff.
Still curious about some of the other questions if anyone is inspired (about how one would intelligently/efficiently choose a backoff), but that answer feels to me like it clarifies my main question! which was why the first async I had wasn't completing at all (it was in a loop and never yielding).
Then the only time it is appropriate to sleep is after you have failed to obtain a right fork (and released the left fork!).
based on what you said I was also able to improve the efficiency of the sync version by one second, by adding a line to drop(lfork) and release the left fork before sleeping for the backoff, cool
