Deadline Scheduling Proposed For the Linux Kernel

c1oud writes "At the last Real-Time Linux Workshop, held in September in Dresden, there was a lot of discussion about the possibility of enhancing real-time capabilities of Linux by adding a new scheduling class to the Linux kernel. According to most kernel developers, this new scheduling class should be based on the Earliest Deadline First (EDF) real-time algorithm. The first draft of the scheduling class was called 'SCHED_EDF,' and it was proposed and discussed on the Linux Kernel Mailing List (LKML) just before the workshop. Recently, a second version of the scheduling class (called 'SCHED_DEADLINE,' to meet the request of some kernel developers) was proposed. Moreover, the code has been moved to a public git repository on Gitorius. The implementation is part of a FP7 European project called ACTORS, and financially supported by the European commission. More details are available."

Comments

Re:What I'm not clear about

[natehoy]

Interesting story a professor of mine told: An old university mainframe was brought offline after decades of operation. A core dump was performed and investigation revealed that there was a process that had been waiting to run for close to 30 years. Somehow, its priority was set to be lower than the idle process and this particular machine did not have automatic escalation of priority in its scheduler.

Actually, I think EDF would fix that, at least to an extent.

Currently, prioritization is done based on, well priority. So if you took a job and set its priority to lower-than-idle, as you stated above, it will obviously never run.

However, with EDF,you assign (if I understand it correctly) a deadline to each task rather than a priority. "Task X really should get done in the next 50 msec, but Task Y can wait up to 12 hours and no one's going to scream". On a normal peak-and-valley loaded machine, it'll work on the first deadline first, and if things queue up the low-"priority" ones will simply have longer deadlines. Ideally, the system has enough capacity to accommodate the longer deadline stuff "early" when it has time.

However, on a heavily-peaked system, eventually those long-deadline jobs are going to get priority simply because their deadlines have been reached. So if you have a 50ms deadline job running every 20ms and those jobs start queuing up, then you submit a 12hour deadline job, in 12 hours that job will get the full attention of the system until it's done, because it has the earliest deadline.

As with all things, this has its advantages and disadvantages. If that job that runs every 20ms is truly critical, then you're not going to like this scheme - eventually the low-"priority" stuff is going to come due and take precedent over your "critical" stuff because it's all based on what you asked for first, not how important each task was. On the other hand, this does prevent the very problem you describe - jobs running at such a low priority that they never get any lovin' at all.