offlist - priority inheritance algorithms

Mon Apr 22 03:34:30 UTC 2013

在 2013-4-21，23:53，Gedare Bloom <gedare at rtems.org> 写道：

> A (standard) heap does not provide any ordering guarantees among
> duplicates. So if you want to provide FIFO release semantics for tied
> priorities waiting on the lock, you cannot do that with a heap. I
> don't know if this is a requirement or not, but I suspect that FIFO
> release is important to avoid starvation.
> 
> RTEMS rbtree with duplicate support can provide ordering guarantees.
> 
Hi Gedare. I understand your mean. But in there the duplicate support is not used. Because the order of thread with the same priority is not important we just want to know the highest priority of thread. If we meet more than one highest priority thread waiting for a lock we just make sure that the thread being held a lock inherent the right priority. So the min-heap does not need to track the order of thread. I do not know whether I explain it clearly.

> -Gedare
> 
> On Sun, Apr 21, 2013 at 1:54 AM, Deng Hengyi <wei.a.yang at gmail.com> wrote:
>> 
>> 在 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
>>