Skip to contentSkip to conversation

new scheduler policy

PATCH In review Nick Piggin 8 participants 23 messages Aug 19, 2003 – Sep 8, 2003

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 new scheduler policy

Hi everyone,

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.

Its against 2.6.0-test3-mm1

Best regards,
Nick

fs/proc/array.c renamed from linux-2.6/fs/proc/array.c +1 -1
diff -Nrup -X dontdiff archs/linux-2.6/fs/proc/array.c linux-2.6/fs/proc/array.c
@@ -162,7 +162,7 @@ static inline char * task_state(struct t
 		"Uid:\t%d\t%d\t%d\t%d\n"
 		"Gid:\t%d\t%d\t%d\t%d\n",
 		get_task_state(p),
-		(p->sleep_avg/1024)*100/(1000000000/1024),
+		p->sleep_avg,
 	       	p->tgid,
 		p->pid, p->pid ? p->real_parent->pid : 0,
 		p->pid && p->ptrace ? p->parent->pid : 0,
include/linux/sched.h renamed from linux-2.6/include/linux/sched.h +6 -3
diff -Nrup -X dontdiff archs/linux-2.6/include/linux/sched.h linux-2.6/include/linux/sched.h
@@ -342,14 +342,17 @@ struct task_struct {
 	struct list_head run_list;
 	prio_array_t *array;
 
+	unsigned long array_sequence;
+	unsigned long timestamp;
+
+	unsigned long sleep_time;
+	unsigned long total_time;
 	unsigned long sleep_avg;
-	long interactive_credit;
-	unsigned long long timestamp;
-	int activated;
 
 	unsigned long policy;
 	cpumask_t cpus_allowed;
 	unsigned int time_slice, first_time_slice;
+	unsigned int used_slice;
 
 	struct list_head tasks;
 	struct list_head ptrace_children;
kernel/sched.c renamed from linux-2.6/kernel/sched.c +127 -360

686 lines not on this page · raw message

#1 lore raw
Quoted 11 lines · Nick Piggin

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).
I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.
Its against 2.6.0-test3-mm1

Say, any chance you could spray out a brief explanation of your new heuristics?

-- wli

#2 lore raw
Quoted 15 lines · William Lee Irwin III
Quoted 12 lines · Nick Piggin

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).
I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.
Its against 2.6.0-test3-mm1

Quoted 3 lines

Say, any chance you could spray out a brief explanation of your new heuristics?

Oh alright. BTW, this one's not for your big boxes yet! It does funny things with timeslices. But they will be (pending free time) made much more dynamic, so it should _hopefully_ context switch even less than the normal scheduler in a compute intensive load.

OK. timeslices: they are now dynamic. Full priority tasks will get 100ms, minimum priority tasks 10ms (this is what needs fixing, but should be OK to test "interactiveness")

interactivity estimator is gone: grep -i interactiv sched.c | wc -l gives 0.

priorities are much the same, although processes are supposed to be able to change priority much more quickly.

backboost is back. that is what (hopefully) prevents X from starving due to the quickly changing priorities thing.

#3 lore raw
Quoted 32 lines · Nick Piggin
Quoted 15 lines · William Lee Irwin III
Quoted 12 lines · Nick Piggin

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).
I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.
Its against 2.6.0-test3-mm1

Quoted 3 lines

Say, any chance you could spray out a brief explanation of your new heuristics?

Oh alright. BTW, this one's not for your big boxes yet! It does funny things with timeslices. But they will be (pending free time) made much more dynamic, so it should _hopefully_ context switch even less than the normal scheduler in a compute intensive load.

OK. timeslices: they are now dynamic. Full priority tasks will get 100ms, minimum priority tasks 10ms (this is what needs fixing, but should be OK to test "interactiveness")

Quoted 8 lines

interactivity estimator is gone: grep -i interactiv sched.c | wc -l gives 0.

priorities are much the same, although processes are supposed to be able to change priority much more quickly.

backboost is back. that is what (hopefully) prevents X from starving due to the quickly changing priorities thing.

And lack of interactivity estimator.

#4 lore raw
Quoted 39 lines · Nick Piggin
Quoted 35 lines · Nick Piggin
Quoted 15 lines · William Lee Irwin III
Quoted 12 lines · Nick Piggin

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).
I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.
Its against 2.6.0-test3-mm1

Quoted 3 lines

Say, any chance you could spray out a brief explanation of your new heuristics?

