Slashdot Mirror
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."
These algorithms will produce substantially worse overall performance in all workloads. However, they allow absolute deadlines to be set for certain tasks. This is mostly useful for embedded devices -- if you're creating a medical device, or a subsystem for a plane, a 20% performance hit to guarantee you don't delay critical tasks for a couple seconds and get people killed isn't even a decision worth thinking about.
This would make Linux a legitimate real time ("RT") kernel. There are RT Linuxes already, but they suck to work with -- I believe RTLinux (one of the RT variants), for example, requires all RT tasks to be in kernel-space.
The upshot is that this is huge for Linux in certain business areas (and other RT OSes are currently quite pricey), but totally useless for your desktop or home server.
Deadline scheduling is well established and has been done many times, in many flavours on other OSes. It's probably even been done on Linux before. But if this one gets upstream with the blessing of the kernel community, it would enhance Linux for everyone rather than just those running particular kernel patches.
Linux seems to be having a lot of realtime-related work (see PREEMPT-RT, a somewhat separate but related area of work) done, which is interesting - I would have said that the conventional wisdom was that large, general-purpose OSes cannot be realtime-ified. It seems like certain parties are determined to prove this wrong - and it's looking to me somewhat like getting to "good enough" realtime behaviour will make large segments of users happy even though it's perhaps unlikely to ever replace ground-up realtime OS designs.
I think the question he is posing is:
Is this type of scheduler perfect? Capable of real time, batch jobs and the mixed fruit bowl of jobs on a typical desktop or server?
The answer is, probably not. There really is no such thing as a perfect scheduler. Different kinds of workloads have different requirements.
A busy real time scheduler will tend to starve low priority jobs. This can become an issue if those low priority jobs manage to grab limited resources they are never given the time to use. As those resources dwindle, real time jobs will be harder to satisfy and the low priority jobs must be terminated or given time to release those resources. I can't really say for certain, but it looks like EDF would have these same kinds of issues.
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.