On Jul13, 2011, at 00:10 , Robert Haas wrote:
> On Jul 12, 2011, at 8:03 AM, Florian Pflug <fgp@phlo.org> wrote:
>> The algorithm is quite straight forward, if one assumes a lock-free
>> implementation of a queue (More on that below)
>
> This is similar to the CAS-based LWLocks I played around with, though
> I didn't use a lock-free queue. I think I probably need to devote some
> time to figuring out why that didn't work out to a win...
Yeah, the non-waitqueue-related parts are mostly identical. The only
significant difference there is that the waiters-present bit is replaced
by fence-and-recheck.
What motivated me to research this was your theory that the problem is
not so much spin-lock contention, but rather those unlucky processes who
lose their time-slice while holding the lock.
If that is true, then maybe the problem with your CAS patch is that
once the LWLocks is contested heavily, the waiters-present bit will be
set pretty much all the time, and the code will thus fall back to
using the spin-lock.
*Reading the code again*
Hm, I just realized that you only clear the waiters-present bit after
emptying the queue completely. With rising contention, you might reach a
point where you never empty the queue completely (unless the lock is
only ever acquired in share mode, that is). As it stands, the CAS patch
is effectively neutralized at this point. It'll even have an adverse
effect due to the higher number of atomic operations compared to the
unpatched version.
I wonder if clearing the waiters-present bit only upon clearing the
queue completely is necessary for correctness. Wouldn't it be OK
to clear the bit after waking up at least one locker? That'd still
guarantee that you cannot end up with a blocked process but no lock
holder, I believe.
best regards
Florian Pflug
