Why do the CFS chase fairness?

Why do the CFS chase fairness?

[Parmenides]

Hi,

   Current kernel 2.6 have adopted the CFS scheduler which try to
ensure that all process can obtain their proportions of allotted
processor fairly.  I have three questions about it.

   1. How to understand unfairness?

   I think unfairness is caused by processes sharing a processor, but
I am not confident of it.  According to Love, as far as fairness is
concerned, if a processor is a perfectly multitasking processor, all
of processes running on it should run simultaneously rather than run
in turn. For example, there are two processes which have the same nice
value. Both of them may run 10 ms on a perfectly multitasking
processor, each at 50% of processor power. This kind of processor is
prefect fair.

   In contrast, if the two processes run in turn on a real processor,
each may run 5ms at 100% of processor power. Although in both of the
two cases two processes run 10ms totally, but the latter case is
unfair because one process runs first, the other has to wait for 5ms.
In other words, when processes running on a real processor, some of
them has to wait more or less until preceding processes use up their
CPU shares. Does unfairness mean that?

   2. Why do processes need fairness?

   Yes, we can argue that now that we human beings need fairness,
processes do so. :-)  But, are there advantages if the scheduler care
about fairness? Just for processes not waiting too long? Or other
reasons?

   3. What's the drawbacks of traditional schdulers?

    According to Love, traditional schedulers assign each process a
absolut timeslcie which yields a constant switching rate but variable
fairness. How to understand 'constant switching rate'? What does cause
'variable fairness'?

Why do the CFS chase fairness?

[Mulyadi Santosa]

Hi...

This would take us back to the days of comp science bachelor seat :)

On Sun, Sep 18, 2011 at 01:29, Parmenides <mobile.parmenides@gmail.com> wrote:
> Hi,
>
> ? Current kernel 2.6 have adopted the CFS scheduler which try to
> ensure that all process can obtain their proportions of allotted
> processor fairly. ?I have three questions about it.
>
> ? 1. How to understand unfairness?

IMHO, the easiest meaning is that:
one task gets proportionally more time slice than the other.

"Proportion" here gets some clue from both process nice level and
later from sleep interval. So, technically process with more negative
nice level (which means higher priority) gets longer time slice.

But that is simply if all processes runs 100% as cpu bound. In
reality, some if not all might run as I/O bound, thus it sleeps.The
longer a process sleep, when it is awake, it is assumed to be working
on something important. Thus it gets temporary priority boost.

That's all great, at least on paper. In reality, even such procedure
is already aplied in the original O(1) scheduler, the perfomance might
suffer in some cases. The problem is still the same, you have N jobs,
but have M processors where M<N. So, one way or another, unfairness
would happen.

> ? 2. Why do processes need fairness?
>
> ? Yes, we can argue that now that we human beings need fairness,
> processes do so. :-) ?But, are there advantages if the scheduler care
> about fairness? Just for processes not waiting too long? Or other
> reasons?

To achieve highest response time IMHO. Yes we have preemption, but
preemption itself takes time. Fortunately the processor is gettting
faster and faster and there was a research that concluded that as long
perceived latency is somewhere under ~250-300 milisecond, you would
see it as "snappy"

> ? 3. What's the drawbacks of traditional schdulers?
>
> ? ?According to Love, traditional schedulers assign each process a
> absolut timeslcie which yields a constant switching rate but variable
> fairness. How to understand 'constant switching rate'? What does cause
> 'variable fairness'?

I believe Robert Love talks about context switching between processes.


Not sure about "variable fairness", but I think that's because a
program could alternately switch between being CPU bound and I/O
bound. In that case, time slices should be dynamically recalculated on
every context switch. Also, notice that a process could voluntarily
call sched_yield(), thus giving up its time slot.

Forgive me if my CS knowledge sucks :)
-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com

Why do the CFS chase fairness?

[Michael Blizek]

Hi!

On 21:48 Sun 18 Sep     , Mulyadi Santosa wrote:
...
> Fortunately the processor is gettting
> faster and faster and there was a research that concluded that as long
> perceived latency is somewhere under ~250-300 milisecond, you would
> see it as "snappy"

300ms is ok only for few operations, like switching windows and even there it
is IMHO more like a deadline than a "does not matter" period. For other
operations 250-300 ms is ages. Animations with 4fps are not. Even for ssh
250-300 ms latency is quite a bit.

see http://www.skytopia.com/project/articles/lag/latency.html

	-Michi
-- 
programing a layer 3+4 network protocol for mesh networks
see http://michaelblizek.twilightparadox.com

Why do the CFS chase fairness?

[Parmenides]

