Re: race on multi-processor solaris

From: David Butenhof (David.Butenhof_at_hp.com)
Date: 12/04/03 

Date: Thu, 04 Dec 2003 09:28:39 -0500

David Schwartz wrote:

>> The bulk of the scalability in Solaris is from a focused effort to
>> reduce contention by improving the design of data structures and
>> locking strategies. Much of this work has been data-driven. (using
>> tools like lockstat(1m) to find actual contention points and fixing
>> them)
>
> And this is what I've been trying to say. Contention is bad.
> Algorithms
> based upon locks prevent contention by descheduling jobs that would
> contend with each other. Lock-free algorithms increase contention by
> allowing contending threads to continue to run concurrently.

This is even more true when you get beyond small-scale SMP systems to
large-scale NUMA memory systems. The single key to performance is to REMOVE
contention. That means careful strategies in data subsetting and alignment,
not in locking (or nonlocking) algorithms. And spinning on any memory is
unthinkably evil -- even kernel "spinlocks" need to do some creative
multi-level synchronization gymnastics (e.g., Mellor-Crummy/Scott
algorithms) so that non-local processors have a chance in heck of ever
making any progress at all. (SenderX's favorite lock-free guarantee that
"someone" is making progress is of no use at all unless the contenders are
100% symmetrical, and that's never the case for common OS shared resource
"choke points".)

Still, of course, some lock-free algorithms can also be decentralized based
on memory locality. (For example many [though not all] "queues" could be
transparently organized as local memory branches off a shared root.) 

-- 
/--------------------[ David.Butenhof@hp.com ]--------------------\
| Hewlett-Packard Company       Tru64 UNIX & VMS Thread Architect |
|     My book: http://www.awl.com/cseng/titles/0-201-63392-2/     |
\----[ http://homepage.mac.com/dbutenhof/Threads/Threads.html ]---/

Relevant Pages

  • Re: Lock-free not useful? (was Re: Reconciling Garbage Collection with Deterministic Finalizatio
    ... There are also other "contention free" algorithms by using ... the Solaris kernel memory allocator ... allocator, no memory contention could be observed (I only had a 12-way ...
    (comp.programming.threads)
  • Re: race on multi-processor solaris
    ... > tools like lockstatto find actual contention points and fixing ... Lock-free algorithms increase contention by allowing ... algorithms that use locks can have the locking granularity very ... contention at the cost of a context switch). ...
    (comp.unix.solaris)
  • Re: Lockfree or not to lockfree thats the question !
    ... So if you have, say, 8 CPUs. ... contention while locks minimize contention. ... If the object is handled in a lock free way, one-third of the time, on ... level algorithms such as memory management, ...
    (comp.programming.threads)
  • Re: Lockfree or not to lockfree thats the question !
    ... So if you have, say, 8 CPUs. ... contention while locks minimize contention. ... If the object is handled in a lock free way, one-third of the time, on ... level algorithms such as memory management, ...
    (comp.programming.threads)
  • Re: race on multi-processor solaris
    ... Atomic as opposed to merely thread-safe? ... > You can also have contention free algorithms. ... Distribued algorithms like Peterson's algorithm and such? ... The LL/SC granularity problem? ...
    (comp.unix.solaris)