Subj : Re: Reader Writer Puzzle
To   : comp.programming.threads
From : Joe Seigh
Date : Wed Jun 15 2005 09:43 pm

bonnie.caballero@ktd-kyocera.com wrote:
> I have some small code here for the Reader and Delete tasks.  But I
> realized that after the Reader increments p to p->next and unlocks the
> read lock, the Delete task might delete the node pointed to by
> (Reader's) p and hence, the Reader would fail when it tries to access p
> in its next loop iteration.  I'm thinking of using reference counts to
> prevent this situation but it's not yet in the code.  What do you
> think?
> 
Yes you would have a problem with nodes being deleted out from under you.
Refcounting can be used in a lock-free solution though it's a little
tricky coming up with a refcount solution that works.  See
http://atomic-ptr-plus.sourceforge.net/ for some examples of these.
The testcase is a readers/writers example, reading a linked lists
that's being concurrently modified.  It's not meant to be a teaching
example though, just for testing the different algorithms.  There's
a lot of papers written on this.  Google for lock-free linked lists
or something.

The other approach is the moving barrier.  You have a lock associated
with each node and lock the nodes you are accessing.  The lock protects
the node data and the next pointer which is part of the node.  There
should be a lock to protect the list anchor.  In this case you have
a permanent anchor node so you can use the lock associated with that.

To traverse the list, you lock the first node, lock the next node and
make it current, unlock the previous node.  After visiting the current
node as long as you want, repeat.

To delete a node, lock the previous node and then the node you are going to
delete.   Link previous node to the following node and unlock.

To add a node, you lock the node you are going to place the node after.

For add and delete, you need the traversal logic above to get to the nodes
you want to delete or insert after.


-- 
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

.