I have written a formal Deadlock prevention code but I'm having trouble implementing this algorithm. Any help is appreciated.
I have represented the algorithm below,
Formal algorithm description
Data structures at a process i: (It is the initial value in the parentheses.)
• OUTi: set of integer, the set of process identifiers which process i is waiting for;
• INi: set of integer, the set of process identifiers which are waiting for process i;
• Pi: set of edge(∅), the set of phantom edges;
• weighti: float(0), the weight value which is accumulated locally before report is sent at a process i;
• rci: string, the request condition of process i;
• first recvi: boolean(true), the flag that determines whether process i has received a probe;
• cur initi: integer(−1), the identifier of the current initiator;
• probe recvedi: integer(0), the number of probes that process i has received. Additional data structures at initiator: (It is the initial value in the parentheses.)
• weightinit: float(0), the weight value accumulated from messages, either probes or reports;
• RCinit: set of request conditions(∅), the request conditions collected from the reports.
Message formats:
• PROBE(i,w): This is a message that diffuses the weight to successors where i is the identifier of the initiator and w the weight;
• REPORT(rc, P,w): It is used to send the weight value back to the initiator attached with the request condition. The rc is the request condition of the current process, the P is the set of phantom edges and the w is the accumulated weight.
Algorithm 1
Receiving a PROBE(init,w) from process s at a non-initiator process i
if first recv = true then
for j ∈ OUTi do
send PROBE(init,w/|OUTi + 1|) to j;
end for
cur initi ← init;
weighti ← 0;
probe recvedi ← 0;
end if
weighti ← weightiw/|OUTi + 1|;
probe recvedi ← probe recvedi + 1;
if s /∈ INi then
Pi = Pi S{s → i};
end if
if probe recvedi = |INi| then
send REPORT(rci, Pi,weighti) to cur initi;
end if
Algorithm 2
Definition of deadlock detection(RC, P)
for {a → b} ∈ P do
get rca from RC marked as rc;
modify every occurrence of b in rc to true;
replace rca in RC with rc;
end for
tmpA ← ∅;
repeat
A ← tmpA;
for tmprci ∈ RC do
if eval(tmprci) = true then
tmpA ← tmpAS{i};
RC ← RC − {tmprci};
end if
end for
until A = tmpA
if RC = ∅ then
declare no deadlock;
else
declare deadlock;
resolution(A,RC);
end if
Algorithm 3
Receiving a REPORT(rc, P,w) at the initiator process i
weightinit ← weightinit + w;
RCinit ← RCinitSrc
Pi ← PiSP
if weightinit=1 then
execute deadlock detection(RCinit, Pi);
end if
