O17int

Food for the starving masses.

This patch prevents any single task from being able to starve the runqueue that it's on. This minimises the impact a poorly behaved application or a malicious one has on the rest of the system. If an

Quoted 5 lines · Con Kolivas

Food for the starving masses.

This patch prevents any single task from being able to starve the runqueue that it's on. This minimises the impact a poorly behaved application or a malicious one has on the rest of the system. If an

I have to disagree. Open a file of a few hundred lines in XEmacs and do a regexp search for "^[> ]*-*\n\\([> ]*.*\n\\)*[> ]*foo". The system will more or less freeze. It's a very nasty regexp, and it's an error to try to use it, but it still shouldn't freeze the system.

Quoted 8 lines

Quoted 3 lines

This patch prevents any single task from being able to starve the runqueue that it's on. This minimises the impact a poorly behaved application or a malicious one has on the rest of the system. If an

I have to disagree. Open a file of a few hundred lines in XEmacs and do a regexp search for "^[> ]*-*\n\\([> ]*.*\n\\)*[> ]*foo". The system will more or less freeze. It's a very nasty regexp, and it's an error to try to use it, but it still shouldn't freeze the system.

Reasonably sure this is a variation on the starvation which O17 won't address.

Please top/vmstat/profile this and I'll look into it. There is potential for starvation without using up full timeslices and this may be it.

Another XEmacs strangeness:

When compiling from xemacs, everything is fine until the compilation is done. Then xemacs starts spinning wildly in some loop doing this:
This goes on for anything from half a second to several seconds. During that time other processes, except X, are starved.

I saw this first with 2.6.0-test1 vanilla, then it went away in -test2 and -test3, only to show up again with O16.3int. My O16.2 kernel seems ok, which seems strange to me since the difference from O16.2 to O16.3 is very small.

Any ideas?

Quoted 5 lines

When compiling from xemacs, everything is fine until the compilation is done. Then xemacs starts spinning wildly in some loop doing this:
This goes on for anything from half a second to several seconds. During that time other processes, except X, are starved.

Quoted 4 lines

I saw this first with 2.6.0-test1 vanilla, then it went away in -test2 and -test3, only to show up again with O16.3int. My O16.2 kernel seems ok, which seems strange to me since the difference from O16.2 to O16.3 is very small.

While being a small patch, 16.2-16.3 was a large change. It removed the very aggressive starvation avoidance of spin on wait waker/wakee in 16.2, which clearly helped your issue.

Quoted 1 line

Any ideas?

Pretty sure we have another spinner. A reniced -11 batch run of top -d 1 and vmstat during the spinning, and a kernel profile for that time will be helpful.

Food for the starving masses.

Quoted 2 lines · Con Kolivas

Food for the starving masses.

snip

Sorry, but I still have the starving problem. the more I use O16/O17 the more problems I encounter. xterms sometimes wake up after half a second for another half a second and falls asleep for a whole second then. after that, it's fully interactive. io-load seems to produce the problem. a simple tar xf linux-2.6.0-test3.tar seems to halt the system. new processes take ages to start. This also happend to me on O16.2. Maybe it's because some AS patches are missing in vanilla but are in 2.6.0-test3-mm?

Quoted 1 line · Con Kolivas

Food for the starving masses.

snip

Sorry, but I still have the starving problem. the more I use O16/O17 the more problems I encounter. xterms sometimes wake up after half a second for another half a second and falls asleep for a whole second then. after that, it's fully interactive. io-load seems to produce the problem. a simple tar xf linux-2.6.0-test3.tar seems to halt the system.

new processes take ages to start. This also happend to me on O16.2.

Maybe it's because some AS patches are missing in vanilla but are in 2.6.0-test3-mm?

Unhappy with this latest O16.3-O17int patch I'm withdrawing it, and recommending nothing on top of O16.3 yet.

More and more it just seems to be a bandaid to the priority inverting spin on waiters, and it does seem to be of detriment to general interacivity. I can now reproduce some loss of interactive feel with O17.

