parking_lot fairness is inadequately modeled (ie., real parking_lot mutexes are not fair)

[sarsko]

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 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):

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:

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 }
}