[concurrency-interest] a little lock free algorithm

studdugie studdugie at gmail.com
Thu Mar 30 21:03:46 EST 2006

Wow! Thank you!

First I want to explain why the class exists so you'll understand the
problem that I set out to solve. Then I'll post the code.

The class is part of a larger network app where one of its features is
that it tracks the availability of the hosts that it communicates
with. The idea is if communicating with a host fails enough times the
host is blacklisted and no attempts will ever be made to communicate
w/ that host in the future (unless someone restarts the system/box).
The system is designed such that it is highly likely that multiple
threads are concurrently communicating with the same host. So lets
assume that there are 8 such threads.

To get from the point where a host fails to when it's blacklisted is
implemented via a simple back off algorithm. The problem that the
class sets out to solve is managing what happens when those 8 threads
realize (simultaneously) that the host failed. Logically speaking,
even though the object will receive 8 requests to update the counters
responsible for calculating the back off, at most only one should
actually do an update.

Now solving this problem using mutual exclusion locking is easy but I
decided, what the hey, we've got a shinny new memory model with new
rules for volatile fields and spiffy atomic classes, so let my try my
hand at a lock free solution.

On 3/30/06, David Holmes <dcholmes at optusnet.com.au> wrote:
> Post away!
> David
> > -----Original Message-----
> > From: concurrency-interest-bounces at cs.oswego.edu
> > [mailto:concurrency-interest-bounces at cs.oswego.edu]On Behalf Of
> > studdugie
> > Sent: Friday, 31 March 2006 9:52 AM
> > To: concurrency-interest at cs.oswego.edu
> > Subject: [concurrency-interest] a little lock free algorithm
> >
> >
> > I've got  ~30 line class that performs a series of updates atomically
> > w/o mutual exclusion locking. I've tested it on a quad processor box
> > using 4, 8, and 16 threads and so far it hasn't produced any incorrect
> > results.  I was wondering if I could post it here to get a second (or
> > third, forth, etc) opinion on whether it works or I'm just getting
> > lucky?
> >
> > Regards,
> >
> > Dane
> >
> > _______________________________________________
> > Concurrency-interest mailing list
> > Concurrency-interest at altair.cs.oswego.edu
> > http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest

More information about the Concurrency-interest mailing list