Your task is to implement a deadlock detection and correction algorithm for an OS. It will process current state of a system, detect if there is a deadlock, and act correspondingly to the result of the detection (as described in lecture notes and the textbook).

Implement your program in single C file detector.c. If the code is too long, please share me about the idea how to build the logical algorithm. What functions do I need and how to use it. Please show me the details Thank you so much.

Preliminary notation (as given in lecture notes):

R_i will denote a resource request vector for process i;

A_i will denote the current resource allocation vector for process i; U will denote unallocated (available) resource vector;

Input for your implementation will consist of several lines.

The first line of the input

n m

contains two integers: n - number of processes in the system (assume processes are numbered from 1 ton), and m - number of resources (assume resources are numbered from 1 to m). This line will be followed by 2n + 1 lines, each containing m integer numbers:

R₁₁, R₁₂, ..., R_1m

R₂₁, R₂₂, ..., R_2m

. . .

R_n1, R_n2, ..., R_nm

A₁₁, A₁₂, ..., A_1m

A₂₁, A₂₂, ..., A_2m

. . .

A_n1, A_n2, ..., A_nm

U₁, U₂, ..., U_m

For example the input

And this Example

Your program will have to try to detect deadlock based on the provided input. If the system is not deadlocked your program will print the order of completion of processes. Your program will have to try to detect deadlock based on the provided input.

For the first example above this will be

3 1 2

Note: If more than one process can complete the execution at any time, print them in the increasing order of process number.

If the system is deadlocked your program will have to find a possible resolution for the deadlock: i.e. it has to find one or more processes which need to be terminated to resolve the deadlock and show the order of completion for the remaining processes. The output, in this case, will contain three lines:

the first line contains process number(s) for the process(es) involved in the deadlock, the second line contains process numbers for processes to be terminated,

third line contains the order of completion of the remaining processes. For the second example above this will be:

1 2 3

1 2

3

The decision which process(es) involved into deadlock needs to be terminated is based on the following very simple rule:

Terminate the process with the smallest process number whose termination will resolve the deadlock.

Note: There might be more than one deadlock cycle in the system. It is possible that more than one process needs to be terminated in order to resolve the deadlock.

0000010 0001000 0000110 51000210 30101000