Oh alright. BTW, this one's not for your big boxes yet! It does funny things with timeslices. But they will be (pending free time) made much more dynamic, so it should _hopefully_ context switch even less than the normal scheduler in a compute intensive load.

OK. timeslices: they are now dynamic. Full priority tasks will get 100ms, minimum priority tasks 10ms (this is what needs fixing, but should be OK to test "interactiveness")

interactivity estimator is gone: grep -i interactiv sched.c | wc -l gives 0.

Quoted 7 lines
Quoted 5 lines

priorities are much the same, although processes are supposed to be able to change priority much more quickly.

backboost is back. that is what (hopefully) prevents X from starving due to the quickly changing priorities thing.

And lack of interactivity estimator.

You forgot to mention fork() splitting its timeslice 2/3 to 1/3 parent to child.

Signature · 1 line
Matt Mackall : http://www.selenic.com : of or relating to the moon
#5 lore raw
Quoted 45 lines · Matt Mackall
Quoted 43 lines · Nick Piggin
Quoted 39 lines · Nick Piggin
Quoted 16 lines · William Lee Irwin III
Quoted 13 lines · Nick Piggin

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).
I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P It still does have a few things that need fixing but I thought I'd get my first hack a bit of exercise.
Its against 2.6.0-test3-mm1

Quoted 4 lines

Say, any chance you could spray out a brief explanation of your new heuristics?

Oh alright. BTW, this one's not for your big boxes yet! It does funny things with timeslices. But they will be (pending free time) made much more dynamic, so it should _hopefully_ context switch even less than the normal scheduler in a compute intensive load.

OK. timeslices: they are now dynamic. Full priority tasks will get 100ms, minimum priority tasks 10ms (this is what needs fixing, but should be OK to test "interactiveness")

interactivity estimator is gone: grep -i interactiv sched.c | wc -l gives 0.

priorities are much the same, although processes are supposed to be able to change priority much more quickly.

Quoted 10 lines
Quoted 5 lines
Quoted 3 lines

backboost is back. that is what (hopefully) prevents X from starving due to the quickly changing priorities thing.

And lack of interactivity estimator.

You forgot to mention fork() splitting its timeslice 2/3 to 1/3 parent to child.

Hmm... did I do that? I don't actually have the code in front of me, but I think the timeslice split is still 50/50 (see fork.c). Its the priority points that go 2/3 to 1/3. Actually its a bit more complex than that even and probably not exactly right...

#6 lore raw
Quoted 8 lines · Nick Piggin
Quoted 5 lines · Matt Mackall

You forgot to mention fork() splitting its timeslice 2/3 to 1/3 parent to child.

Quoted 4 lines

Hmm... did I do that? I don't actually have the code in front of me, but I think the timeslice split is still 50/50 (see fork.c). Its the priority points that go 2/3 to 1/3. Actually its a bit more complex than that even and probably not exactly right...

Actually, it's as you say. The terms sleeptime and timeslice just confused me.

Signature · 1 line
Matt Mackall : http://www.selenic.com : of or relating to the moon
#7 lore raw
In reply to Nick Piggin
Quoted 11 lines · Nick Piggin

Hi everyone,

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

Ok, I took it out for a quick spin...

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender.

(/me wonders what the reports from wine/game folks will be like)

-Mike

#8 lore raw
Quoted 9 lines · Mike Galbraith
Quoted 7 lines · Nick Piggin

Hi everyone,

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).

Quoted 7 lines
Quoted 4 lines

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

Ok, I took it out for a quick spin...

Thanks again.

Quoted 2 lines

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender.

Well, it sounds like a good start, though I'll have to get up to scratch on the array of scheduler badness programs!

I expect throughput to be down in this release due to the timeslice thing. This should be fixable.

I think either there is a bug in my accounting somewhere or I have not quite thought it though properly because priorities don't seem to get distributed well. Also its not using the nanosecond timing stuff (yet). This might help a bit.

Nick

#9 lore raw
Quoted 20 lines · Nick Piggin
Quoted 9 lines · Mike Galbraith
Quoted 7 lines · Nick Piggin

Hi everyone,

As per the latest trend these days, I've done some tinkering with the cpu scheduler. I have gone in the opposite direction of most of the recent stuff and come out with something that can be nearly as good interactivity wise (for me).

Quoted 7 lines
Quoted 4 lines

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

Ok, I took it out for a quick spin...

Quoted 8 lines

Thanks again.

Quoted 2 lines

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender.

Well, it sounds like a good start, though I'll have to get up to scratch on the array of scheduler badness programs!

