Messages in this thread | | | From | Mark Levitt <> | Subject | RE: Real Time scheduler? | Date | Fri, 12 Feb 1999 16:29:06 -0500 |
| |
>You misunderstood my example. There is no deadlock as P0 does not need >lock 1. All P0 needs is to complete the critical section and release Lock 0. >But P1 holds Lock 1 and is waiting for P0 to release lock 0. And >P2 holds Lock 2 and is waiting for P1 to release lock 1 -- so it is waiting >for P0 indirectly ... etc. >The problem is that if you rely >on priority inheritance as your solution,then you must implement >transitive inheritance and that is quite expensive.
Your examples of multiple locks are tangential to the problem then.
P0's priority is boosted to the priority of process 1. If process 2 then tries to take the lock *and* it's priority is higher than P1, P0's priority is boosted to the priority of P2. When P0 releases Lock 0, P0's priority is lowered to it's original priority. Now P2 has the lock and is higher priority than P1. When P2 releases the lock, P1 gets it.
___________________________________________________________ Mark Levitt Not reading coffee in cup A: Technical Writer Abort, Retry, Panic? Citrix Systems http://www.citrix.com ___________________________________________________________
-----Original Message----- From: Victor Yodaiken [mailto:yodaiken@ladron.cs.nmt.edu] Sent: Friday, February 12, 1999 4:16 PM To: markl@citrix.com Cc: p.steiner@t-online.de; linux-kernel@vger.rutgers.edu Subject: Re: Real Time scheduler?
> > From: Victor Yodaiken [mailto:yodaiken@ladron.cs.nmt.edu] > >Or worse, as in my example, P0 has lock L0 and P1 locks L1 and then > >hangs on L0, and P3 locks L3 and then L2 .... so that priority promotions > >are cascaded > > Your example has nothing to do with the problem that priority inheritance is > meant to solve. Your adding a second problem to the example that has a > different solution. > > In your example, Process 0 takes Lock 0. Then Process 1 takes Lock 1. Then > Process 1 tried to take Lock 0. You have a deadlock, but not one that
You misunderstood my example. There is no deadlock as P0 does not need lock 1. All P0 needs is to complete the critical section and release Lock 0. But P1 holds Lock 1 and is waiting for P0 to release lock 0. And P2 holds Lock 2 and is waiting for P1 to release lock 1 -- so it is waiting for P0 indirectly ... etc. The problem is that if you rely on priority inheritance as your solution,then you must implement transitive inheritance and that is quite expensive. P0 holds L0 P1 holds L1 waits on L0 P2 holds L2 waits on L1 P3 holds L3 waits on L2 Px with priority greater than original priority of P0 wants to run.
in this case p0 must inherit from the highest priority of P1,P2,P3 otherwise there is inversion.
To implement, when P_a tries to access resource R, if R is reserved by P_b, then P_a must increase the priority of P_b and then see if P_b is waiting on a resourse R'. If so, P_a must also increase the priority of the process holding R' and so on. When P_a releases resource R, it must revert to the highest priority of any process waiting on any resource it still holds
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |