[fpc-devel] LockFree Queue algorithm

[Dariusz Mazur]

Michael Schnell pisze:
>
>> FUTEX is based on atomic operation, the same as I used.
>> but with lockfree algorithms You don't protect access at all.
>
> I understand this, but I'm nut sure that this really is advantageous.
>
> Any atomic operation in a multicore system with a cache for each core 
> imposes a delay for cache synchronization. 
Any implementation of thread synchronization need care of cache. FUTEX, 
which rely on atomic primitives can't be faster than primitives alone.

In lockfree algorithms we don't block data structures at all. In any 
time others threads can  process data.

Many of researches claim that lockfree algorithms are faster, specially  
with many concurrent threads.


> Thus as little as possible "lock" operations should be issued. 99,99% 
> of the calls will not see another processor or thread concurrently 
> working on the FiFo data.
You have to prevent data loss, when You have hazard with concurrent 
process see: http://en.wikipedia.org/wiki/Concurrency_control
And when You block access do data, others thread stop.

>
> The implementation similar to Futex in the no blocked case needs one 
> lock operation on entry and one on exit. Thus using a thing similar to 
> FUTEX needs some 2,0001 locked operations per call. \
I don;t understand this



Darek