parking_lot fairness is inadequately modeled (ie., real parking_lot mutexes are not fair)
- Dominant language
- Rust
- Stars
- 1.1k
- Forks
- 59
- Avg merge
- 4d 2h
- Merged PRs (30d)
- 15
Description
Ref: https://docs.rs/parking_lot/latest/parking_lot/type.Mutex.html#fairness, https://docs.rs/parking_lot/latest/parking_lot/type.RwLock.html#fairness:
>A typical unfair lock can often end up in a situation where a single thread quickly acquires and releases the same mutex in succession, which can starve other threads waiting to acquire the mutex. While this improves throughput because it doesn’t force a context switch when a thread tries to re-acquire a mutex it has just released, this can starve other threads.
> This mutex uses [eventual fairness](https://trac.webkit.org/changeset/203350) to ensure that the lock will be fair on average without sacrificing throughput. This is done by forcing a fair unlock on average every 0.5ms, which will force the lock to go to the next thread waiting for the mutex.
> Additionally, any critical section longer than 1ms will always use a fair unlock, which has a negligible impact on throughput considering the length of the critical section.
> You can also force a fair unlock by calling `MutexGuard::unlock_fair` when unlocking a mutex instead of simply dropping the MutexGuard.
Alternatives to solve this:
1. Keep the current fairness, meaning we'll miss bugs (but all bugs are real bugs).
2. Swap to `Unfair`, meaning we'll be complete but not sound
3. Model this "holder is in the running to reacquire the mutex" somehow.
1 and 2 are a lot less work, but either not complete or not sound.
Modeling "holder is in the running to reacquire the mutex" is doable, but has some trickiness to it. Releasing a `Mutex`/`RwLock` would be changed to not give the lock to the next task immediately, but instead register that the release has happened, and then check for pending releases whenever a task does something which causes a yield point. Also
> Additionally, any critical section longer than 1ms will always use a fair unlock,
has to be accommodated somehow. The obvious option here is time models, but a time model which doesn't increment the clock (eg., Frozen) will not ever consider a CS longer than 1ms even when it probably should. The alternative then is scheduling decisions, though we don't track those at a per-task level, and its weird to consider a CS to be 1ms if a task is never blocked, it just happens to be not scheduled for a while, or some other metric we track on a per-task level.
All of this tracking seems like too much ado for nothing. I think the better option is to do the following:
Lock aquire gets changed from the following (needless stuff removed):
```rust
pub fn lock(&self) -> MutexGuard<'_, T> {
self.semaphore.acquire_blocking(1).unwrap();
MutexGuard { mutex: self }
}
```
To essentially a loop where we may reblock at the front of the semaphore in the situation where the lock was reacquired by the lock that held it. `lock` would also be updated to allow the previous holder to "skip ahead" (steal), meaning the implementation would be something like the following:
```rust
impl BatchSemaphore {
fn steal_if_stealable(&self, num_permits: usize) {
if self.permits_in_escrow(num_permits) && self.last_holder = current_task() {
self.take_from_escrow(num_permits)
}
}
fn escrowed_acquire(&self, num_permits: usize) {
while true {
self.blocking_acquire(num_permits);
self.put_in_escrow(num_permits);
// Create a race between us and the previous holder
yield_now();
if self.permits_in_escrow(num_permits) {
self.take_from_escrow(num_permits)
break
}
// we lost and have to try again
}
}
pub fn lock(&self) -> MutexGuard<'_, T> {
self.semaphore.steal_if_stealable();
self.semaphore_escrowed_acquire();
MutexGuard { mutex: self }
}
```
Contributor guide
Research direction
Start by reading the Mutex/RwLock lock path and the BatchSemaphore methods shown in the issue, then compare their behavior with the linked parking_lot fairness documentation. Resolve which alternative is sound and complete, including the longer-than-1ms critical-section case; done means the chosen fairness behavior is modeled consistently.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- testing-qa
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100