[sc-users](OT)Some notes on lock-free and wait-free algorithms

[Arie van Schutterhoef <arsche@xxxxxxxxx>]

Some notes on lock-free and wait-free algorithms
http://www.audiomulch.com/~rossb/code/lockfree/
Ross Bencina
11 May 2006

Over the past two decades the research community has developed a body of
knowledge concerning "Lock-Free" and "Wait-Free" algorithms and data
structures. These techniques allow concurrent update of shared data
structures without resorting to critical sections protected by operating
system managed locks. A number of wait-free and lock free algorithms for
simple data structures such as LIFO stacks and FIFO queues have been
published. Lock-free algorithms for more complex data structures such as
priority queues, hash tables, sets, and red-black trees are also known.

Some of the most commonly stated benefits of lock-free synchronisation are:

    * Efficiency benefits compared to lock-based algorithms for some
workloads, including potential scalability benefits on multiprocessor
machines.
    * Support for concurrent update to shared data structures even when
locks aren't available (e.g. in interrupt handlers etc.)
    * Avoidance of priority inversion in real-time systems.

A significant benefit of lock (or wait)-freedom for real-time systems is
that by avoiding locks the potential for priority inversion is avoided.
Solutions for avoiding priority inversion usually involve special real-time
process schedulers. On platforms where a real-time scheduler is not
present, lock-free data structures provide an opportunity to sidestep the
hazards of interlocking with the scheduler.

With the exception of a uniprocessor implementation of a single-reader
single-writer ring buffer FIFO, all the lock-free algorithms which I have
encountered require the use of special atomic processor instructions such
as CAS (compare and swap) or LL/SC (load linked/store conditional).
Furthermore, the correct implementation of these algorithms also requires
an understanding of the use of memory barriers to force the order of some
memory reads and writes on SMP systems. This is because memory controllers
may reorder reads and writes as observed by other processors on an SMP
system (or by prehipherals on a uniprocessor system).

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.....................................................................

  `    |Schreck Ensemble    . . . . . . . . . . . . . . . . . . . . +

    `  |# -laboratory for live electro-acoustic music- #            |
       |             http://www.schreck.nl/                         |
       |             http://www.xs4all.nl/~schreck/                 |
     ` *===========================================================++
     ` |Compositions http://www.xs4all.nl/~schreck/html/compo.html  |
     ` |Samples      http://www.xs4all.nl/~schreck/html/samp.html   |
     ` |Patches      http://www.xs4all.nl/~schreck/html/pat.html    |
     ` |Videos       http://www.xs4all.nl/~schreck/html/video.html  |

     ` |Scores       http://www.xs4all.nl/~schreck/html/scores.html |

       *===========================================================++
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.....................................................................