[fpc-devel] LockFree Queue algorithm

[Michael Schnell]

> Any implementation of thread synchronization need care of cache. 
> FUTEX, which rely on atomic primitives can't be faster than primitives 
> alone.
I said that (using locking instructions to implement a semaphore) I 
might implement something that works similar to FUTEX. I don't intend to 
_use_ FUTEX.
>
> In lockfree algorithms we don't block data structures at all. In any 
> time others threads can  process data.
Of course that is what the software sees. But the use of the "lock" 
instruction will stall this (and other) threads nonetheless. So we can 
discuss what way is the most effective:  IMHO that which uses the fewest 
count of lock instructions in the pass when no blocking due to 
concurrent access is necessary.
>
> 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 blocking due to concurrency will occur very seldom. So the 
implementation of the program path that only checks for the need of 
blocking and sets the semaphore (which needs to be done with the 
appropriate bus-lock hardware support) but does not actually block is 
the critical issue.

-Michael