Feature #21843: Simple Priority Scheduler

• Status: Open
• Assignee: -
• Target version: -

[luke-gru (Luke Gruber)]

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 throughput of CPU-intensive threads 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". 2/3 of 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, and our max consecutive I/O counter is reset.

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. Benchmark results to come :)

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.

Drawbacks / Concerns

This makes the scheduler more complex. Whether or not this will make your threaded Ruby app faster is also workload dependent, and can vary across the lifetime of your program. There are some magic numbers and tuning parameters involved, and it may seem arbitrary and tuning may be tricky. The design tries to be conservative about putting things on the high priority queue.

Conclusion

I have a draft branch here: https://github.com/ruby/ruby/compare/master...luke-gruber:ruby:priority_scheduler_simple

Let me know your thoughts.

Thanks!

[luke-gru (Luke Gruber)]

• Description updated (diff)

[luke-gru (Luke Gruber)]

• Description updated (diff)

[luke-gru (Luke Gruber)]

• Description updated (diff)

[luke-gru (Luke Gruber)]

• Description updated (diff)