SCHED_SOFTRR linux scheduler policy ...

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

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

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

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

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

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

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

- Davide

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

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

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

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

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

- Davide

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

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

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

Hi Davide,

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.

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.

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

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

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

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

and yes, video is even more strict about timings.

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

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

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

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

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

That's what two monitors is for :)

-- Jamie