offlist - priority inheritance algorithms

Sun Apr 21 15:53:43 UTC 2013

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.

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