Protecting against classic deadlock

Question

I've been struggling with this problem for about 24 hours now, I just can't seem to find a way around it.

Say I have a collection of Foo objects:

public class Foo {
    public int SomeValue;

    public void Execute() {
        lock (this) {
            SomeValue++;
        }  
    }
}

// Instantiated elsewhere and filled with lots of Foos
private static ConcurrentCollection<Foo> fooCollection; 

Now I'm calling Execute for every Foo like this (I have a multi-core machine):

Parallel.ForEach(fooCollection, foo => foo.Execute());

---

Now imagine we add a second type of Foo:

public class Bar : Foo {
    private Foo myFriend;

    public new void Execute() {
        lock (this) {
            SomeValue++;
            lock (myFriend) {
                myFriend.SomeValue += SomeValue;
            }
        }  
    }
}

This new Bar still locks itself to maintain consistency during Execute, and increments SomeValue. But it also acquires a lock on its Foo friend, so that myFriend is updated in a threadsafe manner too, before updating myFriend.SomeValue.

The problem I have is that I may have a circular reference chain of Bars, e.g.

bar1.myFriend = bar2; bar2.myFriend = bar1;

In the worst case:

1. bar1.Execute() locks on bar1
2. bar2.Execute() locks on bar2
3. bar1.Execute() waits for lock on bar2
4. bar2.Execute() waits for lock on bar1
5. Deadlock :(

---

So, my question is: How do I get around this problem?

Some realistic metrics about my application:

• My real 'Execute()' method does something a lot more meaningful than this example - please just this example on face value :)
• I have about 50,000 'Foos' in my collection. Execute() is called on each in parallel by N threads, where N = the number of logical cores on the host machine.
• The expected contention ratio (e.g. where a Foo is waiting on another Foo) is low, maybe 5%. The problem would easy if not for the potential of circular references. Speed isn't really the concern for contended access, just the deadlock situation.

Some caveats:

• In this example, I have used lock (Monitor.Enter/Exit), but any thread synchronization construct could be used (e.g. a state variable & Interlocked methods, etc.).
• The application is performance-sensitive - so for the uncontended case I need as much speed as I can get.

I'm hoping there's some standard way of solving this issue that I'm unaware of. I've tried all sorts of gymnastics, but every time I write the worst case out the deadlock is always still a potential.

Thanks in advance. :)

Answer 1

Well, typically to avoid deadlocks we can just prioritise resource, so always try to get lock on the higher priority resources first.

In your case its not as simple as here the objects are of same or derived types.

So a very but twisted way of solving this would be to provide a auto-increment integer to all the instances. Any instance with higher value will be deemed to have a higher priority

so something like

foo p1 = this;
foo p2 = myfriend;
if(p1.priority < p2.priority)
{
    foo t = p2;
    p2 = p1;
    p1 = t;
}
lock(p1)
{
    lock(p2)
    {
        // here you can safely increment both p1 & p2 some value. 

    }
}