[RFC][PATCH] Multimedia scheduling class

[RFC][PATCH] Multimedia scheduling class

[Jussi Laako]

[-- Attachment #1: Type: text/plain, Size: 770 bytes --]

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

[-- Attachment #2: sched-mm4.patch --]
[-- Type: text/x-patch, Size: 7240 bytes --]

diff -ur linux-2.6.27.7-9.orig/include/linux/sched.h linux-2.6.27.7-9.new/include/linux/sched.h
--- linux-2.6.27.7-9.orig/include/linux/sched.h	2008-12-05 03:48:08.000000000 +0200
+++ linux-2.6.27.7-9.new/include/linux/sched.h	2008-12-22 15:04:26.000000000 +0200
@@ -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.c linux-2.6.27.7-9.new/kernel/sched.c
--- linux-2.6.27.7-9.orig/kernel/sched.c	2008-12-05 03:48:08.000000000 +0200
+++ linux-2.6.27.7-9.new/kernel/sched.c	2008-12-29 17:32:20.000000000 +0200
@@ -24,6 +24,7 @@
  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
  *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
  *              Thomas Gleixner, Mike Kravetz
+ *  2008-12-22  Multimedia scheduling class by Jussi Laako.
  */
 
 #include <linux/mm.h>
@@ -97,6 +98,14 @@
 #define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
 
 /*
+ * User definable priorities for SCHED_MM.
+ */
+#define MM_PRIO_MIN		0
+#define MM_PRIO_MAX		39
+#define INV_MM_PRIO(p)		(39-(p))
+#define STATIC_PRIO(p)		((p)+MAX_RT_PRIO)
+
+/*
  * Helpers for converting nanosecond timing to jiffy resolution
  */
 #define NS_TO_JIFFIES(TIME)	((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
@@ -150,6 +159,18 @@
 	return rt_policy(p->policy);
 }
 
+static inline int mm_policy(int policy)
+{
+	if (unlikely(policy == SCHED_MM))
+		return 1;
+	return 0;
+}
+
+static inline int task_has_mm_policy(struct task_struct *p)
+{
+	return mm_policy(p->policy);
+}
+
 /*
  * This is the priority-queue data structure of the RT scheduling class:
  */
@@ -1629,8 +1650,17 @@
 		return;
 	}
 
-	p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
-	p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
+	if (!task_has_mm_policy(p)) {
+		p->se.load.weight =
+			prio_to_weight[p->static_prio - MAX_RT_PRIO];
+		p->se.load.inv_weight =
+			prio_to_wmult[p->static_prio - MAX_RT_PRIO];
+	} else {
+		p->se.load.weight =
+			prio_to_weight[p->static_prio - MAX_RT_PRIO] << 1;
+		p->se.load.inv_weight =
+			prio_to_wmult[p->static_prio - MAX_RT_PRIO] >> 1;
+	}
 }
 
 static void update_avg(u64 *avg, u64 sample)
@@ -1680,6 +1710,8 @@
 
 	if (task_has_rt_policy(p))
 		prio = MAX_RT_PRIO-1 - p->rt_priority;
+	/*else if (task_has_mm_policy(p))
+		prio = MAX_RT_PRIO;*/
 	else
 		prio = __normal_prio(p);
 	return prio;
@@ -4919,7 +4951,13 @@
 	if (on_rq)
 		dequeue_task(rq, p, 0);
 
-	p->static_prio = NICE_TO_PRIO(nice);
+	/*
+	 * No nice for SCHED_MM, always max priority (nice -20).
+	 */
+	if (task_has_mm_policy(p))
+		p->static_prio = MAX_RT_PRIO;
+	else
+		p->static_prio = NICE_TO_PRIO(nice);
 	set_load_weight(p);
 	old_prio = p->prio;
 	p->prio = effective_prio(p);
@@ -5056,6 +5094,7 @@
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
+	case SCHED_MM:
 		p->sched_class = &fair_sched_class;
 		break;
 	case SCHED_FIFO:
@@ -5066,6 +5105,9 @@
 
 	p->rt_priority = prio;
 	p->normal_prio = normal_prio(p);
+	/* SCHED_MM is always at highest normal priority */
+	if (p->policy == SCHED_MM)
+		p->static_prio = prio;
 	/* we are holding p->pi_lock already */
 	p->prio = rt_mutex_getprio(p);
 	set_load_weight(p);
