offlist - priority inheritance algorithms

Sun Apr 21 05:54:30 UTC 2013

在 2013-4-21，上午9:03，Gedare Bloom <gedare at rtems.org> 写道：

> I have not thought through this carefully, but you might like to consider using a rbtree instead of a heap. Heap can have trouble with duplicates, which is a problem for threads that can have the same priority.
> 
The advantage of rbtree is that there is already a implementation in RTEMS. But i do not know why it is a problem when there are the same priority threads stored in heap.  If there are two threads with the same priority waiting for two locks, the first lock is released then the other thread will be the highest priority thread. This is a correct way. I do not know whether i understand your concern, if wrong please correct me.

And if this is problem can rbtree solve this issue?

> On Apr 20, 2013 9:26 AM, "Deng Hengyi" <wei.a.yang at gmail.com> wrote:
> Hi all, 
> 
> About this issue there is a mail [1] which explains very clearly. Here i just give its basic background:
> 
> In RTEMS it implement two priority-inheritance algorithm, one is : the priority of inheritance task is not lowered until all the lock release which is used by default in RTEMS, the other one is : the priority of inheritance task is lowered in stack style when it release a lock which is implemented in RTEMS but not test. 
> 
> The implementation of the later one have a restrict that the order of lock and unlock must be FILO, if not there will be some problem(by default the kernel will post some error).  Actually this is not a general implementation and correct behavior of priority inherence.  The correct way is that whenever the lock inherence is released the priority of the thread held lock should be set to the highest priority of the thread of remain held lock. And [1] also talk about the algorithmic complexity of the possible general implementation. Its summary is listed in the wiki [2]. 
> 
> But in my option there is also a alternative method to implement the general algorithmic with O(log(n) ) and the size of usage is also acceptable.  The data struct can use heap-sort to implement a priority-queuing with insert and delete O(log(n)) and min O(1). And then we can define the maximum depth of lock acquiring and maximum thread waiting for one lock. So that its size also can be reduce to a acceptable range.  In this implementation two heap should be maintained: 
> 1. one heap to store the list of threads that are blocked on a mutex, the highest priority thread can be find with O(1).
> 2. the other heap to store the highest priority threads waiting on one of the muteness that a specific process owns. 
> 
> If a inherence mutex is released the highest priority threads among the second heap can be find easily. 
> 
> This is just my preliminary ideas, if you have any comment please add freely. 
> 
> 
> 
> 1. http://www.rtems.com/ml/rtems-users/2009/may/msg00093.html
> 2. http://www.rtems.org/wiki/index.php/RTEMS_Algorithmic_Complexity
> 
> 
> 在 2013-4-18，下午4:23，wei.a.yang <wei.a.yang at gmail.com> 写道：
> 
>> 
>> 在 2013-4-18，11:54，Xi Yang <hiyangxi at gmail.com> 写道：
>> 
>>> Hi Wei,
>>> 
>>> Sorry for late reply. 
>>> 
>>> 
>>> On 17 April 2013 20:01, wei.a.yang <wei.a.yang at gmail.com> wrote:
>>> Hi all,
>>> 
>>> My understand is that in RTEMS it implement two priority-inheritance algorithm, one is : the priority of inheritance task is not lowered until all the lock release which is used by default in RTEMS, the other one is : the priority of inheritance task is lowered in stack style when it release a lock which is implemented in RTEMS but not test.
>>> 
>>> Yes, you are right. The strict order mutex is the one I implemented 6 years ago, and the implementation was wrong...
>>> 
>>>  
>> Hi Xi, thanks for your reply. And could you point where the implementation is wrong or any reference and example, if you know how to correct it that will be better. 
>>> 
>>> And the priority inheritance algorithm do not solved the deadlock automatically. So in the implement of stack priority inheritance define   to avoid the deadlock situation. Is my understand right?
>>> 
>>> No. The goal of STRICT ORDER MUTEX was to improve the scheduling. For example, task T1's priority is A, it gets two mutexs (M1, M2), and its priority is improved to B(after M1), then to C(after M2). By default, after T1 release M2, RTEMS does not change T1's priority, so T1 is keeping working on priority M2, which is not fair for other tasks.
>>> 
>>> However, because STRICT ORDER MUTEX requires the application to acquire/release locks in FILO order, it may help applications to avoid the deadlock. But it was not designer for avoiding deadlock.
>>> 
>> Yeah I know your mean. If the order is wrong it will return err and tell the app the order is wrong but it will not solve the deadlock.
>> 
>>> Regards.
>>> 
>>>  
>>> 
>>> 在 2013-4-17，0:00，Joel Sherrill <joel.sherrill at oarcorp.com> 写道：
>>> 
>>> > Hi
>>> >
>>> > Tthe first link I found was this:
>>> >
>>> > http://stackoverflow.com/questions/108098/how-does-vxworks-deal-with-priority-inheritance
>>> >
>>> > Which explains the problem very well and how VxWorks changed
>>> > from the algorithm both RTEMS and VxWorks used to a stack
>>> > kind of algorithm.
>>> >
>>> > I want RTEMS to have both and default to more correct.
>>> >
>>> > The RTEMS code is ifdef'ed on __RTEMS_STRICT_ORDER_MUTEX__
>>> > and there really isn't a lot of code.
>>> >
>>> > --
>>> > 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/20130421/2223ac41/attachment-0001.html>