-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

On Tue, Jan 03, 2006 at 09:22:43PM -0500, kpneal@pobox.com wrote:
> 
> A guy I know at work did some experimenting with atomic locks vs the more
> common blocking mutexes. This was in a threaded user-level application
> and not inside an OS (if it matters).
> 
It seems to me that the discussion went way off my original inquiry. I'm
not talking about atomic locks, but about shared data structures that do
not need explicit locks. E.g. parallel readers/writers of a linked list
get serialized correctly without any external locks.

Please look at the following papers:

A Pragmatic Implementation of Non-Blocking Linked-Lists
http://citeseer.ist.psu.edu/harris01pragmatic.html

The Synergy Between Non-blocking Synchronization and Operating System Structure
http://citeseer.ist.psu.edu/greenwald96synergy.html

The first paper describes what I have in mind. It is one of many papers
dealing with lock-free data structures. (I'm also a bit guilty of wrongly
naming them as "lock-free" instead of "non-blocking" in my initial post).

The other is a report on implementing a kernel on top of non-blocking
synchronization primitives. It also gives pointers to the software
implementation of CMPXCHG instruction which, I believe (didn't look into
the papers yet), could be implemented by ras(9).

> 
> Here's one example of an issue: Atomic operations spin. With many threads
> contending this results in lots of CPU being burned with little actual
> work going on. Contrast this with lock types that forfeit the CPU when
> they block.
>
Non-blocking data structures have an upper bound to latency. Achievable
latency is O(n) where n is the number of processes contending for the
data structure. It's very different from one thread acquiring a spinlock
and others indefinetly burning CPU cycles until the spinlock is released.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFDu9mTFtofFpCIfhMRA0qsAJ9cR/ycSzs49jAlENYCed/FaOI3TQCeKjJz
TyCM9SnC4jchjBk3pieyWxg=
=aI7k
-----END PGP SIGNATURE-----