Skip to content

Draft: Fix edge case bug regarding semaphore fairness

Alexandros Tasos requested to merge at1917/pintos-skeleton:lock-fairness into master

The current semaphore implementation suffers from a fairness edge case bug:

Suppose we have two threads, Thread A and Thread B, and a semaphore S where its value is currently 0. Then, suppose we have this sequence of events:

  1. Thread A calls sema_down() and gets placed in the waiting list.
  2. A call to sema_up() wakes Thread A up, value is now 1.
  3. Thread B calls sema_down() without getting to wait, value is now 0.
  4. Thread A tries to decrement the value, but it can't, so it gets placed in the waiting list again.

This pull request fixes the above edge case issue by ensuring that on sema_up, if there are any waiting threads, the counter is not incremented (and any thread that entered the waiting list does not need to try decrementing the counter upon wakeup).

Merge request reports