[LITMUS^RT] Deadline and release miss in EDF

[Björn Brandenburg]

> On 21 Jan 2017, at 00:20, Chen, Tianyang <tiche at seas.upenn.edu> wrote:
> 
> Hi Björn,
> 
> I have some questions about the EDF scheduler.
> 
> I have been looking at the source code of psn_edf scheduler and it looks like when a task misses its deadline(assuming the same as its period), the next release will be checked as soon as requeue() is called. Because the next release should be in the past, the task is put on ready_queue immediately, which might be picked again in the main schedule() function afterwards.

Yes, that is correct. If the next job still has the highest priority (earliest deadline), then the task is immediately eligible to continue execution.

> Let me know if my understanding is correct: Each task will only have one job active

Correct.

> (because rt_param has only one heap_node).

No. The fundamental limitation is that a Linux task (= a thread) is sequential. It has only one runtime stack. That's why there's only one active job at any time. 

> The next release is kinda triggered after the scheduler requeues the task(if it goes to release_queue, it arms the timer to fire on the next release). If the task is on the ready_queue and never picked, there will NOT be a second release.

Not sure what you mean by that. Unless the system is overloaded, no task should "never" be picked.

> 
> Also, there is no release arrow showing on the feather trace pdf if a task is added back to ready_queue right after a deadline miss. Is it missing a trace statement?

Probably. Which scheduler are you looking at?

> So I'm thinking about adding some sort of job buffer to each rt_task and essentially queue jobs, say during some overloaded conditions, and run them later.

Mh, I don't really see the need for that. What are you trying to accomplish?

> But when I looked at the code, there needs some major changes to the code and I can't really avoid breaking other scheduler plugins. I was just thinking about adding a list of heap_node and rt_job param and maybe refactoring anywhere that checks job params, which might be a change. Let me know what you think!

My gut feeling says that a far simpler solution is likely possible.

The notion of a "job" in the old process-based plugins really is a limited form of budget enforcement or "proto-reservations". If you want more robust reservations that deal more gracefully with overruns and backlogged tasks,  check out the P-RES (partitioned reservations) plugin. Alternatively, if you don't want budget enforcement and want overrunning jobs to run to completion, just turn it off when you set the RT params of the task that may overrun.

- Björn