Operating Systems

One algorithm for detecting deadlocks is by using a directed graph will look for a “cycle”
It works by using one dynamic data structure, (for example) L, a list of nodes, as well as a list of arcs. During the algorithm, to prevent repeated inspections, arcs will be marked to indicate that they have already been inspected, The algorithm operates by carrying out the following steps as specified:
1. For each node, N, in the graph, perform the following five steps with N as the starting node.
2. Initialize L to the empty list, and designate all the arcs as unmarked.
3. Add the current node to the end of L and check to see if the node now appears in L two times. If it does, the graph contains a cycle (listed in L) and the algorithm terminates.
4. From the given node, see if there are any unmarked outgoing arcs. If so, go to step 5; if not, go to step 6.
5. Pick an unmarked outgoing arc at random and mark it. Then follow it to the new current node and go to step 3.
6. If this node is the initial node, the graph does not contain any cycles and the algorithm terminates. Otherwise, we have now reached a dead end. Remove it and go back to the previous node, that is, the one that was current just before this one, make that one the current node, and go to step 3.
Using the following as input, code the algorithm as described above to detect a deadlock. Use the following as input to test:
Input the following, (translated as a text file below)
1. Process A holds R and wants S.
2. Process B holds nothing but wants T.
3. Process C holds nothing but wants S.
4. Process D holds U and wants S and T.
5. Process E holds T and wants V.
6. Process F holds W and wants S.
7. Process G holds V and wants U.
The text file should be used as input and should contain the following where ‘:’ = ‘holds’ and ‘#’ = ‘wants’
A:R
A#S
B:0
B#T
C:0
C#S
D:U
D#S
D#T
E:T
E#V
F:W
F#S
G:V
G#U

Using the input organize your two main data structures as
– Processes
– Resources
Create logical graph in C++. Then code the algorithm to do a depth-first-search on the graph to determine if there is a deadlock or not.
Hint to create graph in C++: https://www.tutorialspoint.com/cplusplus-program-to-represent-graph-using-adjacency-list