Investigate other fairness guarantees than FIFO

[syg]

@kmiller68 raises that strictly requiring FIFO fairness may prohibit certain performant locking schemes. We should explore weakening the FIFO requirement while still guaranteeing some kind of fairness.

Edit: note that the blocking wait/wake order is already guaranteed to be FIFO in order of calls to Atomics.wait. It's unclear if relaxing just the promise resolve order would enable other locking schemes.

[conrad-watt]

If there's the possibility that fairness of Atomics.wait might be relaxed, WebAssembly's spec should stay aligned with whatever is decided. I'll keep an eye on this.

[syg]

I didn’t intend the fairness of Atomics.wait to be on the table, only the fairness of the waitAsync promise resolution.

On Fri, Jun 7, 2019 at 01:09 Conrad Watt notifications@github.com wrote:

If there's the possibility that fairness of Atomics.wait might be relaxed, WebAssembly's spec should stay aligned with whatever is decided. I'll keep an eye on this.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/tc39/proposal-atomics-wait-async/issues/12?email_source=notifications&email_token=AAAXLUKYMMPLMEYR4EJEDM3PZGKKVA5CNFSM4HS3RTIKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXENHRI#issuecomment-499700677, or mute the thread https://github.com/notifications/unsubscribe-auth/AAAXLUKRCKG45XEYQAMH7QDPZGKKVANCNFSM4HS3RTIA .

[syg]

I've thought about this a bit more. My current thoughts:

1. We shouldn't spec different fairness guarantees for Atomics.wait and Atomics.waitAsync. That would add to confusion (at the very least) when reading the spec, and would raise a lot of questions about why we would do this?

2. The FIFO guarantee proposed here and already specced for Atomics.wait is that the observed order of EnterCriticalSection be kept FIFO. There's nothing constraining that EnterCriticalSection itself be FIFO, or even fair. The non-FIFO but bounded fairness behavior of WTF::ParkingLot should be perfectly compliant, as that non-FIFOness conceptually happens at the EnterCriticalSection.

In light of that, I plan to continue with the proposal keeping the FIFO guarantee. Thoughts, @kmiller68 and @lars-t-hansen?

(Let's also please not discuss in this thread speccing some kind of non-FIFO fairness for EnterCriticalSection.)

[lars-t-hansen]

FIFO ordering is observable if there's no contention to enter the critical section, and we should observe this order because it probably makes programs more reliable, if only some programs. (I make a thread wait, I wait for a while, then I make another thread wait, then I wake one thread - I know which thread that is.)

If there's contention to enter the critical section then it's different, we pick the order. So long as the EnterCriticalSection is boundedly fair (no starvation while waiting to enter) then there should be no problem. This + the linear list of waiters captures the other intent of the FIFO order, that no waiter should be made to wait indefinitely while those waiting behind it are woken before it.

[syg]

FIFO ordering is observable if there's no contention to enter the critical section, and we should observe this order because it probably makes programs more reliable, if only some programs.

I agree. I also have a hard time imagining non-FIFO bounded fairness applying even to locks without contention, but I may be wrong.

[syg]

So long as the EnterCriticalSection is boundedly fair (no starvation while waiting to enter) then there should be no problem.

Is specifying bounded fairness in EnterCriticalSection even possible? It looks like implementations currently do not have a no-starvation guarantee, except maybe WTF::ParkingLot? pthread_mutex_t isn't guaranteed to be fair (FIFO or otherwise), and both V8 and SpiderMonkey use that internally. I think macOS guarantees fairness but Linux does not (since futexes do not). I'm unclear on Windows.

Putting in that verbiage would, strictly speaking, require implementation changes, and that seems undesirable.

Edit: I guess we already stipulate forward progress, so in light of that saying we require bounded fairness is really just editorial. That said, my current question of existing implementations and starvation still stands: are we hoping for the best from the OS currently?

[lars-t-hansen]

Edit: I guess we already stipulate forward progress, so in light of that saying we require bounded fairness is really just editorial.

Agreed. And I'm agnostic about whether we need to really spell that out.

That said, my current question of existing implementations and starvation still stands: are we hoping for the best from the OS currently?

I expect so. And without a "bound" on the boundedness, who's to say how long you should wait before you get to decide that you're starved? Do we require there to be some kind of accounting code in EnterCriticalSection to ensure boundedness, or can we rely on the probability of acquiring the critical section approaching 1 over time?

[syg]

This has been adequately resolved.