Given the conditions for deadlock, if we record the resource dependency graph of the processors then we can detect deadlock by checking if there is a loop in the graph.
muchanon
Ideally we would avoid deadlock, but if we did detect it, is our only solution just to kill one of the threads? How is this generally implemented? Is their a heuristic used for choosing which thread to kill?
ask
@muchanon Killing a thread is not the solution. We can also rollback the execution on one thread. Preemption of the resources held by one of the threads is another way to resolve a deadlock in the situation.
o_o
It seems that by making 1 of the above conditions no longer true, we are able to avoid deadlock. Is there one in particular that we tend to change in order to prevent deadlock?
paracon
@o_o One of the more common methods, is to have an ordering in which resources should be requested. If a process P1 and P2 need resources A,B,C to complete their operations, then irrespective of when they need it, a fixed order of acquiring the resources can be defined. This has the downside of causing stalls. Since deadlock is considered a uncommon scenario, deadlock prevention is rarely done. Once the deadlock occurs, partial or complete rollback is done depending on the cost of those options.
dmerigou
@o_o in databases systems, it is always the fourth condition (circular wait) that is changed. Indeed, when the database detects a cycle in the dependency graph, it aborts one of the transaction in the cycle, allowing the others to proceed.
Given the conditions for deadlock, if we record the resource dependency graph of the processors then we can detect deadlock by checking if there is a loop in the graph.
Ideally we would avoid deadlock, but if we did detect it, is our only solution just to kill one of the threads? How is this generally implemented? Is their a heuristic used for choosing which thread to kill?
@muchanon Killing a thread is not the solution. We can also rollback the execution on one thread. Preemption of the resources held by one of the threads is another way to resolve a deadlock in the situation.
It seems that by making 1 of the above conditions no longer true, we are able to avoid deadlock. Is there one in particular that we tend to change in order to prevent deadlock?
@o_o One of the more common methods, is to have an ordering in which resources should be requested. If a process P1 and P2 need resources A,B,C to complete their operations, then irrespective of when they need it, a fixed order of acquiring the resources can be defined. This has the downside of causing stalls. Since deadlock is considered a uncommon scenario, deadlock prevention is rarely done. Once the deadlock occurs, partial or complete rollback is done depending on the cost of those options.
@o_o in databases systems, it is always the fourth condition (circular wait) that is changed. Indeed, when the database detects a cycle in the dependency graph, it aborts one of the transaction in the cycle, allowing the others to proceed.