From mboxrd@z Thu Jan 1 00:00:00 1970 MIME-Version: 1.0 In-Reply-To: References: <94b72a275de4f8e6440aa79508edb7a4@terzarima.net> <8426d01eb3f1d86b5f9e8a50efb3e8c6@ladd.quanstro.net> <4EC7A160-58E6-4798-A2DC-62985F4806A7@gmail.com> <86AA4AF2-71B1-4877-968A-808205F7126F@gmail.com> Date: Sun, 31 Oct 2010 14:06:46 +0100 Message-ID: From: Gorka Guardiola To: Fans of the OS Plan 9 from Bell Labs <9fans@9fans.net> Content-Type: text/plain; charset=ISO-8859-1 Subject: Re: [9fans] A little more ado about async Tclunk Topicbox-Message-UUID: 741da7f6-ead6-11e9-9d60-3106f5b1d025 After some research and reading I believe that deadly embrace was first used in: E. W. Dijkstra "EWD108: Een algorithme ter voorkoming van de dodelijke omarming" (in Dutch; "An algorithm for the prevention of the deadly embrace" or so I 've been told. as a synonym for deadlock or actually to describe a cycle in the WFG which is the same. (the bankers algorithm is an algoritm to prevent deadlock). Hoare cites Dijstra when he uses the term deadly embrace: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.104.9460&rep=rep1&type=pdf http://www.eecs.ucf.edu/~dcm/Teaching/COP4600-Fall2010/Literature/Semaphors-Djikstra.pdf Hoare is talking about the events which happen when the process is in an environment, that is, what kind of inputs can make a process go forward. He is talking about empty intersection of the possible events in the environment and the events of the process. In Hoare's model, livelock and deadlock cannot be distinguished, so deadly embrace in his terminology means both. This is because he is establishing an equivalence relation between all the processes which produce the same interaction with the environment (a process is identified by trace). So, yeah, deadlock is a synonym for deadly embrace. Yes, in Hoare's model they are indistinguishable, so when he says deadly embrace, he can refer to both.