Proxy Execution
Posted: Mon Nov 06, 2017
[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)
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)