Re: Anomalous performance increase from mutex profiling

>From: Surer Dink <surerlistmail_at_gmail.com>
>Sent: Apr 17, 2006 11:12 AM
>To: Kris Kennaway <kris_at_obsecurity.org>, smp_at_freebsd.org, current_at_freebsd.org
>Subject: Re: Anomalous performance increase from mutex profiling
>
>On 4/17/06, Kris Kennaway <kris_at_obsecurity.org> wrote:
>> On Mon, Apr 17, 2006 at 03:54:07AM -0400, Surer Dink wrote:
>> > Please excuse if this is a stupid question - but might using MCS or
>> > QOLB locks in this situation be useful?
>>
>> What are they?
>
>Mellor-Crummy Scott:
>http://www.cs.rochester.edu/u/scott/papers/1991_ASPLOS_sync.pdf
>
>An overview comparing various possible optimizations for a few lock
>types, including MCS and QOLB:
>ftp://ftp.cs.utexas.edu/pub/dburger/papers/ISCA97_qolb.pdf
>
>I believe the QOLB proposal only suggested hardware modificaition for
>performance improvement, but could be implemented entirely in software
>- the overheads are high, but offer substantial performance benefit in
>high contention situations.  MCS is based on QOSB, however fully
>implemented in software.
>
>There is also a proposal for changing lock to MCS dynamically, however
>I have not read it:
>ftp://ftp.cag.lcs.mit.edu/pub/papers/pdf/reactive.pdf

Implementation under the GPL, including MCAS and other lockless algorithms
is available here (unfortunately, GPL'ed):

    http://www.cl.cam.ac.uk/Research/SRG/netos/lock-free/

Note that there is no general implementation that does not require use of
asembly language; e.g. the PPC does not have a CAS instruction, and it has
a weak memory model which means you will need to use an explicit barrier
in your implementation (Mac OS X/Darwin provide implementations of the
necessary atomic operations in the header file <libkern/OSAtomic.h> as of
the Tiger release).

-- Terry