Support for single CPU affinity in G-EDF

[Sophie Quinton]

[This problem was presented by Peter Zijlstra during his ECRTS'17 keynote talk, see slide 11]

Support for single CPU affinity in G-EDF (also see the open problem "An alternative admission test for G-EDF"). The expected behaviour of single CPU affinity is that of UP where people 'know' EDF to be optimal. That is, there is an expectation of stricter deadlines.

The 'obvious' hierarchical approach 'local EDF + G-EDF' has issues in that there are fairly trivial task sets that will have (avoidable) deadline misses. The question is, can we do better in a single scheduling function.

The proposal (by me), is to combine EDF and LLF. The observation is that, given the deadline constrained sporadic task model:

e_i <= d_i <= p_i

and discarding the degenerate case of e_i == d_i == p_i, we're left with a model that has at least 2 degrees of freedom (implicit deadline has d_i == p_i) and EDF only employs 1, namely d_i.

This leaves us freedom to differentiate between local and global tasks.

Define laxity_i := d_i - e_i ; when i is a local task, inf. otherwise.

Then: t + e_EDF < d_LLF - e_LLF -> EDF, otherwise LLF

That is, avoid the EDF pick from causing negative laxity.

Similar to EDZL (as pointed out by Luca); can any of that analysis be reused? Marko thought there might be EDZL variants that relax the 0-laxity thing.