[zeromq-dev] atomic ops

[john skaller]

On 09/02/2012, at 2:54 PM, Luca Fascione wrote:

> Also, the CAS you're proposing is tantamount a spinlock, I don't quite 
> see the difference:

Yes, you're spinning. The main difference is the expectation that the
loop will only be taken a tiny fraction of the time. Whereas a conventional
spin-lock is assured to loop many times waiting on the other process.

> So, yeah, I can see it's lock-less, but I don't see that it's lock-free, 
> I'm afraid. Nor wait-free for that matter.

I won't disagree. I always had trouble with the concept. But I think
lock-free basically means not using a mutual exclusion lock.

With the mutex lock, you have to set the lock, do some work,
then clear it .. just in case another thread happens to want to 
access the same data. So you assume the worst, even when in
practice 99.99% of the time there's no contention.

With the lock-free algorithm, you just grab the data and check
its consistent, and 99.99% of the time it is, so you don't need to
loop around and try again, except on those rare cases where
there actually was a contention.

Oh dear I can't resist:

1. The Orc posts guards with radios and submachine guns up 
the street and a getaway truck, so he  can rob the candy store. 
If the cops come the guards blow them away and they all
pile into the truck and leave.

2. The Halfling just steals the candy and if the cops come
quickly puts it back on the shelf, waits till they're gone,
and steals it again.

> Your overarching point remains, unlikely to become a real problem on 
> normal systems with time-slice scheduling and such. But on a simplistic, 
> non time-sharing, system in which you had a thread per "core" and these 
> cooperatively return the core only when they're done, and assuming 
> they're clocked the same (which is likely), it seems you could starve if 
> the alignment is just right (or just unlucky, really

Yes, but you'd need Saturn, Venus and Pluto aligned and a red
cow jumping over a blue Moon.

--
john skaller
skaller at users.sourceforge.net