1

Let's say that we have two core working on the same linked list. One insert and update an entry, another one remove an entry on specific circumstances.

Well if I don't use lock segmentation fault is obvious. Mutex lock or any lock which lock the whole process of a core is not efficient and not good for my program.

I need a kind of lock which work like this: The thread that is inserting and updates an entry work all the time without stop unless its updating an entry which is decided to be removed from list bye the other thread. It is important that both thread can work on the list simultaneously.

If anyone know what kind of lock I should use for this purpose, please share it with me.

Note that the compiler is gcc, I can't use g++.

Jaky
  • 41
  • 6
  • 2
    Since removing or adding a node in a list modifies the neighboring nodes, you can't just lock a single node. You must lock up to three nodes. Unless you can do that atomically, you will sooner or later catch a deadlock. – Some programmer dude Aug 04 '14 at 12:23
  • 3 node is also ok, yes I understand why you say I need to lock 3 node. Still I don't know how to do so. – Jaky Aug 04 '14 at 12:29
  • If you really have two threads that spend the vast majority of their time accessing the very same collection, you should rethink your design. Your two threads will spend so much of their time acquiring and releasing locks that you will not get any benefit from the parallelization, and you will pay heavy costs. – David Schwartz Aug 04 '14 at 12:39
  • @DavidSchwartz well the problem is that my linked list size is over 1 million and I already used any kind of parallelization that someone can think of to reduce link list size. to be honest I have 10 linked lists which 20 core working on them. yet I need delete to be parallel on this list other wise( as I'm doing right now without being parallel) I lose lots of data entries. – Jaky Aug 04 '14 at 12:47
  • 1
    @Jaky Then you should *definitely* rethink your design. You may want to ask a new question describing your problem and the design you're using and asking for a better design. Your cores are going to spend most of their time acquiring and releasing locks and ping-ponging the cache lines that hold them. There's almost certainly a better way. ("*I've got this great design except I need this one magic piece to make it work*" usually means you have a bad design.) – David Schwartz Aug 04 '14 at 12:50
  • 1
    Is this a single pointer linked list (next pointer only) or a double pointer (next and previous) ? When items are deleted, is that from anywhere in the list, or only the head or tail ? When items are added, is that anywhere in the list, or only at the head or tail ? Is deletion relatively rare ? It looks as if there are only ever two threads operating on one list, and only one ever deletes items... yes ? How do the threads decide what item to process next ? Can the deleting thread decide to delete an item at the same time that the other thread decides to update it ? –  Aug 04 '14 at 17:09
  • @gmch well its double pointer. To be exact the linked list is from libghthash library from http://www.bth.se/people/ska/sim_home/libghthash.html delete thread only occur every 10 second. For now I don't use 2 thread. I just pass deleting process to the same thread that insert and update, means it wont insert or update any entry until delete process finished. But its bad I loos some entry during deleting time. tell me if you need more information – Jaky Aug 04 '14 at 18:20
  • Ah. Well, if you've got just the one thread operating on the hash table, and you are losing data, then the problem doesn't appear to be a locking problem. –  Aug 04 '14 at 19:19
  • @gmch I think you didn't get it. I want to add another thread to eliminate my data losing, so I need a good lock to do so – Jaky Aug 04 '14 at 20:45

0 Answers0