Re: [patch] SCHED_SOFTRR linux scheduler policy ...

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Miguel Freitas]

Hi Davide,

I've found your SCHED_SOFTRR patch pretty interesting, the idea sounds
amazingly simple and effective :)

Some months ago i did experiments with multimedia performance on linux
kernel and ideas on what could be improved.

http://cambuca.ldhs.cetuc.puc-rio.br/~miguel/multimedia_sim/

I think it should be a general consensus that joe user must not need to
patch his kernel or run the multimedia player as root just to be able to
watch videos with good quality.

As a xine developer i'm very interested in help improving that
situation. Please let me know if you think this patch has chance of
being accepted into main tree, we can add support in xine for it.

regards,

Miguel

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Miguel Freitas wrote:

> Hi Davide,
>
> I've found your SCHED_SOFTRR patch pretty interesting, the idea sounds
> amazingly simple and effective :)
>
> Some months ago i did experiments with multimedia performance on linux
> kernel and ideas on what could be improved.
>
> http://cambuca.ldhs.cetuc.puc-rio.br/~miguel/multimedia_sim/
>
> I think it should be a general consensus that joe user must not need to
> patch his kernel or run the multimedia player as root just to be able to
> watch videos with good quality.

While I love the new scheduler, it is also true that interactivity comes
at a price. And this is fairness and predictable latency. It is also true
that many multimedia application do use very small buffers, that make them
to require short timings. I have to say that on my machine (P4 2.4GHz),
audio hardly skip during the typical load that my desktop sees, that in
turn is not so high. Like you can see in the couple of graphs that I
quickly dropped inside the SOFTRR page, typical latencies of 150ms are
very easy to obtain. Also, during the load used to measure those
latencies, my machines was perfectly interactive. And this clearly means
that high latencies are not interactivity enemies. I am also very much
sure that way higher latencies will be observable with other loads. It is
sufficent that one interactive task will start eating CPU slices that,
with the current timeslices and decay law, can generate a blackout of
hundreds of milliseconds. There are sufficent to make everyone expecting
bounded latencies to miss them. The patch is trivially simple, like you
can see from the code, and it basically introduces an expiration policy
for realtime tasks (SOFTRR ones). Polite SCHEDRR tasks can benefit of a
really predictable latency (see graph), while if they start to be greedy
they will be expired like other SCHED_OTHER tasks. Since RT processes ends
up getting a pretty decent timeslice, this should be sufficent for them
to perform their timing critical tasks w/out ever being expired. The other
test I did was indeed a task 'for (;;);' running on my machine with
SCHED_SOFTRR policy, and I could not even feel it. Patch acceptance is
tricky and definitely would need more discussion and test. The POSIX
standard clearly does not leave any space for std-user quasi-realtime
policies. The SCHED_RR and SCHED_FIFO are definitely not suitable to be
used from non-root because of the potential starvation they might inflict
to other processes on the system. On the other side, a modification of the
SCHED_RR and SCHED_FIFO behaviour inside the kernel is not good for both
POSIX compliancy and existing real realtime tasks compatibility. Bah, I
don't know. If they're roses they'll bloom ... ;)



> As a xine developer i'm very interested in help improving that
> situation. Please let me know if you think this patch has chance of
> being accepted into main tree, we can add support in xine for it.

With the current patch you do not need any special support if you are
already asking for SCHED_RR policy. If you are not root you will be
automatically downgraded to SCHED_SOFTRR ;)



PS: I just realized that the SOFTRR name is Copyright by Daniel Phillips.
Sorry Daniel, pls do not sue me :)



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Jamie Lokier]

Davide Libenzi wrote:
> With the current patch you do not need any special support if you are
> already asking for SCHED_RR policy. If you are not root you will be
> automatically downgraded to SCHED_SOFTRR ;)

Cool.  What happens if you run two SCHED_SOFTRR tasks and they both
use 50% of the CPU - will that starve all the other tasks?  Or is the
CPU usage of all SOFTRR tasks bounded collectively?

-- Jamie

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Jamie Lokier wrote:

> Davide Libenzi wrote:
> > With the current patch you do not need any special support if you are
> > already asking for SCHED_RR policy. If you are not root you will be
> > automatically downgraded to SCHED_SOFTRR ;)
>
> Cool.  What happens if you run two SCHED_SOFTRR tasks and they both
> use 50% of the CPU - will that starve all the other tasks?  Or is the
> CPU usage of all SOFTRR tasks bounded collectively?

Nope :) They will run their timeslice entirely and then they will try to
get some more. Looking at their last recharge timestamp, Dad scheduler
will put them in bed and will give other tasks a chance to run. But don't
worry, I am very sure there're other exploit available. I just didn't have
enough time to think about it. It is amazing how limited are things that
you can do in one hour :)



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Jamie Lokier]

Davide Libenzi wrote:
> > Cool.  What happens if you run two SCHED_SOFTRR tasks and they both
> > use 50% of the CPU - will that starve all the other tasks?  Or is the
> > CPU usage of all SOFTRR tasks bounded collectively?
> 
> Nope :) They will run their timeslice entirely and then they will try to
> get some more. Looking at their last recharge timestamp, Dad scheduler
> will put them in bed and will give other tasks a chance to run.

Nice, but answer to wrong question, possibly :)

I'm wondering what happens if the tasks are both good, early to bed
without a fuss.  Neither runs their entire timeslice.

Or to illustrate: say xine uses 10% of my CPU.  What happens when I
open 11 xine windows?

-- Jamie

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Jamie Lokier wrote:

> I'm wondering what happens if the tasks are both good, early to bed
> without a fuss.  Neither runs their entire timeslice.
>
> Or to illustrate: say xine uses 10% of my CPU.  What happens when I
> open 11 xine windows?

You need an adaptor ... hmmm ... another CPU :)
(if this is case, it is a trivial fix though)



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Miguel Freitas]

On Sat, 2003-07-12 at 13:20, Jamie Lokier wrote:
> I'm wondering what happens if the tasks are both good, early to bed
> without a fuss.  Neither runs their entire timeslice.
> 
> Or to illustrate: say xine uses 10% of my CPU.  What happens when I
> open 11 xine windows?

well of course 110% is more than what you have of resources and xine
would have to drop frames to keep it up... :)

anyway, if xine uses 10% of your CPU, that time is mostly likely spent
at the decoder thread. the only thread that i would set to use SOFTRR
would be the output thread, which does use very like CPU.

regards,

Miguel

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Jamie Lokier]

Miguel Freitas wrote:
> > I'm wondering what happens if the tasks are both good, early to bed
> > without a fuss.  Neither runs their entire timeslice.
> > 
> > Or to illustrate: say xine uses 10% of my CPU.  What happens when I
> > open 11 xine windows?
> 
> well of course 110% is more than what you have of resources and xine
> would have to drop frames to keep it up... :)

That's fine.  The problem is, does this completely starve the other
tasks such as kswapd, ksoftirqd, bash etc.?

The real problem is can a user accidentally or malicious lock up a box
using SCHED_SOFTRR (when xmms, xine, GNU software radio and modem are
all using it :), and also what about multi-user boxes, can two users
accidentally break it.

Perhaps there should be a _global_ maximum amount of CPU used in
SCHED_SOFTRR beyond which SCHED_SOFTRR tasks get downgraded.

-- Jamie

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Jamie Lokier wrote:

> Miguel Freitas wrote:
> > > I'm wondering what happens if the tasks are both good, early to bed
> > > without a fuss.  Neither runs their entire timeslice.
> > >
> > > Or to illustrate: say xine uses 10% of my CPU.  What happens when I
> > > open 11 xine windows?
> >
> > well of course 110% is more than what you have of resources and xine
> > would have to drop frames to keep it up... :)
>
> That's fine.  The problem is, does this completely starve the other
> tasks such as kswapd, ksoftirqd, bash etc.?
>
> The real problem is can a user accidentally or malicious lock up a box
> using SCHED_SOFTRR (when xmms, xine, GNU software radio and modem are
> all using it :), and also what about multi-user boxes, can two users
> accidentally break it.
>
> Perhaps there should be a _global_ maximum amount of CPU used in
> SCHED_SOFTRR beyond which SCHED_SOFTRR tasks get downgraded.

