Re: Lock convoys
- From: Joe Seigh <jseigh_01@xxxxxxxxxx>
- Date: Sun, 09 Apr 2006 10:50:07 -0400
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
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 ..."
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?
I think this is just the problem that if you have contention on
a lock, the suspend/resume overhead on waiting threads gets added
to the service time for a critical section so you get a hysteresis
effect if you graph performance of the critical section under
increasing and decreasing contention.
Adaptive mutexes do somewhat better than FIFO mutexes since they
allow "queue jumping" and successful queue jumpers don't add
suspend/resume overhead as long as the contention is not constant.
Other strategies to reduce overhead is to spin on the lock for a
a while if the lock owner is executing, the trade off being the
overhead of spinning vs. suspend/resume overhead not taken.
Another strategy is to boost the priority of threads holding the
lock to speed things up. Can also be used as a solution for
priority inversion.
--
Joe Seigh
When you get lemons, you make lemonade.
When you get hardware, you make software. .
- References:
- Lock convoys
- From: chris noonan
- Lock convoys
- Prev by Date: Re: Lock convoys
- Next by Date: Re: Lock convoys
- Previous by thread: Re: Lock convoys
- Next by thread: thread safe dynamic array and/or matrix
- Index(es):
Relevant Pages
|
