5
$\begingroup$

I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different?

for reference, here are the definitions I have of each:

weakly fair: A condition becomes true and remains true at least until after the conditional atomic action has been executed.

strongly fair: If the condition is infinitely often true, a process will eventually see it as true and be able to proceed.

So I think I understand weakly fair, a conditional atomic action will execute when its condition is true, and the condition will remain true until the atomic action has ended.

But I don't see how strongly fair is different from this. for a conditional atomic action, once its condition is true it executes, and because it is atomic, the condition should remain true until it ends, right? this is the same as weakly fair isn't it?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\begingroup$

If you are familiar with temporal logic, the difference is quite easy to demonstrate:

Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually.

Strong fairness is $GFp\to Fq$ (or sometimes $GFp\to GFq$). That is, if $p$ holds infinitely often, then eventually $q$ will hold (or $q$ will hold infinitely often, in the second version).

Your description is slightly different from the above, in that your weak fairness has the "until" flavour, but it's the same idea.

To demonstrate the difference in the approaches, think of yourself as a process trying to gain access to some critical section. If you know that the system is weakly fair, then you need to raise a flag saying that you want access, and you have to keep this flag up all the time, until you get access. If the system has strong fairness, it is enough that you raise the flag every now and then, and you know that eventually you'll get access.

As an alternative example, children who want attention often go "mom" repeatedly until they are granted attention. This is similar to weak-fairness (of the mother), and as you can see, it prevents the child from doing anything else until granted attention. With a strongly-fair mother, it suffices for the child to say "mom" every few minutes, and go about doing other things in the mean time.

By the way, this question has an excellent answer by Cynthia Disenfeld at quora.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great answer, I think I get it now, but let me double check by reiterating an example that would show the difference between the two, and please tell me if my thinking is correct. So lets say I have 2 atomic processes, a and b. Lets say a and b have the same wait condition, (x==1), but they both change the value of x. Weakly fair scheduling means that only one process would run because the condition gets changed before the second process is able to run. However with strongly fair scheduling they are both guaranteed to run because at one point (x==1) was true. Does that sound right? $\endgroup$
    – JDOdle
    Feb 8, 2016 at 17:45
  • $\begingroup$ The fact that $x==1$ was true once is not enough (for either fairness conditions). For weak fairness, you need x==1 to hold consecutively from some point, and for strong fairness you need it to hold infinitely often. The number of processes is irrelevant for this model, by the way (that is, you can think of fairness with a single process). $\endgroup$
    – Shaull
    Feb 8, 2016 at 17:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.