Tuesday, March 17, 2015

Digest for comp.programming.threads@googlegroups.com - 10 updates in 4 topics

Ramine <ramine@1.1>: Mar 16 07:59PM -0700

Hello,
 
 
You have seen me talking about Seqlock in my previous post,
i have giving you a mechanism so that you can use
Seqlock with datastructures with pointers, but there is still
a problem, you have to proove that this mechanism works correctly
with algorithms such as AVL trees and Red Black tree and Skiplists,
but because you can not use this mechanism without proving 100%
that it is working correctly, so since it is not yet proved 100% ,
so the safe way is to avoid Seqlock in this situation and
use the following scalable Distributed reader-writer mutex:
 
https://sites.google.com/site/aminer68/scalable-distributed-reader-writer-mutex
 
 
 
Thank you,
Amine Moulay Ramdane.
bleachbot <bleachbot@httrack.com>: Mar 16 10:09PM +0100

bleachbot <bleachbot@httrack.com>: Mar 16 10:50PM +0100

bleachbot <bleachbot@httrack.com>: Mar 16 10:57PM +0100

bleachbot <bleachbot@httrack.com>: Mar 16 11:45PM +0100

bleachbot <bleachbot@httrack.com>: Mar 17 12:53AM +0100

Ramine <ramine@1.1>: Mar 16 06:52PM -0700

Hello,
 
 
We have to be smart, i have come to an interresting subject...
 
As i have told you before, my SeqlockX is a Seqlock variant that
has eliminated the livelock of the readers when there is many writers,
but as you know you can not use datastructures that use pointers
with Seqlock, so how can we elevate this problem ? this is
an interresting subject, because the Dmitry's Distributed Reader-Writer
mutex is using an atomic lock that uses an mfence , so it is expensive,
so how can i elevate this problem without using RCU ? so i have
tried to reread my AVL sequential algorithm especially in the
FindSuccessor() method that is used for the iterator and the FindKey()
method... so i don't think there is a problem with those methods if they
are used with my SeqlockX , the only problem is when there is
an access violation exception, and this exception will be catched
in Delphi and FreePascal with the following code:
 
try
 
// your reader section here
 
except
On E : EAccessViolation do;
else
raise;
end;
 
 
So i think we can safetly use my SeqlockX with an AVL tree
algorithm to render the AVL tree a fast and concurrent AVL tree..
i don't think that there is a problem with a Skiplist either,
because look at the search() function inside the Skiplist algorithm:
 
function search(l : list; key : keyType; var value : valueType) : boolean;
var k : integer;
p,q : node;
begin
p := l^.header;
for k:= l^.level downto 1 do begin
q := p^.fwd[k];
while q^.key < key do begin
p := q;
q := p^.fwd[k];
end;
end;
if (q^.key <> key) then search := false
else begin
value := q^.value;
search := true;
end;
end;
 
 
If k generates an access violation this will be catched inside the
SeqlockX reader section, that's the same for q^.value or q^.key, other
than that i don't think there is a problem... so no need to use RCU,
my SeqlockX will works just fine with AVL tree and Red Black tree and
with Skiplists and with link lists..
 
 
 
 
Thank you,
Amine Moulay Ramdane.
Ramine <ramine@1.1>: Mar 16 05:15PM -0700

Hello,
 
 
Today i will speak about my SeqlockX that is a variant of the classical
Seqlock that eliminates livelock of the readers when there is many writer.
 
You will read on internet that Seqlock doesn't work with datastructures
that work with "pointers", because when you use the reader section
in an optimistic way, if the writers modify some pointers , you can get
an "exception", so since it is an exception what can we do about it ?
in Delphi and FreePascal you can catch this exception called
"EAccessViolation" inside the reader section like this:
 
try
 
// your reader section here
 
except
// IO error
On E : EAccessViolation do;
else
raise;
end;
 
 
So this way you can effectively use my SeqlockX with datastructures that
uses pointers.
 
 
 
Thank you,
Amine Moulay Ramdane.
Ramine <ramine@1.1>: Mar 16 05:56PM -0700

Hello,
 
 
I think this will work with a linklist and with a SkipList,
i am not sure for AVL trees and Red-Black trees...
 
 
 
Thank you,
Amine Moulay Ramdane.
 
 
 
 
On 3/16/2015 5:15 PM, Ramine wrote:
Ramine <ramine@1.1>: Mar 16 06:03PM -0700

Hello,
 
 
Forget my method , i think it's not good...
 
 
If you are using a read-mostly datastructure with pointers don't use
Seqlock, please use instead the Scalable Distributed Reader-Writer Mutex
here:
 
 
https://sites.google.com/site/aminer68/scalable-distributed-reader-writer-mutex
 
 
Thank you,
Amine Moulay Ramdane.
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.programming.threads+unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)