Something specific for the spin on waiters is required that doesn't affect general performance. The fact that I can reproduce the same starvation in vanilla 2.6.0-test3 but to a lesser extent means this is an intrinsic problem that needs a specific solution.

Quoted 7 lines · Con Kolivas

Unhappy with this latest O16.3-O17int patch I'm withdrawing it, and recommending nothing on top of O16.3 yet.

More and more it just seems to be a bandaid to the priority inverting spin on waiters, and it does seem to be of detriment to general interacivity. I can now reproduce some loss of interactive feel with O17.

Quoted 4 lines

Something specific for the spin on waiters is required that doesn't affect general performance. The fact that I can reproduce the same starvation in vanilla 2.6.0-test3 but to a lesser extent means this is an intrinsic problem that needs a specific solution.

I can see only one possible answer to this - never allow a normal task to hold the cpu for long stretches (define) while there are other tasks runnable. (see attachment)

I think the _easiest_ fix for this particular starvation (without tossing baby out with bath water;) is to try to "down-shift" in schedule() when next == prev. This you can do very cheaply with a find_next_bit(). That won't help the case where there are multiple tasks involved, but should fix the most common case for dirt cheap. (another simple alternative is to globally "down-shift" periodically)

The most generally effective form of the "down-shift" anti-starvation tactic that I've tried, is to periodically check the head of all queues below current position (can do very quickly), and actively select the oldest task who hasn't run since some defined deadline. Queues are serviced based upon priority most of the time, and based upon age some of the time.

Everything I've tried along these lines has a common upside: works, and
downside: butt ugly :)

Quoted 13 lines · Mike Galbraith

Quoted 11 lines · Con Kolivas

Unhappy with this latest O16.3-O17int patch I'm withdrawing it, and recommending nothing on top of O16.3 yet.

More and more it just seems to be a bandaid to the priority inverting spin on waiters, and it does seem to be of detriment to general interacivity. I can now reproduce some loss of interactive feel with O17.

Something specific for the spin on waiters is required that doesn't affect general performance. The fact that I can reproduce the same starvation in vanilla 2.6.0-test3 but to a lesser extent means this is an intrinsic problem that needs a specific solution.

Quoted 3 lines

I can see only one possible answer to this - never allow a normal task to hold the cpu for long stretches (define) while there are other tasks runnable. (see attachment)

I assume you mean the strace ? That was the only attachment, and it just looks like shiploads of schedule() from the get time of day. Yes?

Quoted 6 lines

I think the _easiest_ fix for this particular starvation (without tossing baby out with bath water;) is to try to "down-shift" in schedule() when next == prev. This you can do very cheaply with a find_next_bit(). That won't help the case where there are multiple tasks involved, but should fix the most common case for dirt cheap. (another simple alternative is to globally "down-shift" periodically)

Err funny you should say that; that's what O17 did. But it hurt because it would never allow a task that used a full timeslice to be next==prev. The

less I throttled that, the less effective the antistarvation was. However
this is clearly a problem without using up full timeslices. I originally thought they weren't trying to schedule lots because of the drop in ctx during starvation but I forgot that rescheduling the same task doesnt count as a ctx.

Also I recall that winegames got much better in O10 when everything was
charged at least one jiffy (pre nanosecond timing) suggesting those that were waking up for minute amounts of time repeatedly were being penalised; thus taking out the possibility of the starving task staying high priority for long.

Quoted 6 lines

The most generally effective form of the "down-shift" anti-starvation tactic that I've tried, is to periodically check the head of all queues below current position (can do very quickly), and actively select the oldest task who hasn't run since some defined deadline. Queues are serviced based upon priority most of the time, and based upon age some of the time.

Hmm also sounds fudgy.

Quoted 6 lines

less I throttled that, the less effective the antistarvation was.
However
this is clearly a problem without using up full timeslices. I originally thought they weren't trying to schedule lots because of the drop in ctx during starvation but I forgot that rescheduling the same task doesnt count as a ctx.

Hmm. In what way did it hurt interactivity? I know that if you pass the cpu off to non-gui task who's going to use his full 100 ms slice, you'll definitely feel it. (made workaround, will spare delicate tummies;) If you mean that, say X releases the cpu and has only a couple of ms left on it's slice and is alone in it's queue, that preempting it at the end of it's slice after having only had the cpu for such a short time after wakeup hurts, you can qualify the preempt decision with a cpu possession time check.

Quoted 6 lines

Also I recall that winegames got much better in O10 when everything was
charged at least one jiffy (pre nanosecond timing) suggesting those that were waking up for minute amounts of time repeatedly were being penalised; thus taking out the possibility of the starving task staying high priority for long.

(unsure what you mean here)

I wish I could get mm3 running so I could evaluate those interactivity statements. I can't imagine it being worse than what I'm experiencing now:

That would be compiling the kernel, bunzipping a file, and some cron mandb thing that was running gzip in the background niced. Plus X and Mozilla, which probably starts the problem. At the end there, you see things calm down. That's also the way it starts out, then something sets off the "priority inversion" and the machine becomes completely worthless. Even the task that are running aren't really accomplishing anything. So the load goes from around 4/5 into the teens and the context switching makes a corresponding jump. And then both interactivity AND throughput fall through the floor.

I can't imagine any interactivity regressions that are worse than this behavior...

And this happens with just X and Mozilla running. It happens less often without X running, but still happens. Even if I'm at a VT, it could take 5-6 seconds for my text to appear after I type. This happens all the time, about once every few minutes and correlates with a simultaneous increase in context switches and load.

Can you set a cutoff point where if the process uses less that X percent of the max timeslice, it is penalized? I don't know if it's possible to do a loop of empty spins at some point and time it to find out what the cut-off point should be...otherwise I imagine it would need to be tuned for every processor speed. Could you use the bogomips to gauge the speed of the machine and use that to determine the min timeslice?
From what I understand above, that would perhaps be more selective than
just penalizing every process and have a positive affect on everything...of course I'm open to the possibility that I have it all wrong ;-)

Umm. You didn't mention which kernel/patch? I seem to recall you were using Osomething but which?

If this is Osomething, can you tell me when it started doing this and what vanilla does.

I wish I could get mm3 running so I could evaluate those interactivity statements. I can't imagine it being worse than what I'm experiencing now:

Quoted 8 lines · Mike Galbraith

Quoted 5 lines

less I throttled that, the less effective the antistarvation was. However
this is clearly a problem without using up full timeslices. I originally thought they weren't trying to schedule lots because of the drop in ctx during starvation but I forgot that rescheduling the same task doesnt count as a ctx.

Hmm. In what way did it hurt interactivity? I know that if you pass the cpu off to non-gui task who's going to use his full 100 ms slice, you'll definitely feel it. (made workaround, will spare delicate tummies;) If you mean that, say X releases the cpu and has only a couple of ms left on it's slice and is alone in it's queue, that preempting it at the end of it's slice after having only had the cpu for such a short time after wakeup hurts, you can qualify the preempt decision with a cpu possession time check.

I wish I could get mm3 running so I could evaluate those interactivity statements. I can't imagine it being worse than what I'm experiencing now:

9  0  63968  21992  19672 319056    0    0     0    46 1231   289 87 13
0  0
5  0  63968  21096  19704 320020    0    0     0    26 1202   300 86 14  0  0
14  0  63968  21104  19704 320020    0    0     0     0 1578   385 86 14  0  0
8  0  63968  20448  20152 320048    0    0     7    41 1189   294 91
9  0  0
15  0  63968  19552  20132 321052    0    0     6    76 5926  1330 87 13  0  0
13  0  63968  18992  20132 321664    0    0     0    31 5464  1266 87 13  0  0
11  0  63968  18676  20100 321976    0    0     0    65 4613  1008 87 13  0  0
8  0  63968  18044  20100 322660    0    0     0    14 4643  1132 87 13  0  0
16  0  63968  17660  20100 323024    0    0     0    20 5273  1272 87 13  0  0
14  0  63968  12092  20060 328596    0    0     0    24 5110  1221 87 13  0  0
14  0  63968  11644  20052 329052    0    0     0    68 5264  1285 87 13  0  0
13  0  63968  11324  19924 329560    0    0     0    34 4473  1125 87 13  0  0
16  0  63968  10740  19964 329880    0    0     1    74 1494   445 90 10  0  0
procs -----------memory---------- ---swap-- -----io---- --system-- ----cpu----
r  b   swpd   free  inact active   si   so    bi    bo   in    cs us sy id wa
22  0  63968  10452  19968 330300    0    0     1    51 4584  1059 88 12  0  0
14  0  63968  10004  19940 330736    0    0     0    90 6567  1547 87 13  0  0
15  0  63968   9188  20048 331472    5    0    10   106 5176  1289 87 13  0  0
13  0  63968  13932  20016 326824    6    0     6    26 6026  1318 87 13  0  0
12  0  63968  13412  19984 327324    0    0     0    24 4683  1083 87 13  0  0
13  1  63968  12700  20012 327956    0    0    16    46 5673  1313 87 13  0  0
12  0  63968  12252  20084 328296    0    0     6    78 3499   780 88 12  0  0
18  0  63968  11468  20060 329016    0    0     0    35 5456  1231 87 13  0  0
13  0  63968  12052  20096 328580    0    0     3    96 4430   988 87 13  0  0
13  0  63968   5012  19144 336532    0    0     0    62 5672  1225 88 12  0  0
16  0  63964   6624  17976 336088    0    0     0   297 4808  1041 88 12  0  0
11  0  63964   5616  17964 337124    0    0     0    69 5219  1094 89 11  0  0
16  1  63964   6732  15688 338276   13    0    20   155 4984  1156 87 13  0  0
4  1  63964   7772  12544 340436   13    0    20    11 1070   201 90 10  0  0
3  1  63964   4364  11560 344840    0    0    86   338 1038   250 92
8  0  0

That would be compiling the kernel, bunzipping a file, and some cron mandb thing that was running gzip in the background niced. Plus X and Mozilla, which probably starts the problem. At the end there, you see things calm down. That's also the way it starts out, then something sets off the "priority inversion" and the machine becomes completely worthless. Even the task that are running aren't really accomplishing anything. So the load goes from around 4/5 into the teens and the context switching makes a corresponding jump. And then both interactivity AND throughput fall through the floor.

I can't imagine any interactivity regressions that are worse than this behavior...

And this happens with just X and Mozilla running. It happens less often without X running, but still happens. Even if I'm at a VT, it could take 5-6 seconds for my text to appear after I type. This happens all the time, about once every few minutes and correlates with a simultaneous increase in context switches and load.

Quoted 8 lines

Quoted 5 lines

Also I recall that winegames got much better in O10 when everything was
charged at least one jiffy (pre nanosecond timing) suggesting those that were waking up for minute amounts of time repeatedly were being penalised; thus taking out the possibility of the starving task staying high priority for long.

(unsure what you mean here)

Can you set a cutoff point where if the process uses less that X percent of the max timeslice, it is penalized? I don't know if it's possible
to do a loop of empty spins at some point and time it to find out what the cut-off point should be...otherwise I imagine it would need to be tuned for every processor speed. Could you use the bogomips to gauge the speed of the machine and use that to determine the min timeslice? From what I understand above, that would perhaps be more selective than just penalizing every process and have a positive affect on everything...of course I'm open to the possibility that I have it all wrong ;-)

Wes

Those high interrupt counts are all stalls? What kernel is that?

Quoted 6 lines · Con Kolivas

Quoted 5 lines · Mike Galbraith

Quoted 4 lines · Con Kolivas

Unhappy with this latest O16.3-O17int patch I'm withdrawing it, and recommending nothing on top of O16.3 yet.

More and more it just seems to be a bandaid to the priority inverting

