offlist - priority inheritance algorithms

Sun Apr 21 01:03:17 UTC 2013

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.
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/20130420/dc999b61/attachment-0001.html>