Re: Lock-Free stack in Ada SPARK

[stevenselectronicmail@gmail.com]

On Saturday, February 11, 2017 at 2:40:23 PM UTC-8, Dmitry A. Kazakov wrote:
> On 2017-02-11 20:36, Jeffrey R. Carter wrote:
> > Perhaps someone will enlighten me.
> >
> > All of the lock-free structures that I've looked at involved busy
> > waiting on a memory location via an atomic test-and-set/compare-and-swap
> > operation.
> 
> Yes.
> 
> > To my mind, that's an implementation of a lock, and I don't understand
> > why these are considered lock free.
> 
> You are right. An implementation based on protected objects is clearly a 
> blocking.
> 
> Yet in its idea protected objects meant to be somewhere in-between. 
> Logically, at the application level, a protected action is considered 
> "instant" and thus logically it is "lock-free", provided the programmer 
> does not abuse it running cycles on the context of a protected action.
> 
> But it is not instant at the machine level. If the protected object 
> overhead were comparable to a few normal processor instructions and 
> would never cause any task losing the CPU, then it might be considered 
> "lock-free" both logically and physically. But it certainly not so on 
> most architectures.
> 
> -- 
> Regards,
> Dmitry A. Kazakov
> http://www.dmitry-kazakov.de

Dmitry you seem confused. I don't use normal protected objects. I use the special Lock_Free pragma which allows to generate lock-free code for certain very restricted protected objects.