Навеяно жизнью, всю неделю воюю на фронте многопоточности. От недосыпу и поехавшей крыши придумалась такая задачка:

Имеется два потока T1 и T2, выполняющие в цикле n1 и n2 команд соответственно. Процессор выполняет попеременно по одной команде в каждом потоке. В каждом потоке имеется три известных точки (известных всмысле номера команды): Ln (lock), Un (unlock), Wn (wait). Потоки ожидают друг на друге, т.е. если в момент достижения точки W2 потоком T2, поток Т1 прошёл точку L1 но не прошёл U1, то Т2 засыпает и ждёт. Аналогично симметрично. Здесь, надеюсь, всё понятно.
Теперь вопросы:
1. для заданных Nn, Ln, Un, Wn для n (- [1,2] оценить вероятность deadlock-а
2. в каких случаях deadlock невозможен?
3. в каких гарантирован?
4. обобщить до N потоков

ЗЫ: По-моему, получилось нечто нерешаемое, но зато по теме форума