priority inheritance algorithms

yangwei weiyang wei.a.yang at gmail.com
Thu Apr 25 14:26:32 UTC 2013


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.

 > > 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130425/76b9d46b/attachment.html>


More information about the devel mailing list