(looks like a fine start to me. my box [and subjective driver] give it a one thumb up plus change;)

Quoted 7 lines

I expect throughput to be down in this release due to the timeslice thing. This should be fixable.

I think either there is a bug in my accounting somewhere or I have not quite thought it though properly because priorities don't seem to get distributed well. Also its not using the nanosecond timing stuff (yet). This might help a bit.

Hmm. I watched priority distribution (eyeballs, not instrumentation), and it looked "right" to me until the load reached "fairly hefty"... at the point where swap really became a factor, distribution flattened, and the mean priority rose (high). I did see some odd-ball high priority cc1's at the low to moderate end (historically indicator of trouble here), but not much. At what I call moderate load, it behaved well, and looked/felt good.

-Mike

#10 lore raw
In reply to Mike Galbraith
Quoted 4 lines · Mike Galbraith

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once

Quoted 8 lines

swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender.
(/me wonders what the reports from wine/game folks will be like)

Someone else appears to have done some work on the X priority inversion issue who I'd like to drag into this discussion, though there doesn't really appear to be an opportune time.

Haoqiang, any chance you could describe your solutions to the X priority inversion issue?

-- wli

#19 lore raw
In reply to Nick Piggin
Quoted 4 lines · Nick Piggin

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

I timed a pathological benchmark from hell I've been playing with lately. Three consecutive runs following a fresh boot. Time is in seconds:

2.4.21 821 21 25
2.6.0-test3-mm1 724 946 896
2.6.0-test3-mm1-nick 905 987 997

