SCHED_DEADLINE on heterogeneous multicores

Did you know...?

LWN.net is a subscriber-supported publication; we rely on subscribers to keep the entire operation going. Please help out by buying a subscription and keeping LWN on the net.

As already mentioned in other talks, the SCHED_DEADLINE policy currently does not consider the capacities or the running frequencies of the various CPU cores. This mainly impacts two different aspects: admission control and task placement.

The SCHED_DEADLINE admission control is designed with two goals: avoiding overload (that is, avoid starving non-deadline tasks) and providing performance guarantees to deadline tasks. Unfortunately, the current code assumes that all of the CPU cores have the same maximum capacity (which is assumed to be equal to the maximum capacity of the fastest core), and this assumption breaks the admission-control mechanism. A simple experiment (creating SCHED_DEADLINE tasks until the admission control fails) shows that on a big.LITTLE CPU, it is currently possible to starve non-deadline tasks. A first patch that has been submitted to the Linux kernel mailing list fixes this issue by considering the maximum capacity of each CPU core when performing the admission control. Repeating the experiment shows that the patch is effective (until thermal throttling slows down the CPU, but this is a different issue).

Other patches submitted to the Linux kernel mailing list and discussed in this presentation try to fix the SCHED_DEADLINE migration mechanism so that deadline tasks are placed on CPU cores based the cores' capacities. In particular, the patches try make sure that deadline tasks are not scheduled on cores that are too slow (the scheduler checks if a task "fits" on a core — that is, the task can be scheduled on the core without missing a deadline — before migration) or too fast (the scheduler tries to select the slowest core where the task fits). The first check is needed for the correctness of the scheduler, while the second one is useful for power saving or to leave fast cores idle for other (maybe more time-consuming) tasks.

During the presentation, some possible issues with the patch set's approach were discussed. The discussion also covered some possible alternative implementations: in particular, in how to check if a core is fast enough to run a deadline task:

• For the task, should we consider the static runtime and period, or the current runtime and scheduling deadline?
• For the core, should we consider its capacity at the current running frequency, or its maximum capacity at the highest running frequency?

Finally, some experimental results were presented, showing that the patch set makes the scheduler more correct (some missed deadlines due to incorrect task placement are avoided) and reduces the energy consumption.