Tools and Benchmarks for Real-Time Systems

Problems raised in the keynote of Peter Zijlstra at ECRTS'17 • Probabilistic task model

2017-11-06T11:19:26+01:00

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

Probabilistic task model.

There are a number of places where probabilistic (like) things pop up.

unprivileged GRUB would require a per-task limit on allows overrun
measurement based WCET, typically results in a distribution of sorts
SoftRT many stream workloads that want to maximize machine utilization, lower WCET budget to increase efficiency but then rely on overrun / unused bandwidth reclaim to deal with peaks.

If we extend the task model with 1 more variable that is a 'variance' on budget, for example a 0-sum limit on overrun (overrun is added to the sum, and underrun subtracted from the sum and is limited to [0,x]) can this be usefully employed by the scheduling function?

Statistics: Posted by Sophie Quinton — Mon Nov 06, 2017

Problems raised in the keynote of Peter Zijlstra at ECRTS'17 • Support for single CPU affinity in G-EDF

2017-11-06T11:13:58+01:00

[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.

Statistics: Posted by Sophie Quinton — Mon Nov 06, 2017

Problems raised in the keynote of Peter Zijlstra at ECRTS'17 • An alternative admission test for G-EDF

2017-11-06T11:11:58+01:00

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

An alternative admission test for G-EDF (proposed by Tommaso Cucinotta).

Instead of the regular: U = \Sum u_t <= m, use:

U_i = \Sum (u_t / w_t) <= 1
t \elem all tasks runnable on i

where w_t is the (hemming) weight of t's CPU affinity bitmask.

The term 'recoverable' is coined to mean it avoids the ever escalating missing of deadlines (does it?) and if so, is that then a sufficient guarantee to claim bounded tardiness?

Statistics: Posted by Sophie Quinton — Mon Nov 06, 2017

Problems raised in the keynote of Peter Zijlstra at ECRTS'17 • Proxy Execution

2017-11-06T11:10:21+01:00

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

Proxy Execution (proposed by Doug Niehaus KU), as a schedule function invariant alternative of Priority Inheritance / Deadline+Bandwidth-Inheritance.

Define a task to consists of a scheduler-context and an execution-context. The scheduler-context is that part of the task state the scheduler uses to make task selection (priority / deadline / bandwidth etc..). The execution context is that part of the task that is used to execute code (stack / registers etc..).

Where PI (and DI) need a second implementation of the schedule function (partial order operator) in order to _order_ the blocked-on list of a mutex, Proxy Execution does things 'backwards' and leaves all blocked tasks on the ready-queue.

By leaving blocked tasks on the ready-queue we use the regular scheduling function to pick the highest 'priority' task and then follow the blocked-on chain until we find a runnable task.

Then we use the scheduling-context of the first pick with the execution-context of the block chain walk.

SMP will need 'migrations' of blocked tasks in order to avoid having multiple CPUs trying to run the same execution context (they'd enter at
different blocked tasks on the block chain).

Invariant: the block-chain walk must not cross CPUs.

CBS throttle would take a task off the ready-queue and place it back on on replenishment.

Requested; analysis of this scheme and does it provide better guarantees than M-BWI (which is very pessimistic).

(The KUSP project appear to have an implementation, but I did not find papers)

Statistics: Posted by Sophie Quinton — Mon Nov 06, 2017