@@ -5087,19 +5129,26 @@
 		policy = oldpolicy = p->policy;
 	else if (policy != SCHED_FIFO && policy != SCHED_RR &&
 			policy != SCHED_NORMAL && policy != SCHED_BATCH &&
-			policy != SCHED_IDLE)
+			policy != SCHED_IDLE && policy != SCHED_MM)
 		return -EINVAL;
 	/*
 	 * Valid priorities for SCHED_FIFO and SCHED_RR are
 	 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
 	 * SCHED_BATCH and SCHED_IDLE is 0.
+	 * SCHED_MM has valid range from MM_PRIO_MIN to MM_PRIO_MAX.
 	 */
-	if (param->sched_priority < 0 ||
-	    (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
-	    (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
-		return -EINVAL;
-	if (rt_policy(policy) != (param->sched_priority != 0))
-		return -EINVAL;
+	if (mm_policy(policy)) {
+		if (param->sched_priority < MM_PRIO_MIN ||
+		    param->sched_priority > MM_PRIO_MAX)
+			return -EINVAL;
+	} else {
+		if (param->sched_priority < 0 ||
+		    (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
+		    (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
+			return -EINVAL;
+		if (rt_policy(policy) != (param->sched_priority != 0))
+			return -EINVAL;
+	}
 
 	/*
 	 * Allow unprivileged RT tasks to decrease priority:
@@ -5176,7 +5225,11 @@
 		p->sched_class->put_prev_task(rq, p);
 
 	oldprio = p->prio;
-	__setscheduler(rq, p, policy, param->sched_priority);
+	if (mm_policy(policy))
+		__setscheduler(rq, p, policy,
+			STATIC_PRIO(INV_MM_PRIO(param->sched_priority)));
+	else
+		__setscheduler(rq, p, policy, param->sched_priority);
 
 	if (running)
 		p->sched_class->set_curr_task(rq);
@@ -5321,7 +5374,10 @@
 	if (retval)
 		goto out_unlock;
 
-	lp.sched_priority = p->rt_priority;
+	if (task_has_mm_policy(p))
+		lp.sched_priority = INV_MM_PRIO(USER_PRIO(p->static_prio));
+	else
+		lp.sched_priority = p->rt_priority;
 	read_unlock(&tasklist_lock);
 
 	/*
@@ -5630,6 +5686,9 @@
 	case SCHED_RR:
 		ret = MAX_USER_RT_PRIO-1;
 		break;
+	case SCHED_MM:
+		ret = MM_PRIO_MAX;
+		break;
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
@@ -5655,6 +5714,9 @@
 	case SCHED_RR:
 		ret = 1;
 		break;
+	case SCHED_MM:
+		ret = MM_PRIO_MIN;
+		break;
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
diff -ur linux-2.6.27.7-9.orig/kernel/sched_fair.c linux-2.6.27.7-9.new/kernel/sched_fair.c
--- linux-2.6.27.7-9.orig/kernel/sched_fair.c	2008-12-05 03:48:04.000000000 +0200
+++ linux-2.6.27.7-9.new/kernel/sched_fair.c	2008-12-23 09:50:23.000000000 +0200
@@ -18,6 +18,9 @@
  *
  *  Adaptive scheduling granularity, math enhancements by Peter Zijlstra
  *  Copyright (C) 2007 Red Hat, Inc., Peter Zijlstra <pzijlstr@redhat.com>
+ *
+ *  Multimedia scheduling by Jussi Laako
+ *  Copyright (C) 2008 Nokia Corporation, Jussi Laako <jussi.laako@nokia.com>
  */
 
 #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) {

Re: [RFC][PATCH] Multimedia scheduling class

[Peter Zijlstra]

On Mon, 2008-12-29 at 20:40 +0200, Jussi Laako wrote:
> 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...

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?

Re: [RFC][PATCH] Multimedia scheduling class

[Jussi Laako]

Peter Zijlstra wrote:
> 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.

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.

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

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

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

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

Re: [RFC][PATCH] Multimedia scheduling class

[Jussi Laako]

Jussi Laako wrote:
> 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.

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

Re: [RFC][PATCH] Multimedia scheduling class

[Peter Zijlstra]

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

On Tue, 2008-12-30 at 10:39 +0200, Jussi Laako wrote:

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

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

> ....and these tasks are not sporadic, but strictly periodic...
> 
> > I'm not sure why you think SCHED_FIFO isn't good enough for your
> > applications, could you elaborate on that?
> 
> Actually the biggest problem is that many of the developers are not
> comfortable with using SCHED_FIFO for the purpose... :)

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

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

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.

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

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.

Re: [RFC][PATCH] Multimedia scheduling class

[Jussi Laako]

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

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

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

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?

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

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

Re: [RFC][PATCH] Multimedia scheduling class

[James Courtier-Dutton]

Jussi Laako wrote:
> Peter Zijlstra wrote:
>> Well, that's not my problem is it ;-), just batter them with a
>> clue-stick, no need to fudge the kernel for that.
> 
> Sure, been doing that already... :)
> There's just sort of a huge gap between rt-schedulers and the normal
> scheduler.
> 
>> 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.
> 
> 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.
> 

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.

Re: [RFC][PATCH] Multimedia scheduling class

[Jussi Laako]

James Courtier-Dutton wrote:
>> 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.
> 
> 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.

Re: [RFC][PATCH] Multimedia scheduling class

[Peter Zijlstra]

On Mon, 2009-01-26 at 01:09 +0200, Jussi Laako wrote:
> James Courtier-Dutton wrote:
> >> 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.
> > 
> > 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.

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

[-- Attachment #1: Type: text/plain, Size: 1349 bytes --]

Hi,

Peter Zijlstra wrote:
> 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.

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

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

Any news on this one?


	- Jussi

[-- Attachment #2: sched-tiny.patch --]
[-- Type: text/x-patch, Size: 4358 bytes --]

diff -urN linux-2.6.29.2.orig/include/linux/sched.h linux-2.6.29.2.new/include/linux/sched.h
--- linux-2.6.29.2.orig/include/linux/sched.h	2009-04-27 20:37:11.000000000 +0300
+++ linux-2.6.29.2.new/include/linux/sched.h	2009-05-11 11:02:26.000000000 +0300
@@ -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 -urN linux-2.6.29.2.orig/kernel/sched.c linux-2.6.29.2.new/kernel/sched.c
--- linux-2.6.29.2.orig/kernel/sched.c	2009-04-27 20:37:11.000000000 +0300
+++ linux-2.6.29.2.new/kernel/sched.c	2009-05-11 11:02:26.000000000 +0300
@@ -24,6 +24,7 @@
  *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri
  *  2007-11-29  RT balancing improvements by Steven Rostedt, Gregory Haskins,
  *              Thomas Gleixner, Mike Kravetz
+ *  2008-12-22  Multimedia scheduling class by Jussi Laako.
  */
 
 #include <linux/mm.h>
@@ -98,6 +99,14 @@
 #define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO))
 
 /*
+ * User definable priorities for SCHED_MM.
+ */
+#define MM_PRIO_MIN		0
+#define MM_PRIO_MAX		39
+#define INV_MM_PRIO(p)		(39-(p))
+#define STATIC_PRIO(p)		((p)+MAX_RT_PRIO)
+
+/*
  * Helpers for converting nanosecond timing to jiffy resolution
  */
 #define NS_TO_JIFFIES(TIME)	((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))
@@ -160,6 +169,18 @@
 	return rt_policy(p->policy);
 }
 
+static inline int mm_policy(int policy)
+{
+	if (unlikely(policy == SCHED_MM))
+		return 1;
+	return 0;
+}
+
+static inline int task_has_mm_policy(struct task_struct *p)
+{
+	return mm_policy(p->policy);
+}
+
 /*
  * This is the priority-queue data structure of the RT scheduling class:
  */
@@ -5282,6 +5303,7 @@
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
+	case SCHED_MM:
 		p->sched_class = &fair_sched_class;
 		break;
 	case SCHED_FIFO:
@@ -5292,6 +5314,8 @@
 
 	p->rt_priority = prio;
 	p->normal_prio = normal_prio(p);
+	if (task_has_mm_policy(p))
+		p->static_prio = prio;
 	/* we are holding p->pi_lock already */
 	p->prio = rt_mutex_getprio(p);
 	set_load_weight(p);
@@ -5329,19 +5353,26 @@
 		policy = oldpolicy = p->policy;
 	else if (policy != SCHED_FIFO && policy != SCHED_RR &&
 			policy != SCHED_NORMAL && policy != SCHED_BATCH &&
-			policy != SCHED_IDLE)
+			policy != SCHED_IDLE && policy != SCHED_MM)
 		return -EINVAL;
 	/*
 	 * Valid priorities for SCHED_FIFO and SCHED_RR are
 	 * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
 	 * SCHED_BATCH and SCHED_IDLE is 0.
+	 * SCHED_MM has valid range from MM_PRIO_MIN to MM_PRIO_MAX.
 	 */
-	if (param->sched_priority < 0 ||
-	    (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
-	    (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
-		return -EINVAL;
-	if (rt_policy(policy) != (param->sched_priority != 0))
-		return -EINVAL;
+	if (mm_policy(policy)) {
+		if (param->sched_priority < MM_PRIO_MIN ||
+		    param->sched_priority > MM_PRIO_MAX)
+			return -EINVAL;
+	} else {
+		if (param->sched_priority < 0 ||
+		    (p->mm && param->sched_priority > MAX_USER_RT_PRIO-1) ||
+		    (!p->mm && param->sched_priority > MAX_RT_PRIO-1))
+			return -EINVAL;
+		if (rt_policy(policy) != (param->sched_priority != 0))
+			return -EINVAL;
+	}
 
 	/*
 	 * Allow unprivileged RT tasks to decrease priority:
@@ -5418,7 +5449,11 @@
 		p->sched_class->put_prev_task(rq, p);
 
 	oldprio = p->prio;
-	__setscheduler(rq, p, policy, param->sched_priority);
+	if (mm_policy(policy))
+		__setscheduler(rq, p, policy,
+			STATIC_PRIO(INV_MM_PRIO(param->sched_priority)));
+	else
+		__setscheduler(rq, p, policy, param->sched_priority);
 
 	if (running)
 		p->sched_class->set_curr_task(rq);
@@ -5563,7 +5598,10 @@
 	if (retval)
 		goto out_unlock;
 
-	lp.sched_priority = p->rt_priority;
+	if (task_has_mm_policy(p))
+		lp.sched_priority = INV_MM_PRIO(USER_PRIO(p->static_prio));
+	else
+		lp.sched_priority = p->rt_priority;
 	read_unlock(&tasklist_lock);
 
 	/*
@@ -5890,6 +5928,9 @@
 	case SCHED_RR:
 		ret = MAX_USER_RT_PRIO-1;
 		break;
+	case SCHED_MM:
+		ret = MM_PRIO_MAX;
+		break;
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
@@ -5915,10 +5956,14 @@
 	case SCHED_RR:
 		ret = 1;
 		break;
+	case SCHED_MM:
+		ret = MM_PRIO_MIN;
+		break;
 	case SCHED_NORMAL:
 	case SCHED_BATCH:
 	case SCHED_IDLE:
 		ret = 0;
+		break;
 	}
 	return ret;
 }

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Artem Bityutskiy]

Jussi Laako wrote:
> Peter Zijlstra wrote:
>> 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.
> 
> 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...

Ingo,

would it be possible to comment on this?

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Peter Zijlstra]

On Mon, 2009-05-11 at 11:22 +0300, Jussi Laako wrote:
> Hi,
> 
> Peter Zijlstra wrote:
> > 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.
> 
> 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...
> 
> > 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.
> 
> Any news on this one?

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.

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Henrik Austad]

[-- Attachment #1: Type: text/plain, Size: 800 bytes --]

On Mon, May 11, 2009 at 11:22:28AM +0300, Jussi Laako wrote:
> Hi,
> 
> Peter Zijlstra wrote:
> [..]
> > 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.
> 
> Any news on this one?

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


[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Peter Zijlstra wrote:
> 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.

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.

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

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Peter Zijlstra wrote:
> 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).

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Peter Zijlstra]

On Tue, 2009-05-12 at 13:07 +0300, Jussi Laako wrote:
> Peter Zijlstra wrote:
> > 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).
> 
> 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?

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.

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

On Tue, 12 May 2009, Peter Zijlstra wrote:

> There is an occasional stutter, but not much.

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.

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

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Chris Friesen]

Jussi Laako wrote:
> Peter Zijlstra wrote:
> 
>>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.
> 
> 
> 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.

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Chris Friesen wrote:
> 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.

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Raistlin]

[-- Attachment #1: Type: text/plain, Size: 1122 bytes --]

On Tue, 2009-05-12 at 19:34 +0300, Jussi Laako wrote:
> Chris Friesen wrote:
> > 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.
> 
> 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.
> 
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 / raistlin@ekiga.net /
dario.faggioli@jabber.org

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 197 bytes --]

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Chris Friesen]

Jussi Laako wrote:
> Chris Friesen wrote:
> 
>>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.
> 
> 
> How would this be mapped to a POSIX standard API?

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.

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

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Raistlin wrote:
> 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?

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Chris Friesen wrote:
> 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.

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

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

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.

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

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Raistlin wrote:
> 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?

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Chris Friesen]

Jussi Laako wrote:
> Chris Friesen wrote:
> 
>>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.
> 
> 
> This is the problem... It has to work this way, otherwise it's pretty
> useless.

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

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

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

Re: [RFC][PATCH] Multimedia scheduling class, take 2

[Jussi Laako]

Chris Friesen wrote:
> 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.

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