Multimedia scheduling class

Hi,

I have created an experimental multimedia scheduling class (SCHED_MM) for use with multithreaded non-hardcore-realtime multimedia applications, such as ones based on gstreamer. These typically don't follow the determinism rules of well behaved SCHED_FIFO applications. However, these usually handle tasks like VoIP call audio processing, where somewhat lower scheduling latency is needed to obtain good user experience. Usually these are not very CPU-heavy and are mostly IO-bound processes. Thus, something between normal SCHED_OTHER and SCHED_FIFO is needed in a way where different threads of execution can set different kinds of scheduling parameters.

I have attached an initial version of my experimental patch for comments...

Best regards,

- Jussi Laako

diff -ur linux-2.6.27.7-9.orig/include/linux/sched.h linux-2.6.27.7-9.new/include/linux/sched.h
@@ -38,6 +38,7 @@
 #define SCHED_BATCH		3
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
+#define SCHED_MM		6
 
 #ifdef __KERNEL__
 

diff -ur linux-2.6.27.7-9.orig/kernel/sched_fair.c linux-2.6.27.7-9.new/kernel/sched_fair.c
@@ -18,6 +18,9 @@
  *
  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <[email protected]>
+ *
+ *  Multimedia scheduling by Jussi Laako
+ *  Copyright (C) 2008 Nokia Corporation, Jussi Laako <[email protected]>
  */
 
 #include <linux/latencytop.h>

@@ -959,7 +962,8 @@
 	if (unlikely(cfs_rq->nr_running == 1))
 		return;
 
-	if (likely(!sysctl_sched_compat_yield) && curr->policy != SCHED_BATCH) {
+	if (likely(!sysctl_sched_compat_yield) &&
+		curr->policy != SCHED_BATCH) {
 		update_rq_clock(rq);
 		/*
 		 * Update run-time statistics of the 'current'.

@@ -1293,6 +1297,11 @@
 {
 	s64 gran, vdiff = curr->vruntime - se->vruntime;
 
+	/* preempt always for multimedia tasks */
+	if (unlikely(task_of(curr)->policy != SCHED_MM &&
+		task_of(se)->policy == SCHED_MM))
+		return 1;
+
 	if (vdiff <= 0)
 		return -1;
 

@@ -1331,9 +1340,25 @@
 	if (unlikely(p->policy == SCHED_BATCH))
 		return;
 
+	/*
+	 * Only non-multimedia tasks can be preempted.
+	 */
+	if (unlikely(p->policy != SCHED_MM && curr->policy == SCHED_MM))
+		return;
+
 	if (!sched_feat(WAKEUP_PREEMPT))
 		return;
 
+	/*
+	 * Preempt non-multimedia tasks with multimedia tasks immediately.
+	 */
+	if (unlikely(p->policy == SCHED_MM && curr->policy != SCHED_MM)) {
+		update_rq_clock(rq);
+		update_curr(cfs_rq);
+		resched_task(curr);
+		return;
+	}
+
 	find_matching_se(&se, &pse);
 
 	while (se) {

Sorry, I don't think this is a viable solution for anything.

This is typically the domain of soft-realtime, and as such would need a realtime scheduling class -- using a proportional class like you did just doesn't make sense for these tasks.

Eventually we'd hope to provide an sporadic task EDF based scheduler with hard and soft realtime capabilities, but until that time, FIFO and RR are the classes to use for anything realtime.

I'm not sure why you think SCHED_FIFO isn't good enough for your applications, could you elaborate on that?

Yes, this is for a soft-realtime usage. Some of the tasks are CPU-intensive while being realtime'ish, like video codecs and some audio processing tasks. These audio processing tasks can have some amount of buffering. The idea behind this patch is to make these tasks overlap with the normal tasks while giving a slightly more responsive scheduling behavior and to favor these multimedia tasks over others.

Another option would be to create another scheduler which could overlap with the normal one, in a way FIFO/RR overlap. After inspecting current scheduler code I thought that this kind of modification and use of the same task tree would be feasible, instead of having it's own run queue.

Yes, this is also what I thought first and I still believe this would also be a good addition. After a bit more thinking I concluded that it might be a bit too hard-realtime'ish for many of the tasks. It would become rather close to running FIFO with flat priority?

...and these tasks are not sporadic, but strictly periodic...

Actually the biggest problem is that many of the developers are not comfortable with using SCHED_FIFO for the purpose... :)
FIFO is unsuitable for video codecs, RR would be better there, but still it would starve rest of the system too much in some cases (it can lose some frames to keep rest of the system responsive).
Some multimedia software is just not implemented in a way that it would be safe to run these at RT-priority (having various too nondeterministic code paths).

- Jussi

I've been running a kernel with the scheduler patch on my x86-64 desktop since Christmas.

Here are some test results... Workload in these tests is mostly starting a browser and rendering a set of reasonably heavy pages which creates CPU load spikes. BKL is a bit of a problem too...

I think this is reasonably good result.

Results for the deskop (x86-64), voluntary preempt enabled (as the proprietary ATI display driver behaves badly with full preempt):

SCHED_OTHER:
maximum latency: 45098.2 µs
average latency: 366.2 µs
missed timer events: 16

SCHED_MM:
maximum latency: 10051.2 µs
average latency: 44.7 µs
missed timer events: 0

SCHED_FIFO:
maximum latency: 720.3 µs
average latency: 23.1 µs
missed timer events: 0

Results for an OMAP3-based platform, preempt enabled:

SCHED_OTHER:
maximum latency: 44.7 ms
average latency: 1.8 ms
missed timer events: 227

SCHED_MM:
maximum latency: 19.2 ms
average latency: 1.1 ms
missed timer events: 23

SCHED_FIFO:
maximum latency: 10.7 ms
average latency: 0.7 ms
missed timer events: 1

Best regards,

- Jussi Laako

Right, so I totally lost this thread in my inbox -- sorry for that.

Not quite so, you can avoid starvation with deadline schedulers, just limit their budget.

Well, that's not my problem is it ;-), just batter them with a clue-stick, no need to fudge the kernel for that.

Right, which is where deadline scheduling would be nice. Once you start running into the budget throttle you know you've got to start dropping frames in order to keep up.

The proposal is for it to start sending SIGXCPU once it starts throttling tasks in order to notify them of missed deadlines etc.

Like said, deadline schedulers can help here. You can even dynamically adjust the parameters -- eg. fall back to half frame rate but double budget or something.

Sure, been doing that already... :)
There's just sort of a huge gap between rt-schedulers and the normal scheduler.

For sure this is nice for certain tasks. I'm not entirely convinced if the average media player or Flash-plugin would or should start using these.

I believe both approaches could co-exist to address different needs. SCHED_MM is for the average software and is in a sense similar to SCHED_BATCH and SCHED_IDLE, just targeting different use cases. Modification is reasonably small and shouldn't have any impact when not used. Deadline scheduler would probably belong to the SCHED_RR/SCHED_FIFO family?

Managing the budget in an average system will be painful. In a completely embedded environment this is of course rather straightforward.

There is never a need for media players to use this.
Media players have time stamps on the displayed frames.
If the timestamp on a frame indicates it has taken too long to decode it, the media player just skips the frame until it reaches frames that have non-expired time stamps. No need for any kernel help here.

This is completely irrelevant. These media players still play audio and sync video to audio. Many of these players are not programmed in a way that it would be safe to run these on SCHED_FIFO. Or the environment these are running in is not safe enough. But still smooth video and audio playback is needed, even in cases when locate database is being rebuilt in the background and possibly other CPU and IO intensive tasks are running. Any skipped frames make the video playback look jumpy, if frames are lost, it should be single frame periodically, not burst of frames at once...

Good everyday normal example is HD video played from Youtube or similar site using Flash plugin inside browser. There can be various background tasks running at the same time, but the video playback should still be smooth. One may want to run thread doing video decoding at significantly lower priority than audio decoding thread in order to maintain overall system responsiveness in cases of high CPU load from the video decoding part. While the audio thread shouldn't starve or miss it's deadline.

Right, and I think the solution to this problem is twofold, 1) application writers should start writing (soft) realtime applications if they want (soft) realtime behaviour -- there's just no way around that.

