lkml.org 
[lkml]   [1999]   [Feb]   [12]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
SubjectRE: Real Time scheduler?
Date
>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/

\
 
 \ /
  Last update: 2005-03-22 13:50    [W:0.131 / U:0.024 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site