Re: OSDL Bug 3770

Re: OSDL Bug 3770

[Nick Piggin]

Loic Domaigne wrote:

> Hello Nick!
> Hello NPTL Mailing List!
>

Hello Loic! Thanks for the interesting mail.

I'm CCing lkml and Ingo with this, because I wouldn't feel comfortable 
to veto
this myself.

lkml: We're discussing the fact that on SMP machines, our realtime 
scheduling
policies are per-CPU only. This caused a problem where a high priority 
task on
one CPU caused all lower priority tasks on that CPU to be starved, while 
tasks
on another CPU with the same low priority were able to run.

>>> Ah, the problem is that when the driver thread has a higher
>>> priority than the worker threads, so when the driver goes into an
>>> infinite loop  waiting, the able to schedule, however.
>>
>
> Although POSIX legally permits such implementation for realtime policy 
> on SMP machines, this implementation is clearly *NOT* REASONABLE.
>

Well I haven't done much in the realtime area... but nobody has 
complained till now.

> The reason is extremely simple: the application *CANNOT* necessarily 
> known that it gets stuck behind a higher-priority thread (though it 
> could had run on another CPU if the scheduler had decided otherwise). 
> That's *NOT* doable to program in a deterministic fashion in such 
> "realtime"-environement
>

You could use CPU binding. I'd argue that this may be nearly a 
requirement for
any realtime system of significant complexity on an SMP system.

*But*, notice that the program in question did not run on UP and 
randomly fail
on SMP, rather it would not work on single processor AT ALL.

> [
> "Realtime" put into quote. I am speaking here of soft realtime, that 
> is an environment whose tasks scheduling follow a specific 
> deterministic order. I am not speaking about hard-realtime that have 
> additional timing constraints. Following that definition, we can say 
> that Linux offers (soft) "Realtime".
> ]
>
>
>> > The driver really needs to sleep, use a mutex, use a lower priority,
>>
>>> or  something in order for it to work.
>>
>
> NO! It is not the responsability of the application to fix that 
> behavior! We can in our case because 'we know', but some applications 
> don't!!!
>

That's a bit hand-wavy ;) but I don't dismiss it out of hand because as 
I said,
I'm not so familiar with this area. I would be interested in an example 
of some
application where this matters, and which absolutely can't use any 
synchronisation
primitives.

>
> The mistake done here is interesting. When you have a pool of servers, 
> you can proceed in two ways to serve the clients:
>
>     (1) make a FIFO queue for each server. When a client arrives, it
>         chooses the queue that is the shortest.
>
>     (2) make an unique FIFO queue for all servers. All clients are
>         queued, and when a server is done it takes the first client
>         waiting on that big queue.
>
> Queuing theory proves that (2) is better. Exactly due to the reason we 
> have here. With (1), the guys in the queue might get stuck if the 
> corresponding server is blocked by a client. With (2), when a server 
> is blocked by a client, it doesn't prevent the other clients to be 
> served by other servers.
>

But that model is flawed for SMP scheduling. If it were that easy, we 
might have a
single queue for _all_ tasks.

The main problem is the cost of synchronisation and cacheline sharing. A 
secondary
problem is that of CPU affinities - moving a task to another CPU nearly 
always has
some non zero cost in terms of cache (and in case of NUMA, memory) 
efficiency.

Our global queue scheduler was basically crap for more than 4 CPUs. We 
could give
RT tasks a global queue with little impact to non-RT workloads (in fact, 
I think
early iterations of the 2.6 scheduler trialed this)... but let's not 
cripple the
RT apps that do the right thing (and need scalablility).

Another problem is that scheduling may not be O(1) anymore, if you have 
CPU affinity
bindings in place.

To summaries, I believe that if per-CPU RT queues is allowed within 
POSIX, then we
want to go with the sanest possible implementation, and force any broken 
apps to
fix themselves.... let's not cave in now :)

Nick

> [
> An historical note. USA had implemented (2) in offices, supermarkets 
> and such long before Europa. Because in Europe, customers were 
> convinced that model (2) took more time, because the queue was longer.
> ]
>
>

Re: OSDL Bug 3770

[Ingo Molnar]

* Loic Domaigne <loic-dev@gmx.net> wrote:

> > Yes, it does support hard CPU binding - sched_setaffinity
> 
> Yes, I believe that /sched_setaffinity()/ offers a practical solution
> to the problem we are faced. 

