Lockless list help!

Question

Hi im trying to write a lockless list i got the adding part working it think but the code that extracts objects from the list does not work to good :(

Well the list is not a normal list.. i have the Interface IWorkItem

interface IWorkItem
{
    DateTime ExecuteTime { get; }
    bool Cancelled { get; }
    void Execute(DateTime now);
}

and well i have a list where i can add this :P and the idear is when i run Get(); on the list it should loop it until it finds a IWorkItem that

If (item.ExecuteTime < DateTime.Now)

and remove it from the list and return it.. i have ran tests with many threads on my dual core cpu and it seems that Add works never failed so far but the Get function looses some workitems some where i have no idear whats wrong.....

ps if i get this working any one is free to use the code :) well you are any way but i dont se the point when its bugged :P

The code is here http://www.easy-share.com/1903474734/LinkedList.zip and if you try to run it you will see that it will some times not be able to get as many workitems as it did put in the list...

Edit: I have got a lockless list working it was faster than using the lock(obj) statment but i have a lock object that uses Interlocked that was still outpreforming the lockless list, im going to try to make a lockless arraylist and se if i get the same results there when im done ill upload the result here..

Answer 1

I am in no way an expert on the subject, but as far as I can see, you need to either make the ExecutionTime-field in the implementation of IWorkItem volatile (of course it might already be that) or insert a memorybarrier either after you set the ExecutionTime or before you read it.

Answer 2

So are you sure that it needs to be lockless? Depending on your work load the non-blocking solution can sometimes be slower. Check out this MSDN article for a little more. Also proving that a lockless data structure is correct can be very difficult.

Answer 3

You can use a timestamping protocol for datastructures just fine, mirroring this example from the database world:

Concurrency

But be clear that each item needs both a read and write timestamp, and be sure to follow the rules of the algorithm clearly.

There are some additional difficulties of implementing this on a linked list though, I think. The database example would be fine for a vector where you know the array index of what you want. However, in a linked list, you may need to walk down the pointers -- and the structure of the list could change while you are searching! I guess you could solve that by some sort of nuance (or if you just want to traverse the "new" list as it is, do nothing), but it poses a problem. Try to solve it without introducing some rollback condition that makes it worse than locking the list!

Answer 4

The problem is your algorithm: Consider this sequence of events:

Thread 1 calls list.Add(workItem1), which completes fully.

Status is: first=workItem1, workItem1.next = null

Then thread 1 calls list.Add(workItem2) and reaches the spot right before the second Replace (where you have the comment "//lets try").

Status is: first=workItem1, workItem1.next = null, nextItem=workItem1

At this point thread 2 takes over and calls list.Get(). Assume workItem1's executionTime is now, so the call succeeds and returns workItem1.

After this status is: first = null, workItem1.next = null (and in the other thread, nextItem is still workItem1).

Now we get back to the first thread, and it completes the Add() by setting workItem1.next:=workItem2.

If we call list.Get() now, we will get null, even though the Add() completed successfully.

You should probably look up a real peer-reviewed lock-free linked list algorithm. I think the standard one is this by John Valois. There is a C++ implementation here. This article on lock-free priority queues might also be of use.