EDF Pluggable Scheduler

[Petr Benes]

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