Linux scheduler (scheduling) questions

Linux scheduler (scheduling) questions

[Povolotsky, Alexander]

Hello Everyone,

I  have "general"  Linux  OS scheduling  questions, especially with regards
as those apply to the (latest) Linux  2.6  scheduler features (would really
appreciate if whether/when/while answering those questions listed  below,
you could pinpoint differences between Linux 2.6 and Linux 2.4 !): 

0.  I was told that the Linux kernel could be configured with one of the 3
(? ) different scheduling policies - could someone describe       
     those to me in details ?

1.   How rescheduling is "induced" in above scheduling policies ?
      Does at least one of above mentioned scheduling policies uses "clock
tick" as a scheduling event ?
     Also, releasing mutex lock (semaphore) in Linux application/user-space
task - is it considered (by the sched) as a
     "rescheduling event" ? - (in addition to "clock tick" event) - this is
true for PSOS / VxWorks RTOSes.
     
2.  Linux 2.6 (I was told it is the same for Linux 2.4.21-15) has priorities
0-99 for RT priorities and 100-139 for normal   (SCHED_NORMAL)   tasks.

> I presume that priorities 0-99 are "recommended" (or enforced ?) for
> Linux kernel "native" tasks ... and "out or reach" for application
> tasks (unless one dares to merge application into the Linux kernel,
> masquerading it as a "system level command" - did anyone tried this ? -
> I presume it is not recommended ...  )  ?
> 
Under what priority the OS system calls are executed ?

3.  Is  priority inversion and its prevention (priority inheritance or
priority ceilings) applicable to Linux ) for application/user-space tasks (
with priorities in the range 100-139) ?
> Similar question for the situation when the "application" process
> executes "OS system call" in the kernel address space ?
> Similar question for the RT tasks (which I presume are Linux kernel
> "native" tasks, always executing in the kernel address space ? ) ?
> 
4. What about scheduling threads ? - as I have understood (from the FAQ on
http://www.tux.org/lkml/ ), threads in Linux are implemented in the kernel
space - is this information up to date, i.e. - is it applicable to Linux 2.6
? and what it actually means 
(does it mean that threads are always running in the kernel space ? - that
sounds a bit strange ...).
With what  priorities threads are running ? - do those priorities depend on
the priority of the application/user space process from which the  clone
system call was made  ?). 
5. Deviating from the scheduling line of questions (but staying with threads
issues): is there an option in clone(2)  to make threads 
   not to run in the same  address space but rather act as independent
process(es).

> Thanks,
> Best Regards,
> Alex Povolotsky
-----Original Message-----
From: Ingo Molnar [mailto:mingo@elte.hu]
Sent: Monday, June 28, 2004 10:40 AM
To: Povolotsky, Alexander
Subject: Re: Any differences (between 2.4 and 2.6) in Linux kernel
scheduling

Alexander,

you might want to post your questions to linux-kernel@vger.kernel.org
(or some other, RT related mailing list). The scheduler is described in
a rudimentary way in Documentation/sched-design.txt, sched-coding.txt,
with no focus on RT though.

	Ingo

>  
> 
> 

Re: Linux scheduler (scheduling) questions

[Felipe Alfaro Solana]

On Tue, 2004-06-29 at 08:51 -0400, Povolotsky, Alexander wrote:

> 5. Deviating from the scheduling line of questions (but staying with threads
> issues): is there an option in clone(2)  to make threads 
>    not to run in the same  address space but rather act as independent
> process(es).

If you want something in a different address space, then you want a
process. Threads of the same process share the whole address space
(except they have their own stack) and this have some advantages, like
faster CPU context switching between threads of the same process, and
faster creation times, among others.

Re: Linux scheduler (scheduling) questions

[Con Kolivas]

[-- Attachment #1: Type: text/plain, Size: 3931 bytes --]

Povolotsky, Alexander writes:

> I  have "general"  Linux  OS scheduling  questions, especially with regards
> as those apply to the (latest) Linux  2.6  scheduler features (would really
> appreciate if whether/when/while answering those questions listed  below,
> you could pinpoint differences between Linux 2.6 and Linux 2.4 !): 
> 
> 0.  I was told that the Linux kernel could be configured with one of the 3
> (? ) different scheduling policies - could someone describe       
>      those to me in details ?

Three different policies are currently supported:
SCHED_NORMAL (also known as SCHED_OTHER) has a soft priority mechanism 
over the 'nice' range of -20 to +19 (static priority of 100-139) which 
decides according to the priority which task goes first, and how much 
timeslice it gets. This system dynamically alters the priority to allow 
interactive tasks to go first, and is designed to prevent starvation of 
lower priority tasks with an expiration policy. 

SCHED_RR is a fixed real time policy over the static range of 0-99 where a 
lower number (higher priority) task will repeatedly go ahead of _any_ tasks 
lower priority than itself. It is called RR because if multiple tasks are at 
the same priority it will Round Robin between those tasks. 

SCHED_FIFO is a fixed real time policy the static range of 0-99 where a
lower number (higher priority) task will repeatedly go ahead of _any_ tasks
lower priority than itself. Unlike RR, if a task does not give up the cpu it 
will run indefinitely even if other tasks are the same static priority as 
itself.

Unprivileged users are not allowed to set SCHED_RR or SCHED_FIFO because of 
the real risk of these tasks causing starvation.

> 1.   How rescheduling is "induced" in above scheduling policies ?
>       Does at least one of above mentioned scheduling policies uses "clock
> tick" as a scheduling event ?

Preemption is built into this mechanism where any higher priority task will 
preempt the current running task at any time. SCHED_NORMAL tasks have a 
timeout policy based on scheduler_tick that allows other tasks of the same 
priority to run and considers that task for expiration. SCHED_RR tasks have 
a timeout policy also based on scheduler tick that allows tasks of the same 
priority to run. SCHED_FIFO tasks never time out.

> 2.  Linux 2.6 (I was told it is the same for Linux 2.4.21-15) has priorities
> 0-99 for RT priorities and 100-139 for normal   (SCHED_NORMAL)   tasks.
> 
>> I presume that priorities 0-99 are "recommended" (or enforced ?) for
>> Linux kernel "native" tasks ... and "out or reach" for application
>> tasks (unless one dares to merge application into the Linux kernel,
>> masquerading it as a "system level command" - did anyone tried this ? -
>> I presume it is not recommended ...  )  ?

See above.

> Under what priority the OS system calls are executed ?

The kernel threads run at different priorities dependent on what they do. 
Run 'top -b -n 1' and you'll see a list of different tasks with the name k* 
that are kernel threads. On SMP systems, the migration thread is SCHED_FIFO 
priority 0 which means it always goes ahead of everything else. The rest of 
the kernel threads vary between SCHED_NORMAL 'nice' -20 to +19 (static 
priority 100-139).

> 3.  Is  priority inversion and its prevention (priority inheritance or
> priority ceilings) applicable to Linux ) for application/user-space tasks (
> with priorities in the range 100-139) ?

There is no intrinsic mechanism in the kernel to prevent priority inversion. 
Generic anti-starvation mechanims minimise the harm that priority inversion 
can do but there can be a lot of wasted cpu cycles for poorly coded 
applications. This is more true of 2.6 than 2.4 because the cpu scheduler 
does far more 'out of order' scheduling where a task can run many many times 
dependent on priority before another task will ever run.

Hope this helps,
Cheers,
Con


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]