[concurrency-interest] Low cpu usage with fair ReentrantLock

Martin Buchholz martinrb at google.com
Mon May 10 14:46:06 EDT 2010

It's hard to build a mental model of the costs of
concurrent programming operations:

- a CAS or volatile write may be 100x more expensive than a non-volatile write
- context switch may be 100x more expensive than CAS (measuring CPU time).
- On top of the CPU costs of parking, the parked thread will not get a chance to
run again until the OS gets around to reschedule it, which is probably
1 or 10 ms
on Linux (HZ).
- With fair locks, it is not only the parked thread that will not get
a chance to
run again for a scheduler quantum,
but all of the other threads that tried to acquire during the parked period.
Which will tend to limit throughput on Linux to HZ lock acquisitions per second.

Perhaps with fair locks, we should try harder to spin for a while
before blocking,
because the penalty for blocking is so very high.  But that's a big
engineering project.


On Mon, May 10, 2010 at 09:48, Doug Lea <dl at cs.oswego.edu> wrote:
> On 05/10/10 10:30, Andrew Haley wrote:
>> Does anyone have any idea why a fair ReentrantLock should result in
>> such low CPU usage?  This pattern of usage has, apparently, been
>> observed in more realistic workloads, from which this test case has
>> been extracted.
> Because blocking and unblocking a thread can be 100X more
> expensive than just performing a CAS.
> Under fair locks, even if there are on average plenty of
> "spaces" where the lock is available, a few collisions
> will tend to lead to sustained phases where the lock
> is awaiting the first waiter to wake up, causing others
> to block until it does. So the entire program can
> only run at the rate it takes to block+unblock a thread
> (a form of "convoying").
> For non-fair locks, other threads are allowed to "barge"
> in during these periods where the lock is not actually
> held, and grab the lock before head of queue wakes up.
> This tends to happen a lot, making them much faster.
> -Doug
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list