Linux scheduler (scheduling) questions vs threads

Linux scheduler (scheduling) questions vs threads

[Povolotsky, Alexander]

Sorry for bothering and annoying everyone on this list again with additional
questions ...

Let assume there is one (and only one) application (user space ) process
running on the Linux 2.6 - with multiple threads within it, created via
"clone" (this happens, I presume, for example, if one uses Monta Vista
library for porting PSOS to Linux).

What scheduling policies those threads (within the same process) will be
governed by (if any )?

Or is it user's responsibility to arrange threads scheduling via some means
of inter-process synchronization (such as signals, etc ) ?

Thanks,
Best Regards,
Alex Povolotsky

-----Original Message-----
From: Con Kolivas [mailto:kernel@kolivas.org]
Sent: Tuesday, June 29, 2004 6:53 PM
To: Povolotsky, Alexander
Cc: 'linux-kernel@vger.kernel.org'; 'andrebalsa@altern.org'; 'Richard E.
Gooch'; 'Ingo Molnar'; 'rml@tech9.net'; 'akpm@osdl.org'
Subject: Re: Linux scheduler (scheduling) questions


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 ?
> 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 ...  )  ?

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
with 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.

> 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

Re: Linux scheduler (scheduling) questions vs threads

[Ingo Molnar]

* Povolotsky, Alexander <Alexander.Povolotsky@marconi.com> wrote:

> Sorry for bothering and annoying everyone on this list again with additional
> questions ...
> 
> Let assume there is one (and only one) application (user space ) process
> running on the Linux 2.6 - with multiple threads within it, created via
> "clone" (this happens, I presume, for example, if one uses Monta Vista
> library for porting PSOS to Linux).
> 
> What scheduling policies those threads (within the same process) will be
> governed by (if any )?

in Linux there's no difference between the scheduling of 'threads' and
'processes'. Both are internally a 'task'. If two tasks share the same
MM (this is possible via the use of clone()) then they are called
threads. If a task has its own MM (normally created via fork()) then
it's called a process - but the scheduler doesnt care.

so the normal Linux scheduling policy applies to 'threads' too. Fully
preemptable, SCHED_NORMAL by default, or SCHED_FIFO/SCHED_RR if you set
it. The priority (or rt_priority) can be set per-task as well. Newly
created threads/processes may inherit (or not) the policy of the parent,
this largely depends on the library implementation.

	Ingo

Re: Linux scheduler (scheduling) questions vs threads

[Bill Davidsen]

Ingo Molnar wrote:
> * Povolotsky, Alexander <Alexander.Povolotsky@marconi.com> wrote:
> 
> 
>>Sorry for bothering and annoying everyone on this list again with additional
>>questions ...
>>
>>Let assume there is one (and only one) application (user space ) process
>>running on the Linux 2.6 - with multiple threads within it, created via
>>"clone" (this happens, I presume, for example, if one uses Monta Vista
>>library for porting PSOS to Linux).
>>
>>What scheduling policies those threads (within the same process) will be
>>governed by (if any )?
> 
> 
> in Linux there's no difference between the scheduling of 'threads' and
> 'processes'. Both are internally a 'task'. If two tasks share the same
> MM (this is possible via the use of clone()) then they are called
> threads. If a task has its own MM (normally created via fork()) then
> it's called a process - but the scheduler doesnt care.
> 
> so the normal Linux scheduling policy applies to 'threads' too. Fully
> preemptable, SCHED_NORMAL by default, or SCHED_FIFO/SCHED_RR if you set
> it. The priority (or rt_priority) can be set per-task as well. Newly
> created threads/processes may inherit (or not) the policy of the parent,
> this largely depends on the library implementation.

On a multi-user machine this may result in undesirable behaviour, since 
each thread seems to compete for resources and the machine may get VERY 
slow if someone deos something anti-social. There is a Mandelbrot 
drawing program which allows use of threads, it will do very bad things 
to system performance to have 8 CPU bound threads generating graphics so 
X is doing a lot of work as well. Student claimed it was part of his 
math homework...

-- 
    -bill davidsen (davidsen@tmr.com)
"The secret to procrastination is to put things off until the
  last possible moment - but no longer"  -me

Re: Linux scheduler (scheduling) questions vs threads

[Bill Davidsen]

Chris Siebenmann wrote:
> You write:
> | Ingo Molnar wrote:
> [...]
> | > so the normal Linux scheduling policy applies to 'threads' too. [...]
> [...]
> | On a multi-user machine this may result in undesirable behaviour, since 
> | each thread seems to compete for resources and the machine may get VERY 
> | slow if someone deos something anti-social.
> 
>  This is nothing unique to threads; the same problem appears if a
> program (or a user) uses a bunch of CPU-eating processes. I imagine
> that any real solution will have to be per-user 'beancounting' and
> limits, which have yet to make it into the Linux kernel.

Actually, yes it is. While students can be warned about the results of 
fork bombing a system, both in terms of what happens to the system and 
to their access, it's far less obvious that starting a program which 
does a lot of threads is equally bad behaviour.

The desirability for per-user scheduling is also shown by the student 
who build a large project with "-j4" as a make option and "-pipe" as a 
compile option. Yes, it makes the program complete sooner, and it 
generally is done with no malice.

Hopefully some form of this will appear in the 2.7 kernel, although past 
discussions in several places have resulted in more heat than light on 
the topic.


-- 
bill davidsen <davidsen@tmr.com>
   CTO TMR Associates, Inc
   Doing interesting things with small computers since 1979

Re: Linux scheduler (scheduling) questions vs threads

[Paul Rolland]

> Chris Siebenmann wrote:
> > You write:
> > | Ingo Molnar wrote:
> > [...]
> > | > so the normal Linux scheduling policy applies to 
> 'threads' too. [...]
> > [...]
> > | On a multi-user machine this may result in undesirable 
> behaviour, since 
> > | each thread seems to compete for resources and the 
> machine may get VERY 
> > | slow if someone deos something anti-social.
> > 
> >  This is nothing unique to threads; the same problem appears if a
> > program (or a user) uses a bunch of CPU-eating processes. I imagine
> > that any real solution will have to be per-user 'beancounting' and
> > limits, which have yet to make it into the Linux kernel.
> 

What about ulimit'ing users ?

bash-2.05$ ulimit -a
core file size (blocks)     0
data seg size (kbytes)      unlimited
file size (blocks)          unlimited
max locked memory (kbytes)  unlimited
max memory size (kbytes)    unlimited
open files                  1024
pipe size (512 bytes)       8
stack size (kbytes)         8192
cpu time (seconds)          unlimited
max user processes          4087
virtual memory (kbytes)     unlimited

Regards,
Paul