Subject: Re: lock-free data structures
To: Brett Lymn <blymn@baesystems.com.au>
From: David Laight <david@l8s.co.uk>
List: tech-kern
Date: 01/05/2006 21:35:58
On Tue, Jan 03, 2006 at 10:12:34PM +1030, Brett Lymn wrote:
> On Mon, Jan 02, 2006 at 06:03:11PM -0800, Garrett D'Amore wrote:
> >
> > Isn't this the "normal" way of handling locking on SMP class
> > machines?
> >
>
> Well "normal" for handling locking - you have a basic instruction that
> can perform an "atomic" instruction. You can use a thing called
> Peterson's Algorithm to perform the atomic lock without requiring
> underlying hardware support.
If that is the algorithm I think it might be, it doesn't work on all
architectures. Specificly it doesn't work on most sparc cpus.
The thing is that for any sort of compare+exchange instruction to be
useful it must do a locked bus cycle - so has the same basic cost
at acquiring a lock. Using a lock is much more portable.
Some CPUs have a rmw instruction, but the data written and/or the read
value is constrained in some way - so you can't do an actual exchange.
IIRC at least one cpu needs locks to be initialised to ~0.
David
--
David Laight: david@l8s.co.uk