Fairness of semaphore

[bikeshedder]

I was looking for fairness guarantees of the Semaphore implementation and didn't find anything mentioned in the docs. After some digging I found that event_listener::Event is used internally and documented as being fair.

However looking at the implementation of Semaphore::acquire I can see that it is implemented as a loop calling try_acquire and creating a EventListener in order to wait for a permit.

async-lock/src/semaphore.rs

Lines 86 to 95 in 48a5b62

	loop {
	if let Some(guard) = self.try_acquire() {
	return guard;
	}
	match listener.take() {
	None => listener = Some(self.event.listen()),
	Some(l) => l.await,
	}
	}

If I'm not mistaken it's possible that this code listens for an event and right after being woken another tasks snatches that permit away. This could lead to starvation where the tasks never manages to get a permit.

I think I've seen that exact behavior in some of my benchmarks where some workers hung forever causing timeouts and outliers.

I was wondering if there is a "easy" and correct way to make this implementation fair.

If that's out of scope for async-lock a small text in the documentation would be nice that it is not designed to be fair.

[zeenix]

I was wondering if there is a "easy" and correct way to make this implementation fair.

I wouldn't know of any (at least a simple-enough one). @taiki-e would you have some ideas?

If that's out of scope for async-lock a small text in the documentation would be nice that it is not designed to be fair.

Yeah, we should do that if @taiki-e doesn't have any ideas either.

[abonander]

A fair semaphore would also be a requirement to use this in SQLx as otherwise it can easily lead to starvation at high contention. We previously learned this the hard way when we tried to use async-std's MPMC channels as the core primitive for our connection pool: smol-rs/async-channel#6

[notgull]

We could implement this in a similar way to Mutex by having a fair flag on the Semaphore. When it's set, it would make users newly acquiring the Semaphore wait for others to take it first.