priority inheritance algorithms

Deng Hengyi wei.a.yang at gmail.com
Sat Apr 27 14:58:44 UTC 2013


在 2013-4-26,下午11:52,Joel Sherrill <joel.sherrill at oarcorp.com> 写道:

> On 4/26/2013 9:37 AM, Gedare Bloom wrote:
>> 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.
> The best way to think of what I have in my head as Thread Set is as a pure
> virtual base class. It defines the required API for all Thread Set implementations.
> Specific algorithms with their own data structures would derive from that
> base class. I see four key operations:
> 
> + initialize
> + insert by priority
> + extract
> + get highest priority
> 
> In terms of what we have now in RTEMS,, it is comparable to how all Scheduler
> implementations have the same API but their own algorithm and data structures.
> 
> There is only one instance of a single Scheduler "class" in a system. But
> Thread Sets are more generally useful and should be able to be "instanced"
> for use by the Thread Queue, a Scheduler, or another purpose.
> 
> Does that make sense?
> 
> I don't expect you to implement the Thread Set framework, but the
> any Thread Set management should be in methods and follow the
> pattern. If you inline this code, you will create work for us later to
> extract it.
> 
I understand that the thread set management has some layers: a standard unified API, some independent components like many algorithm implementations which can be configured. So that the thread set manager just define its standard API and then the algorithm just follow its API to implement the struct and algorithm. 
>>>> 
>>>>>> 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
>>> 
> 
> 
> -- 
> 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
> 





More information about the devel mailing list