RE: [PATCH] Abstracted Priority Inheritance for RT

[linux@horizon.com]

>>> Do you plan to use that callback for priority inheritance?
>>> If so: It would lead to an recursive algorithm. That is not very nice in
>>> the kernel with a limited call-stack. It is not so much a problem if the
>>> mechanism is used in the kernel only, but if it is used for user-space
>>> locking, which can have unlimited neesting, it is potential problem.
>>
>> I'm not sure I see how this could become recursive, could you explain
>> more?
?
> Maybe he is referring to the case?
> 
> A owns M
> B owns N and is waiting for M
> A is trying to wait for N

No, that's just a straight deadlock and a bug whether you have PI oir not.
The recursive concern is the following case:

Process priorities: A < B < C < ...

Process A holds lock 1
Process B holds lock 2 and is trying for lock 1
Process C holds lock 3 and is trying for lock 2
Process D holds lock 4 and is trying for lock 3

Now see what happens when high-priority process E tries to
take lock 4.  We need to push its priority all the way down
the chain to process A.

If a process is only allowed to try for one lock at a time, that could,
in theory, be done iteratively, but it might take some care.


Actually, the tricky part of priority inheritance implementation is
usually dropping the priority properly when locks are released.

For example, with priorities A < B < C:
Process A holds locks 1 and 2
Process B is trying for lock 1
Process C is trying for lock 2

Now, if process A were to drop lock 1, its priority would stay
elevated to C's level.  But if it were to drop lock 2, its
proproty would drop to B's level, and C would preempt it.
You can come up with some very perverse priority trees this way.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/