EDF Pluggable Scheduler

[Gedare Bloom]

On Mon, Apr 4, 2011 at 1:14 PM, Petr Benes <benesp16 at fel.cvut.cz> wrote:
> Hi,
>
> Thank you for the reply, it looks that for the best convenience matching to
> the current pluggable scheduler framework your advice regarding the
> Scheduler_Update is reasonable and instinctive.
>
> However, I have just one more question. If we consider deadlines as
> current_priority, which is an uint32 type, since the deadline is a
> continuously increasing time, the current_priority overflows sooner or
> later. That is not a problem for the deadline comparison, I can handle it,
> but starts to matter as far as the Priority Inheritance Protocol is
> concerned. It does not know that a later deadline may be represented by a
> lower (overflown) number.
>
> How do you look upon this issue? Would be a solution to have another
> pluggable function implementing a priority comparison operation? Is this
> just a short-sighted point of view of EDF?
>
One solution would be pluggable priority comparison -- it is in fact
an approach I took when designing a generic Priority Handler. Another
solution would be to translate deadline to current priority within the
EDF scheduler when assigning absolute deadline on job release and
enforce the invariant that earlier absolute deadline corresponds to
smaller priority values. This can be done by using deadline folding
and some boundary checks to see which 'window' (high or low) the
current deadlines are using. By restricting relative deadlines to be
less than 2^7, you can even map absolute deadlines onto the 256
priority levels known by RTEMS already.

Also, I forgot to mention that if you use the rate_monotonic to create
periodic tasks, you also may find it necessary to add a call-out in
the periodic 'tick' that updates absolute deadline values. I think
this is mentioned also in Martin's thesis. It is a current gap in the
pluggable scheduler interface, which is due to the lack of knowledge
of 'period' within the score.

-Gedare

> Kind regards
>
> Petr
>
>
>
> On 03/31/2011 09:15 PM, Gedare Bloom wrote:
>>
>> Hi Petr,
>>
>> This is an interesting project. I did not concern myself with
>> synchronization issues, so I did not implement anything to deal with
>> deadilne interchange. With the pluggable scheduler framework, it
>> should be sufficient to implement Scheduler_Update -- I don't know if
>> enough information is passed currently, you may need to ensure that
>> current_priority always represents the thread's deadline.
>>
>> I consider this a failing of the tight integration of threads and
>> priority values. I tried to refactor this priority handling into a
>> separate Priority Handler, but it was hard to separate the priority
>> logic and still have efficient thread management.  It might be
>> worthwhile to reconsider this in light of the need to handle priority
>> in an opaque way in the mutex code.
>>
>> There was another edf implementation done (
>> http://code.google.com/p/rtems-edf/ ) that is based on Martin's work
>> as well. It was implemented before the pluggable interface.
>>
>> I have not revised my EDF to fit the current pluggable framework (it
>> is close, but some variations), as I am waiting on the merge of the
>> red-black tree (https://www.rtems.org/bugzilla/show_bug.cgi?id=1641).
>>
>> Good luck, and feel free to contact me for more details/assistance.
>> Gedare
>>
>> On Thu, Mar 31, 2011 at 6:59 AM, Petr Benes<benesp16 at fel.cvut.cz>  wrote:
>>>
>>> Dear Mr. Bloom,
>>>
>>> I am applying to you for an advice regarding RTEMS scheduling.
>>>
>>> I am currently working on my master thesis at CTU Prague dealing with
>>> porting a resource reservation framework (www.frescor.org) onto RTEMS. I
>>> need to ensure a temporal independence/isolation of separate tasks and
>>> for
>>> this we are to use an EDF scheduler with an incorporated CBS (Constant
>>> Bandwidth Server).
>>>
>>> As far as I am concerned, you work on some EDF or you have it done. I
>>> assume
>>> it is a pluggable one, since there is the feature in RTEMS 4.11 already
>>> implemented.
>>>
>>> I have just finished a quickie implementation of a pluggable EDF on my
>>> own
>>> (git at rtime.felk.cvut.cz:/rtems-pluggable-edf) having Martin Molnar's one
>>> as
>>> an example. I guess you know each other (he is also from CTU).
>>>
>>> The question I have is whether you happen to have some solution or at
>>> least
>>> an idea how to handle Deadline interchange and you are willing to share
>>> the
>>> experience. There is nothing reasonable proposed in the thesis by Martin
>>> Molnar (https://dip.felk.cvut.cz/browse/pdfcache/molnam1_2006dipl.pdf).
>>> So
>>> far, for sake of simplicity, I was thinking about some kind of hack
>>> making
>>> use of the current RAPs used by priority scheduling.
>>>
>>> Best regards
>>>
>>> Bc. Petr Beneš
>>> --------------------------
>>> mail  : benesp16 at fel.cvut.cz
>>> web   : www.petben.net
>>> mobile: +420 774 990 750
>>> icq   : 286131561
>>> _______________________________________________
>>> rtems-users mailing list
>>> rtems-users at rtems.org
>>> http://www.rtems.org/mailman/listinfo/rtems-users
>>>
>
>
> --
> Bc. Petr Beneš
> --------------------------
> mail  : benesp16 at fel.cvut.cz
> web   : www.petben.net
> mobile: +420 774 990 750
> icq   : 286131561
> _______________________________________________
> rtems-users mailing list
> rtems-users at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-users
>