2011/9/18 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
> Hi...
>
> This would take us back to the days of comp science bachelor seat :)
>
>>
>> ? 1. How to understand unfairness?
>
> IMHO, the easiest meaning is that:
> one task gets proportionally more time slice than the other.

   Well, even with the CFS scheduler, tasks still can have different
processor shares according to their priorities. Conceptually, for
examp, suppose that there are three tasks with priorities 1, 2, 3,
respectively. For some fixed schedule period (targeted latency), which
determined by the number of tasks in run queue, the three tasks obtain
their CPU shares: 1/6, 2/6, 3/6 of the schedule period. Of course, in
reality, CPU share of each tasks also needs its weight (determined by
task's priority) be taken into account.

   However, it is said that we can consider this manner of allocating
CPU time is still fair because the scheduler approaches (at least
approximately) user's intension, that is: tasks with different
priorities get relevant CPU shares in terms of the their priorities.
If so,  IMHO it is also not hard for traditional schedulers to achieve
fairness. For the above three tasks, the scheduler may allocate 5ms,
10ms, 15ms timeslice for each. That way, each task would receive the
intended CPU shares as the CFS scheduler does.

   So, I can not see the differences between traditional schedulers,
which are based on timeslice, and the CFS scheduler, which divide some
schedule period into shares in proportion to tasks' priorities. It
seems that both take the same effect.

   I think the clear idea of what fairness is may help us understand unfairness.

>
>> ? 2. Why do processes need fairness?
>>
> To achieve highest response time IMHO.

   How does fairness give tasks more higher response time?

Why do the CFS chase fairness?

[Mulyadi Santosa]

Hi :)

On Mon, Sep 19, 2011 at 21:22, Parmenides <mobile.parmenides@gmail.com> wrote:
> ? Well, even with the CFS scheduler, tasks still can have different
> processor shares according to their priorities.

Correct and agree :)

> Conceptually, for
> examp, suppose that there are three tasks with priorities 1, 2, 3,
> respectively. For some fixed schedule period (targeted latency), which
> determined by the number of tasks in run queue, the three tasks obtain
> their CPU shares: 1/6, 2/6, 3/6 of the schedule period. Of course, in
> reality, CPU share of each tasks also needs its weight (determined by
> task's priority) be taken into account.

correct again. This "weighting" mechanism is the core of making
"fairness" happen...or at least approaching such situation.

> ? So, I can not see the differences between traditional schedulers,
> which are based on timeslice, and the CFS scheduler, which divide some
> schedule period into shares in proportion to tasks' priorities. It
> seems that both take the same effect.

Neither do I :)

Seriously, what I consider "more fair" is Con Kolivas BFS scheduler
these days. No excessive "time slice weighting", just priority
stepping and very strict deadline.

>>> ? 2. Why do processes need fairness?
>>>
>> To achieve highest response time IMHO.
>
> ? How does fairness give tasks more higher response time?
>
I took this chance to add: to maximize throughput too...

well, if you have processess let's say A, B, C. A and B are CPU bound,
C sleeps most of the times (let's say it's vim process running)

If a scheduler implement very fair scheduling, then whenever user
press a key in vim window, C should be kicked in ASAP and then run.
However, as C yields its time slice, A or B should back ASAP too.

If the scheduler is not really fair, then C should wait longer to be
back running. But C should not be given too much time so A and B have
more time to complete their number crunching works

Between A and B themselves should be balance somewhat, but not too
short. Too short and they would spend more time switching to each
other, too long and we would see they starve each other.

Above are my interpretation, so pls CMIIW...


-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com

Why do the CFS chase fairness?

[Parmenides]

Hi,

> 2011/9/19 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
> Hi :)
>
> Seriously, what I consider "more fair" is Con Kolivas BFS scheduler
> these days. No excessive "time slice weighting", just priority
> stepping and very strict deadline.
>

Hmm..., does that mean timeslice weighting introduce unfainess? If we
think fairness relies on each task not fetching more timeslice than
other tasks, the eaiest way to achieve fairness is to give every task
the same timeslice. But this way seemingly can not be considered as
fair. So, an exact definition of fairness will be appreciated.


> I took this chance to add: to maximize throughput too...
>
> well, if you have processess let's say A, B, C. A and B are CPU bound,
> C sleeps most of the times (let's say it's vim process running)
>
> If a scheduler implement very fair scheduling, then whenever user
> press a key in vim window, C should be kicked in ASAP and then run.
> However, as C yields its time slice, A or B should back ASAP too.
>
> If the scheduler is not really fair, then C should wait longer to be
> back running. But C should not be given too much time so A and B have
> more time to complete their number crunching works
>

