[PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Zhiqiang Zhang]

>From the contex,the definition of the destiny of a task
C_i/min{D_i,T_i},where T_i is not referred before, should be
substituted by C_i/min{D_i,P_i}.

----------------------------------------

Signed-off-by: Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>
---
 Documentation/scheduler/sched-deadline.txt | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
index 21461a0..194664b 100644
--- a/Documentation/scheduler/sched-deadline.txt
+++ b/Documentation/scheduler/sched-deadline.txt
@@ -169,8 +169,8 @@ CONTENTS
  of all the tasks executing on a CPU if and only if the total utilisation
  of the tasks running on such a CPU is smaller or equal than 1.
  If D_i != P_i for some task, then it is possible to define the density of
- a task as C_i/min{D_i,T_i}, and EDF is able to respect all the deadlines
- of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,T_i} of the
+ a task as C_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
+ of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,P_i} of the
  densities of the tasks running on such a CPU is smaller or equal than 1
  (notice that this condition is only sufficient, and not necessary).
 
-- 
1.9.0

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Luca Abeni]

Hi,

On Fri, 3 Apr 2015 16:18:33 +0800
Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com> wrote:

> >From the contex,the definition of the destiny of a task
> C_i/min{D_i,T_i},where T_i is not referred before, should be
> substituted by C_i/min{D_i,P_i}.
You are right, "T_i" should be substituted with "P_i"...
But now that I look at it more carefully, I think that "C_i" is also
wrong... It should be "WCET_i".


BTW, speaking about documentation: I still have some SCHED_DEADLINE
documentation patches in my local tree... I'll update and send them in
next week. Juri, should I send the patches to you, or submit directly
to the mailing list?

			Thanks,
				Luca
> 
> ----------------------------------------
> 
> Signed-off-by: Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>
> ---
>  Documentation/scheduler/sched-deadline.txt | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/Documentation/scheduler/sched-deadline.txt
> b/Documentation/scheduler/sched-deadline.txt index 21461a0..194664b
> 100644 --- a/Documentation/scheduler/sched-deadline.txt
> +++ b/Documentation/scheduler/sched-deadline.txt
> @@ -169,8 +169,8 @@ CONTENTS
>   of all the tasks executing on a CPU if and only if the total
> utilisation of the tasks running on such a CPU is smaller or equal
> than 1. If D_i != P_i for some task, then it is possible to define
> the density of
> - a task as C_i/min{D_i,T_i}, and EDF is able to respect all the
> deadlines
> - of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,T_i}
> of the
> + a task as C_i/min{D_i,P_i}, and EDF is able to respect all the
> deadlines
> + of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,P_i}
> of the densities of the tasks running on such a CPU is smaller or
> equal than 1 (notice that this condition is only sufficient, and not
> necessary). 

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Juri Lelli]

Hi Luca,

On 03/04/15 11:52, Luca Abeni wrote:
> Hi,
> 
> On Fri, 3 Apr 2015 16:18:33 +0800
> Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com> wrote:
> 
>> >From the contex,the definition of the destiny of a task
>> C_i/min{D_i,T_i},where T_i is not referred before, should be
>> substituted by C_i/min{D_i,P_i}.
> You are right, "T_i" should be substituted with "P_i"...
> But now that I look at it more carefully, I think that "C_i" is also
> wrong... It should be "WCET_i".
> 
> 
> BTW, speaking about documentation: I still have some SCHED_DEADLINE
> documentation patches in my local tree... I'll update and send them in
> next week. Juri, should I send the patches to you, or submit directly
> to the mailing list?
> 

As you prefer, I'll review them anyway :). I guess you can just
send them on the list if you like, so that you'll receive more
comments in one go.

Thanks a lot,

- Juri

