priority inheritance algorithms

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

2013/4/25 Pavel Pisa <ppisa4lists at>

> 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
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
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the devel mailing list