offlist - priority inheritance algorithms

[Gedare Bloom]

Ah, ok. Then a heap might be fine. We just need to consider carefully
all of the use cases.

>>> 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.
>>>>
I don't understand.. there is no "process" in RTEMS, so number 2 does
not make a lot of sense. All you need is number 1 I think? But you
need this structure for every mutex.

-Gedare