spin

Quoted 1 line

Quoted 1 line

Quoted 1 line

on waiters, and it does seem to be of detriment to general

interacivity.

Quoted 3 lines

Quoted 3 lines

Quoted 3 lines

I can now reproduce some loss of interactive feel with O17.

Something specific for the spin on waiters is required that doesn't

affect

Quoted 1 line

Quoted 1 line

Quoted 1 line

general performance. The fact that I can reproduce the same starvation

in

Quoted 4 lines

Quoted 4 lines

Quoted 2 lines

vanilla 2.6.0-test3 but to a lesser extent means this is an intrinsic problem that needs a specific solution.

I can see only one possible answer to this - never allow a normal task

to

Quoted 6 lines

Quoted 2 lines

hold the cpu for long stretches (define) while there are other tasks runnable. (see attachment)

I assume you mean the strace ? That was the only attachment, and it just looks
like shiploads of schedule() from the get time of day. Yes?

(no, ~2 seconds of X being awol)

Quoted 1 line

Quoted 1 line

I think the _easiest_ fix for this particular starvation (without

tossing

Quoted 2 lines

Quoted 2 lines

baby out with bath water;) is to try to "down-shift" in schedule() when next == prev. This you can do very cheaply with a find_next_bit().

That

Quoted 1 line

Quoted 1 line

won't help the case where there are multiple tasks involved, but should

fix

Quoted 5 lines

Quoted 2 lines

the most common case for dirt cheap. (another simple alternative is to globally "down-shift" periodically)

Err funny you should say that; that's what O17 did. But it hurt because it would never allow a task that used a full timeslice to be next==prev. The

If someone is marked for resched, it means we want to give someone else the cpu right? In this case at least, re-selecting blender is not the right thing to do. Looks like he's burning rubber... going nowhere fast.

Quoted 5 lines

less I throttled that, the less effective the antistarvation was. However
this is clearly a problem without using up full timeslices. I originally thought they weren't trying to schedule lots because of the drop in ctx during starvation but I forgot that rescheduling the same task doesnt count as a ctx.

Hmm. In what way did it hurt interactivity? I know that if you pass the cpu off to non-gui task who's going to use his full 100 ms slice, you'll definitely feel it. (made workaround, will spare delicate tummies;) If

you mean that, say X releases the cpu and has only a couple of ms left on it's slice and is alone in it's queue, that preempting it at the end of it's slice after having only had the cpu for such a short time after wakeup hurts, you can qualify the preempt decision with a cpu possession time check.

Quoted 3 lines

Also I recall that winegames got much better in O10 when everything was
charged at least one jiffy (pre nanosecond timing) suggesting those that

were

Quoted 3 lines

waking up for minute amounts of time repeatedly were being penalised; thus taking out the possibility of the starving task staying high priority for long.

(unsure what you mean here)

Quoted 6 lines

Quoted 6 lines

The most generally effective form of the "down-shift" anti-starvation tactic that I've tried, is to periodically check the head of all queues below current position (can do very quickly), and actively select the oldest task who hasn't run since some defined deadline. Queues are serviced based upon priority most of the time, and based upon age some

of

Quoted 3 lines

Quoted 1 line

the time.

Hmm also sounds fudgy.

Yeah. I crossbred it with a ~deadline scheduler, and created a mutt.

         -Mike (2'6"") 

Quoting Mike Galbraith <[email protected]>:

Quoted 5 lines

Quoted 5 lines

Quoted 5 lines

The most generally effective form of the "down-shift" anti-starvation tactic that I've tried, is to periodically check the head of all queues below current position (can do very quickly), and actively select the oldest task who hasn't run since some defined deadline. Queues are serviced based upon priority most of the time, and based upon age some

Quoted 6 lines

of

Quoted 3 lines

Quoted 1 line

the time.

Hmm also sounds fudgy.

Yeah. I crossbred it with a ~deadline scheduler, and created a mutt.

But how did this mutt perform?

Food for the starving masses.