What is the difference between weak fairness and strong fairness?

What is the difference between weak fairness and strong fairness? What would be an example, which cont开发者_Go百科ains set of variables and set of actions?

---

Given a transition graph:

1. Weak fairness ensures that the execution cannot remain forever in a state where there are enabled actions leading to other states.
2. Under strong fairness no action can be enabled infinitely often without being executed.

---

I am not completely sure, but I believe this is the answer:

Strong vs. weak

A scheduler is strongly fair if every process enabled infinitely often will run eventually.

A scheduler is weakly fair if every process enabled persistently will run eventually.

• For shared-variable programs, weak fairness is reasonable
• For synchronous processes, weak fairness is reasonable, but it is not very useful (enabledness is not local)
• Strong fairness is not realistic (too much book-keeping)
• For asynchronous processes, weak fairness is both reasonable and useful

Example

a!0 k n:=0; go:=true;
do
    (go ^ a?x ! go:=false)
    2 (go ! n:=n + 1)
od

It would be unfair to keep executing the second alternative, since this would keep ignoring the potential for synchronized communication between the two processes, which could have been performed on an infinite number of occasions.

An efficient implementation should try to be reasonably fair and should ensure that an output command is not delayed unreasonably often after it first becomes executable.

What's fair?

• Such an execution is not strongly fair, but weakly fair.
• Assuming strong fairness the program terminates with n = 0.
• Assuming weak fairness, the program may also diverge.