Re: Proposal of tunable fix for scalability of 8.4

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.

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.

> 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.

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.

Matthew

--
So, given 'D' is undeclared too, with a default of zero, C++ is equal to D.
mnw21, commenting on the "Surely the value of C++ is zero, but C is now 1"
response to "No, C++ isn't equal to D. 'C' is undeclared [...] C++ should
really be called 1" response to "C++ -- shouldn't it be called D?"