Write a program that will surely go into deadlock [closed]

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()    { } }