3 replies to this topic

[joninty]

I want to use use compare and swap in linked list
Lets say I had a CompareAndSwap(int* address, int compareTo, int swap);
so if the value at address is the same as compare to I put the value of swap into the address.
I then return the value at address.
How would I use this to insert at front and delete nodes, to make a lock free linked list?
Cheers,
Jo

[mnirahd]

Hi Jo,

Can you please make some more explanation of what you're trying to do!

If I've understood correctly you would be creating a link list that would be operated by a more than one threads. In such case, you need to make link list insertion and deletion operations thread-safe by using mutex/semaphore. This would ensure that link list is not corrupted.

I could put some example code for you. Please can you tell me what OS you're working on. Linux or Widows?

Munir

[joninty]

Its an OS independent algorithm.
I'm just wonder how I the use of CompareAndSwap() might effect my standard insert and delete functions. I dont want to lock the data.
Hope that makes sense!

[Groogy]

**EDIT**
Sorry, just saw that I misunderstood completely. Give me a sec and I might have something for you.

Well the thing with List an the like is that they are data structures/containers and those most generally not capable of being run in parallel without a lock. What you can do is change how you work WITH them. Like the example I gave when I misunderstood your "CompareAndSwap" for a sorting algorithm.

A very good thumb rule when it comes to multicore programming. If it's not simple then don't do it.

But I might have found something of interest for you here. But this will still act as a kind of lock
since the while loop will keep trying until it can get it right. And I don't think it's 100% safe.

void push(int t)

{

        Node * node = new Node(t);

        do

        {

                 node->next = head;

         } while(!CompareAndSwap(&head, node, node->next));

}

Reference: http://www.cs.cmu.ed...31_LockFree.pdf page 14

Previous:

Quote

We're going trough multicore programming at my university currently. Our last session was about synchronization nodes which should work perfect for you.

You divide the linked list into several different chunks, then you give each thread it's own chunk to work with. The most simple implementation would be that each thread is allocated the chunk at the start of execution and is done when finished with that chunk. And when the threads are all done they reach the "synchronization node" where the main thread takes over again. The task to be done is to put all the chunks back together.

I might have miss-understood what you were looking for but since you said lock free list this is what came to mind.

Edited by Groogy, 31 October 2010 - 03:49 PM.