ce8
Subj : Re: Lock free t-safe smart pointer based on double linked list
To   : comp.programming.threads
From : axter
Date : Thu May 12 2005 11:20 pm


rGlory wrote:
> Hi,
>
> I spent some time breaking my head on this topic recently. I got some
> interesting results (at least for me) and would like to discuss it.
> Mostly I would be happy if somebody could point that I am reinventing
> my wheel here. It is rather interesting and challenging problem for
me
> but I got into a point where I do not want to spend more of my time
on
> something that's already known.
>
> So I tried to make algorithms on lock free thread safe double linked
> list element removal and insertion. Since I am trying to implement
> smart pointer I do not need a traversal algorithm. But to find one
> would not hurt :).  So I have this:
> struct item {
>    item *forward, *backward;
> };
> and item is initialized so forward and backward point to itself.
>
> and two atomic operations:
> item *set_forward( item *to, item *it );
> item *set_backward( item *to, item *it );
>
> they set "to->forward" or "to->backward" pointer to "it"
> and return old value atomically. So the first algorithm is
> insert_right:
> void insert_right( item *left, item* it )
> {
>    set_backward( it, left );
>    item *right = set_forward( left, it );
>    item *tmp = set_forward( it, right );
>    set_backward( right, it );
> }
>
> I made a small program to check all combinations of atomic operations
> happened from different threads and it looks like that insert_right
is
> safe to another insert_right independend of where that insertion
> happened. (I checked combinations of operations up to 3 threads) Now
> trivial implementation of removal:
> void remove( item *it )
> {
>    item *left = set_backward( it, it );
>    item *right = set_forward( it, it );
>    item *tmp = set_forward( left, right );
>    set_backward( right, left );
> }
>
> This removal algorithm works safe if running in parallel of
> insert_right where left is the same as it for remove. Which is not
the
> case when item being removed is left->forward. There are some
> combinations of operations where double linked list is broken. And
what
> is interesting that all such combinations can be detected by tmp
value
> in insert_right and remove functions. But it is not simple to solve
> such situation (at least for me). Also I tried another insertion
> algorithm "insert_left" which is a reflection of
> "insert_right". Again it looks to safe to use them together if the
> same element used as first argument. But not the case when
insert_right
> uses on item and insert_left uses another one. (if there are two
> elements already in the list).
>
> There is another problem though. To use such structure as SP I need
to
> put a pointer into struct item. It is not clear to me how to safely
> assign such pointer when "everything can change any time".
>
> Any ideas?

For a thread safe C++ smart pointer, check out the following link:
http://code.axter.com/sync_ptr.h

The sync_ptr smart pointer is a wrapper class that can make the
instance of any object thread safe.  In windows it can use critical
section logic or mutex, and in UNIX/Linux it uses POSIX mutex logic.

.

0