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 ← ∅;
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;
declare deadlock;
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

1 Month
Discussion Span
Last Post by JamesCherrill
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.