[Prev][Next][Index][Thread]
Re: CPU inheritance issue
> I think the problem you describe should not happen with a proper mutex
> implemenation.
Ok, I buy this. It would be nice to come up with a convincing argument or
proof that CPUI does the right thing, though - there are lots of nasty
cases when you get a number of threads and chained blocking.
Intuitively, CPUI is equivalent to basic priority inheritance in the sense
that they are both greedy algorithms that attempt to allow the highest
priority thread to make the fastest possible progress.
> An interesting case would be where Z blocks W/O donating time to the
> lock holder: in this case, A,B, and Z would all have to wait until
> the mutex was released and one of them was scheduled again.
> This case shows the downsides of using partial priority inheritance,
> where CPU is only sometimes donated.
Yeah - a bad priority inheritance scheme is not a good thing. Victor
Yodaiken has written some interesting notes about the difficulty of
getting these protocols right:
http://www.cs.nmt.edu/~yodaiken/articles/priority.ps
In particular, basic priority inheritance as described in the 1990 paper
by Sha, Rajkumar, and Lehoczky is incorrect. FWIW, it looks like the
OSKit implementation is correct - the difference lies in how to calculate
the priority of a thread when it releases a mutex. Sha et al. say that it
should go to the priority that it was when the mutex was acquired; what is
required is to recalculate the maximum priority of the set of blocked
threads.
John
--
John Regehr | regehr@virginia.edu | http://www.cs.virginia.edu/~jdr8d/
grad student | Department of Computer Science | University of Virginia
References: