GATE Overflow Test Series | Mixed Subjects | Test 3 | Question: 6

Question

Which of the following statements is/are correct? (Mark all the appropriate choices)

• A. A cycle in the wait-for graph is a necessary condition for deadlock to exist
• B. A cycle in the wait-for graph is a sufficient condition for deadlock to exist when only single instance is available per resource
• C. Testing for view serializability is NP-complete
• D. Testing for conflict serializability is NP-complete

Answer 1

A cycle in the wait-for graph is a necessary and sufficient condition for deadlock to exist when only a single instance is available per resource.

Conflict serializability can be tested using topologial sort of the precedence graph which can be done in polynomial time.

Testing for view serializability is much more complex than testing for conflict serializability and is proved to be NP-complete (in NP class and Np-hard).