Thread: Thread safe double linked list

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    11

    Thread safe double linked list

    I nead a linked list, that can be safely accessed by more then one threads. I want to be able to add, delete and move elements in the list. I also want to be able to have something like objects that act like iterators, pointing to elements of the list. I want those iterators to be able to move forward and backward and may stay on and element for a long time. The list must protect these elements from deletion or moving (you can't move or delete element while there are iterators on it). I want it all to be as efficient as possible. For more then a week I've tried many things, but this is very very complicated. Has anyone ever met the need to have a good linked list in a multithreading environment? I really hope that someone has a solution, because it seems this situation is too complicated for my brain.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The only time I used (POSIX) threads was in an app where I wanted multiple processes to share some variables. I guess that is a main purpose of threads, and it seems to work perfectly to me.

    So it should not be a problem sharing link list pointers either. Are you having some specific problem?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So what do you want to happen when thread1 tries to delete a node which is currently pointed to by an iterator in thread2 (for a long time)?

    > you can't move or delete element while there are iterators on it
    What does this mean?
    If I insert an element before it, does that "move" it?
    What about inserting after it, does that "move" it?

    In some senses, the answer is yes for both, as the node in question is either further away from the start, or further away from the end (depending on your point of view).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    Quote Originally Posted by MK27 View Post
    The only time I used (POSIX) threads was in an app where I wanted multiple processes to share some variables. I guess that is a main purpose of threads, and it seems to work perfectly to me.

    So it should not be a problem sharing link list pointers either. Are you having some specific problem?
    All that quote tells me is that you know nothing about multithreaded programming.

    As Salem alluded to, this problem is mainly about what behavior you want to occur when threads modify nodes that have iterators pointing to them. One possible solution is to have a mutex lock for the entire list, and then another lock for each node. When an iterator is being modified, it first locks the list mutex, then locks the node mutex that it is pointing to, then finally unlocks the list mutex. Then if a different thread attempts to delete that node, that delete call will block until the iterator is deleted or moved.

    That solution is probably the easiest to implement, but it is not the most efficient. Using reader/writer locks would help out quite a bit in this situation. The iterator could get a read lock which would allow other iterators to point to the same node. That way only write calls would block for an extended amount of time. None of this covers the case where an iterator sits on a node for a long period of time though.

    There is no simple solution to this sort of problem. This is why most people choose to lock outside the container, not inside.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > and may stay on and element for a long time
    I see this as a good way to basically lock up the system for no good reason.

    Either threads are not the answer, or a list is not the answer.

    Perhaps it's time to explain the problem, and not how to fix a broken solution.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    All that quote tells me is that you know nothing about multithreaded programming.
    Yes, that is what I said. I was trying to prompt the OP, who may or may not know more than me (the later would be hard, but not impossible) a bit.

    It is still true that "there should not be a problem sharing pointers between threads", by which I meant, it is possible, how are you hung up? If I thought it was not possible, I would say "there is a problem sharing pointers between threads, such that it is impossible". But I think that would be lying.
    Last edited by MK27; 06-01-2009 at 11:45 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  7. #7
    Registered User
    Join Date
    Apr 2009
    Posts
    11
    So... about the behaviour:
    if there are iterators on an element that I want to delete there will be two variants of delete function: the first will block until the element is not pointed by enyone else, the second will return with some return code indicating that the element wasn't deleted.
    By moving element I mean take an element from the middle of the list and for example and put it in the beginning... or before or after element, pointed by another iterator.
    The locks... If I lock every element that's pointed, then there's also a problem: let's suppose that we use rw locks. I want to delete an element, so I lock it for writing. Then some other thread tries to lock it for reading and blocks. I go on deleting the element, which includes destroying the lock, so the other thread will be waiting for a destroyed lock... And besides when deleting an element I have to modify the pointers of the adjucent elements... What lock should i use for them?
    I thought about using one lock for all the list and locking it when using the pointers. It may seem more effective because only one lock is used. On the other hand I may block operations in the beginning of the list, when I want to make modifications in the end of the list. However even then I must know which element is occupied... How do I do that? I thought about putting a variable counting the iterators currently pointing to the element and protect it with the same global lock. But what do I do when I try to delete and I find out I can't? I should wait for the element to become free, right? Well, how do I know when the element becomes free... Condition variable for every element with one mutex? Even with one lock it gets pretty complicated. And I also wander if I should use a mutex or a rw lock in that case. I have to protect the pointers so I must use the lock every time I move an iteraotr. This would be very few operations, but how would it behave on a multiprocessor machine (that it will need to run on, but can't test right now)? Will one processor when lock affect the performance of the other processor? I think I will try the global lock approach, but any comments will be appreciated. Thanks

  8. #8
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,268
    The locks... If I lock every element that's pointed, then there's also a problem: let's suppose that we use rw locks. I want to delete an element, so I lock it for writing. Then some other thread tries to lock it for reading and blocks. I go on deleting the element, which includes destroying the lock, so the other thread will be waiting for a destroyed lock... And besides when deleting an element I have to modify the pointers of the adjucent elements... What lock should i use for them?
    That's why you need to have a lock for the entire list as well. When you delete a node, you first lock the entire list, then lock the node you are going to delete, then unlock both locks. A read iterator won't be able to attempt to lock the node because it must also get the list lock before it can attempt to lock the node.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Testing some code, lots of errors...
    By Sparrowhawk in forum C Programming
    Replies: 48
    Last Post: 12-15-2008, 04:09 AM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. need some help with last part of arrays
    By Lince in forum C Programming
    Replies: 3
    Last Post: 11-18-2006, 09:13 AM
  4. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM