Question

I have done the a and b, but i'm so confuse with other questions, could someone help me to fix these questions, thanks so much.

4 Directed graphs Directed graphs are sometimes used operating systems when trying to avoid deadlock, which is a condition when several processes are waiting for a resource to become available, but this wil never happen because Page 2 p2 T2 Figure 1: Minimal example of a resource allocation graph with deadlock other processes are holding on to those resources and are themselves waiting for other resources. In the simplest example, process p is holding resource ri and is waiting for resource r2 while process p is holding resource r2 and waiting for resource Let R be a set of resources and P be a set of processes. Define the resource allocation graph to be the directed graph G on RU 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. Note that G will always be 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: For our purposes, there are a few things that can happen. The operating system's actions are o if there is a process p that is not waiting for any resources_that is, there are no edges (r, p) for any ir 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. if (r,p) is an edge and there are no edges (p',r) for any p', 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 verter 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 (PUR,E) has a minimal vertex p P then the system can make progress 1 mark b. Suppose that a resource graph G = (PU R, E) contains a minimal element r E 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 Page 3 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 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: use the above result on each connected component. What happens when you put the components together?) 1 mark e. Suppose that G (PUR, E) is acyclic. If we identify a minimal element rERof G that is isolated (i.e. there are no edges in or out of r) then this still does not allow us to progress. Argue that if all rE R are isolated, then there must also exist a minimal element p E P. Note that any isolated vertex a minimal element. 1 mark f. Suppose that G(PUR, E) is acyclic. Argue that if all minimal elements in R are isolated, and there exists at least one non-isolated element r R (which is hence not minimal) then there must be a pEP that is a minimal element. (Hint: r is in some connected component that has a minimal element.) 1 mark g. From the above facts, argue that if a resource allocation graph G- (PU R, E) has no cycles, then the system can progress. (Hint: you will need to note that questions e and f above cover all possible cases 1 mark Total marks: 20

Answer 1

The questions are heavily oriented towards discrete mathematics, but I will try my best to explain every answer. I will use descriptive proofs to answer all the proves and will also provide you with images wherever possible. If doubt still persists ask me in the comments and I will be more than happy to help you out.

Somethings I want to clear it out beforehand. I have assumed that minimal element here means minimal vertex in a directed graph. This has not been explicitly mentioned in the question but I believe this assumption is correct as every proof works itself out with this assumption. First of all, by minimal vertex/element of a directed graph, we mean any vertex whose in-degree is zero. By in-degree of a vertex, we mean the number of edges that are directed towards that vertex (going into that vertex). Thus when we say that the directed graph has a minimal element we mean that there exists a vertex in the given directed graph whose in-degree is zero. Now let us try to answer the questions (excluding a and b as you have already solved them).

C:- Let us prove this using contradiction. Suppose we have a cyclic directed graph consisting of a minimal element. Here we assume that all the vertices in the graph are going to take part in the cycle of the graph. So suppose we have vertices {a, b, c, d}, and the cycle is of the form (a->b->c->d->a). As you can see none of the vertices of the graph has in-degree equal to zero but we have previously assumed that the graph would have a minimal element (a vertex with in-degree equal to 0), so we have arrived at a contradiction. Thus the graph needs to be acyclic.

D:- This is kind of straightforward. Every connected component of the graph is acyclic as the entire graph is acyclic. Now as it has been given that we consider connected components without considering the direction of the edges, thus the connected components in this graph would be found out using the idea of an undirected graph. Once we have found out all the connected components in the directed graph, we see that each connected component is acyclic in nature. Now from the proof (A), we have shown that if a directed graph is acyclic in nature then there exist a minimal element in the directed graph. Now since all the connected components are acyclic in nature, this would be true for all the components.

E:- Here it has been given that the graph is directed and acyclic in nature as usual and that all the resource (r) vertices are isolated, that is no edge is going out from any r vertex or coming into any r vertex. All the r vertices are present as single nodes in the network. So we are left with only vertices that consist of only p vertices. Thus we have a directed graph with only the process (p) vertices. Now, all we have to prove is that the graph consisting of only p vertices consists of a minimal element with the given condition that the graph is acyclic in nature. But wait we have already proved this in proof (C), thus if any directed acyclic graph with some isolated vertices present, then the non-isolated vertices form the acyclic part of the graph and also consist of a minimal element from the set of the non-isolated vertex.

F:- It has been given that all the minimal R vertices are isolated in nature. That means there is no edge either going out or coming into any of the R vertices. Thus we are left with non-minimal R vertices and the P vertices of the graph. Since all the R vertices are non-minimal in nature, thus their in-degree is not equal to zero. That is edges has to come into the R vertices. Now we are left with the P vertices to analyze. Now, as usual, the graph is acyclic in nature. The acyclic part of the graph is formed by at least one R vertex and all the remaining P vertices. Now edges can come and go out from that R vertex but not from the P vertices as it would result in the formation of a cycle in the graph which is prohibited.

G:- This answer has already been explained in the diagram.

Now I will provide you with some example graphs for each of the answers.

C:-

0 Mc direek ivimalsmtnol cl

D:-

d/ om utud omponet ㄣ eneutid Conneeted nem 1

E:-

R4 Mimimal lement P3

F:-

Isolated Venheu et lst one Linuee element fa Mmme element

I have tried my best to put it into words my thoughts about the proof. If you have any problem regarding the answers feel free to ask me in the comments and I will be more than happy to help you out.