In the deadlock detection algorithm employing the technique of graph reductions, show that the order of the graph reductions does not matter, the same final state will result. [Hint: No matter what the order, after each reduction, the available resource pool increases.]
What will be an ideal response?
Suppose there is an array, FREE, such that FREE i indicates the number of free resources of type i. When a process is reduced, it frees all of its allocated resources and removes all of its request edges. Removing a request edge does not affect the FREE array. However, freeing an allocated resource of type i increases FREE I by 1. Therefore, a series of reductions can never decrease any element of FREE.
Computer Science & Information Technology