2009-10-29 15:08:30

by Daniel Rodrick

[permalink] [raw]
Subject: Questions about linux scheduler

Hi list,

I'm following the Robert Love's book and am trying to understand the
Linux O(1) scheduler. So here is my understanding. The kernel allows
the applications to specify two types of priorities

* Realtime Priorities: Range from 0 to 99
* Non-realtime priorities: Also called "nice" values range from -20 to +19.

(The above are mutually exclusive)


Over all Scheduling algo
=================
* A total of 140 priorities (100 RT + 40 non-RT) - these priorities
are static - do not change over time.
* A lower priority process will run only if there are no runnable
processes in priority above it - this automatically means that all RT
processes get to run before non-RT processes.
* tasks on the same priority level are scheduled round robin

Is my above understanding correct? Where my understanding doesn't fit
is the conncept of dynamic timeslice calculation. IMHO, the dynamic
timeslice calculation applies only to Non-RT processes, right? Because
a higher priority RT process should always get to run.

Thanks,

Dan


2009-10-29 20:01:33

by Chris Friesen

[permalink] [raw]
Subject: Re: Questions about linux scheduler

On 10/29/2009 09:08 AM, Daniel Rodrick wrote:
> Hi list,
>
> I'm following the Robert Love's book and am trying to understand the
> Linux O(1) scheduler.

The details of Rob Love's book are now out of date and no longer
applicable to the current scheduler. Some of the overall concepts are
still applicable though.

> So here is my understanding. The kernel allows
> the applications to specify two types of priorities
>
> * Realtime Priorities: Range from 0 to 99

Actually, 1 to 99.

> * Non-realtime priorities: Also called "nice" values range from -20 to +19.
>
> (The above are mutually exclusive)

Correct.

> Over all Scheduling algo
> =================
> * A total of 140 priorities (100 RT + 40 non-RT) - these priorities
> are static - do not change over time.

So far so good.

> * A lower priority process will run only if there are no runnable
> processes in priority above it - this automatically means that all RT
> processes get to run before non-RT processes.

True for RT, not true for non-RT. In the current scheduler the non-RT
tasks are stored in a time-ordered structure rather than the 40
runqueues that were used before. A non-RT task will run once it becomes
the most "urgent" task based on its nice level, how much cpu time it
uses, and how long it's been since it ran last relative to other tasks
on the system.

> * tasks on the same priority level are scheduled round robin

True for RT. For non-RT, tasks of other nice levels may be interleaved
depending on how much cpu time they've been using.

> Is my above understanding correct? Where my understanding doesn't fit
> is the conncept of dynamic timeslice calculation. IMHO, the dynamic
> timeslice calculation applies only to Non-RT processes, right? Because
> a higher priority RT process should always get to run.

With the new scheduler I think it's fair to say that non-RT tasks don't
really have a fixed "timeslice". The amount of time they get to run is
determined by their nice level, previous cpu usage, cpu usage of other
tasks, etc.

Chris

2009-10-29 20:05:40

by Jonathan Corbet

[permalink] [raw]
Subject: Re: Questions about linux scheduler

Hi, Daniel,

I'm not a scheduler expert by any stretch, but I can try to play one on
the net...

> I'm following the Robert Love's book and am trying to understand the
> Linux O(1) scheduler.

Note that the O(1) scheduler is no more; it was replaced by the
completely fair scheduler in 2.6.23. For the purposes of your
questions things haven't changed a lot, but it's completely different
internally.

> So here is my understanding. The kernel allows
> the applications to specify two types of priorities
>
> * Realtime Priorities: Range from 0 to 99
> * Non-realtime priorities: Also called "nice" values range from -20 to +19.

You're really talking about different scheduling classes. There are
two realtime classes (FIFO and RR), both of which trump the interactive
class (SCHED_OTHER).

> * A total of 140 priorities (100 RT + 40 non-RT) - these priorities
> are static - do not change over time.

Sort of, but realtime priorities are really an entirely different scale.

> * A lower priority process will run only if there are no runnable
> processes in priority above it - this automatically means that all RT
> processes get to run before non-RT processes.

That is true for the realtime classes. SCHED_OTHER will give
lower-priority processes a bit of time even in the presence of runnable
high-priority processes.

> * tasks on the same priority level are scheduled round robin

SCHED_RR does that, SCHED_FIFO does not. SCHED_OTHER is
fairness-based, which has RR-like characteristics but is not quite the
same.

Hope that helps,

jon

Jonathan Corbet / LWN.net / [email protected]

2009-10-30 10:20:12

by Daniel Rodrick

[permalink] [raw]
Subject: Re: Questions about linux scheduler

Hi,

>
>> * A lower priority process will run only if there are no runnable
>> processes in priority above it - this automatically means that all RT
>> processes get to run before non-RT processes.
>
> True for RT, not true for non-RT. ?In the current scheduler the non-RT
> tasks are stored in a time-ordered structure rather than the 40
> runqueues that were used before. ?A non-RT task will run once it becomes
> the most "urgent" task based on its nice level, how much cpu time it
> uses, and how long it's been since it ran last relative to other tasks
> on the system.

One last question ... the nice value of a process never changes
(unless done explicitly using nice system call), right?

Thanks,

Dan

2009-10-30 15:55:35

by Mulyadi Santosa

[permalink] [raw]
Subject: Re: Questions about linux scheduler

On Fri, Oct 30, 2009 at 5:20 PM, Daniel Rodrick
<[email protected]> wrote:
> One last question ... the nice value of a process never changes
> (unless done explicitly using nice system call), right?
>

Correct.... notice that only root who is able to alter the nice value
of any processes freely. Normal user can only renice its own created
process and only increase its nice value (thus decreasing its static
priority)


--
regards,

Mulyadi Santosa
Freelance Linux trainer and consultant

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