Why do processes with higher priority to be allocated more timeslice?

Why do processes with higher priority to be allocated more timeslice?

[Parmenides]

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.

Why do processes with higher priority to be allocated more timeslice?

[Mulyadi Santosa]

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

Why do processes with higher priority to be allocated more timeslice?

[Parmenides]

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.

Why do processes with higher priority to be allocated more timeslice?

[Jeff Donner]

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.

Why do processes with higher priority to be allocated more timeslice?

[Parmenides]

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.

Why do processes with higher priority to be allocated more timeslice?

[Mulyadi Santosa]

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

Why do processes with higher priority to be allocated more timeslice?

[Parmenides]

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! :-)

Why do processes with higher priority to be allocated more timeslice?

[Mulyadi Santosa]

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

Why do processes with higher priority to be allocated more timeslice?

[Sri Ram Vemulpali]

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 at kernelnewbies.org
> http://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies
>



-- 
Regards,
Sri.