Problem 5. In amtiprogramming environment, several concurrent com putational pro
ID: 3709289 • Letter: P
Question
Problem 5. In amtiprogramming environment, several concurrent com putational processes compete for the use of resources (e.g., disk, scanner CD-rom. A resource is assigned to at most one process, while the other processes who have requested that resource are waiting until the resource is released and made available. A deadlock occurs when processes end up waiting forever because resources are never freed. This happens when the resource-allocation digraph contains a directed cycle. Indeed, if such a cycle exists, say po: To: Pi: r: P2: r2: Po. we have that processor po is waiting for resource ro, which is assigned to processor pi. At the same time, processor P is waiting for resource ri, which is assigned to processor p, and processor P2 is waiting for resource r2, which is assigned to processor po. Hence, po P and pa keep on waiting indefinitely for resources. The example below shows a deadlock caused by a directed cycle in the resource- allocation digraph Speaker Printer Scanner Pl P2 P3 CD-rom To detect deadlocks, a multiprogramming operating system needs to deter- mine whether the resource-allocation digraph is acyelic (ie., it has no directed cycles). Give an efficient algorithm for testing whether a digraph is acyclic. What is the time complexity of your algorithm?Explanation / Answer
COMPLEXITY - O(V+E) V - Vertex, E - Edges