Re: Lock-Free stack in Ada SPARK

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

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