Runtime with ideal scheduling: < 2 seconds (we're thrashing).

If anybody has thrashing test cases closer to the real world, I'd be very interested to learn about them.

Roger

#20 lore raw
Quoted 10 lines · Roger Luethi
Quoted 6 lines · Nick Piggin

I haven't run many tests on it - my mind blanked when I tried to remember the scores of scheduler "exploits" thrown around. So if anyone would like to suggest some, or better still, run some, please do so. And be nice, this isn't my type of scheduler :P

Quoted 10 lines

I timed a pathological benchmark from hell I've been playing with lately. Three consecutive runs following a fresh boot. Time is in seconds:

2.4.21 821 21 25
2.6.0-test3-mm1 724 946 896
2.6.0-test3-mm1-nick 905 987 997

Runtime with ideal scheduling: < 2 seconds (we're thrashing).

Cool. Can you post the benchmark source please?

#21 lore raw
Quoted 11 lines · Nick Piggin
Quoted 9 lines

I timed a pathological benchmark from hell I've been playing with lately. Three consecutive runs following a fresh boot. Time is in seconds:

2.4.21 821 21 25
2.6.0-test3-mm1 724 946 896
2.6.0-test3-mm1-nick 905 987 997

Runtime with ideal scheduling: < 2 seconds (we're thrashing).

Cool. Can you post the benchmark source please?

http://hellgate.ch/code/ploc/thrash.c

A parallel kernel build can generate some decent thrashing, too, but I wanted a short and simple test case that conveniently provides the information I need for both logging daemon and post processing tool.

Note: The benchmark could trivially be made more evil which would prevent 2.4.21 from finishing over 30 times faster (as it often does). I intentionally left it they way it is.

While everybody seems to be working on interactivity, I am currently looking at this corner case. This should be pretty much orthogonal to your own work.

Roger

#22 lore raw
Quoted 21 lines · Roger Luethi
Quoted 12 lines · Nick Piggin
Quoted 10 lines

I timed a pathological benchmark from hell I've been playing with lately. Three consecutive runs following a fresh boot. Time is in seconds:

2.4.21 821 21 25
2.6.0-test3-mm1 724 946 896
2.6.0-test3-mm1-nick 905 987 997

Runtime with ideal scheduling: < 2 seconds (we're thrashing).

Cool. Can you post the benchmark source please?

http://hellgate.ch/code/ploc/thrash.c

A parallel kernel build can generate some decent thrashing, too, but I wanted a short and simple test case that conveniently provides the information I need for both logging daemon and post processing tool.

Quoted 8 lines

Note: The benchmark could trivially be made more evil which would prevent 2.4.21 from finishing over 30 times faster (as it often does). I intentionally left it they way it is.

While everybody seems to be working on interactivity, I am currently looking at this corner case. This should be pretty much orthogonal to your own work.

Yes, improvements for this problem are usually in the form of a secondary scheduler of sorts somewhere in the VM. Hard problem.

#11 lore raw
In reply to William Lee Irwin III
Quoted 12 lines · William Lee Irwin III
Quoted 4 lines · Mike Galbraith

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender. (/me wonders what the reports from wine/game folks will be like)

Someone else appears to have done some work on the X priority inversion issue who I'd like to drag into this discussion, though there doesn't really appear to be an opportune time.

Quoted 7 lines

Haoqiang, any chance you could describe your solutions to the X priority inversion issue?

-- wli

I didn't follow the whole discussion. But from what wli has described to me, the problem (xmms skips frames) is pretty like a X scheduler problem.

X server works like this:
"The X server uses select(2) to detect clients with pending input. Once the set of clients with pending input is determined, the X server starts executing requests from the client with the smallest file descriptor. Each client has a buffer which is used to read some data from the network connection, that buffer can be resized to hold unusually large requests, but is typically 4KB. Requests are executed from each client until either the buffer is exhausted of complete requests or after ten requests. After requests are read from all of the ready clients, the server determines whether any clients still have complete requests in their buffers. If so, the server foregoes the select(2) call and goes back to processing requests for those clients. When all client input buffers are exhausted of complete requests, the X server returns to select(2) to await additional data. " --- Keith Packard, "Efficiently Scheduling {X} Clients", FREENIX-00,

Basically, the X server does a round robin for all the clients with pending input. It's not surprising that xmms skip frames when there are a lot of "heavy" x requests pending. I am not sure if this the cause of the problem that you guys are talking about. But anyway, if this the cause, here is my 2 cents:

I think the scheduler of X server has to be "smarter". It has to know which X client is more "important" and give the important client a high priority, otherwise the priority inversion problem will be un-avoidable. Suppose the system can provide something like "get_most_important_client()" , the X server can be fixed this way:
The X server calls get_most_important_client() before it starts to handle an X request. If the return is not NULL, it handles the request from this "important" client. This way, an "important" x client only need to wait a maximun of a single X request (instead of unlimited number of X requests) to get served.

The problem now is how can we decide which X client is the most important? Well, I guess there are a lot of solutions. I have a kernel based solution to this question. The basic idea is: keep the processes blocked by X server in the runqueue. If a certain process (P) of this kind is scheduled, the kernel switch to the X server instead. If the X server get scheduled in this way, it can handle the X requests from this very process (P). If you have interest, you can take a look at http://www.ncl.cs.columbia.edu/publications/cucs-005-03.pdf .

Let me know your comments...

#12 lore raw
Quoted 27 lines · Haoqiang Zheng
Quoted 12 lines · William Lee Irwin III
Quoted 3 lines · Mike Galbraith

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender. (/me wonders what the reports from wine/game folks will be like)

Someone else appears to have done some work on the X priority inversion issue who I'd like to drag into this discussion, though there doesn't really appear to be an opportune time.

Quoted 7 lines

Haoqiang, any chance you could describe your solutions to the X priority inversion issue?

-- wli

I didn't follow the whole discussion. But from what wli has described to me, the problem (xmms skips frames) is pretty like a X scheduler problem.

X server works like this:
"The X server uses select(2) to detect clients with pending input. Once the set of clients with pending input is determined, the X server starts executing requests from the client with the smallest file descriptor. Each client has a buffer which is used to read some data from the network connection, that buffer can be resized to hold unusually large requests, but is typically 4KB. Requests are executed from each client until either the buffer is exhausted of complete requests or after ten requests. After requests are read from all of the ready clients, the server determines whether any clients still have complete requests in their buffers. If so, the server foregoes the select(2) call and goes back to processing requests for those clients. When all client input buffers are exhausted of complete requests, the X server returns to select(2) to await additional data. " --- Keith Packard, "Efficiently Scheduling {X} Clients", FREENIX-00,

Quoted 8 lines

Basically, the X server does a round robin for all the clients with pending input. It's not surprising that xmms skip frames when there are a lot of "heavy" x requests pending. I am not sure if this the cause of the problem that you guys are talking about. But anyway, if this the cause, here is my 2 cents:

I think the scheduler of X server has to be "smarter". It has to know which X client is more "important" and give the important client a high priority, otherwise the priority inversion problem will be un-avoidable. Suppose the system can provide something like "get_most_important_client()" , the X server can be fixed this way:
The X server calls get_most_important_client() before it starts to handle an X request. If the return is not NULL, it handles the request from this "important" client. This way, an "important" x client only need to wait a maximun of a single X request (instead of unlimited number of X requests) to get served.

The problem now is how can we decide which X client is the most important? Well, I guess there are a lot of solutions. I have a kernel based solution to this question. The basic idea is: keep the processes blocked by X server in the runqueue. If a certain process (P) of this kind is scheduled, the kernel switch to the X server instead. If the X server get scheduled in this way, it can handle the X requests from this very process (P). If you have interest, you can take a look at http://www.ncl.cs.columbia.edu/publications/cucs-005-03.pdf .

Let me know your comments...

Very interesting. I think X could be smarter about scheduling maybe quite easily by maintaining a bit more state, say a simple dynamic priority thing, just to keep heavy users from flooding out the occasional users. But AFAIK, the X club is pretty exclusive, and you would need an inside contact to get anything done.

There are still regressions in the CPU scheduler though.

Your last point didn't make sense to me. A client still needs to get CPU time. I guess I should look at the paper. Having to teach the scheduler about X doesn't sit well with me. I think the best you could hope for there _might_ be a config option _if_ you could show some significant improvements not attainable by modifying either X or the kernel in a more generic manner.

#13 lore raw
Quoted 50 lines · Nick Piggin
Quoted 28 lines · Haoqiang Zheng
Quoted 13 lines · William Lee Irwin III
Quoted 3 lines · Mike Galbraith

Test-starve.c starvation is back (curable via other means), but irman2 is utterly harmless. Responsiveness under load is very nice until I get to the "very hefty" end of the spectrum (expected). Throughput is down a bit at make -j30, and there are many cc1's running at very high priority once swap becomes moderately busy. OTOH, concurrency for the make -jN in general appears to be up a bit. X is pretty choppy when moving windows around, but that _appears_ to be the newer/tamer backboost bleeding a kdeinit thread a bit too dry. (I think it'll be easy to correct, will let you know if what I have in mind to test that theory works out). Ending on a decidedly positive note, I can no longer reproduce priority inversion troubles with xmms's gl thread, nor with blender. (/me wonders what the reports from wine/game folks will be like)

Someone else appears to have done some work on the X priority inversion issue who I'd like to drag into this discussion, though there doesn't really appear to be an opportune time.

Quoted 7 lines

Haoqiang, any chance you could describe your solutions to the X priority inversion issue?

-- wli

I didn't follow the whole discussion. But from what wli has described to me, the problem (xmms skips frames) is pretty like a X scheduler problem.

X server works like this:
"The X server uses select(2) to detect clients with pending input. Once the set of clients with pending input is determined, the X server starts executing requests from the client with the smallest file descriptor. Each client has a buffer which is used to read some data from the network connection, that buffer can be resized to hold unusually large requests, but is typically 4KB. Requests are executed from each client until either the buffer is exhausted of complete requests or after ten requests. After requests are read from all of the ready clients, the server determines whether any clients still have complete requests in their buffers. If so, the server foregoes the select(2) call and goes back to processing requests for those clients. When all client input buffers are exhausted of complete requests, the X server returns to select(2) to await additional data. " --- Keith Packard, "Efficiently Scheduling {X} Clients", FREENIX-00,

Quoted 8 lines

Basically, the X server does a round robin for all the clients with pending input. It's not surprising that xmms skip frames when there are a lot of "heavy" x requests pending. I am not sure if this the cause of the problem that you guys are talking about. But anyway, if this the cause, here is my 2 cents:

I think the scheduler of X server has to be "smarter". It has to know which X client is more "important" and give the important client a high priority, otherwise the priority inversion problem will be un-avoidable. Suppose the system can provide something like "get_most_important_client()" , the X server can be fixed this way:
The X server calls get_most_important_client() before it starts to handle an X request. If the return is not NULL, it handles the request from this "important" client. This way, an "important" x client only need to wait a maximun of a single X request (instead of unlimited number of X requests) to get served.

The problem now is how can we decide which X client is the most important? Well, I guess there are a lot of solutions. I have a kernel based solution to this question. The basic idea is: keep the processes blocked by X server in the runqueue. If a certain process (P) of this kind is scheduled, the kernel switch to the X server instead. If the X server get scheduled in this way, it can handle the X requests from this very process (P). If you have interest, you can take a look at http://www.ncl.cs.columbia.edu/publications/cucs-005-03.pdf .

Let me know your comments...

Very interesting. I think X could be smarter about scheduling maybe quite easily by maintaining a bit more state, say a simple dynamic priority thing, just to keep heavy users from flooding out the occasional users. But AFAIK, the X club is pretty exclusive, and you would need an inside contact to get anything done.

Quoted 9 lines

There are still regressions in the CPU scheduler though.

Your last point didn't make sense to me. A client still needs to get CPU time. I guess I should look at the paper. Having to teach the scheduler about X doesn't sit well with me. I think the best you could hope for there _might_ be a config option _if_ you could show some significant improvements not attainable by modifying either X or the kernel in a more generic manner.

Yes, this is exactly what Keith Packard did in this paper: http://keithp.com/~keithp/talks/usenix2000/smart.html . The X scheduler is certainly "smarter" by giving a higher priority to more interactive X clients. But I think guessing the importance of a client by the X server itself is flawed because the X server doesn't have a whole picture of the system. For example, it doesn't know anything about the "nice" value of a process. I think the kernel is in the best position to decide which process is more important. That's why I proposed kernel based approach.

Quoted 8 lines

Your last point didn't make sense to me. A client still needs to get CPU time. I guess I should look at the paper. Having to teach the scheduler about X doesn't sit well with me. I think the best you could hope for there _might_ be a config option _if_ you could show some significant improvements not attainable by modifying either X or the kernel in a more generic manner.

My paper is about solving the priority inversion problem in general, not specific to the X server. But it can be used in this case.

-- Haoqiang

#14 lore raw

Hi!

Quoted 7 lines
Quoted 7 lines

about X doesn't sit well with me. I think the best you could hope for there
_might_ be a config option _if_ you could show some significant improvements not attainable by modifying either X or the kernel in a more
generic manner.

Quoted 9 lines

Yes, this is exactly what Keith Packard did in this paper:
http://keithp.com/~keithp/talks/usenix2000/smart.html . The X scheduler is certainly "smarter" by giving a higher priority to more interactive X clients. But I think guessing the importance of a client by the X server itself is flawed because the X server doesn't have a whole picture of the system. For example, it doesn't know anything about the "nice" value of a process. I think the kernel is in the best position to decide which process is more important. That's why I proposed kernel based approach.

Tasks can easily report their interactivity needs/nice value. X are already depend on clients not trying to screw each other, so thats okay.

Signature · 2 lines
				Pavel
Written on sharp zaurus, because my Velo1 broke. If you have Velo you don't need...
#15 lore raw
Quoted 6 lines · Pavel Machek
Quoted 2 lines

in the best position to decide which process is more important. That's why I proposed kernel based approach.

Tasks can easily report their interactivity needs/nice value. X are already depend on clients not trying to screw each other, so thats okay.

There is a slight problem with a kernel based approach too - the app may be remote.

Alan

#16 lore raw

How do you define "priority inversion" if the app is remote?

Quoted 18 lines · Alan Cox
Quoted 8 lines · Pavel Machek
Quoted 3 lines

in the best position to decide which process is more important. That's why I proposed kernel based approach.

Tasks can easily report their interactivity needs/nice value. X are already depend on clients not trying to screw each other, so thats okay.

There is a slight problem with a kernel based approach too - the app may be remote.

Alan

#17 lore raw
Quoted 1 line · Haoqiang Zheng

How do you define "priority inversion" if the app is remote?

You have to know the dependancies for the entire system, its nearly impossible to do. Once you have the apps also waiting for each other and for direct communications (eg via a database or a shared service) life gets fun.

For local apps one thing that has been suggested and some microkernels have played with is a syscall that basically is "send this message and donate the rest of my timeslice to.."

#18 lore raw
Quoted 6 lines · Alan Cox

You have to know the dependancies for the entire system, its nearly impossible to do. Once you have the apps also waiting for each other and for direct communications (eg via a database or a shared service) life gets fun.

If we assume the priority of a remote process is the same as its local priority (local p->prio), I think something can still be done.
Let's make up an example first. Assume we have two machines A and B. P1 runs at machine A while P2,P3 run at machine B. P2 is the database server. In this case, I think the priority inversion problem can be solved iff:
1. P2 (the database server) handles requests according to the clients priority.
2. P2 inherits the priority of its current client (client with the highest priority).

Quoted 6 lines

For local apps one thing that has been suggested and some microkernels have played with is a syscall that basically is "send this message and donate the rest of my timeslice to.."

In the additional syscall based approach, the applications have to be re-written and the application developers have to know exactly where the timeslice should be denoted to. This is not usually feasible. On the other hand, everything is done automatically and transparently in the approach I suggested.