Can I understand like this: each task advance its progress tinier than
traditional timeslice, which makes C has more chances to be selected
to preempt A or B owing to its higher priority? Higer priority makes
C's virtual time smaller than A and B.

Why do the CFS chase fairness?

[Mulyadi Santosa]

Hi .....

I am reaching my virtual limit here, so beg me pardon :)

On Mon, Sep 19, 2011 at 23:26, Parmenides
> Hmm..., does that mean timeslice weighting introduce unfainess? If we
> think fairness relies on each task not fetching more timeslice than
> other tasks, the eaiest way to achieve fairness is to give every task
> the same timeslice.

At the extreme theoritical side, yes, ....but again that is if all are
CPU bound.... the complication comes since in reality most processes
are mixture of CPU and I/O bound...or sometimes I/O bound only.

> Can I understand like this: each task advance its progress tinier than
> traditional timeslice, which makes C has more chances to be selected
> to preempt A or B owing to its higher priority? Higer priority makes
> C's virtual time smaller than A and B.
>

in non preemptive kernel i.e cooperative scheduling, your above
suggested idea is the right way to achieve fairness in such situation.
However, since user space (and now kernel space too) implements
preemptive, adjusting time slice is not really necessary to make C
kicks back into run queue.

What the scheduler needs perhaps at this point is good priority
recalculation is C could run ASAP. If not, even though C is in run
queue, it still can beat the other processes in the competition of CPU
time.


-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com

Why do the CFS chase fairness?

[Parmenides]

Hi,

I have gotten clearer idea of fairness between processes. Thanks for
your explanation with enough patience. :-)

2011/9/20 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
> Hi .....
>
> I am reaching my virtual limit here, so beg me pardon :)
>
> On Mon, Sep 19, 2011 at 23:26, Parmenides
>> Hmm..., does that mean timeslice weighting introduce unfainess? If we
>> think fairness relies on each task not fetching more timeslice than
>> other tasks, the eaiest way to achieve fairness is to give every task
>> the same timeslice.
>
> At the extreme theoritical side, yes, ....but again that is if all are
> CPU bound.... the complication comes since in reality most processes
> are mixture of CPU and I/O bound...or sometimes I/O bound only.
>
>> Can I understand like this: each task advance its progress tinier than
>> traditional timeslice, which makes C has more chances to be selected
>> to preempt A or B owing to its higher priority? Higer priority makes
>> C's virtual time smaller than A and B.
>>
>
> in non preemptive kernel i.e cooperative scheduling, your above
> suggested idea is the right way to achieve fairness in such situation.
> However, since user space (and now kernel space too) implements
> preemptive, adjusting time slice is not really necessary to make C
> kicks back into run queue.
>
> What the scheduler needs perhaps at this point is good priority
> recalculation is C could run ASAP. If not, even though C is in run
> queue, it still can beat the other processes in the competition of CPU
> time.
>
>
> --
> regards,
>
> Mulyadi Santosa
> Freelance Linux trainer and consultant
>
> blog: the-hydra.blogspot.com
> training: mulyaditraining.blogspot.com
>

Why do the CFS chase fairness?

[Mulyadi Santosa]

Hi Permenides :)

On Tue, Sep 20, 2011 at 18:11, Parmenides <mobile.parmenides@gmail.com> wrote:
> Hi,
>
> I have gotten clearer idea of fairness between processes. Thanks for
> your explanation with enough patience. :-)

Looks like I made few typos here and there, so allow me to put few erratas :)

> 2011/9/20 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
>> What the scheduler needs perhaps at this point is good priority
>> recalculation is C could run ASAP. If not, even though C is in run

"recalculation so C could be executed ASAP. ......."

>> queue, it still can beat the other processes in the competition of CPU

"...it could be beaten by other processes.."

-- 
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

blog: the-hydra.blogspot.com
training: mulyaditraining.blogspot.com

Why do the CFS chase fairness?

[Parmenides]

2011/9/21 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
> Hi Permenides :)
>
> Looks like I made few typos here and there, so allow me to put few erratas :)
>
>> 2011/9/20 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
>>> What the scheduler needs perhaps at this point is good priority
>>> recalculation is C could run ASAP. If not, even though C is in run
>
> "recalculation so C could be executed ASAP. ......."
>
>>> queue, it still can beat the other processes in the competition of CPU
>
> "...it could be beaten by other processes.."
>

Yes, even with enough timeslice, if C does not have high enough
priority, it can not preempt A or B. That's the point where priority
play its role when the scheduler prefer to IO-bound tasks. Thank you
again.