Re: lwlocks and starvation

I wrote:
> Neil Conway <neilc(at)samurai(dot)com> writes:
>> AFAICS, that is not the case. See lwlock.c, circa line 264: in LW_SHARED
>> mode, we check if "exclusive" is zero; if so, we acquire the lock
>> (increment the shared lock count and do not block). And "exclusive" is
>> set non-zero only when we _acquire_ a lock in exclusive mode, not when
>> we add an exclusive waiter to the wait queue.

> Ooh, you are right. I think that may qualify as a bug ...

I am thinking of addressing this issue by applying the attached patch.
The patch prevents a would-be shared locker from cutting in front of a
waiting exclusive locker. It is not a 100% solution because it does not
cover the case where a waiting exclusive locker is released, then a new
shared locker arrives at the lock before the exclusive locker is given
any cycles to acquire the lock. However I don't see any cure for the
latter problem that's not worse than the disease (granting the lock to
the released waiter immediately is definitely not better).

On the other hand we might consider that this isn't a big problem and
just leave things as they are. We haven't seen any indication that
starvation is a real problem in practice, and so it might be better to
avoid extra trips through the kernel scheduler. In particular, I think
the existing behavior may fit in better with the idea that a shared
locker should be able to acquire and release the lock multiple times
during his timeslice, regardless of whether there is contention.

And on the third hand, I think the heavily-contended LWLocks are only
taken in exclusive mode anyway, so this may be mostly a moot point.

Comments?

regards, tom lane

*** src/backend/storage/lmgr/lwlock.c.orig Sun Aug 29 01:06:48 2004
--- src/backend/storage/lmgr/lwlock.c Wed Nov 24 23:13:19 2004
***************
*** 261,267 ****
}
else
{
! if (lock->exclusive == 0)
{
lock->shared++;
mustwait = false;
--- 261,273 ----
}
else
{
! /*
! * If there is anyone waiting for the lock, we don't take it.
! * This could only happen if an exclusive locker is blocked
! * by existing shared lockers; we want to queue up behind him
! * rather than risk starving him indefinitely.
! */
! if (lock->exclusive == 0 && lock->head == NULL)
{
lock->shared++;
mustwait = false;
***************
*** 376,382 ****
}
else
{
! if (lock->exclusive == 0)
{
lock->shared++;
mustwait = false;
--- 382,394 ----
}
else
{
! /*
! * If there is anyone waiting for the lock, we don't take it.
! * This could only happen if an exclusive locker is blocked
! * by existing shared lockers; we want to queue up behind him
! * rather than risk starving him indefinitely.
! */
! if (lock->exclusive == 0 && lock->head == NULL)
{
lock->shared++;
mustwait = false;