priority inheritance algorithms

[Joel Sherrill]

On 4/25/2013 9:26 AM, yangwei weiyang wrote:
>
> 2013/4/25 Pavel Pisa <ppisa4lists at pikron.com 
> <mailto: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

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.

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 <http://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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130425/40a93475/attachment.html>