EDF Pluggable Scheduler

Petr Benes benesp16 at fel.cvut.cz
Mon Apr 4 17:54:48 UTC 2011


Oh, thanks. This looks I can stay within the pluggable space now.
Let's see how I end up :).

Petr

P.S.: I should have posted this as a link to the git:
http://rtime.felk.cvut.cz/gitweb/rtems-pluggable-edf.git


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.
>
> 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
>>>>



More information about the users mailing list