[concurrency-interest] Low cpu usage with fair ReentrantLock

[Gregg Wonderly]

Andrew Haley wrote:
> On 05/10/2010 11:42 PM, David Holmes wrote:
>> Andrew Haley writes on Tuesday, 11 May 2010 2:36 AM:
>>> Perhaps so.  It's hard to tell from that javadoc exactly what is
>>> meant: I thought, from reading that, that "slower; often much slower"
>>> referred to slow operation with high CPU loads when locking rather
>>> than, as we have here, CPUs being starved of work.  But in any case,
>>> given the fact that locking is so rare, I found this result a little
>>> bit surprising.
>> Just one further comment. Locking may be "rare" from the perspective of
>> locked-work:unlocked-work, but it would seem that your threads are executing
>> in-phase, and so contention is actually high.
> 
> So it seems.  They don't start in phase, but because of the convoying
> effect they eventually move into lock-step.  I wonder how often this
> happens  the real world applications.

This happens anytime that an "event" is slower than other events.  On slower 
CPUs and systems with random delays associated with Disk I/O, network activity 
and other places where randomization occurs, these types of things can be 
remedied.  But by and large, there is not a single multi-threaded application 
which won't show this behavior in some form when mostly CPU is involved with 
some form of rendezvous point that takes much longer to execute.

Think about this as you would a highway with tollgates every 5 miles.  With 
significant traffic through the toll gates, eventually backups start, and never 
really disappear until queuing theory things kick in such that the departure 
rate finally outstrips the arrival rate.

One thing you can try, is to use random "sleeps" to distribute the "position" of 
the threads over the time interval between "gates".  Find out what the average 
time is, between gates.  Then do something like

if( contendedLastLockTooLong ) {
	Thread.sleep( (long)(Math.random(gateTime/numberOfThreads)+1) );
}

to make the thread back off it's position relative to the others in the 
"timeline" of work through the gates.

Gregg Wonderly