search

geraintpalmer / DetectingDeadlockInQingNetworkSimulation

0 stars 0 forks source link

Find whatever references you can #2

Open drvinceknight opened 9 years ago

drvinceknight commented 9 years ago

Find references about deadlock, list and we can discuss here perhaps? (Might not be called this throughout)

drvinceknight commented 9 years ago

Depending on what you find, this could or could not be a paper I think :+1:

geraintpalmer commented 9 years ago

System Deadlocks - Coffman and Elphick This paper talks about general deadlocks in terms of tasks and resources (although if we think of task as a customer and resource as a server, I think its equivalent: it mentions a traffic deadlock where roadspace is a resource). For when there is 1 resource of each type (e.g. all nodes have 1 server) then by building a state graph (very similar to what we are doing, with an edge between resources ri and rj if a task holding ri requests rj) deadlock is detected once the state graph contains a cycle. For when there are more than 1 of each type of resource, this isn't possible. An algorithm is presented which detects deadlock in this case, not using graphs theory. The runtime of this algorithm is proportional to the square of the number of tasks.

geraintpalmer commented 9 years ago

Also, this kind of general deadlock is called "deadly embraces" as well as deadlock

geraintpalmer commented 9 years ago

Graph-Theoretic Deadlock Detection and Resolution for Flexible Manufacturing Systems - Hyuenbo Cho, T. K. Kumaran, and Richard A. Wysk A network of machines, where parts flow from one to another, is investigated. When a part cannot enter another machine it is retained there (blocked). Deadlock here is called part flow deadlock. For part flow deadlock, a system status graph (updated over time) is constructed, where nodes can be occupied by resources. Simple bounded circuits are defined, and the following theorem: "A simple bounded circuit represents a part flow dead-lock if and only if all the nodes in the simple bounded circuit are occupied." Not sure if this problem is equivalent to queueing network deadlock or not.

drvinceknight commented 9 years ago

That one sounds very similar...

On Fri, 10 Apr 2015 19:23 Geraint Palmer notifications@github.com wrote:

Graph-Theoretic Deadlock Detection and Resolution for Flexible Manufacturing Systems - Hyuenbo Cho, T. K. Kumaran, and Richard A. Wysk http://ieeexplore.ieee.org.abc.cardiff.ac.uk/stamp/stamp.jsp?tp=&arnumber=388784%5D A network of machines, where parts flow from one to another, is investigated. When a part cannot enter another machine it is retained there (blocked). Deadlock here is called part flow deadlock. For part flow deadlock, a system status graph (updated over time) is constructed, where nodes can be occupied by resources. Simple bounded circuits are defined, and the following theorem: "A simple bounded circuit represents a part flow dead-lock if and only if all the nodes in the simple bounded circuit are occupied." Not sure if this problem is equivalent to queueing network deadlock or not.

— Reply to this email directly or view it on GitHub https://github.com/geraintpalmer/DetectingDeadlockInQingNetworkSimulation/issues/2#issuecomment-91644502 .

geraintpalmer commented 9 years ago

Ie, but I'm not sure their problem is equivalent to ours: they don't mention more than one type of resource (equivalent to multi servers), and they know where the part is going a few moves ahead, as if a path is mapped out. I could be mistaken though.