Bug #21840: Locking a mutex can lead to starvation

• Status: Open
• Assignee: luke-gru (Luke Gruber)
• Target version: 4.0
• Backport: 3.2: UNKNOWN, 3.3: UNKNOWN, 3.4: UNKNOWN, 4.0: UNKNOWN

[luke-gru (Luke Gruber)]

Continually locking a mutex m can lead to starvation if all other threads are on the waitq of m.

Let T be the thread that keeps on acquiring mutex m in a loop.

Iteration 1:

1. T locks mutex m
2. All other threads attempt to acquire m and end up on its waitq
3. T releases the GVL, doesn't wake any other threads because they're all waiting on m
4. T returns from the blocking function, resets its running_time to 0, acquires the GVL and continues running
5. T unlocks m. It adds the head of the waitq (T2) to the thread readyq. T continues running

Iteration 2:

1. T locks mutex m
2. T calls a blocking function. This time, it dequeues the readyq (ex: T2) and sends it the wakeup signal. T runs its blocking function
3. T2 wakes up, acquires the GVL and attempts to lock mutex m. It fails and goes back asleep, putting itself back on the waitq of m.
4. T returns from the blocking function, sets its running_time back to 0, acquires the GVL and keeps running
5. T unlocks m. It adds the head of the waitq (ex: T3) to the end of the thread readyq. T continues running. Repeat Iteration 2 except the head of readyq is now T3

The problem is that T can never be pre-empted.

Example script:

m = Mutex.new

def fib(n)
  return n if n <= 1
  fib(n - 1) + fib(n - 2)
end

t1_running = false
t1 = Thread.new do
  t1_running = true
  loop do
    fib(20)
    m.synchronize do
      $stderr.puts "t1 iter"
    end
  end
end

loop until t1_running

5.times.map do
  Thread.new do
    m.synchronize do
    end
  end
end.each(&:join)