priority inheritance algorithms

Fri Apr 26 14:37:03 UTC 2013

On Fri, Apr 26, 2013 at 10:22 AM, yangwei weiyang <wei.a.yang at gmail.com> wrote:
>
>
>
> 2013/4/25 Joel Sherrill <joel.sherrill at oarcorp.com>
>>
>> On 4/25/2013 9:40 AM, Gedare Bloom wrote:
>>>
>>> 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.
>>
>> 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.
>
> From the IRC log of talking about the "thread set" i got the core of "thread
> set" is to implement a class framework of how to operate the threads blocked
> by acquiring resources according to different schedulers. I do know whether
> i really understand the mechanism of "thread set", if wrong please correct
> me.
>
Right.

> The key to solve this priority inheritance algorithms is also to find a
> suitable method or algorithms to operate the threads blocked by mutex, so if
> the "thread set" is proposaled by another student i think this problem can
> be solved after the design of "thread set" is done. Because if this priority
> inheritance algorithms is solved now it also should be modified to adapt the
> "thread set".
>
Yes there may be some dependency between the two.

> But i think the "thread set" does not impact the choice of algorithms. I
> understand the "thread set" is just a framework, different algorithms to
> manage the priority ordered thread can be exsit in the "thread set", is it
> right?
I think "Thread Set" captures the notion of both the data structure
and the algorithm that manages the threads that wait for a resource.
But I guess we will see how the thread set code shapes up too.

>>
>>
>>>> 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
>>>>
>>
>>
>> --
>> 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
>>
>
>
>
> --
> Wei Yang
> Best Regards
>
> wei.a.yang at gmail.com
>