You need per-user policies to achieve fairness, the global allocation
won't work. You need global fairness towards tasks != SOFTRR *and* local
fairness towards tasks == SOFTRR. If you limit globally the maximum time
that SOFTRR tasks can suck, you'll achieve global fairness. But you do not
prevent a single user to suck most of this slice by creating many SOFTRR
tasks (or exploits). I can easily fix this if someone will show real
interest in the thing. Since it has been a while that I was not
looking at the scheduler, yesterday I googled a little bit and I saw
that there are a few issues where you do not need SOFTRR to completely
starve other tasks though (the irman thingy for example). IMHO these
should be discussed before going in 2.6, to either fix them or publicly
recognize them as "Not A Bug".



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Jamie Lokier]

Davide Libenzi wrote:
> You need per-user policies to achieve fairness, the global allocation
> won't work.

Agreed that fairness is complicated.  However, a global limit is
needed because it's a big security hole to not have one.  I wonder if
a global limit can't be implemented very simply?  Users interfering
with each other's real-timeness is not half as bad as users locking up
a box.

-- Jamie

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sun, 13 Jul 2003, Jamie Lokier wrote:

> Davide Libenzi wrote:
> > You need per-user policies to achieve fairness, the global allocation
> > won't work.
>
> Agreed that fairness is complicated.  However, a global limit is
> needed because it's a big security hole to not have one.  I wonder if
> a global limit can't be implemented very simply?

Yes, it is farily/very simple. I'll write it down today ...



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Bill Huey]

On Sat, Jul 12, 2003 at 08:59:18AM -0700, Davide Libenzi wrote:
> On Sat, 12 Jul 2003, Jamie Lokier wrote:
> 
> > Davide Libenzi wrote:
> > > With the current patch you do not need any special support if you are
> > > already asking for SCHED_RR policy. If you are not root you will be
> > > automatically downgraded to SCHED_SOFTRR ;)
> >
> > Cool.  What happens if you run two SCHED_SOFTRR tasks and they both
> > use 50% of the CPU - will that starve all the other tasks?  Or is the
> > CPU usage of all SOFTRR tasks bounded collectively?
> 
> Nope :) They will run their timeslice entirely and then they will try to
> get some more. Looking at their last recharge timestamp, Dad scheduler
> will put them in bed and will give other tasks a chance to run. But don't
> worry, I am very sure there're other exploit available. I just didn't have
> enough time to think about it. It is amazing how limited are things that
> you can do in one hour :)

Hey,

Have any of you folks seen this ?

	http://www.linuxdevices.com/articles/AT6078481804.html
	http://research.microsoft.com/~mbj/papers/tr-99-59_abstract.html

Neat stuff. This with a fully preemptive kernel is one of Linux kernel
dreams for multimedia.

bill

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Bill Huey wrote:

> Have any of you folks seen this ?
>
> 	http://www.linuxdevices.com/articles/AT6078481804.html
> 	http://research.microsoft.com/~mbj/papers/tr-99-59_abstract.html
>
> Neat stuff. This with a fully preemptive kernel is one of Linux kernel
> dreams for multimedia.

This is funny. Every time I found something interesting to read (papers) I
print them and I stock on my desk. The are 25Kg of papers piled on my desk
right now. Thanks to you, 25.05Kg now ;) Upon a brief read, The Italian Job,
hemm ... paper, is very similar to SOFTRR. Once you change their "server"
notion with the per-user allocation I have in mind, it'll come even
closer. I really didn't have time to read the MS paper though. The problem
is not if it can be done, the problem is how bad ppl wants it.



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Bill Huey]

On Sat, Jul 12, 2003 at 07:39:25PM -0700, Davide Libenzi wrote:
> This is funny. Every time I found something interesting to read (papers) I
> print them and I stock on my desk. The are 25Kg of papers piled on my desk
> right now. Thanks to you, 25.05Kg now ;) Upon a brief read, The Italian Job,
> hemm ... paper, is very similar to SOFTRR. Once you change their "server"
> notion with the per-user allocation I have in mind, it'll come even
> closer. I really didn't have time to read the MS paper though. The problem
> is not if it can be done, the problem is how bad ppl wants it.

I want it badly, but that's just me. :) The MS is about extending these
concept to apply to SMP resource allocation, which currently isn't something
that these kind of schedulers do. IMO, all of this kind of stuff is going to
be crucial for the next generation of operating systems.  Glue that scheduler
to a thread that's suppose to process network packets/io channels and you'll
have ubiquitous QoS throughout the system directly controllable by the scheduler.

That's my intuition on the subject. Time will tell.

bill

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Miguel Freitas]

Hi Davide,

