Why do processes with higher priority to be allocated more timeslice?
Hi, It seems that Linux's scheduler tends to allocate longer timeslice for processes with higher priority. Actually, the CFS scheduler which is a new scheduler in Linux kernel also does the same thing. But, I think this way does not fit with scheduler's principle. The goal chased by a scheduler is low latency and high thoughput. Normally, a I/O-bound process has higher priority, while a CPU-bound process has lower priority. So, a I/O-bound process (which has enough timeslice) can preempt a CPU-bound process easily. This way ensures lower latency. It is also necessary that CPU-bound processes are to be allocated longer timeslice to improve throughput owing to less process switch costs. That means lower priority processes (CPU-bound) should be allocated longer timeslice, whichs obviously conflicts with the actual practice taken by the Linux's scheduler. Any explanation? Thanks.
Hi :) On Mon, Sep 26, 2011 at 09:16, Parmenides <mobile.parmenides@gmail.com> wrote:
Hi,
It seems that Linux's scheduler tends to allocate longer timeslice for processes with higher priority.
"tends".....yes, at least theoritically..... but not really in every cases in reality....
Actually, the CFS scheduler which is a new scheduler in Linux kernel also does the same thing. But, I think this way does not fit with scheduler's principle.
remember the keyword you ask? "fairness"? that is being fair to all processes.... but since, there are always more processes than processors, unfairness always happen.....
The goal chased by a scheduler is low latency and high thoughput. Normally, a I/O-bound process has higher priority, while a CPU-bound process has lower priority.
you are referring above as dynamic priority, I believe. As for static priority, quite likely, all I/O and CPU bound processes start at static prio level 0
So, a I/O-bound process (which has enough timeslice) can preempt a CPU-bound process easily.
yes, because I/O bound one sleep quite a long time and its dynamic priority gets a bonus. But if it sleeps not quite long, the bonus won't be too significant to "defeat" current running one, so it has to wait longer to be run by processor.
This way ensures lower latency. It is also necessary that CPU-bound processes are to be allocated longer timeslice to improve throughput owing to less process switch costs. That means lower priority processes (CPU-bound) should be allocated longer timeslice, whichs obviously conflicts with the actual practice taken by the Linux's scheduler. Any explanation?
What you refer initially is the time when time slice assignment is strictly derived from the static/nice level. So e.g process with nice level 0 has lesser time slice that nice level -5. But as you can see, situation change dynamically during run time, thus static prio must be taken into dynamic priority. And dynamic priority itself, must take another factor for time slice calculation. Here, sleep time comes into play. -- regards, Mulyadi Santosa Freelance Linux trainer and consultant blog: the-hydra.blogspot.com training: mulyaditraining.blogspot.com
2011/9/26 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
Hi :)
Actually, the CFS scheduler which is a new scheduler in Linux kernel also does the same thing. But, I think this way does not fit with scheduler's principle.
remember the keyword you ask? "fairness"? that is being fair to all processes.... but since, there are always more processes than processors, unfairness always happen.....
In fact, I am interested in the length of timeslice rather than fairness at this point. :-)
This way ensures lower latency. It is also necessary that CPU-bound processes are to be allocated longer timeslice to improve throughput owing to less process switch costs. That means lower priority processes (CPU-bound) should be allocated longer timeslice, whichs obviously conflicts with the actual practice taken by the Linux's scheduler. Any explanation?
What you refer initially is the time when time slice assignment is strictly derived from the static/nice level. So e.g process with nice level 0 has lesser time slice that nice level -5.
But as you can see, situation change dynamically during run time, thus static prio must be taken into dynamic priority. And dynamic priority itself, must take another factor for time slice calculation. Here, sleep time comes into play.
Ok, suppose that there is a CPU-bound process and a I/O-bound process, both of them are allocated the same nice level 0. After some time, the I/O-bound process will receive higher dynamic priority owing to its frequent sleeping. Now that the I/O-bound process more like to sleep, why does the scheduler give it longer timeslice? After all, it really does not need more time. On ther other hand, the CPU-bound process will receive lower dynamic priority as its punishment because it costs more CPU time. Lower dynamic priority indicates this process is more 'CPU-bound', that is this process need more CPU time. If the scheduler allocates longer timeslice for this process, the frequency of process switch will be reduced. I think that will help to improve throughput of the entire system.
On Mon, Sep 26, 2011 at 10:10 AM, Parmenides <mobile.parmenides@gmail.com> wrote:
2011/9/26 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
Actually, the CFS scheduler which is a new scheduler in Linux kernel also does the same thing. But, I think this way does not fit with scheduler's principle.
remember the keyword you ask? "fairness"? that is being fair to all processes.... but since, there are always more processes than processors, unfairness always happen.....
In fact, I am interested in the length of timeslice rather than fairness at this point. :-)
This way ensures lower latency. It is also necessary that CPU-bound processes are to be allocated longer timeslice to improve throughput owing to less process switch costs. That means lower priority processes (CPU-bound) should be allocated longer timeslice, whichs obviously conflicts with the actual practice taken by the Linux's scheduler. Any explanation?
What you refer initially is the time when time slice assignment is strictly derived from the static/nice level. So e.g process with nice level 0 has lesser time slice that nice level -5.
But as you can see, situation change dynamically during run time, thus static prio must be taken into dynamic priority. And dynamic priority itself, must take another factor for time slice calculation. Here, sleep time comes into play.
Ok, suppose that there is a CPU-bound process and a I/O-bound process, both of them are allocated the same nice level 0. After some time, the I/O-bound process will receive higher dynamic priority owing to its frequent sleeping. Now that the I/O-bound process more like to sleep, why does the scheduler give it longer timeslice? After all, it really does not need more time.
Well, if it doesn't need more time then it doesn't matter what its priority is, when it goes to sleep waiting for some IO it yields back the remainder of its time. You could give it as long a timeslice as you like; it won't use more than it needs, because it mostly waits on IO.
On ther other hand, the CPU-bound process will receive lower dynamic priority as its punishment because it costs more CPU time. Lower dynamic priority indicates this process is more 'CPU-bound', that is this process need more CPU time. If the scheduler allocates longer timeslice for this process, the frequency of process switch will be reduced. I think that will help to improve throughput of the entire system.
A lot of the time the IO process won't be runnable, as it's waiting on IO. When the kernel is looking to dole out CPU time at those times, well the CPU-bound process is the only one that can take it. So the kernel gives it to it, lower priority or not. CFS doesn't distort anything.
Hi Jeff, 2011/9/27 Jeff Donner <jeffrey.donner@gmail.com>:
Well, if it doesn't need more time then it doesn't matter what its priority is, when it goes to sleep waiting for some IO it yields back the remainder of its time. You could give it as long a timeslice as you like; it won't use more than it needs, because it mostly waits on IO.
A lot of the time the IO process won't be runnable, as it's waiting on IO. When the kernel is looking to dole out CPU time at those times, well the CPU-bound process is the only one that can take it. So the kernel gives it to it, lower priority or not.
CFS doesn't distort anything.
For this example, it is really ok. But, dynamic priority doesn't has nothing to do with timeslice. I have no intention to give any remarks conerning whichever scheduler (Forgive me if I seem do that.) :-). Actually, a common characteristics of Linux's schedulers is that timeslices will be longer with priorities raising . I am just curious about why the the schedulers takes this policy. IMHO, this policy somewhat conflicts with intuition. I think there must be some motivations to take this policy, but I have no idea about it.
Hi :) On Tue, Sep 27, 2011 at 09:07, Parmenides <mobile.parmenides@gmail.com> wrote:
Actually, a common characteristics of Linux's schedulers is that timeslices will be longer with priorities raising .
generally I agree with that.... :)
I am just curious about why the the schedulers takes this policy.
simply to say that, the more important a job is, it should be given longer time to run... but, the process has privilege to yield before time slice is up...and when it comes back,it will use the remaining time slice.....and its dynamic priority will stay the same (that's the property that I recall....)
IMHO, this policy somewhat conflicts with intuition. I think there must be some motivations to take this policy, but I have no idea about it.
well, you can think, what happen if you take the other direction for the policy? higher priority, but less time slice? that, IMHO, is less intuitive. -- regards, Mulyadi Santosa Freelance Linux trainer and consultant blog: the-hydra.blogspot.com training: mulyaditraining.blogspot.com
Hi, Mulyadi 2011/9/27 Mulyadi Santosa <mulyadi.santosa@gmail.com>:
simply to say that, the more important a job is, it should be given longer time to run... but, the process has privilege to yield before time slice is up...and when it comes back,it will use the remaining time slice.....and its dynamic priority will stay the same (that's the property that I recall....)
well, you can think, what happen if you take the other direction for the policy? higher priority, but less time slice? that, IMHO, is less intuitive.
Initially, I think that the scheduler should enlarge the timeslices of CPU-bound processes to improve throughput. But, now I have realized that the two goals of schedulers, namely shorter latency and higher throughput, can not be achieved at the same time. Linux scheduler may prefer to the former. Thanks! :-)
Hi :) On Tue, Sep 27, 2011 at 20:06, Parmenides <mobile.parmenides@gmail.com> wrote:
Initially, I think that the scheduler should enlarge the timeslices of CPU-bound processes to improve throughput.
True.... :)
But, now I have realized that the two goals of schedulers, namely shorter latency and higher throughput, can not be achieved at the same time. Linux scheduler may prefer to the former. Thanks! :-)
I always think that the problem is, let N is the number of the jobs, and M is the number of processor, whenever N>M, scheduler could never achieve ideal situation (both lower latency and higher throughput). If at least N=M, now that's we're talkin' :) Another problem is actually Linux kernel is not real time kernel. It's not really a big problem actually in most cases, but in some cases it might e.g sound processing. Unbounded latency in non real time kernel is a big no no in such situations. Just my 2 cents thought :) -- regards, Mulyadi Santosa Freelance Linux trainer and consultant blog: the-hydra.blogspot.com training: mulyaditraining.blogspot.com
Missed a lot of exciting conversation. Here is the link follow it you will understand the reason of fairness http://www.linuxjournal.com/article/10267 the reason the low-priority task gets less time slice is appropriate to balance between latency and throughput. If high priority task (interactive) needs to preempt the low priority task, in such case, if the system is fully preemptive, it makes sense to give larger time slice for low priority task. If the system is completely preemptive (which is not in normal vanilla kernel), in such case the smaller time slice for low priority task becomes max latency for interactive task to get scheduled. I see in the current kernel code, there is check whether to reschedule the current execution context when returning from interrupt (top half and bottom half), checks "need_resch" field in task_struct. So, I think according to your argument you should able to increase the time slice for low priority task to decrease context switches. You can modify code and test to see what happens. Sri On Tue, Sep 27, 2011 at 11:44 AM, Mulyadi Santosa <mulyadi.santosa@gmail.com> wrote:
Hi :)
On Tue, Sep 27, 2011 at 20:06, Parmenides <mobile.parmenides@gmail.com> wrote:
Initially, I think that the scheduler should enlarge the timeslices of CPU-bound processes to improve throughput.
True.... :)
But, now I have realized that the two goals of schedulers, namely shorter latency and higher throughput, can not be achieved at the same time. Linux scheduler may prefer to the former. Thanks! :-)
I always think that the problem is, let N is the number of the jobs, and M is the number of processor, whenever N>M, scheduler could never achieve ideal situation (both lower latency and higher throughput). If at least N=M, now that's we're talkin' :)
Another problem is actually Linux kernel is not real time kernel. It's not really a big problem actually in most cases, but in some cases it might e.g sound processing. Unbounded latency in non real time kernel is a big no no in such situations.
Just my 2 cents thought :)
-- 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
-- Regards, Sri.
participants (4)
-
Jeff Donner -
Mulyadi Santosa -
Parmenides -
Sri Ram Vemulpali