And 2), the kernel can help by providing a deadline based scheduler, which should make the above easier and less likely to mess up the rest of the system. ie. a deadline scheduled application will not exceed its allotted budget, unlike a FIFO scheduled app.

Hi,

Just to avoid need for reviewing and reworking ~800 klocs of user space code in just gstreamer, here's a second take on patches. This time splitting things into smaller pieces. Attached patch exposes 40 priorities ~ nice values as something accessible through sched_()/pthreads API in order to control priorities of individual threads. Current Linux implementation of SCHED_OTHER is broken in a way, that it exposes only one single priority level - 0. Thus no possibility to properly control priorities of threads through pthread API. This is patch is against 2.6.29.2 and not tested, but builds. I can also send rest of the changes as separate small feature patches as needed. However, before doing any more work I would like to hear opinions on this and especially what is wrong with the code or idea...

Any news on this one?

- Jussi

diff -urN linux-2.6.29.2.orig/include/linux/sched.h linux-2.6.29.2.new/include/linux/sched.h
@@ -38,6 +38,7 @@
 #define SCHED_BATCH		3
 /* SCHED_ISO: reserved but not implemented yet */
 #define SCHED_IDLE		5
+#define SCHED_MM		6
 
 #ifdef __KERNEL__
 

Ingo,

would it be possible to comment on this?

Best Regards,
Artem Bityutskiy (Артём Битюцкий)

Utter lack of time on my side to work on any of the problems there.

As to the patch, I still think its an exceedingly bad idea to create such a horridly ill defined scheduler class. There's nothing that keeps people from stuffing everything in there and either generating DoS issues or still generating bad interactivity.

I certainly don't think the current situation is bad enough to warrant things like that, media on my machines works peachy (*cheer* for XV on R600).

