EDF Pluggable Scheduler

Fri Apr 8 15:32:45 UTC 2011

Petr:

check out [1] for a description of a (hardware) deadline folding
algorithm for edf.

-Gedare

1: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641283
Scalable hardware earliest-deadline-first scheduler for ATM switching networks

On Fri, Apr 8, 2011 at 6:22 AM, Petr Benes <benesp16 at fel.cvut.cz> wrote:
> On 04/04/2011 07:30 PM, Gedare Bloom wrote:
>>
>> 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.
>
> Yes, the mapping is a fairly good idea, the numbers may be arbitrary, just
> the order should be maintained. But the problem with deadlines is that the
> mapped priorities drift away and overflow no matter what mapping I use.
> 1) Then, I can use the 'windows', in practice, I subtract half of the span
> when the priorities drift out into the second half of span. But if I do this
> at once for all pending tasks (to keep consistency of the priorities order),
> I may kill a lot of time.
> 2) I can keep updating this on every tick, so nothing is drifting out.
> And that is a real-time suicide :).
>>
>> 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
>>>
>
>
> --
> 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
>