Back in April, I posted a comment about the Earliest-Deadline-First (EDF) scheduling discipline that was not fully accurate. I had commented that the original, overly-simplified explanations of EDF claimed that task sets would be `feasible', even though the explanations did not include any accounting for context switching.
Sanjoy, a Theoretician here in my department, corrected my assertions, saying
It can be shown [...] that an edf schedule on n jobs will have <= 2n-1 context switches, rather than oodles. In analyzing a system, this context-switch overhead is accounted for by "inflating" (in the analysis) the execution requirement parameters of each job by the amount of time taken to perform 2 context switches.Of course, he's right. He's published several important papers in the Real-Time area and knows it all far better than I do.
In retrospect, I was really commenting on the methodology of the proof more than on EDF per se; the original proofs of EDF's optimality (from Liu and Layland) do not account for context-switching cost. As such, I found the proofs unconvincing -- at least for practicable definitions of feasible.