priority inheritance algorithms

Joel Sherrill joel.sherrill at
Thu Apr 25 14:44:43 UTC 2013

On 4/25/2013 9:40 AM, Gedare Bloom wrote:
> On Thu, Apr 25, 2013 at 10:34 AM, Joel Sherrill
> <joel.sherrill at> wrote:
>> On 4/25/2013 9:26 AM, yangwei weiyang wrote:
>> 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 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.
>> 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
>> --
>> Joel Sherrill, Ph.D.             Director of Research & Development
>> joel.sherrill at        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

Joel Sherrill, Ph.D.             Director of Research & Development
joel.sherrill at        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
Support Available                (256) 722-9985

More information about the devel mailing list