Write a program that will surely go into deadlock

Question

I recently got this questions asked in an interview.

I answered that deadlock occurs if the interleaving goes wrong, but the interviewer insisted that a program that will always go into deadlock regardless of interleaving can be written .

Can we write such a program ? Can you point me to some example program like that ?

Answer 1

UPDATE: This question was the subject of my blog in January 2013. Thanks for the great question!

---

How can we write a program that will always go into deadlock no matter how the threads are scheduled?

Here's an example in C#. Note that the program appears to contain no locks and no shared data. It has only a single local variable and three statements, and yet it deadlocks with 100% certainty. One would be hard-pressed to come up with a simpler program that deadlocks with certainty.

Exercise to the reader #1: explain how this deadlocks. (An answer is in the comments.)

Exercise to the reader #2: demonstrate the same deadlock in Java. (An answer is here: https://stackoverflow.com/a/9286697/88656)

class MyClass
{
  static MyClass() 
  {
    // Let's run the initialization on another thread!
    var thread = new System.Threading.Thread(Initialize);
    thread.Start();
    thread.Join();
  }

  static void Initialize() 
  { /* TODO: Add initialization code */ }

  static void Main() 
  { }
}