On Sat, 2003-07-12 at 12:20, Davide Libenzi wrote:
> While I love the new scheduler, it is also true that interactivity comes
> at a price. And this is fairness and predictable latency. It is also true
> that many multimedia application do use very small buffers, that make them
> to require short timings.


I guess you are talking about mostly audio applications here. For video
playback these timings are even tighter and there is very little the
application itself can do to improve it (it's not a matter of increasing
the buffer size).

It is also true that most people won't be running heavy applications
while watching a video. It's not like the xmms that we leave running on
background while working.


> I have to say that on my machine (P4 2.4GHz),
> audio hardly skip during the typical load that my desktop sees, that in
> turn is not so high. Like you can see in the couple of graphs that I
> quickly dropped inside the SOFTRR page, typical latencies of 150ms are
> very easy to obtain.


150ms latency would kill any video application.

There is no equivalent of sound card's or kernel audio buffers for
frames, the application just _have_ to be scheduled in time to display
the frame (basicaly tell X to display a frame from shared memory, for
example).

In xine, we have separated decoder and output threads with a queue of
about 15 frames between them. So just the output thread needs
predictable latency, and that thread does use very little CPU.

Also the problem may get a little worse as people start trying to get
better quality from their systems. I recently added a plugin in xine
(tvtime) that deinterlaces frames to full tv field rate (60Hz). While
playing a DVD @ 30Hz under a 2.4 kernel (HZ=100) is usually acceptable,
60Hz pushes the requirements a little further: the output thread must be
scheduled every 16ms.


> The patch is trivially simple, like you
> can see from the code, and it basically introduces an expiration policy
> for realtime tasks (SOFTRR ones).

yes, i saw that, pretty nice!
i have yet to try it (i don't have any recent 2.5 on my machine)


> Patch acceptance is
> tricky and definitely would need more discussion and test.


Sure. But let me add a voice of support here: I would be great if kernel
provided a way to multimedia or interactive applications to request a
better latency predictability (or hint the scheduler somehow) without
need of being root. If that comes in a form of a new scheduler policy,
or just allowing small negative nice values for non-root i don't mind...


> With the current patch you do not need any special support if you are
> already asking for SCHED_RR policy. If you are not root you will be
> automatically downgraded to SCHED_SOFTRR ;)


We don't currently request SCHED_RR in xine. At least Ingo once adviced
me he didn't thought it was right for a multimedia application to use
that. The problem is that currently we have an all (root can set -nice,
scheduler policy, etc) or nothing situation.
 
regards,

Miguel

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Miguel Freitas wrote:

> I guess you are talking about mostly audio applications here. For video
> playback these timings are even tighter and there is very little the
> application itself can do to improve it (it's not a matter of increasing
> the buffer size).

Yes, it was audio I was talking about ...


> > I have to say that on my machine (P4 2.4GHz),
> > audio hardly skip during the typical load that my desktop sees, that in
> > turn is not so high. Like you can see in the couple of graphs that I
> > quickly dropped inside the SOFTRR page, typical latencies of 150ms are
> > very easy to obtain.
>
>
> 150ms latency would kill any video application.
>
> There is no equivalent of sound card's or kernel audio buffers for
> frames, the application just _have_ to be scheduled in time to display
> the frame (basicaly tell X to display a frame from shared memory, for
> example).

and yes, video is even more strict about timings.


> > The patch is trivially simple, like you
> > can see from the code, and it basically introduces an expiration policy
> > for realtime tasks (SOFTRR ones).
>
> yes, i saw that, pretty nice!
> i have yet to try it (i don't have any recent 2.5 on my machine)

It should be trivial to do something like that for the old scheduler.


> > Patch acceptance is
> > tricky and definitely would need more discussion and test.
>
> Sure. But let me add a voice of support here: I would be great if kernel
> provided a way to multimedia or interactive applications to request a
> better latency predictability (or hint the scheduler somehow) without
> need of being root. If that comes in a form of a new scheduler policy,
> or just allowing small negative nice values for non-root i don't mind...

You'd need a nice value that will keep you away from being caught by
interactive SCHED_OTHER. Otherwise yes, this is another solution. Did you
try it with xine under high load ?



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Miguel Freitas]

