docs: Task scheduling fairness and acquire-lock yield

[tae-soo-kim]

The current docs on task scheduling have nothing about fairness on its module page.

I found some explanation on the yield_now page:

It is generally not guaranteed that the runtime behaves like you expect it to when deciding which task to schedule next after a call to yield_now(). In particular, the runtime may choose to poll the task that just ran yield_now() again immediately without polling any other tasks first.

It doesn't tell me if this applies only to yield_now function or any yields in general.

When coupled with another topic: Mutex, this becomes very confusing. The Mutex docs mention it is fair:

Tokio’s Mutex works in a simple FIFO (first in, first out) style where all calls to lock complete in the order they were performed. In that way the Mutex is “fair” and predictable in how it distributes the locks to inner data.

And the lock method:

Locks this mutex, causing the current task to yield until the lock has been acquired.

Literally this says a task acquiring Mutex yields every time (even if it can be acquired right now). Since the runtime doesn't offer a strong guarantee about what task is scheduled next, it could happen that it's always the same task being scheduled which acquire-release the mutex infinitely. Then saying the mutex is fair is pointless, because other tasks do not even have a chance to be scheduled.

[Darksonn]

The fairness of the mutex refers to the case where many tasks are waiting to lock it. In that case, it's guaranteed to give the lock to the task that has been waiting for the longest. It's not talking about tasks not using the mutex.

Literally this says a task acquiring Mutex yields every time

That's not the intended meaning of the sentence.

[Darksonn]

Since the runtime doesn't offer a strong guarantee about what task is scheduled next, it could happen that it's always the same task being scheduled which acquire-release the mutex infinitely.

Actually, this can not happen. If there is another task waiting for the mutex, then your task will fail to acquire the lock.

[tae-soo-kim]

What I think can be improved in current docs:

1. The lock method, instead of

   Locks this mutex, causing the current task to yield until the lock has
   been acquired.

   shall be replaced by something like

   Locks this mutex, causing the current task to yield. No yield occurs if
   the lock can be acquired instantly. As an exception, there are a budget
   of operations and if ... the current task still yields even if the lock
   can be acquire instantly ...

   This is not the final wording, but just to suggest enumerating all the cases
   when an acquire does and does not yield so that the doc is technically
   correct.

2. Tasks can only be yielded/cancelled at await points.

   This is the norm but should be explicitly confirmed because it's important.

   This could be put into tokio::task.

3. The scheduler's scheduling policy.

   How the scheduler picks the task to schedule next? This may be complicated,
   but at least should mention guarantees about starvation/no-starvation and
   fairness/no-fairness. I'm not sure if wait-free is a correct term in the
   case of tokio.

   Because there are different schedulers, tokio::runtime should have a
   section about this for each scheduler (multi-thread and current-thread).

4. The scheduler's shutdown process (for each scheduler).

[tae-soo-kim]

If there is another task waiting for the mutex, then your task will fail to acquire the lock.

If the scheduler deeply favors my task, then other tasks don't even have a chance to wait for the mutex. Only after you mentioned some no-starvation guarantees that this becomes impossible.

[Darksonn]

If the scheduler deeply favors my task, then other tasks don't even have a chance to wait for the mutex. Only after you mentioned some no-starvation guarantees that this becomes impossible.

For the simple case of two tasks that want to acquire a mutex, this is not the case: The scheduler will never poll a task that hasn't notified its waker, so the "deeply favored task" must be skipped by the runtime after polling it once.

So what you're saying is only really true in this kind of scenario:

tokio::join!(
    mutex.lock(),
    async { loop { yield_now().await; } }
);

Granted, we do guarantee fairness even in the above case.