that's the short-term workaround. Another model for CPU-bound RT tasks
is the use of isolcpus. (see Documentation/kernel-parameters.txt)

but that's the thinking behind current RT scheduling: no global sorting
of priorities is done on SMP, but if you know the priorities and the
workload in advance you can manually bind them to specific CPUs.

> But I am eager to try the RT-patchset of Ingo. 

this is obviously more experimental stuff, and feedback is welcome. It
is the current 'playground' for RT related scheduling features.

	Ingo

Re: OSDL Bug 3770

[Loic Domaigne]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset="us-ascii", Size: 1079 bytes --]

Hello Nick, 

> >Does Linux tolerate hard CPU binding? By hard CPU binding, I mean 
> >that the application tells the scheduler "I want to run there", 
> >and the scheduler schedules the thread(s) "there" regardless if it 
> >makes sense or not ( The decision is left to the application). 
> 
> Yes, it does support hard CPU binding - sched_setaffinity

Yes, I believe that /sched_setaffinity()/ offers a practical solution to the
problem we are faced. 

But I am eager to try the RT-patchset of Ingo. 


> [snip interesting dialogue]
> 
> Thanks for your detailed comments, they were interesting.

... Glad to hear. You're welcome!  



Cheers,  
Loic. 

-- 
--
// Sender address goes to /dev/null (!!) 
// Use my 32/64 bits, ANSI C89, compliant email-address instead:   

unsigned y[]=
{0,34432,26811,16721,41866,63119,61007,48155,26147,10986};
void x(z){putchar(z);}; unsigned t; 
main(i){if(i<10){t=(y[i]*47560)%65521;x(t>>8);x(t&255);main(++i);}}

+++ Sparen Sie mit GMX DSL +++ http://www.gmx.net/de/go/dsl
AKTION für Wechsler: DSL-Tarife ab 3,99 EUR/Monat + Startguthaben

Re: OSDL Bug 3770

[Nick Piggin]

Loic Domaigne wrote:

>Hello Nick,
>
>Thanks for your reply! 
> 
>L = Loic 
>N = Nick 
>
>N> lkml: We're discussing the fact that on SMP machines, our realtime 
>N> scheduling policies are per-CPU only. This caused a problem where a 
>N> high priority task on one CPU caused all lower priority tasks on that 
>N> CPU to be starved, while tasks on another CPU with the same low 
>N> priority were able to run.
>
>That summary should readily motivate you to make a patch ;-) 
>
>But thing are a bit worse actually. It is easily to build an example 
>where a lower priority thread is executing while a higer priority thread
>is waiting. For instance, something like: 
>
>CPU0:
>Thread with prio 30 gets the CPU.
>Thread with prio 25 is waiting.
>
>CPU1:
>Thread with prio 20 gets the CPU.
>Thread with prio 15 is waiting.
>
>

Yep.


[snip]

>L> The reason is extremely simple: the application *CANNOT* necessarily 
>L> known that it gets stuck behind a higher-priority thread (though it 
>L> could had run on another CPU if the scheduler had decided otherwise). 
>L> That's *NOT* doable to program in a deterministic fashion in such 
>L> "realtime"-environement
>N>
>N>
>N> You could use CPU binding. I'd argue that this may be nearly a
>N> requirement for any realtime system of significant complexity on 
>N> an SMP system.
>
>Agree. Real-world system will likely want to have a control on which 
>CPU the threads runs on SMP machine. 
>
>Does Linux tolerate hard CPU binding? By hard CPU binding, I mean 
>that the application tells the scheduler "I want to run there", 
>and the scheduler schedules the thread(s) "there" regardless if it 
>makes sense or not ( The decision is left to the application). 
>
>With such hard CPU binding, it seems to me that our "unfortunate 
>behavior" isn't problematic anymore. Because the application can gain 
>control again over the scheduler (so to speak). 
>
>On the other hand, if the scheduler might ignore the CPU binding 
>(thus, not hard binding, but rather CPU affinity), then I am afraid 
>that the issue might remain problematic.  
>
>

Yes, it does support hard CPU binding - sched_setaffinity

[snip interesting dialogue]

Thanks for your detailed comments, they were interesting.

I hope that the fact we have hard CPU binding is a sufficient
solution to the problem.

Thanks
Nick