priority inheritance algorithms

[Gedare Bloom]

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.

> 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.

> 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
>