Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

[Gregory Haskins]

Sorry for topposting....still on vaca via blackberry..

I am in favor of dropping too...this patch was really just an RFC in response to Dmity's observation....its probably too premature to include this type of thing, if ever at all..

-Greg 
-----Original Message-----
From: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Ingo Molnar <mingo@elte.hu>
To: Dmitry Adamushko <dmitry.adamushko@gmail.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Gregory Haskins <GHaskins@novell.com>
Cc:  <linux-kernel@vger.kernel.org>

Sent: 6/13/2008 7:08:04 AM
Subject: Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

On Wed, 2008-06-11 at 12:05 +0200, Dmitry Adamushko wrote:
> 2008/6/11 Peter Zijlstra <a.p.zijlstra@chello.nl>:
> > On Wed, 2008-06-11 at 00:58 +0200, Dmitry Adamushko wrote:
> >> Hi Gregory,
> >>
> >>
> >> regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f
> >>
> >>
> >> I think we can do it simpler. Please take a look at the patch below.
> >>
> >> Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and twice so on x86_64),
> >> let's add "exclusive" (the ones that are bound to this CPU) tasks to the head of the queue
> >> and "shared" ones -- to the end.
> >>
> >> In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not queued as now), meaning that
> >> a task {i+1} is being placed in front of the previously woken up task {i}. But I don't think that
> >> this behavior may cause any realistic problems.
> >
> > Doesn't this violate POSIX ?
> >
> 
> If so, then the idea of "prioritize non-migratable tasks over
> migratable ones" violates it, not just an artefact of this particular
> implementation.
> 
> No matter which implementation is used, we have a situation when a
> woken-up single-CPU-bound task (let's call it 'p') can preempt a
> current task with effects as follows:
> 
> - 'current' is not guaranteed to get another CPU;
> 
> - there might have been other pending tasks (of equal prio) on this
> queue. As a result, 'p' starts running before them violating currently
> used (explicitly requested by POSIX?) round-robin behavior.

> We may just consider dropping this idea completely.
> (my 0.02$)

If we cannot guarantee POSIX compliant scheduling I think we should get
rid of this.

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

[Dmitry Adamushko]

2008/6/18 Ingo Molnar <mingo@elte.hu>:
>
> * Gregory Haskins <ghaskins@novell.com> wrote:
>
>> >>> On Mon, Jun 16, 2008 at  3:17 PM, in message
>> <1213643862.16944.142.camel@twins>, Peter Zijlstra <a.p.zijlstra@chello.nl>
>> wrote:
>> > On Mon, 2008-06-16 at 19:59 +0200, Dmitry Adamushko wrote:
>> >
>> >> One way or another, we have different aritifacts (and mine have likely
>> >> more) but conceptually, both "violates" POSIX if a strict round-robin
>> >> scheduling is required.
>> >
>> > http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
>> > ag_02_08_04_01
>> >
>> > Is quite strict on what FIFO should do, and I know of two points where
>> > we deviate and should work to match.
>>
>> Thanks for the link, Peter.  When you read that, its pretty clear that
>> this whole concept violates the standard.  Its probably best to just
>> revert the patch and be done with it.
>
> no, there's no spec violation here - the spec is silent on SMP issues.
>
> the spec should not be read to force a global runqueue for RT tasks.
> That would be silly beyond imagination.

I don't think it would actually make sense to specify behavior in
terms of per-cpu queues. This is an implementation detail. So the
_global_ (system-wise) queue makes more sense  (at least to me :-) if
one wants to define user-visible scheduling behavior.

e.g. as follows:
(http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#tag_02_08_04_01)

[quote]
"Threads scheduled under this policy are chosen from a thread list
that is ordered by the time its threads have been on the list without
being executed;"
[/quote]

>From the POV of users, I think only the "global" queue would make
sense. Otherwise, the sentence is rather useless.


[quote]
"generally, the head of the list is the thread that has been on the
list the longest time, and the tail is the thread that has been on the
list the shortest time."
[/quote]

OTOH, some differences can be justified by this "generally" word :-)

so it might be understood as something like this:

task_N can get a CPU only if all other pending runnable tasks that
have been enqueued earlier than task_N (of the same class and prio)
can _not_ start running on this CPU (e.g. due to their affinity).

Note, that our case is somewhat more subtle. We preempt a currently
running task in the hope that it can start running on another CPU
immediately, but we can't guarantee it.

Anyway, we are likely to win wrt cpu time distribution, but this fact
of 'preemption' is a new 'artifact' indeed.

if POSIX can be understood as : a SCHED_FIFO/RR task can be preempted
_only_ by a task with a higher prio and has to consume cpu-time as
long as it wants (FIFO) or till its timeslice expires (RR) , then we
violate it with this new behavior.


>
>        Ingo
>

-- 
Best regards,
Dmitry Adamushko

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

[Peter Zijlstra]

On Wed, 2008-06-18 at 12:39 +0200, Ingo Molnar wrote:
> * Gregory Haskins <ghaskins@novell.com> wrote:
> 
> > >>> On Mon, Jun 16, 2008 at  3:17 PM, in message
> > <1213643862.16944.142.camel@twins>, Peter Zijlstra <a.p.zijlstra@chello.nl>
> > wrote: 
> > > On Mon, 2008-06-16 at 19:59 +0200, Dmitry Adamushko wrote:
> > > 
> > >> One way or another, we have different aritifacts (and mine have likely
> > >> more) but conceptually, both "violates" POSIX if a strict round-robin
> > >> scheduling is required.
> > > 
> > > http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
> > > ag_02_08_04_01
> > > 
> > > Is quite strict on what FIFO should do, and I know of two points where
> > > we deviate and should work to match.
> > 
> > Thanks for the link, Peter.  When you read that, its pretty clear that 
> > this whole concept violates the standard.  Its probably best to just 
> > revert the patch and be done with it.
> 
> no, there's no spec violation here - the spec is silent on SMP issues.
> 
> the spec should not be read to force a global runqueue for RT tasks. 
> That would be silly beyond imagination.

Sadly, some people do read it like that.

> so ... lets apply Dmitry's nice simplification, hm?

As long as it doesn't wreck the per RQ queue model and only affects the
SMP interaction that would be acceptable I guess.

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

[Ingo Molnar]

* Gregory Haskins <ghaskins@novell.com> wrote:

> >>> On Mon, Jun 16, 2008 at  3:17 PM, in message
> <1213643862.16944.142.camel@twins>, Peter Zijlstra <a.p.zijlstra@chello.nl>
> wrote: 
> > On Mon, 2008-06-16 at 19:59 +0200, Dmitry Adamushko wrote:
> > 
> >> One way or another, we have different aritifacts (and mine have likely
> >> more) but conceptually, both "violates" POSIX if a strict round-robin
> >> scheduling is required.
> > 
> > http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
> > ag_02_08_04_01
> > 
> > Is quite strict on what FIFO should do, and I know of two points where
> > we deviate and should work to match.
> 
> Thanks for the link, Peter.  When you read that, its pretty clear that 
> this whole concept violates the standard.  Its probably best to just 
> revert the patch and be done with it.

no, there's no spec violation here - the spec is silent on SMP issues.

the spec should not be read to force a global runqueue for RT tasks. 
That would be silly beyond imagination.

so ... lets apply Dmitry's nice simplification, hm?

	Ingo

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

[Gregory Haskins]

>>> On Mon, Jun 16, 2008 at  3:17 PM, in message
<1213643862.16944.142.camel@twins>, Peter Zijlstra <a.p.zijlstra@chello.nl>
wrote: 
> On Mon, 2008-06-16 at 19:59 +0200, Dmitry Adamushko wrote:
> 
>> One way or another, we have different aritifacts (and mine have likely
>> more) but conceptually, both "violates" POSIX if a strict round-robin
>> scheduling is required.
> 
> http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
> ag_02_08_04_01
> 
> Is quite strict on what FIFO should do, and I know of two points where
> we deviate and should work to match.

Thanks for the link, Peter.  When you read that, its pretty clear that this whole concept violates the standard.  Its probably best to just revert the patch and be done with it.

Regards,
-Greg