Re: Why do the CFS chase fairness?
Hi, I have gotten clearer idea of fairness between processes. Thanks for your explanation with enough patience. :-) 2011/9/20 Mulyadi Santosa mulyadi.sant...@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 ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: Why do the CFS chase fairness?
Hi Permenides :) On Tue, Sep 20, 2011 at 18:11, Parmenides mobile.parmeni...@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.sant...@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 ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: Why do the CFS chase fairness?
2011/9/21 Mulyadi Santosa mulyadi.sant...@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.sant...@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. ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: Why do the CFS chase fairness?
Hi, 2011/9/19 Mulyadi Santosa mulyadi.sant...@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. ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: Why do the CFS chase fairness?
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 ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
Re: Why do the CFS chase fairness?
Hi... This would take us back to the days of comp science bachelor seat :) On Sun, Sep 18, 2011 at 01:29, Parmenides mobile.parmeni...@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 MN. 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 ___ Kernelnewbies mailing list Kernelnewbies@kernelnewbies.org http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
