Deadline scheduling for 3.14

Corbet's picture

Realtime programming is all about deadlines, but it has often been noted that few deadlines appear to be applicable when it comes to getting realtime code into the mainline kernel.  Deadline scheduling is a classic example; I first wrote about it in 2009, and the work had already been underway for some time at that point.  But the long wait is almost over; deadline scheduling has been merged for the 3.14 kernel, which will probably be released in late March.  It may well be the most significant feature that will appear in that release.

Traditional realtime scheduling is all about priorities; each process running in a system is given a priority, and, at any given time, the runnable process with the highest priority is the one that gets the CPU.  But it has long been recognized that priorities do not map well to many real-world problems and that configuring realtime systems with priorities can be tricky.  So researchers have been looking for better ways, one of which is deadline scheduling.

With a deadline scheduler, there are no more priorities.  Instead, each process has three attributes: (1) an amount of work that it needs to do (called the "worst-case execution time"), (2) a deadline by which that work must be done, and (3) a periodicity which says how often it must do its job.  The scheduler in its simplest form will run whichever process's deadline expires first.  If careful "admission control" is done (essentially making sure that the sum of worst-case execution times does not exceed the amount of CPU time available), the scheduler will be in a position to guarantee that every process will be able to get its work done by its deadline.

Since people designing realtime systems tend to think in terms of deadlines ("shut the system down within 10ms or it will explode"), they are naturally well served by a deadline scheduler.  But there are a number of other situations where deadline scheduling can help too.  Imagine a video player application that must receive, render, and display each frame before the next arrives.  By setting up its deadlines and periodicity accordingly, it can be sure of receiving the right amount of CPU time just when it needs it.  That makes the programming easier and eliminates the possibility that a runaway video player running with realtime priority could take over the system.

So why did this clearly useful work take so long to get into the mainline kernel?  The delay is partly due to the fact that the developers have mostly been students at an Italian university; students — even graduate students — have a certain tendency to get distracted at times.  But it is also true that making large changes to a core subsystem like the scheduler is hard to do.  The scheduler has to work for everybody, whether they are running on a phone handset or a supercomputer; writing code that will work well across that variety of workloads is not easy.  Deadline scheduling is also an ongoing research concept; it is not always clear how to make it work well on, for example, systems with large numbers of processors.  So the code took a long time to get right, and will probably require more work before it is truly ready for widespread use.

That said, it is a major piece of work and a huge enhancement to the Linux CPU scheduler.  Congratulations are due to the many developers who have worked on this code over the years.