In the pop() side of this lockfree quueue we have:
function gFLQueue.pop(var tm:_R):boolean;
var newhead, lastHead : integer;
If you have noticed, after he is incrementing head with an
interlockedCompareExchange(), he is doing a tm:=getObject(lastHead);
and this is an error i think, cause if the thread
is prempeted and another thread have put another value in the same
place as lashead, the value willl be invalid and corrupted.
I have corrected this problem in my lockfree_mpmc fifo queue version
So, becarefull with those lockfree algorithms.
And i have tried to enhance my lockfree_mpmc and i have
used an exponential backoff in the pop side of the algorithm and it
gives better performance under contention with 28.317 millions pop transations
The queue with a windows critical section on both the push and the pop
sides of the algorithm scored very bad under contention with
4 threads. Here is the benchmarks using the windows critical section:
Only 370692 push transactions per second
and only 503024 push transactions per second
Now the list of memory ordering guarantees in the Intel x86 memory model:
Loads are not reordered with other loads.
Stores are not reordered with other stores.
Stores are not reordered with older loads.
In a multiprocessor system, memory ordering obeys causality (memory
ordering respects transitive visibility).
In a multiprocessor system, stores to the same location have a total
In a multiprocessor system, locked instructions have a total order.
Loads and stores are not reordered with locked instructions.
But Loads may be reordered with older stores to different locations
But what is important for us is MEMORY VISIBILITY across threads..
So, the only variables in lockfree_mpmc that are used across threads
are tail and head.. And since in a multiprocessor system, locked instructions
have a total order. So, the lock cmpxchg (inside the CAS) in the push() side
of lockfree_mpmc does in fact achieve sequential consistency and
LockedIncLong(temp) in the push side of lockfree_mpmc 1.12 also
achieve sequential consistency
And tail and head are properly aligned to avoid false sharing...
Andof course i was speaking about sequential consistency in the x86 architecture..
You candownload lockfree_mpmc 1.12 from:
Amine Moulay Ramdane.
How to verify that lockfree_mpmc is correct ?
You can for example reason like this
first , in the source code i am using a margin of
1000 threads, so you can not have more than 1000 threads
accessing the lockfree queue at the same time...
And here is the ObjectPascal source code of the push() side:
function TLockfree_MPMC.push(tm : tNodeQueue):boolean;
if getlength >= fsize
asm pause end;
So, let say the size of the bounded lockfree_mpmc queue is 1000 , and
imagine that the threads are executing the "if getlength >= fsize " all at the same
time, and imagine that the getlength() returns 999, so, the
"if getlength >= fsize" will returns false , and since we have
fSize:=(1 shl aPower) - margin inside the constructor,
with a margin of 1000 (margin must be >= to the number of threads) ,
there will be nooverflow.
And here is the source code of the pop() side:
function TLockfree_MPMC.pop(var obj:tNodeQueue):boolean;
var lastHead : longword;
As you have noticed, there is a test like this:
if CAS(head,lasthead,lasthead+1) , and this test
avoids something like the ABA problem, cause if head
have changed , the CAS() will fail.
Amine Moulay Ramdane
Microsoft Office 2010 is actually the newest software from microsoft office 2010 keys Microsoft Corporation introduced in the last year. Its leading aims tend to be to catch the present business requirements and to be on top of every competition with regard to the international market criteria. This can be a very good idea to obtain Microsoft Office 2010 Key immediately to maintain norton antivirus keys yourself up-to-date and to present you with the vast qualified progress opportunities for success. Microsoft Office 2010 is available in both 32-bit and 64-bit editions, but attention please the two are not able to co-exist on the very same personal computer. All of the Office 2010 editions are kaspersky antivirus keys suitable for Windows XP SP3, Windows Vista and Windows 7.