> From: Doug Lea [mailto:dl@cs.oswego.edu]
>
> I think the underlying tension here is that many designs/algorithms
> that somehow rely on volatiles or spinning will work in the desired
> fashion only on platforms that maintain a minimal level of ("weak" or
> probablistic) fairness. Some of these designs/algorithms are
> sometimes more efficient than alternatives (on these platforms), so
> people want to be able to use them.
>
In my experience, code that relies on spinning, possibly with
Thread.yield(), is not reliable anyway. The right way to to build such code
is to put a call to something like exponential_wait(n) into the spin loop,
where n increases with the number of loop iterations and
exponential_wait(n):
- for small n spins for time exponential in n,
- for medium n calls Thread.yield(),
- for large n calls Thread.sleep to sleep for a time exponential in n.
(Ideally these should probably all randomize the wait times a bit, and you
dynamically adjust the boundary between "small" and "medium".)
If you only spin, you get horrible uniprocessor performance, since you
repeatedly end up spinning for the rest of your time slice. If you
immediately yield, you usually get horrible multiprocessor performance. If
you never sleep, you get stuck if you have multiple waiting threads, and the
thread you're waiting for happens to be at lower priority. (I think this is
unavoidable in practice, e.g. because some implementations will use
degrading priorities. You might not get stuck forever, but you will end up
wasting seconds ping-ponging between two waiting threads. Real systems tend
to have opportunities to get stuck forever as well.)
Assuming you follow this discipline, I think we need no real fairness
guarantees, beyond the guarantee that if there are runnable threads, one of
them will be run. Eventually all waiting threads go to sleep for
sufficiently long to force one of the others to run. If you don't follow a
discipline like this one, your code will be broken anyway. Thus I'm not
convinced that we need to worry about fairness in this context.
Hans
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:36 EDT