complete the following questions inside the doc
p 1 p 2 r 1 r 2 Figure 1: Minimal example of a resource allocation graph with deadlock. Directed graphs Directed graphs are sometimes used in operating systems when trying to avoid deadlock, which is a condition when several processes are waiting for a resource to become available, but this will never happen because other processes are holding on to those resources and are themselves waiting for other resources. In the simplest example, process p1 is holding resource r1 and is waiting for resource r2 while process p2 is holding resource r2 and waiting for resource r1. This is depicted in figure 1. Let R be a set of resources and P be a set of processes (not necessarily the one depiced in figure 1). Define the resource allocation graph to be the directed graph G on R∪P with edges (p,r) where process p is holding resource r, and (r,p) where process p is waiting for resource r. To avoid trivial cases, we will assume that P,R 6= ∅. Note that G will always be anti-symmetric since a process will not wait for a resource that it already has. Also, G is bipartite with P and R forming the partition on the edges. For our purposes, there are a few things that can happen. The operating system’s actions are: · if there is a process p that is not waiting for any resources — that is, there are no edges (r,p) for any r — the operating system can choose to run p. Only one process can be running at a time. The process runs until it performs an action on the graph (discussed below). · if (r,p) is an edge and there are no edges (p0,r) for any p0, the operating system can assign resource r to process p, adding edge (p,r) to the graph and removing (r,p) If at least one of the above is possible, then the system can make progress. Process have the following possible actions: · if p is running and (p,r) is an edge, then p can release a resource r, deleting edge (p,r) from the graph · a running process p can request a resource r, adding edge (r,p) to the graph a. A minimal vertex or minimal element in a directed graph is a vertex v such that there are no edges (u,v) in the graph for any u. Argue that if the resource allocation graph G = (P ∪R,E) has a minimal vertex p ∈ P then the system can make progress. (1 mark) b. Suppose that a resource graph G = (P ∪R,E) contains a minimal element r ∈ R and also contains an edge (r,p) for some p. Argue that the system can make progress. (1 mark) c. Suppose that G is a directed graph with a finite and non-empty set of vertices. Argue that if G is acyclic then G has a minimal element. (Hint: we covered directed acyclic graphs in the lecture, which might be useful. Alternatively, suggest a simple method that is guaranteed to find a minimal element and argue why.) (1 mark) d. For a directed graph G, we consider connectedness and connected components by ignoring the direction of any edges and taking the usual definitions for undirected graphs. Argue that if a resource graph is connected and acyclic then the system can progress. (Hint, there are two cases!) (1 mark) e. Argue that if G is an acyclic graph with a finite and non-empty set of vertices then every connected component of G contains a minimal element. (Hint: what happens when we consider each component? What happens when we put them back together?) (1 mark) f. Suppose that G is an acycle resource graph. Argue that the system can progress. (Hint: you need to consider the case that connected components may be isolated vertices. What happens if all minimal elements in R are isolated?) (1 mark) g. The above line of thought shows that being acyclic is sufficient for the system to make progress. Is being acyclic a necessary condition for the system being able to make progress? If yes, give a proof. If no, give a counterexample. Page 2 Page 2