- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Hello,
Look at: http://www.emadar.com/fpc/lockfree.htm
In the pop() side of this lockfree quueue we have:
--------------
function gFLQueue.pop(var tm:_R):boolean;
var newhead, lastHead : integer;
begin
repeat
lastHead:=head;
if tail<>head
then
begin
pointer(newHead):=interlockedCompareExchange(pointer(head),pointer(lastHead
+1),pointer(lasthead));
if newHead=lastHead
then
begin
tm:=getObject(lastHead);
result:=true; exit;
end; end
else
begin
result:=false;
exit;
end;
until false;
end;
end.
----
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
1.12
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
per second.
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
order.
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:
http://pages.videotron.com/aminer/
Amine Moulay Ramdane.
Link Copied
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
Hello,
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;
var lasttail,newtemp:longword;
begin
if getlength >= fsize
then
begin
result:=false;
exit;
end;
result:=true;
newTemp:=LockedIncLong(temp);
lastTail:=newTemp-1;
setObject(lastTail,tm);
repeat
if CAS(tail,lasttail,newtemp)
then
begin
exit;
end;
asm pause end;
until false;
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;
begin
repeat
lastHead:=head;
if tail<>head
then
begin
obj:=getObject(lastHead);
if CAS(head,lasthead,lasthead+1)
then
begin
result:=true;
exit;
end
else backoff2.delay;
end
else
begin
result:=false;
exit;
end;
until false;
end;
----
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.
Thank you.
Amine Moulay Ramdane
- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report Inappropriate Content
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.
![](/skins/images/872293744008A34B36F8ABF94A46CC66/responsive_peak/images/icon_anonymous_message.png)
- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page