> 			Thanks,
> 				Luca
>>
>> ----------------------------------------
>>
>> Signed-off-by: Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>
>> ---
>>  Documentation/scheduler/sched-deadline.txt | 4 ++--
>>  1 file changed, 2 insertions(+), 2 deletions(-)
>>
>> diff --git a/Documentation/scheduler/sched-deadline.txt
>> b/Documentation/scheduler/sched-deadline.txt index 21461a0..194664b
>> 100644 --- a/Documentation/scheduler/sched-deadline.txt
>> +++ b/Documentation/scheduler/sched-deadline.txt
>> @@ -169,8 +169,8 @@ CONTENTS
>>   of all the tasks executing on a CPU if and only if the total
>> utilisation of the tasks running on such a CPU is smaller or equal
>> than 1. If D_i != P_i for some task, then it is possible to define
>> the density of
>> - a task as C_i/min{D_i,T_i}, and EDF is able to respect all the
>> deadlines
>> - of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,T_i}
>> of the
>> + a task as C_i/min{D_i,P_i}, and EDF is able to respect all the
>> deadlines
>> + of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,P_i}
>> of the densities of the tasks running on such a CPU is smaller or
>> equal than 1 (notice that this condition is only sufficient, and not
>> necessary). 
> 

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Luca Abeni]

On 04/08/2015 11:31 AM, Juri Lelli wrote:
> Hi Luca,
>
> On 03/04/15 11:52, Luca Abeni wrote:
>> Hi,
>>
>> On Fri, 3 Apr 2015 16:18:33 +0800
>> Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com> wrote:
>>
>>> >From the contex,the definition of the destiny of a task
>>> C_i/min{D_i,T_i},where T_i is not referred before, should be
>>> substituted by C_i/min{D_i,P_i}.
>> You are right, "T_i" should be substituted with "P_i"...
>> But now that I look at it more carefully, I think that "C_i" is also
>> wrong... It should be "WCET_i".
>>
>>
>> BTW, speaking about documentation: I still have some SCHED_DEADLINE
>> documentation patches in my local tree... I'll update and send them in
>> next week. Juri, should I send the patches to you, or submit directly
>> to the mailing list?
>>
>
> As you prefer, I'll review them anyway :). I guess you can just
> send them on the list if you like, so that you'll receive more
> comments in one go.
Ok; I am finishing to check what I wrote, and I'll send an RFC to the
mailing list after lunch.


			Thanks,
				Luca

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Henrik Austad]

On Fri, Apr 03, 2015 at 04:18:33PM +0800, Zhiqiang Zhang wrote:
> From the contex,the definition of the destiny of a task

I'm sure we would all like to have a perfect scheduler, however, knowing 
the destiny of a task is a bit beyond what we can do now ;)

> C_i/min{D_i,T_i},where T_i is not referred before, should be
> substituted by C_i/min{D_i,P_i}.

Actually, I'd prefer we use T_i to describe the period and not P because:

- P is easy to confuse with priority - which has _nothing_ to do with 
  deadline scheduling

- I was going to state that "the litterature is consistent in its usage of 
  'T_i' for task i's period". But then I dived through some of the books 
  and of course it isn't. Buttazzo use T, Jane Liu use P and so on. 
  However, I state that *most* litterature use T_i do denote the period of 
  task i. Burns & Davis has a nice summary of RT-litterature [1].

So I'd rather prefer a s/P_i/T_i/ throughout the text.

I realise that I've reviewed quite a lot of this, and I have some vague 
memories of this being discussed earlier, Juri? Luca?


> ----------------------------------------
> 
> Signed-off-by: Zhiqiang Zhang <zhangzhiqiang.zhang@huawei.com>
> ---
>  Documentation/scheduler/sched-deadline.txt | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/Documentation/scheduler/sched-deadline.txt b/Documentation/scheduler/sched-deadline.txt
> index 21461a0..194664b 100644
> --- a/Documentation/scheduler/sched-deadline.txt
> +++ b/Documentation/scheduler/sched-deadline.txt
> @@ -169,8 +169,8 @@ CONTENTS
>   of all the tasks executing on a CPU if and only if the total utilisation
>   of the tasks running on such a CPU is smaller or equal than 1.
>   If D_i != P_i for some task, then it is possible to define the density of
> - a task as C_i/min{D_i,T_i}, and EDF is able to respect all the deadlines
> - of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,T_i} of the
> + a task as C_i/min{D_i,P_i}, and EDF is able to respect all the deadlines
> + of all the tasks running on a CPU if the sum sum_i C_i/min{D_i,P_i} of the

