Subject: Re: Lock Request Queue FIFO? - msg#00001

On Sat, 1 Oct 2005, David L. Rager wrote:

Howdy All,

When several threads ask for a currently used lock, is the wait queue first
in first out, or is it nondeterministic?

Thanks in advance,
David


It's basically FIFO, but that's not guaranteed.

If there's contention for a lock, a thread waits on a semaphore, and
the semaphore's created (at least on Mach/Darwin) with FIFO scheduling
options. When the owning thread unlocks a contended lock, the owning
thread signals that semaphore, and whatever thread has been waiting
the longest should wake up and try to obtain the (now available) lock
again.

It's possible that some other thread that hasn't been waiting could
sneak in front of that recently awakened thread and obtain the lock
between the time that the owner releases it and the time that the
longest-waiting thread wakes up; the recently-awakened thread would go
back to waiting on the semaphore (and would be at the end of the
queue.)

I think that it would be hard to guarantee FIFO (as opposed to "FIFO,
but nothing prevents another thread from cutting in front of the
line") semantics without involving the OS more in non-contended cases,
and I think that that involvement would be undesirable.