priority inheritance algorithms

Fri Apr 26 14:22:13 UTC 2013

2013/4/25 Joel Sherrill <joel.sherrill at oarcorp.com>

> On 4/25/2013 9:40 AM, Gedare Bloom wrote:
>
>> On Thu, Apr 25, 2013 at 10:34 AM, Joel Sherrill
>> <joel.sherrill at oarcorp.com> wrote:
>>
>>> On 4/25/2013 9:26 AM, yangwei weiyang wrote:
>>>
>>>
>>> 2013/4/25 Pavel Pisa <ppisa4lists at pikron.com>
>>>
>>>> Hello Deng Hengyi,
>>>>
>>>> On Thursday 25 April 2013 07:27:20 wei.a.yang wrote:
>>>>
>>>>> Hi, Pavel. Thank you for your advice. And in my former mail my proposal
>>>>> is
>>>>> very similar with the mechanism in the Linux. But the different is that
>>>>> I
>>>>> use two min-heap instead of two plist because of good algorithm
>>>>> complexity
>>>>> of min-heap.
>>>>>
>>>> It worth to evaluate what is better algorithm - RB-tree or min-heap.
>>>> RB tree allows to use "static" nodes which are part of the task
>>>> structure. The classic array base heap tree with 2n and 2n+1 children
>>>> requires per queue array allocation and result in the limited/compile
>>>> time defined depth or requires reallocations. But may it be you have
>>>> other algorithm on mind.
>>>>
>>>>  Yeah,  now in my opinion the algorithm candidates are RB tree and
>>> min-heap.
>>> But just as you said the disadvantage of min-heap is its size
>>> allocation. So
>>> i will
>>> evalutate the two and select a more suitable for RTEMS. If you have any
>>> more
>>> better way please comment freely.
>>>
>>> Gedare and I have been discussing the idea of Thread Sets which are
>>> ordered by priority. We currently have three implementations of this
>>> functionality in RTEMS:
>>>
>>>   + Deterministic Priority Scheduler's bitmaps and FIFO set
>>>   + Simple Priority Scheduler single list
>>>   + Thread Queue Priority Blocking Block2N structure
>>>
>>>  There is also the rbtree ready queue in EDF/CBS.
>>
> Forgot that one. :(
>
>  I would like to see these all use "classes" which implement the Thread
>>> Set.
>>> The choice of which algorithm to use is determined by O(space) and
>>> O(time).
>>> The decision can vary based on use case in RTEMS or application
>>> requirements.
>>>
>>>  The Thread Set for scheduling is being proposed by a different
>> student. We should avoid overlap/dependency here. Weiy is looking at
>> synchronization problems in SMP along with the atomic operations code
>> improvements. We can refactor the approach taken into a thread set
>> later if it makes sense and we have solved the Thread Set design and
>> implementation issues.
>>
> Agreed. But if his project ends up creating another one or duplicating one
> that that student would end up doing, then it needs to follow the Thread
> Set
> model rather than creating another problem.
>
> At that point, it is just a matter of who implements one class first. It
> is just
> packaging but better to do it in the right form. If he ends up creating the
> rbtree Thread Set the same as the EDF/CBS schedulers, then the other
> student just has to move the schedulers to using that.
>
> I don't want to add that work to this project. Just avoid creating work
> to be redone later.

>From the IRC log of talking about the "thread set" i got the core of
"thread set" is to implement a class framework of how to operate the
threads blocked by acquiring resources according to different schedulers. I
do know whether i really understand the mechanism of "thread set", if wrong
please correct me.

The key to solve this priority inheritance algorithms is also to find a
suitable method or algorithms to operate the threads blocked by mutex, so
if the "thread set" is proposaled by another student i think this problem
can be solved after the design of "thread set" is done. Because if this
priority inheritance algorithms is solved now it also should be modified to
adapt the "thread set".

But i think the "thread set" does not impact the choice of algorithms. I
understand the "thread set" is just a framework, different algorithms to
manage the priority ordered thread can be exsit in the "thread set", is it
right?

>
>  If we need another set managed by another structure, that is fine. But I
>>> think this set of helper classes is important to have.
>>>
>>>  I have done some testing of RTEMS and Linux PI implementations.
>>>>>> You can find my test code cor RTEMS classic API
>>>>>> and POSIX RTEMS and Linux in the repo
>>>>>>
>>>>> Good work. But I want to know the mechanism of RTEMS test. You know
>>>>> there
>>>>> are two PI algorithms in RTEMS. One is used by default, the other one
>>>>> should define __RTEMS_STRICT_ORDER_MUTEX__ to use it. You test two
>>>>> algorithms all?
>>>>>
>>>> I have tested default one. The __RTEMS_STRICT_ORDER_MUTEX__ should
>>>> behave as expected but there is risk that some code/libray we use
>>>> does not access mutexes in the strict LIFO order.
>>>>
>>>> Best wishes,
>>>>
>>>>               Pavel
>>>>
>>>
>>>
>>>
>>> --
>>> Wei Yang
>>> Best Regards
>>>
>>> wei.a.yang at gmail.com
>>>
>>>
>>>
>>> --
>>> Joel Sherrill, Ph.D.             Director of Research & Development
>>> joel.sherrill at OARcorp.com        On-Line Applications Research
>>> Ask me about RTEMS: a free RTOS  Huntsville AL 35805
>>> Support Available                (256) 722-9985
>>>
>>>
>>> ______________________________**_________________
>>> rtems-devel mailing list
>>> rtems-devel at rtems.org
>>> http://www.rtems.org/mailman/**listinfo/rtems-devel<http://www.rtems.org/mailman/listinfo/rtems-devel>
>>>
>>>
>
> --
> Joel Sherrill, Ph.D.             Director of Research & Development
> joel.sherrill at OARcorp.com        On-Line Applications Research
> Ask me about RTEMS: a free RTOS  Huntsville AL 35805
> Support Available                (256) 722-9985
>
>

-- 
Wei Yang
Best Regards

wei.a.yang at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130426/2d1836b5/attachment-0001.html>