2015-04-03 08:22:06

by Zhiqiang Zhang

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

>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 <[email protected]>
---
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


2015-04-03 11:03:24

by Luca Abeni

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

Hi,

On Fri, 3 Apr 2015 16:18:33 +0800
Zhiqiang Zhang <[email protected]> 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 <[email protected]>
> ---
> 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).

2015-04-03 17:57:49

by Henrik Austad

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

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 <[email protected]>
> ---
> 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

2015-04-03 19:47:32

by Luca Abeni

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

Hi Henrik,

On Fri, 3 Apr 2015 19:57:37 +0200
Henrik Austad <[email protected]> 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

2015-04-07 09:48:29

by Luca Abeni

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

On 04/03/2015 09:47 PM, Luca Abeni wrote:
> On Fri, 3 Apr 2015 19:57:37 +0200
> Henrik Austad <[email protected]> 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

2015-04-08 09:31:04

by Juri Lelli

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

Hi Luca,

On 03/04/15 11:52, Luca Abeni wrote:
> Hi,
>
> On Fri, 3 Apr 2015 16:18:33 +0800
> Zhiqiang Zhang <[email protected]> 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 <[email protected]>
>> ---
>> 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).
>

2015-04-08 10:34:38

by Luca Abeni

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

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 <[email protected]> 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