I happen to know that Dario (CC'ed) has been working on a userspace framework to ease the use of writing soft-realtime (soft as in media based applications) in C, mitigating a lot of the risks of using SCHED_FIFO and the like.

Perhaps he's willing to expand on that.

I'm still working on my SCHED_PFAIR stab. Expect an RFC someday soon

pfair is a deadline-driven algorithm that also executes the tasks at a steady rate, minimizing jitter as well as meeting deadlines. This give tasks better expressiveness when it comes to instructing the scheduler how to treat the task. I'll give a more formal intro in the upcoming RFC :)

henrik

Lite patch practically exports nice levels as scheduling priorities in order to make it possible to assign different levels to different threads of the same process.

Naturally pretty much anything works when CPU load is under 25%. When the load on low power embedded system is around 95-100% things get hairier...

"Buy faster CPU" is not always an option...

- Jussi

By the way, here's a good test case for a desktop, preferably UP:
- run something like this in a loop:

	find / -type f -exec grep asd "{}" ";"

- run x11perf * numcpus in a loop
- run glxgears * numcpus
- go to youtube frontpage with a web browser
- start for example "totem" mediaplayer and play full-HD H.264 movie

Does the movie playback and audio go smoothly? Can you play youtube HD videos smoothly?

- Jussi

I don't know about youtube, that flash thing doesn't seem to deliver full hd content, and I'm not sure where to click, but playing a full-hd trailer from the network using vlc seems to work just fine with 4 x11perf and 4 glxgears and that find thing.

There is an occasional stutter, but not much.

Thing is, adding static preemption priories into SCHED_OTHER (which is basically what you propose I think) doesn't really help, I can still load the machine high enough so that there simply isn't time available to decode the frames while maintaining proportional fairness -- no matter how preemptive you get.

This is not acceptable and something to get rid of... VLC probably has quite a bit of buffering for audio, while my use cases are mostly for doing video calls, where the buffering has to be kept reasonably low to not extend conversation latency for the audio too much.

First I would like to discuss possibility of assigning different priorities to different threads of a SCHED_OTHER process. (pthread_setschedparam() etc)

Second the idea is to reach nice compromise between normal SCHED_OTHER and hardcore SCHED_FIFO for application which fall between these two. And sure, the definite idea is that this SCHED_OTHER approach wouldn't be absolute in that sense, but would improve the overall situation.

According to my tests, full patch reduces timing misses 10x while not removing those completely. SCHED_FIFO removes all misses, but is a bit too hardcore for things like running browser-embedded flash plugin...

- Jussi

If all you're trying to do is allow different threads to run at different nice levels, what about extending sys_setpriority() to take a "which" of PRIO_THREAD? We'd probably have to call the syscall directly until/unless libc picks up the new option.

Chris

How would this be mapped to a POSIX standard API? I would like to see something which works straight out with pthread_setschedprio()/pthread_getschedparam(). In order it to work correctly it also needs sys_sched_get_priority_min and sys_sched_get_priority_max.

- Jussi

Well, I'm not sure I can see why, since nor a "SCHED_MM" scheduling policy, nor having priorities for SCHED_OTHER (different from nice levels) is _not_ POSIX compliant, is it?

Dario

<<This happens because I choose it to happen!>> (Raistlin Majere)
----------------------------------------------------------------------
Dario Faggioli, ReTiS Lab, Scuola Superiore Sant'Anna, Pisa  (Italy)

http://blog.linux.it/raistlin / [email protected] /
[email protected]

You'd call sys_setpriority. Actually, you'd probably have to call syscall(__NR_getpriority...) until glibc picks up the new option.

Then for the "which" field, instead of PRIO_PROCESS you would use a new PRIO_THREAD (or PRIO_TASK, whichever makes more sense) which would only set the nice level for the specific thread specified in the "who" field.

Of course, without glibc/pthreads support you would only be able to set the nice level for the current thread since you don't have any way to map from "pthread_t *" to tid. And you wouldn't be able to create new threads with a particular nice level already set. But that argument holds true for a new sched policy as well, because glibc checks the policy internally and only knows about the normal three.

This option extends the "nice" API rather than the static priority API, so all of the above would still have a static priority of 0 for SCHED_OTHER.

Chris

It is still accessible through the normal API. POSIX specifies just a set of standard schedulers and gives OS free choice of defining more. These are still accessible through the same functions. I could modify the patch to not introduce a new policy and to just modify the existing SCHED_OTHER the same way (and AFAIK it would still comply with POSIX), I just wanted to have these separate for the other changes and to keep the old behavior intact.

POSIX just defines API where there is concept of policy(int) and priority(int) and a method to query minimum and maximum priority for given policy. Then it defines base set of policies, but not their priority ranges or such.

Your proposal would need introduction of completely new function...

- Jussi

This is the problem... It has to work this way, otherwise it's pretty useless.

Don't tell that to my system, where also SCHED_IDLE, SCHED_BATCH (which are btw not listed on POSIX either) ...and... SCHED_MM work. It goes directly to kernel which does the checks and fails if it sees fit.

For extending "nice" API, I would first ask for extension in POSIX, and once it's there I could think about implementation.

And still this doesn't solve the second level problem.

- Jussi

By the way, why is SCHED_IDLE and SCHED_BATCH OK, but not SCHED_MM?

Or is it the name? How about SCHED_INTERACTIVE?

- Jussi

Then you're hooped, because glibc checks for scheduler policies it "knows" about.

Really? You can call pthread_attr_setschedpolicy() with a policy of SCHED_MM? On my copy of glibc 2.8 it explicitly checks for FIFO/RR/OTHER and anything else is rejected.

Chris

My copy of 2.9 has that fixed (original one is still broken), because that's also broken for SCHED_IDLE and SCHED_BATCH which have been in the kernel for a while already.

I'm not sure, but I think pthread_setschedparam() and sched_setscheduler() didn't need fixing.

- Jussi