Prevent starvation when acquiring mutex over and over (#15877)

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

See https://bugs.ruby-lang.org/issues/21840 for more details.

Solution:

When a thread `T1` wakes up `T2` during mutex unlock but `T1` or any other thread successfully acquires it
before `T2`, then we record the `running_time` of the thread during mutex acquisition. Then during unlock, if
that thread's running_time is less than the saved running time, we set it back to the saved time.

Fixes [Bug #21840]

1 files changed, 33 insertions, 0 deletions

diff --git a/test/ruby/test_thread.rb b/test/ruby/test_thread.rb
index b2d8e73693..60e3aa772a 100644
--- a/test/ruby/test_thread.rb
+++ b/test/ruby/test_thread.rb
@@ -1664,4 +1664,37 @@ q.pop
       assert_operator elapsed, :>=, 0.1, "sub-millisecond sleeps should not return immediately"
     end;
   end
+
+  # [Bug #21840]
+  def test_mutex_owner_doesnt_starve_waiters
+    assert_ruby_status([], "#{<<~"begin;"}\n#{<<~'end;'}")
+    begin;
+      m = Mutex.new
+
+      fib = lambda { |n|
+        return n if n <= 1
+        fib(n - 1) + fib(n - 2)
+      }
+
+      t1_running = false
+      t1 = Thread.new do
+        t1_running = true
+        loop do
+          fib(20)
+          m.synchronize do
+            File.open(__FILE__) { } # reset timeslice due to blocking operation
+          end
+        end
+      end
+
+      loop until t1_running
+
+      3.times.map do
+        Thread.new do
+          m.synchronize do
+          end
+        end
+      end.each(&:join)
+    end;
+  end
 end