Re: Lock convoys
- From: David Hopwood <david.nospam.hopwood@xxxxxxxxxxxxxxxx>
- Date: Sun, 09 Apr 2006 01:18:44 GMT
chris noonan wrote:
Back in the topic "Lock Free -- where to start" (October 2005),
I gave a quantitative example of how using a lock in a
multithreaded application can increase the number of
context switches the system suffers eleven-fold.
My analysis was of the form:
"Every time a thread is caught holding the lock at the expiry of
its scheduling quantum, the following bad things happen ..."
At the time, I couldn't extend the example to an application
in which thread switching is mainly I/O driven. Besides, eleven-
fold is enough to affect performance, but not to destroy it.
Recently I stumbled across this excellent article which
presents a more powerul mechanism:
http://blogs.msdn.com/sloh/archive/2005/05/27/422605.aspx
It's worth pointing out that asynchronous message passing is not
subject to lock convoys, or any similar problem. The equivalent design
in an async message passing system would have a server object in its own
thread/process that accepts messages from clients. The client threads do
not need to block in order to send messages to the server. Note that
this is also true if the clients need a result or confirmation that the
operation has completed; in that case each client will immediately
receive a "promise" for the result, and are called back when this promise
resolves, but they can handle other messages in the meantime.
The gist of it is that certain synchronisation objects impose
fairness, for example only allowing contending threads to take
a lock strictly in the order in which they blocked on it. Then
the argument becomes:
"If a thread is ever caught holding the lock at the expiry of
its scheduling quantum, even once, the following bad things
happen evermore ..."
It is not fairness that is responsible for this problem; it's blocking.
Even in a system where the main synchronization primitives do not block,
it is difficult to avoid some blocking (e.g. for GC or page faults), but
the less frequent it is, the less likely it is to cause performance
problems.
AFAICS, if two threads are involved, normal service is likely
to be resumed at the end of the next quantum. If more threads
are involved, the lock convoy persists indefinitely. The cost
of the convoy is one thread switch per lock access, which
could easily mean thousands of switches per quantum
(before taking into account the cost of the switches
themselves).
The example in the article is for Windows CE critical section,
and the article hints that the way critsec works is subject to
change. Does anyone know which other OS'es are likely to
show this behaviour?
In principle it can happen in any lock-based system; the implementation
of locks (or critical sections) only affects how likely it is to happen.
--
David Hopwood <david.nospam.hopwood@xxxxxxxxxxxxxxxx>
.
- References:
- Lock convoys
- From: chris noonan
- Lock convoys
- Prev by Date: Re: pthread_create() doesn't start a new thread sometimes but doesn't return non-zero value on return.
- Next by Date: Re: pthreads on freeBSD 4.7
- Previous by thread: Lock convoys
- Next by thread: Re: Lock convoys
- Index(es):
Relevant Pages
|
