Issue #21843 has been reported by luke-gru (Luke Gruber). ---------------------------------------- Feature #21843: Simple Priority Scheduler https://bugs.ruby-lang.org/issues/21843 * Author: luke-gru (Luke Gruber) * Status: Open ---------------------------------------- Hi, There's a problem with Ruby's scheduler that I want to solve. # The Problem Since Ruby schedules threads using round-robin inside a Ractor, threads doing I/O after only running for a short time are punished. Once the I/O finishes, they are put on the back of the ready queue and have to wait for max `N * 100ms` where `N` is the number of threads in the queue before it (100ms is the quantum for threads with normal `Thread#priority`). Most ruby threads don't use up their full timeslice (I'm guessing), but they are still punished by CPU hogs. I would like to more fairly run threads that are punished for giving up their timeslice early. My goals for such a scheduler are the following: # The Goal * Threads that give up their timeslice early are rewarded with a priority boost. * Simple approach (no vruntime like Linux's CFS, not too many runqueues, etc) with easy to understand design and implementation. * No starvation. There can be no worst-case scenario where a thread is stuck in a queue. * Make perf. gains for programs with threads that perform mixed workloads of I/O and CPU. * In worst-case scenarios (100% CPU threads with background I/O threads) don't slow down by a considerable amount. # The Design ### Queues and Dequeue The design is simple and uses 2 queues `high` and `low`. The scheduler tracks the order each thread is put in a queue, and the order is global for both queues. If a thread on the head of the `high` queue was put there before the thread on the head of the `low` queue, the `high` thread is dequeued. If the `low` thread was enqueued first, then this is considered a "priority decision". Half the time during a priority decision, the thread from `high` is dequeued, otherwise `low` is dequeued. ### Enqueue Which queue is a thread placed on when it is ready to run? * When there are no threads in any queue, we always pick `high`. * If we just performed I/O and didn't even use up 1/10 of our timeslice, we are enqueued in `high`. We can do this max 3 times in a row, and only if `Thread#priority >= 0`. * If we were in the low queue, every 4 "enqueues" we check the accumulated timeslice time taken during the last 4 timeslices. If that time is less than 1/2 of our quantum, we are enqueued in `high`. This can only happen if `Thread#priority >= 0`. * Otherwise, we are enqueued in `low`. This design is very conservative, and attempts not to punish CPU-intensive threads. # Testing + Benchmarking I would like to add a suite of tests to `ruby-bench` that would test the scheduler in different scenarios, including scenarios in which it could potentially perform worse than round-robin. This set of benchmarks would be useful going forward when making any changes to the scheduler. I already have several scripts that I've used for testing my draft PR. # Feature Flags and API I don't know if a feature like this would need to be behind a flag, marked as experimental, etc. Maybe it could even be enabled by `Thread.scheduler = :priority`. # Alternatives I'm open to any ideas and different approaches. I know that prioritizing more fairness in timeslice time is one approach, but we could also simply enqueue threads that are marked `Thread#priority > 0` more often in the `high` queue. Right now their timeslice is increased but they don't get special treatment in the queues. I have a draft branch here: https://github.com/ruby/ruby/compare/master...luke-gruber:ruby:priority_sche... Let me know your thoughts. Thanks! -- https://bugs.ruby-lang.org/