Messages in this thread | | | Date | 2 Jun 2005 00:52:59 -0000 | From | linux@horizon ... | Subject | RE: [PATCH] Abstracted Priority Inheritance for RT |
| |
>>> 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/
| |