Re: Proposal of tunable fix for scalability of 8.4

On 3/20/09 8:28 AM, "Matthew Wakeling" <matthew(at)flymine(dot)org> wrote:

> On Thu, 19 Mar 2009, Scott Carey wrote:
>> In type B, the ratio of requests that must context switch is always ==
>> 1. Every request must queue and wait!
>
> A remarkably good point, although not completely correct. Every request
> that arrives when the lock is held in any way already will queue and wait.
> Requests that arrive when the lock is free will run immediately. I admit
> it, this is a killer for this particular locking strategy.
>

Yeah, its the "when there is lock contention" part that is a general truth
for all locks.

As for this killing this strategy, there is one exception:
If we know the operations done inside the lock are very fast, then we can
use pure spin locks. Then there is no context switching at all, ant it is
more optimal to go from list to list in smaller chunks with no 'cutting in
line' as in this strategy. Although, even with spins, a limited number of
line cutters is helpful to reduce overall spin time.

As a general reader/writer lock spin locks are more dangerous. It is often
optimal to spin for a short time, then if the lock is still not attained
context switch out with a wait. Generally speaking, lock optimization for
heavily contended locks is an attempt to minimize context switches with the
least additional CPU overhead.

> Firstly, let's say that if the lock is in shared mode, and there are no
> exclusive waiters, then incoming shared lockers can be allowed to process
> immediately. That's just obvious. Strictly following your or my suggestion
> would preclude that, forcing a queue every so often.
>

Definitely an important optimization!

>> One way to guarantee some fairness is to compromise between the two.
>>
>> Lets call this proposal C. Unfortunately, this is less elegant than the
>> other two, since it has logic for both. It could be made tunable to be
>> the complete spectrum though.
>>
>> * exclusive-lock held and all exclusives process - first N new X
>> requests welcome, N+1 and later X requests and all shared locks queue.
>>
>> * shared-lock held and shareds process - first N new S requests welcom,
>> N+1 and later S requests and all X locks queue
>
> I like your solution. For now, let's just examine normal shared/exclusive
> locks, not the ProcArrayLock. The question is, what is the ideal number
> for N?
>
> With your solution, N is basically a time limit, to prevent the lock from
> completely starving exclusive (or possibly shared) locks. If the shared
> locks are processing, then either the incoming shared requests are
> frequent, at which point N will be reached soon and force a switch to
> exclusive mode, or the shared requests are infrequent, at which point the
> lock should become free fairly soon. This means that having a count should
> be sufficient as a "time" limit.
>
> So, what is "too unfair"? I'm guessing N can be set really quite high, and
> it should definitely scale by the number of CPUs in the machine. Exact
> values are probably best determined by experiment, but I'd say something
> like ten times the number of CPUs.

I would have guessed something large as well. Its the extremes and
pathological cases that are most concerning. In normal operation, the limit
should not be hit.

>
> As for ProcArrayLock, it sounds like it is very much a special case. The
> statement that the writers don't interfere with each other seems very
> strange to me, and makes me wonder if the structure needs any locks at
> all, or at least can be very partitioned. Perhaps it could be implemented
> as a lock-free structure. But I don't know what the actual structure is,
> so I could be talking through my hat.
>

I do too much of that.
If it is something that should have very short lived lock holding then spin
locks or other very simple structures built on atomics could do it. Even a
linked list is not necessary if its all built with atomics and spins since
'waking up' is merely setting a single value all waiters share. But I know
too little about what goes on when the lock is held so this is getting very
speculative.