My argument for T_i vs. P_i aside, I do agree that we should not use T_i 
here whilst using P_i in other places. We should strive to be internally 
consistent above all else.

So *if* we are going to use P_i for period, then this is correct and should 
be applied.

>   densities of the tasks running on such a CPU is smaller or equal than 1
>   (notice that this condition is only sufficient, and not necessary).
>  
> -- 
> 1.9.0
> 

Just my $0.02 etc etc :)


1) http://www-users.cs.york.ac.uk/~robdavis/papers/MPSurveyv5.0.pdf

-- 
Henrik Austad

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Luca Abeni]

Hi Henrik,

On Fri, 3 Apr 2015 19:57:37 +0200
Henrik Austad <henrik@austad.us> wrote:
[...]
> > C_i/min{D_i,T_i},where T_i is not referred before, should be
> > substituted by C_i/min{D_i,P_i}.
> 
> Actually, I'd prefer we use T_i to describe the period and not P
> because:
> 
> - P is easy to confuse with priority - which has _nothing_ to do with 
>   deadline scheduling
> 
> - I was going to state that "the litterature is consistent in its
> usage of 'T_i' for task i's period". But then I dived through some of
> the books and of course it isn't. Buttazzo use T, Jane Liu use P and
> so on. However, I state that *most* litterature use T_i do denote the
> period of task i. Burns & Davis has a nice summary of RT-litterature
> [1].
I think literature is more or less equally divided between "P" and
"T" (I suspect I personally used different letters in different
papers :)


> So I'd rather prefer a s/P_i/T_i/ throughout the text.
> 
> I realise that I've reviewed quite a lot of this, and I have some
> vague memories of this being discussed earlier, Juri? Luca?
I remember there was a discussion (and I seem to remember that the
symbol used for the period was changed at least one time, but I might
be wrong), but I do not remember the details.

Next week I'll have some time for working on this; I'll search the old
emails and I'll try to reconstruct the discussion.

[...]
> > - a task as C_i/min{D_i,T_i}, and EDF is able to respect all the
> > deadlines
> > - of all the tasks running on a CPU if the sum sum_i
> > C_i/min{D_i,T_i} of the
> > + a task as C_i/min{D_i,P_i}, and EDF is able to respect all the
> > deadlines
> > + of all the tasks running on a CPU if the sum sum_i
> > C_i/min{D_i,P_i} of the
> 
> My argument for T_i vs. P_i aside, I do agree that we should not use
> T_i here whilst using P_i in other places. We should strive to be
> internally consistent above all else.
I fully agree with this ;-)


			Luca

Re: [PATCH] Documentation/scheduler/sched-deadline.txt: correct definition of density as C_i/min{D_i,P_i}

[Luca Abeni]

On 04/03/2015 09:47 PM, Luca Abeni wrote:
> On Fri, 3 Apr 2015 19:57:37 +0200
> Henrik Austad <henrik@austad.us> wrote:
[...]
>> I realise that I've reviewed quite a lot of this, and I have some
>> vague memories of this being discussed earlier, Juri? Luca?
> I remember there was a discussion (and I seem to remember that the
> symbol used for the period was changed at least one time, but I might
> be wrong), but I do not remember the details.
>
> Next week I'll have some time for working on this; I'll search the old
> emails and I'll try to reconstruct the discussion.
Sorry, after searching in my old emails I've not been able to find
references to this particular topic (T_i vs P_i).
Maybe I lost some emails, or maybe I mis-remembered the old discussion...

Anyway, as I said I am fine with changing P_i in T_i if there is a general
agreement.



				Luca