Apple Interview Question
Software Engineer / DevelopersCheck if there is a cycle (circlular wait) in resource allocation graph.
1) There are two kinds of nodes in the graph - process node and resource node.
process node - process or thread
resource node - mutex, semaphore; for mutex, a resource has only one instance, while a semaphore may have mutiple instances
2) When a process P requests a resource R, add a request edge (P->R) into resource allocation graph
3) When a process is granted a resource, request edge (P->R) is atomically transformed into assignment edge (R->P).
4) For system where each resource only has one instance, there exists a cycle in resource allocation graph iff there is deadlock.
Use watchdog
- ANS May 27, 2010