On Sat, 2003-07-12 at 13:30, Davide Libenzi wrote:
> > > Patch acceptance is
> > > tricky and definitely would need more discussion and test.
> >
> > Sure. But let me add a voice of support here: I would be great if kernel
> > provided a way to multimedia or interactive applications to request a
> > better latency predictability (or hint the scheduler somehow) without
> > need of being root. If that comes in a form of a new scheduler policy,
> > or just allowing small negative nice values for non-root i don't mind...
> 
> You'd need a nice value that will keep you away from being caught by
> interactive SCHED_OTHER. Otherwise yes, this is another solution. Did you
> try it with xine under high load ?

Since i upgraded my computer recently it's difficult to compare with the
experiments i made before. But basically no, i haven't tried to make
xine smooth under high load. my primary complain was that even a small
background load caused by KSysGuard (KDE system monitor) could make it
drop frames from time to time. with nice values like -2 the problem was
completely fixed.

regards,

Miguel

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sat, 12 Jul 2003, Miguel Freitas wrote:

> On Sat, 2003-07-12 at 13:30, Davide Libenzi wrote:
> Since i upgraded my computer recently it's difficult to compare with the
> experiments i made before. But basically no, i haven't tried to make
> xine smooth under high load. my primary complain was that even a small
> background load caused by KSysGuard (KDE system monitor) could make it
> drop frames from time to time. with nice values like -2 the problem was
> completely fixed.

IMMIC (If My Math Is Correct :) you would need a nice -11 to be completely
sure that your task will not be preempted by an iteractive SCHED_OTHER
(one can go to +5 and the other might go to -5) with the current settings.



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Jamie Lokier]

Miguel Freitas wrote:
> It is also true that most people won't be running heavy applications
> while watching a video.

I can't think of a better time to run that numerical simulation!

> It's not like the xmms that we leave running on background while
> working.

That's what two monitors is for :)

-- Jamie

[patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

I finally found a couple of hours for this and I also found a machine were
I can run 2.5, since luck abandoned myself about this. The small page
describe the obvious and contain the trivial patch and the latecy test app :

http://www.xmailserver.org/linux-patches/softrr.html



- Davide

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Pavel Machek]

Hi!

> I finally found a couple of hours for this and I also found a machine were
> I can run 2.5, since luck abandoned myself about this. The small page
> describe the obvious and contain the trivial patch and the latecy test app :
> 
> http://www.xmailserver.org/linux-patches/softrr.html

What happens if evil user forks 60 processes, marks them all
SCHED_SOFTRR, and tries to starve everyone else?
							Pavel
-- 
When do you have a heart between your knees?
[Johanka's followup: and *two* hearts?]

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Alan Cox]

On Sul, 2003-07-13 at 12:50, Pavel Machek wrote:
> Hi!
> 
> > I finally found a couple of hours for this and I also found a machine were
> > I can run 2.5, since luck abandoned myself about this. The small page
> > describe the obvious and contain the trivial patch and the latecy test app :
> > 
> > http://www.xmailserver.org/linux-patches/softrr.html
> 
> What happens if evil user forks 60 processes, marks them all
> SCHED_SOFTRR, and tries to starve everyone else?

With the current scheduler you lose. Rik did some playing with a fair
share scheduler some time ago. That actually works very well for a lot
of these sorts of things. You can nice processes up (but only by
penalising your own processes) and conceptually you'd be able to soft
real time on a per user basis this way. 

Alan

Re: [patch] SCHED_SOFTRR linux scheduler policy ...

[Davide Libenzi]

On Sun, 13 Jul 2003, Pavel Machek wrote:

> Hi!
>
> > I finally found a couple of hours for this and I also found a machine were
> > I can run 2.5, since luck abandoned myself about this. The small page
> > describe the obvious and contain the trivial patch and the latecy test app :
> >
> > http://www.xmailserver.org/linux-patches/softrr.html
>
> What happens if evil user forks 60 processes, marks them all
> SCHED_SOFTRR, and tries to starve everyone else?

Oh, no doubt you can do it. The SOFTRR thing can be fixed for this, pretty
easily. The problem, like Alan is saying, is that with the current
scheduler you do not need SOFTRR to starve other tasks. This is why I said
that all the issues that have been grought up in the last few months
should be discussed before going in 2.6. So that we can either say that
are corner cases that we can ive ith, or we fix them. I didn't follow the
scheduler after the first merge but it seems that a couple of issues
should be addressed before 2.6.



- Davide