Re: [PATCH] sched/deadline: Add sched_dl documentation

[Juri Lelli <juri.lelli@gmail.com>]

On 01/27/2014 11:29 PM, Luca Abeni wrote:
> Hi Steven,
> 
> On Mon, 27 Jan 2014 12:09:38 -0500
> Steven Rostedt <rostedt@goodmis.org> wrote:
> [...]
>>>> Lets take a case where deadline == period. It seems that the above
>>>> would be true any time there was any delay to starting the task
>>>> or the task was interrupted by another SCHED_DEADLINE task.
>>> Not sure about this... Notice that above only applies when a task
>>> wakes up (moving from a "sleeping" state to a "ready to run"
>>> state). Not when an already ready task is scheduled.
>>> Or did I misunderstand your comment?
>>
>> No no, you understood, I missed that this only happens on wakeup. But
>> then I have to ask, what happens if the task blocks on a mutex? Would
>> that cause this check to happen then?
> Well, in theory, this check has to be performed every time the task
> wakes up from any kind of sleeping (mutex, or anything else).
> I think this is what happens in practice with the current
> implementation, but maybe I am missing something in the implementation
> details.
> 

Yes. The call graph looks like:

 enqueue_task_dl()
  -> enqueue_dl_entity()
   -> update_dl_entity() <-- this does the check through dl_entity_overflow()

and enqueue_task_dl() gets called every time the task wakes up and is enqueued
back in the dl_rq (e.g., it was waiting on a mutex).

Thanks,

- Juri

>> It may be nice to add some comments about exactly when this check is
>> performed.
> Well, maybe "wake-up" is not the right term according to the
> terminology used in the Linux kernel... The check should be performed
> every time the task changes its state from sleeping (TASK_INTERRUPTIBLE
> or TASK_UNINTERRUPTIBLE, I think) to "ready to execute" (TASK_RUNNING,
> I think) and enters the ready queue (well, RB tree :). If someone can
> suggest a more appropriate wording, I'll fix the document accordingly.
> 
> 
>>>> For example, lets say we have two SD tasks. One that has 50ms
>>>> runtime and a 100ms period. The other has a 1ms runtime and a
>>>> 10ms period.
>>>>
>>>> The above two should work perfectly fine together. The 10ms period
>>>> task will constantly schedule in on the 100ms task.
>>>>
>>>> When the 100ms task runs, it could easily be delayed by 1ms due
>>>> to the 10ms task. Then lets look at the above equation
>>> See above: the check for the 100ms task is only performed when the
>>> task unblocks (at the beginning of its period), not when it's
>>> scheduled (after the 10ms taks).
>>>
>>> This check is designed to take care of the following situation:
>>> - consider a task with runtime 10ms and period equal to deadline
>>> equal to 100ms
>>> - assume the task wakes up at time t, and is assigned "remaining
>>>   runtime" 10ms and "scheduling deadline" t+100ms
>>> - assume the task blocks after executing for 2ms. The "remaining
>>>   runtime" is now 8ms
>>> - can the task use "remaining runtime" 8ms and "scheduling deadline"
>>>   t+100ms when it wakes up again?
>>>   Answer: if it wakes up before t+20ms, it can. Otherwise, it
>>> cannot, because it would consume a fraction of CPU time larger than
>>> 10%, causing missed deadlines in other tasks.
>>
>> Ah, you answered my question here. The check happens every time the
>> task blocks as well. I still need to read the papers, and even more
>> importantly, start running more tests with tracing on to review what
>> exactly happens in the implementation.
> If you read the original CBS paper, you'll see that it does not talk
> about "wake-up" and "sleep", because it always considers a wake-up as a
> job arrival, and a task blocking as a job end. This is because the
> original paper only considers a simplified task model, without
> "self-suspending jobs".
> In SCHED_DEADLINE, things are not so simple, because it has to consider
> real situations with real tasks not using the simplified original
> real-time task model...
> 
>>>>> + SCHED_DEADLINE can be used to schedule real-time tasks
>>>>> guaranteeing that
>>>>> + the jobs' deadlines of a task are respected. In order to do
>>>>> this, a task
>>>>> + must be scheduled by setting:
>>>>> +
>>>>> +  - runtime >= WCET
>>>>> +  - deadline = D
>>>>> +  - period <= P
>>>>> +
>>>>> + IOW, if runtime >= WCET and if period is >= P, then the
>>>>> scheduling deadlines
>>>>> + and the absolute deadlines (d_j) coincide, so a proper
>>>>> admission control
>>>>> + allows to respect the jobs' absolute deadlines for this task
>>>>> (this is what is
>>>>> + called "hard schedulability property" and is an extension of
>>>>> Lemma 1 of [2]).
>>>>
>>>> I wonder if we should state the obvious (which is never obvious).
>>>> That is the user must also have the following.
>>>>
>>>>   runtime < deadline <= period
>>>>
>>>> Although it is fine for deadline = period, runtime should be less
>>>> than deadline, otherwise the task will take over the system.
>>> I think if "runtime < deadline <= period" is not respected, then the
>>> admission control will fail... But yes, repeating it here can be
>>> useful. If needed I'll add it to the document.
>>
>> Yeah, it's one of those things that you should know, but I can see
>> users screwing it up ;-)
> Ok...
> What about presenting this as an example of the admission test failing?
> Something like: 'notice that if "runtime" > "deadine" the admission
> test will surely fail.'
> (BTW, I am not sure if the "deadline <= period" condition is really
> needed... Maybe not respecting it does not make too much sense, but I
> think it is not strictly needed for schedulability purposes).
> 
> 
> 
> 			Thanks,
> 				Luca
>