Skip to contentSkip to conversation

Questions.

SHED Ian Kumlien 9 participants 36 messages Aug 31, 2003 – Sep 4, 2003 2 messages not in the archive

lore
Share & tools
lore
#0 lore raw

Hi,

I'll risk sounding like a moron again =)

I still wonder about the counter intuitive quantum value for processes... (or timeslice if you will)

Why not use small quantum values for high pri processes and long for low pri since the high pri processes will preempt the low pri processes anyways. And for a server working under load with only a few processes (assuming they are all low pri) would lessen the context switches.

And a system with "interactive load" as well would, as i said, preempt the lower pris. But this could also cause a problem... Imho there should be a "min quantum value" so that processes can't preempt a process that was just scheduled (i dunno if this is implemented already though).

Imho this would also make it easy to get the right pri for highpri processes since the quantum value is smaller and if you use it all up you get demoted.

Anyways, I've been wondering about the inverted values in the scheduler and for a mixed load/server load i don't see the benefit... =P

PS. Do not forget to CC me since i'm not on this list... DS.

Signature · 1 line
Ian Kumlien <[email protected]>
#1 lore raw
Quoted 21 lines · Ian Kumlien

Hi,

I'll risk sounding like a moron again =)

I still wonder about the counter intuitive quantum value for processes... (or timeslice if you will)

Why not use small quantum values for high pri processes and long for low pri since the high pri processes will preempt the low pri processes anyways. And for a server working under load with only a few processes (assuming they are all low pri) would lessen the context switches.

And a system with "interactive load" as well would, as i said, preempt the lower pris. But this could also cause a problem... Imho there should be a "min quantum value" so that processes can't preempt a process that was just scheduled (i dunno if this is implemented already though).

Imho this would also make it easy to get the right pri for highpri processes since the quantum value is smaller and if you use it all up you get demoted.

Quoted 6 lines

Anyways, I've been wondering about the inverted values in the scheduler and for a mixed load/server load i don't see the benefit... =P

PS. Do not forget to CC me since i'm not on this list... DS.

Search for "Nick's scheduler policy" ;)

#2 lore raw
Quoted 1 line · Nick Piggin

Search for "Nick's scheduler policy" ;)

Heh, yeah, i have been following your and con's work via marc.theaimsgroup.com. =)

But wouldn't ingos off the shelf stuff work better with the quantum values like that?

And is the preempt min quantum in there?

Signature · 1 line
Ian Kumlien <[email protected]>
#3 lore raw
Quoted 8 lines · Ian Kumlien
Quoted 2 lines · Nick Piggin

Search for "Nick's scheduler policy" ;)

Heh, yeah, i have been following your and con's work via marc.theaimsgroup.com. =)

Well, my patch does almost exactly what you describe.

Quoted 4 lines

But wouldn't ingos off the shelf stuff work better with the quantum values like that?

That means more complexity and behaviour that is more difficult to trace. The interactivity stuff is already a monster to tune.

Quoted 3 lines

And is the preempt min quantum in there?

No. If you do that, you'll either break the priority concept very badly, or you'll break it a little bit and turn the scheduler into an O(n) one.

#4 lore raw
Quoted 6 lines · Nick Piggin
Quoted 1 line · Ian Kumlien
Quoted 6 lines
Quoted 2 lines

And is the preempt min quantum in there?

No. If you do that, you'll either break the priority concept very badly, or you'll break it a little bit and turn the scheduler into an O(n) one.

Well I guess you could just break it a little bit without it being O(n)

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

#7 lore raw

[Forgot to CC LKML last time, so i didn't remove old text ]

Quoted 10 lines · Nick Piggin
Quoted 8 lines · Ian Kumlien
Quoted 7 lines · Nick Piggin
Quoted 6 lines · Ian Kumlien
Quoted 1 line · Nick Piggin

Search for "Nick's scheduler policy" ;)

Heh, yeah, i have been following your and con's work via marc.theaimsgroup.com. =)

Quoted 6 lines
Quoted 3 lines
Quoted 1 line

Well, my patch does almost exactly what you describe.

Yes, i know =)... You and con should team up =)

Heh, well we discuss stuff sometimes, but we disagree on things. Which is a good thing because now our eggs are in two baskets.

Yes, but sometimes it feels like a merger would be better... As long as the propper quantum usage prevails =)

Quoted 9 lines
Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

But wouldn't ingos off the shelf stuff work better with the quantum values like that?

That means more complexity and behaviour that is more difficult to trace. The interactivity stuff is already a monster to tune.

Oh, humm, how much did you change btw? =))

Yeah quite a lot. Lots included removing the interactivity stuff.

Humm, yeah, that should work automatically with the "used the full quantum" if thats still in that is... =)

Quoted 13 lines
Quoted 6 lines
Quoted 5 lines
Quoted 1 line

And is the preempt min quantum in there?

No. If you do that, you'll either break the priority concept very badly, or you'll break it a little bit and turn the scheduler into an O(n) one.

Quoted 6 lines
Quoted 2 lines

Well I guess you could just break it a little bit without it being O(n)

Well, i just thought since each context switch/reschedule is costly... Having something that prevents a freshly scheduled process from being forced off before it can actually do something would be usefull.

Quoted 5 lines

Yeah it is, but the process will still take a lot of the penalty, and if it is using a lot of CPU in context switching, then it will get a lower priority anyway. Possibly there could be a very small additional penalty per context switch, but so far it hasn't been a big problem AFAIK.

Well my idea was more... The highest pri gets MIN_QUANT and a preemt can't happen faster than MIN_QUANT or so..
If i remember correctly, 2.6 spends much more time doing the actual context switches (not time / context switch but amount during this period). The new 1000 HZ thingy doesn't have to have that effect...

And since to many context switches are inefficient imho, some standoffs would be good =)

Signature · 1 line
Ian Kumlien <[email protected]>
#8 lore raw
Quoted 5 lines · Ian Kumlien

[Forgot to CC LKML last time, so i didn't remove old text ]

On Sun, 2003-08-31 at 12:57, Nick Piggin wrote:

Quoted 7 lines
Quoted 3 lines

Heh, well we discuss stuff sometimes, but we disagree on things. Which is a good thing because now our eggs are in two baskets.

Yes, but sometimes it feels like a merger would be better... As long as the propper quantum usage prevails =)

Nope. They're going in different directions. We'd slow each other down.

Quoted 7 lines
Quoted 3 lines

Yeah quite a lot. Lots included removing the interactivity stuff.

Humm, yeah, that should work automatically with the "used the full quantum" if thats still in that is... =)

You've lost me here.
My stuff is the opposite of what the interactivity stuff is trying to do. The interactivity stuff _does_ kind of implement variable timeslices in the form of re queueing stuff. I think it would be a nightmare for them to put my variable timeslices on top of that and then get it to all work properly.

Quoted 11 lines
Quoted 7 lines

Yeah it is, but the process will still take a lot of the penalty, and if it is using a lot of CPU in context switching, then it will get a lower priority anyway. Possibly there could be a very small additional penalty per context switch, but so far it hasn't been a big problem AFAIK.

Well my idea was more... The highest pri gets MIN_QUANT and a preemt can't happen faster than MIN_QUANT or so..

My idea is to try to make it as simple as possible, and no simpler (as a great man put it!). So more is less if you know what I mean.

I think this is going against how the scheduler (and UNIX schedulers in general) have generally behaved. Its very likely that you'd be better off fixing your app / other broken bit of kernel code though.

I don't know... maybe...

Quoted 8 lines

If i remember correctly, 2.6 spends much more time doing the actual context switches (not time / context switch but amount during this period). The new 1000 HZ thingy doesn't have to have that effect...

And since to many context switches are inefficient imho, some standoffs would be good =)

I'm not sure. I think the 1000HZ thing is mainly from timer interrupts. The scheduler should be pretty well agnostic to the 100->1000 change, other than having higher resolution. Increased context switches might indicate something is not being scaled with HZ properly though.

Yes context switches are inefficient. The tradeoff is vs scheduling latency and there is no way around that.

#9 lore raw
Quoted 7 lines · Nick Piggin
Quoted 5 lines · Ian Kumlien

[Forgot to CC LKML last time, so i didn't remove old text ]

On Sun, 2003-08-31 at 12:57, Nick Piggin wrote:

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Heh, well we discuss stuff sometimes, but we disagree on things. Which is a good thing because now our eggs are in two baskets.

Yes, but sometimes it feels like a merger would be better... As long as the propper quantum usage prevails =)

Nope. They're going in different directions. We'd slow each other down.

Okis.

Quoted 7 lines
Quoted 6 lines
Quoted 2 lines

Yeah quite a lot. Lots included removing the interactivity stuff.

Humm, yeah, that should work automatically with the "used the full quantum" if thats still in that is... =)

Quoted 6 lines

You've lost me here.
My stuff is the opposite of what the interactivity stuff is trying to do. The interactivity stuff _does_ kind of implement variable timeslices in the form of re queueing stuff. I think it would be a nightmare for them to put my variable timeslices on top of that and then get it to all work properly.

Well, i dunno how your patch works (i forget =))... But afair ingos interactivity patches was about the amount of the quantum that was used. And combining that with high = small and low = large would automatically balance the priorities accordingly.

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

Yeah it is, but the process will still take a lot of the penalty, and if it is using a lot of CPU in context switching, then it will get a lower priority anyway. Possibly there could be a very small additional penalty per context switch, but so far it hasn't been a big problem AFAIK.

Quoted 7 lines
Quoted 3 lines

Well my idea was more... The highest pri gets MIN_QUANT and a preemt can't happen faster than MIN_QUANT or so..

My idea is to try to make it as simple as possible, and no simpler (as a great man put it!). So more is less if you know what I mean.

Yup =)

Quoted 6 lines

I think this is going against how the scheduler (and UNIX schedulers in general) have generally behaved. Its very likely that you'd be better off fixing your app / other broken bit of kernel code though.

I don't know... maybe...

Humm i thought more in the direction of:
Preempt prior to MIN_QUANT being used -> put it on the runqueue as the next process being scheduled, change the running tasks timeslice -> continue with current task.

(make the current tasks timeslice appear as used.)

Quoted 4 lines
Quoted 4 lines

If i remember correctly, 2.6 spends much more time doing the actual context switches (not time / context switch but amount during this period). The new 1000 HZ thingy doesn't have to have that effect...

Quoted 8 lines
Quoted 3 lines

And since to many context switches are inefficient imho, some standoffs would be good =)

I'm not sure. I think the 1000HZ thing is mainly from timer interrupts. The scheduler should be pretty well agnostic to the 100->1000 change, other than having higher resolution. Increased context switches might indicate something is not being scaled with HZ properly though.

hummm i dunno, but afair the scheduler uses that timing aswell...

Quoted 2 lines

Yes context switches are inefficient. The tradeoff is vs scheduling latency and there is no way around that.

Thus, keeping preempt from being able to preempt other tasks prior to MIN_QUANT being used is bad.. =)

Which also might fix the "child preempting parent on fork" problem that con patched afair.
(dunno if you have the same problem though...)

Signature · 1 line
Ian Kumlien <[email protected]>
#10 lore raw
In reply to Ian Kumlien
Quoted 4 lines · Ian Kumlien

Why not use small quantum values for high pri processes and long for low pri since the high pri processes will preempt the low pri processes anyways. And for a server working under load with only a few processes (assuming they are all low pri) would lessen the context switches.

The rationale behind giving high priority processes a large timeslice is two-fold:

(1) if they are interactive, then they won't actually use it all (this is the point you are making). But,

(2) Having a large timeslice ensures that they have a high probability of having available timeslice when they _do_ need it.

So, yes, interactive processes can get by with a small timeslice, because that is by-definition all they need. But they do need to run often (i.e., as I think you have mentioned in your last email, interactive processes are "run often for short periods"), so the large timeslice ensures that they are never expired.

A counterargument might be that the large timeslice is a detriment to other high priority processes. But the thinking is that, by definition, interactive processes won't use all of the timeslice. And thus will not hog the CPU. If they do, the interactivity estimator will quickly bring them down.

That is the rationale in the current scheduler, anyhow. Nick's current work is interesting, and a bit different.

Quoted 4 lines

And a system with "interactive load" as well would, as i said, preempt the lower pris. But this could also cause a problem... Imho there should be a "min quantum value" so that processes can't preempt a process that was just scheduled (i dunno if this is implemented already though).

I don't think this is a good idea. I see your intention, but we have priorities for a reason.

Robert Love

#11 lore raw
Quoted 7 lines · Robert Love
Quoted 4 lines · Ian Kumlien

Why not use small quantum values for high pri processes and long for low pri since the high pri processes will preempt the low pri processes anyways. And for a server working under load with only a few processes (assuming they are all low pri) would lessen the context switches.

Quoted 8 lines

The rationale behind giving high priority processes a large timeslice is two-fold:

(1) if they are interactive, then they won't actually use it all (this is the point you are making). But,

(2) Having a large timeslice ensures that they have a high probability of having available timeslice when they _do_ need it.

Since they would have a high pri still, and preempt is there... it should be back on the cpu pretty quick.

Quoted 5 lines

So, yes, interactive processes can get by with a small timeslice, because that is by-definition all they need. But they do need to run often (i.e., as I think you have mentioned in your last email, interactive processes are "run often for short periods"), so the large timeslice ensures that they are never expired.

But, it also creates problems for when a interactive process becomes a cpu hog. Like this the detection should be faster, but should be slowed down somewhat.

Quoted 5 lines

A counterargument might be that the large timeslice is a detriment to other high priority processes. But the thinking is that, by definition, interactive processes won't use all of the timeslice. And thus will not hog the CPU. If they do, the interactivity estimator will quickly bring them down.

But, hogs would instead cause a context switch hell and lessen the throughput on server loads...

Quoted 2 lines

That is the rationale in the current scheduler, anyhow. Nick's current work is interesting, and a bit different.

Yes, saner imho =)

Quoted 7 lines
Quoted 4 lines

And a system with "interactive load" as well would, as i said, preempt the lower pris. But this could also cause a problem... Imho there should be a "min quantum value" so that processes can't preempt a process that was just scheduled (i dunno if this is implemented already though).

I don't think this is a good idea. I see your intention, but we have priorities for a reason.

I don't see how priorities would be questioned... Since, all i say is that a task that gets preempted should have a guaranteed time on the cpu so that we don't waste cycles doing context switches all the time.

I can see that Ingos current scheduler is good from a desktop standpoint, but having it that way is not warranted when preempt comes in to the picture (if i correctly understand it's workings)... With preempt i actually see no reason for the priority inversion.. And to answer someone who mailed about this before: "Yes, it does seem to be slower than my Amigas, esp the ones that use Executive...". (That feedback scheduler rocks =))

Signature · 1 line
Ian Kumlien <[email protected]>
#12 lore raw
Quoted 2 lines · Ian Kumlien

Since they would have a high pri still, and preempt is there... it should be back on the cpu pretty quick.

Ah, but no! You assume we do not have an expired list and round robin scheduling.

Once a task exhausts its timeslice, it cannot run until all other tasks exhaust their timeslice. If this were not the case, high priority tasks could monopolize the system.

Quoted 3 lines

But, it also creates problems for when a interactive process becomes a cpu hog. Like this the detection should be faster, but should be slowed down somewhat.

I agree, although I do think it responds fairly quick. But, regardless, this is why I am interested in Nick's work. The interactivity estimator can never be perfect.

Quoted 2 lines

But, hogs would instead cause a context switch hell and lessen the throughput on server loads...

Hm, why?

Quoted 3 lines

I don't see how priorities would be questioned... Since, all i say is that a task that gets preempted should have a guaranteed time on the cpu so that we don't waste cycles doing context switches all the time.

But latency is important.

Robert Love

#13 lore raw
Quoted 7 lines · Robert Love
Quoted 2 lines · Ian Kumlien

Since they would have a high pri still, and preempt is there... it should be back on the cpu pretty quick.

Ah, but no! You assume we do not have an expired list and round robin scheduling.

hummm, I assume that a high pri process can preempt a low pri process... The rest sounds sane to me =), Please tell me what i'm missing.. =)

Quoted 3 lines

Once a task exhausts its timeslice, it cannot run until all other tasks exhaust their timeslice. If this were not the case, high priority tasks could monopolize the system.

All other? including sleeping?... How many tasks can be assumed to run on the cpu at a time?....

Should preempt send the new quantum value to all "low pri, high quantum" processes?

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Quoted 7 lines
Quoted 3 lines

But, it also creates problems for when a interactive process becomes a cpu hog. Like this the detection should be faster, but should be slowed down somewhat.

I agree, although I do think it responds fairly quick. But, regardless, this is why I am interested in Nick's work. The interactivity estimator can never be perfect.

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

Quoted 4 lines
Quoted 2 lines

But, hogs would instead cause a context switch hell and lessen the throughput on server loads...

Hm, why?

Since it's rescheduled after a short runtime or, might be. From someones mail i saw (afair), there was much more context switches in 2.6 than in 2.4. And each schedule consumes time and cycles.

Quoted 5 lines
Quoted 3 lines

I don't see how priorities would be questioned... Since, all i say is that a task that gets preempted should have a guaranteed time on the cpu so that we don't waste cycles doing context switches all the time.

But latency is important.

Oh yes, but otoh, if you are really keen on the latency then you'll do realtime =)

Signature · 1 line
Ian Kumlien <[email protected]>
#14 lore raw
Quoted 2 lines · Ian Kumlien

hummm, I assume that a high pri process can preempt a low pri process... The rest sounds sane to me =), Please tell me what i'm missing.. =)

No no. The rule is "the highest priority process with timeslice remaining runs" not just "the highest priority process runs."

Otherwise, timeslice wouldn't matter much!

When a process exhausts its timeslice, it is moved to the "expired" list. When all currently running tasks expire their timeslice, the scheduler begins servicing from the "expired" list (which then becomes the "active" list, and the old active list becomes the expired).

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

If timeslices did not play a role, then high priority tasks would always monopolize the system.

This is a classic priority-based round-robin scheduler.

Quoted 6 lines
Quoted 3 lines

Once a task exhausts its timeslice, it cannot run until all other tasks exhaust their timeslice. If this were not the case, high priority tasks could monopolize the system.

All other? including sleeping?... How many tasks can be assumed to run on the cpu at a time?....

I wasn't clear: all other _runnable_ tasks.

Once a task "expires" (exhausts its timeslice), it will not run again until all other tasks, even those of a lower priority, exhaust their timeslice.

This is a major difference between normal tasks and real-time tasks.

Quoted 2 lines

Should preempt send the new quantum value to all "low pri, high quantum" processes?

I don't follow this?

Quoted 3 lines

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

If you need to guarantee that a task always runs when runnable, you want real-time.

If you just want to give a scheduling boost, to ensure greater runnability, lower latency, and larger timeslices... nice values suffice.

Quoted 2 lines

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

A lot of this is just the interactivity estimator making the wrong estimate.

Quoted 3 lines

Since it's rescheduled after a short runtime or, might be. From someones mail i saw (afair), there was much more context switches in 2.6 than in 2.4. And each schedule consumes time and cycles.

Context switches (as in process to process changes) should be about the same?

Interrupt frequency has gone up in x86 (1000 vs 100). Maybe that is what they are seeing.

Quoted 2 lines

Oh yes, but otoh, if you are really keen on the latency then you'll do realtime =)

Agreed. But at the same time, not every "interactive" task should be real-time. In fact, nearly all should not. I do not want my text editor or mailer to be RT, for example.

They just need a scheduling boost.

Robert Love

#15 lore raw
Quoted 7 lines · Robert Love
Quoted 2 lines · Ian Kumlien

hummm, I assume that a high pri process can preempt a low pri process... The rest sounds sane to me =), Please tell me what i'm missing.. =)

No no. The rule is "the highest priority process with timeslice remaining runs" not just "the highest priority process runs."

Then i'm beginning to agree with the time unit... Large timeslice but in units for high pri tasks... So that high pri can run (if needed) 2 or 3 times / timeslice.

More like MAX_QUANT_ON_QUEUE/MIN_QUANT or so...

Quoted 1 line

Otherwise, timeslice wouldn't matter much!

Just sounds odd to me.

Quoted 4 lines

When a process exhausts its timeslice, it is moved to the "expired" list. When all currently running tasks expire their timeslice, the scheduler begins servicing from the "expired" list (which then becomes the "active" list, and the old active list becomes the expired).

Ok, good solution

Quoted 5 lines

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Quoted 5 lines

If timeslices did not play a role, then high priority tasks would always monopolize the system.

This is a classic priority-based round-robin scheduler.

Quoted 8 lines
Quoted 6 lines
Quoted 3 lines

Once a task exhausts its timeslice, it cannot run until all other tasks exhaust their timeslice. If this were not the case, high priority tasks could monopolize the system.

All other? including sleeping?... How many tasks can be assumed to run on the cpu at a time?....

I wasn't clear: all other _runnable_ tasks.

Yes, but how many runable tasks would you have on a system in one go, while maintaining interactivity...
(Ie, what amount would the scheduler actually have to deal with..)

Quoted 3 lines

Once a task "expires" (exhausts its timeslice), it will not run again until all other tasks, even those of a lower priority, exhaust their timeslice.

Yeah, it seems like my idea would need several run queues with diff timeslices to make up.

Quoted 6 lines

This is a major difference between normal tasks and real-time tasks.

Quoted 2 lines

Should preempt send the new quantum value to all "low pri, high quantum" processes?

I don't follow this?

Never mind, bad idea, sucky thing... =P

Quoted 7 lines
Quoted 3 lines

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

Yes, like the feedback scheduler...

Quoted 2 lines

If you need to guarantee that a task always runs when runnable, you want real-time.

... yes... =)

Quoted 3 lines

If you just want to give a scheduling boost, to ensure greater runnability, lower latency, and larger timeslices... nice values suffice.

nicevalues/pri is always the best way imho.

Quoted 5 lines
Quoted 2 lines

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

A lot of this is just the interactivity estimator making the wrong estimate.

Yes, But... When you come from AmigaOS, and have used Executive... things like this is dis concerning. Executive is a scheduler addition for amigaos that has many schedulers to choose from. One of which is the original feedback scheduler. While a feedback scheduler consumes some cpu it still allows you to play mp3's while surfing the net on a 50 mhz 68060. Hearing about 500mhz machines that skip is somewhat.. odd.

And afair it has no real interactivity estimator.

(If you are interested you can always search for Executive on aminet.. It has several scheduler policies including those that work great on small machines (25mhz or so))

Quoted 6 lines
Quoted 3 lines

Since it's rescheduled after a short runtime or, might be. From someones mail i saw (afair), there was much more context switches in 2.6 than in 2.4. And each schedule consumes time and cycles.

Context switches (as in process to process changes) should be about the same?

Apparently they are not... I should have saved the link...

Quoted 2 lines

Interrupt frequency has gone up in x86 (1000 vs 100). Maybe that is what they are seeing.

I dunno, i didn't pay that much attention and i can't find it now =P

Quoted 6 lines
Quoted 2 lines

Oh yes, but otoh, if you are really keen on the latency then you'll do realtime =)

Agreed. But at the same time, not every "interactive" task should be real-time. In fact, nearly all should not. I do not want my text editor or mailer to be RT, for example.

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler.

500 mhz is a lot of horsepower when it comes to playing mp3's and scheduling.. It feels like something is wrong when i see all these discussions but i most certainly don't know enough to even begin to understand it. I only tried to show the thing i thought was really wrong but you do have a point with the runqueues and timeslices =P

Quoted 1 line

They just need a scheduling boost.

imho, that shouldn't really be needed... =P
(although executive apparently had a pri boost for active window... I doubt that i ran with it though... Been a while =))

Signature · 1 line
Ian Kumlien <[email protected]>
#16 lore raw
Quoted 10 lines · Ian Kumlien
Quoted 5 lines · Robert Love

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Please read my RFC
(http://marc.theaimsgroup.com/?l=linux-kernel&m=106178160825835&w=2) which has this extensively explained. If this were the case after one timeslice, then dragging a window in X at load of say 32 would be impossible; the window would move for 0.1 second, stand still for 3.2 seconds then move for another 0.1 second.

Quoted 9 lines
Quoted 7 lines
Quoted 3 lines

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

Yes, like the feedback scheduler...

Priority inversion to some extent will exist in any scheduler design that has priorities. There are solutions available but they incur a performance penalty elsewhere (some people are currently experimenting). The inversion problems inherent in my earlier patches are largely gone with the duration and severity of inversion being either equal to or smaller than the instances that occur in the vanilla scheduler. Nick's approach may work around it differently but documentation is hard to find (hint Nick*).

Quoted 6 lines
Quoted 5 lines
Quoted 2 lines

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

A lot of this is just the interactivity estimator making the wrong estimate.

Quoted 6 lines

Yes, But... When you come from AmigaOS, and have used Executive... things like this is dis concerning. Executive is a scheduler addition for amigaos that has many schedulers to choose from. One of which is the original feedback scheduler. While a feedback scheduler consumes some cpu it still allows you to play mp3's while surfing the net on a 50 mhz 68060. Hearing about 500mhz machines that skip is somewhat.. odd.

That's in an attempt to make them as high throughput machines as possible. Xmms skipping is basically killed off as a problem in both Nick's and my patches. If it still remains it is almost certainly a disk i/o problem (no dma) or hitting swap memory.

Quoted 4 lines

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler.

Multiple processors to do different tasks on amigas kinda helped there...

Quoted 5 lines

500 mhz is a lot of horsepower when it comes to playing mp3's and scheduling.. It feels like something is wrong when i see all these discussions but i most certainly don't know enough to even begin to understand it. I only tried to show the thing i thought was really wrong but you do have a point with the runqueues and timeslices =P

Things are _never ever ever ever_ as simple as they appear on the surface.

Cheers,
Con

#17 lore raw
Quoted 2 lines · Con Kolivas
Quoted 1 line · Ian Kumlien

On Mon, 2003-09-01 at 01:41, Robert Love wrote:

[ big snip ]

Quoted 6 lines
Quoted 4 lines

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler.

Multiple processors to do different tasks on amigas kinda helped there...

Amiga had just one multipurpose CPU. All other processors were completelly specialized. It was just that one of these, the blitter, could be used as a generic "memcpy on steroids" processor, allowing you to mix 3 sources with shifting and logical operations onto one destination.

Quoted 7 lines
Quoted 5 lines

500 mhz is a lot of horsepower when it comes to playing mp3's and scheduling.. It feels like something is wrong when i see all these discussions but i most certainly don't know enough to even begin to understand it. I only tried to show the thing i thought was really wrong but you do have a point with the runqueues and timeslices =P

Things are _never ever ever ever_ as simple as they appear on the surface.

This is SOOOO true :)

Greets, Antonio.

#18 lore raw
In reply to Con Kolivas
Quoted 12 lines · Con Kolivas
Quoted 10 lines · Ian Kumlien
Quoted 5 lines · Robert Love

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Quoted 6 lines

Please read my RFC
(http://marc.theaimsgroup.com/?l=linux-kernel&m=106178160825835&w=2) which has this extensively explained. If this were the case after one timeslice, then dragging a window in X at load of say 32 would be impossible; the window would move for 0.1 second, stand still for 3.2 seconds then move for another 0.1 second.

Thats nicely written, but it feels very complex...
The more i read it the more i like the "currency" implementation in Executive (since i never understood how feedback worked exactly, it was a while ago since i read it).

Just give all processes money to spend on cpu time... Set a high limit and let em spend =)

Quoted 10 lines
Quoted 9 lines
Quoted 7 lines
Quoted 3 lines

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

Yes, like the feedback scheduler...

Quoted 7 lines

Priority inversion to some extent will exist in any scheduler design that has priorities. There are solutions available but they incur a performance penalty elsewhere (some people are currently experimenting). The inversion problems inherent in my earlier patches are largely gone with the duration and severity of inversion being either equal to or smaller than the instances that occur in the vanilla scheduler. Nick's approach may work around it differently but documentation is hard to find (hint Nick*).

What i meant with priority inversion is that highpri should have small timeslices and low pri should have large... Sorry if i was unclear. (maybe the same size timeslice but separated in to timeunits)

Quoted 13 lines
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

A lot of this is just the interactivity estimator making the wrong estimate.

Quoted 6 lines

Yes, But... When you come from AmigaOS, and have used Executive... things like this is dis concerning. Executive is a scheduler addition for amigaos that has many schedulers to choose from. One of which is the original feedback scheduler. While a feedback scheduler consumes some cpu it still allows you to play mp3's while surfing the net on a 50 mhz 68060. Hearing about 500mhz machines that skip is somewhat.. odd.

Quoted 4 lines

That's in an attempt to make them as high throughput machines as possible. Xmms skipping is basically killed off as a problem in both Nick's and my patches. If it still remains it is almost certainly a disk i/o problem (no dma) or hitting swap memory.

Humm, ok... The only desktop i have where i have switched between O(1) and common is my laptop... which sadly didn't run either nick or your work... So i have no comparison with your or nicks work.

Quoted 6 lines
Quoted 4 lines

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler.

Multiple processors to do different tasks on amigas kinda helped there...

Well, yes, but... Not when it comes to scheduling.

Quoted 7 lines
Quoted 5 lines

500 mhz is a lot of horsepower when it comes to playing mp3's and scheduling.. It feels like something is wrong when i see all these discussions but i most certainly don't know enough to even begin to understand it. I only tried to show the thing i thought was really wrong but you do have a point with the runqueues and timeslices =P

Things are _never ever ever ever_ as simple as they appear on the surface.

If they were... Life would be boring =P

Signature · 1 line
Ian Kumlien <[email protected]>
#19 lore raw
In reply to Ian Kumlien
Quoted 3 lines · Ian Kumlien

Then i'm beginning to agree with the time unit... Large timeslice but in units for high pri tasks... So that high pri can run (if needed) 2 or 3 times / timeslice.

Exactly.

Quoted 9 lines
Quoted 5 lines

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Not penalized... all tasks go through the same thing.

Look at it like this. Assume we have:

Task A, B, and C at priority 10 (the highest) Task D at priority 5
Tasks E and F at priority 0 (the lowest)

We run them in that order: A, B, C, D, E, then F. And repeat. (Actually, within a given priority, the tasks are run round-robin in any nonspecific order.. effectively first-come, first-served scheduling).

If [any task] has exhausted its timeslice, it will not run until the remaining tasks exhaust their timeslice. Once all tasks have expired, we start over.

So the total scheduling routine tasks the sum of the timeslices of tasks A,B,C,D,E,F. And only when they are all 100% CPU bound.

Quoted 3 lines

Yes, but how many runable tasks would you have on a system in one go, while maintaining interactivity...
(Ie, what amount would the scheduler actually have to deal with..)

Most systems only have a handful (1-2) running tasks that are actually running.

For example:

	$ ps aux|awk '{print $8}'|grep R|wc -l
	     4
	$ ps aux|wc -l
	     87

But Unix is designed for timesharing among many interactive tasks. It works. The problem faced today in 2.6 is juggling throughput versus latency in the scheduler, with the interactivity estimator.

Robert Love

#20 lore raw
Quoted 6 lines · Robert Love

Look at it like this. Assume we have:

Task A, B, and C at priority 10 (the highest) Task D at priority 5
Tasks E and F at priority 0 (the lowest)

Quoted 7 lines

We run them in that order: A, B, C, D, E, then F. And repeat. (Actually, within a given priority, the tasks are run round-robin in any nonspecific order.. effectively first-come, first-served scheduling).

If [any task] has exhausted its timeslice, it will not run until the remaining tasks exhaust their timeslice. Once all tasks have expired, we start over.

I hate to keep butting in and saying this but this is not quite what happens. If a task is considered interactive (a priority boost of 2 or more) and it uses up a full timeslice then it is checked to see if a starvation limit has been exceeded by the tasks on the expired array. If it hasn't exceeded the limit, the interactive task will be rescheduled again ahead of everything else. ie if A is the only task still considered interactive after using up it's timeslice the first time it will go

A,B,C,A
before anything else

and if nothing else is interactive it can even go
A,B,C,A,A,A
etc until A is not considered interactive (boost lost) or the starvation limit is exceeded.

This is not just with my patches; this is Ingo's design.

Con

#21 lore raw
Quoted 7 lines · Con Kolivas

I hate to keep butting in and saying this but this is not quite what happens. If a task is considered interactive (a priority boost of 2 or more) and it uses up a full timeslice then it is checked to see if a starvation limit has been exceeded by the tasks on the expired array. If it hasn't exceeded the limit, the interactive task will be rescheduled again ahead of everything else. ie if A is the only task still considered interactive after using up it's timeslice the first time it will go

I know this. I mentioned earlier what I was saying was ignoring the interactive task reinsertion optimization.

I am trying to explain things in general.

Robert Love

#22 lore raw
In reply to Robert Love
Quoted 14 lines · Robert Love
Quoted 3 lines · Ian Kumlien

Then i'm beginning to agree with the time unit... Large timeslice but in units for high pri tasks... So that high pri can run (if needed) 2 or 3 times / timeslice.

Exactly.

Quoted 6 lines
Quoted 5 lines

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

Quoted 5 lines
Quoted 3 lines

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Not penalized... all tasks go through the same thing.

Yeah, that part was unclear though. =)

[Snip: Thanks for the explanation i'll reply in Con's mail if needed ]

Quoted 3 lines

But Unix is designed for timesharing among many interactive tasks. It works. The problem faced today in 2.6 is juggling throughput versus latency in the scheduler, with the interactivity estimator.

Yeah...

Signature · 1 line
Ian Kumlien <[email protected]>
#23 lore raw
In reply to Ian Kumlien
Quoted 32 lines · Ian Kumlien
Quoted 7 lines · Robert Love
Quoted 2 lines · Ian Kumlien

hummm, I assume that a high pri process can preempt a low pri process... The rest sounds sane to me =), Please tell me what i'm missing.. =)

No no. The rule is "the highest priority process with timeslice remaining runs" not just "the highest priority process runs."

Then i'm beginning to agree with the time unit... Large timeslice but in units for high pri tasks... So that high pri can run (if needed) 2 or 3 times / timeslice.

More like MAX_QUANT_ON_QUEUE/MIN_QUANT or so...

Quoted 1 line

Otherwise, timeslice wouldn't matter much!

Just sounds odd to me.

Quoted 4 lines

When a process exhausts its timeslice, it is moved to the "expired" list. When all currently running tasks expire their timeslice, the scheduler begins servicing from the "expired" list (which then becomes the "active" list, and the old active list becomes the expired).

Ok, good solution

Quoted 5 lines

This implies that a high priority, which has exhausted its timeslice, will not be allowed to run again until _all_ other runnable tasks exhaust their timeslice (this ignores the reinsertion into the active array of interactive tasks, but that is an optimization that just complicates this discussion).

Quoted 6 lines

So it's penalised by being in the corner for one go? or just pri penalised (sounds like it could get a corner from what you wrote... Or is it time for bed).

Quoted 2 lines

If timeslices did not play a role, then high priority tasks would always monopolize the system.

This happened on Amiga.

Quoted 58 lines
Quoted 10 lines

This is a classic priority-based round-robin scheduler.

Quoted 6 lines
Quoted 3 lines

Once a task exhausts its timeslice, it cannot run until all other tasks exhaust their timeslice. If this were not the case, high priority tasks could monopolize the system.

All other? including sleeping?... How many tasks can be assumed to run on the cpu at a time?....

I wasn't clear: all other _runnable_ tasks.

Yes, but how many runable tasks would you have on a system in one go, while maintaining interactivity...
(Ie, what amount would the scheduler actually have to deal with..)

Quoted 3 lines

Once a task "expires" (exhausts its timeslice), it will not run again until all other tasks, even those of a lower priority, exhaust their timeslice.

Yeah, it seems like my idea would need several run queues with diff timeslices to make up.

Quoted 6 lines

This is a major difference between normal tasks and real-time tasks.

Quoted 2 lines

Should preempt send the new quantum value to all "low pri, high quantum" processes?

I don't follow this?

Never mind, bad idea, sucky thing... =P

Quoted 7 lines
Quoted 3 lines

Damn thats a tough cookie, i still think that the priority inversion is bad. Don't know enough about this to actually provide a solution... Any one else that has a view point?

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

Yes, like the feedback scheduler...

Quoted 2 lines

If you need to guarantee that a task always runs when runnable, you want real-time.

... yes... =)

Quoted 3 lines

If you just want to give a scheduling boost, to ensure greater runnability, lower latency, and larger timeslices... nice values suffice.

nicevalues/pri is always the best way imho.

Quoted 5 lines
Quoted 2 lines

Hummm, the skips in xmms tells me that something is bad.. (esp since it works perfectly on the previus scheduler)

A lot of this is just the interactivity estimator making the wrong estimate.

Quoted 6 lines

Yes, But... When you come from AmigaOS, and have used Executive... things like this is dis concerning. Executive is a scheduler addition for amigaos that has many schedulers to choose from. One of which is the original feedback scheduler. While a feedback scheduler consumes some cpu it still allows you to play mp3's while surfing the net on a 50 mhz 68060. Hearing about 500mhz machines that skip is somewhat.. odd.

Ian, I came from Amiga to Linux many moons ago, and their target are very different... on Amiga, the mouse pointer is drawn as a hardware sprite (same as an C64 or an arcade machine), and the mouse movement counters are handled in hardware too, so your mouse pointer can't _EVER_ get laggy.

The sound system is very different, on Amiga you ask the system to callback to you when audio needs replenishing, and anyways you could boost the player priority so that multichanel or mp3 playing gets more priority than other tasks. I can recall playing mp3 on a 68030/50 and having to boost the player's priority so that it would get no skipping. As you probably know 68060 machines, even if at the same mhz, have about 8x raw calculation power.

So, I also feel very bad about linux when my audio skips on my 900mhz machine and I see reports that it does the same on 2400mhz ones, but I can understand that the general design and target is not the same... Amiga was _designed_, both software and hardware wise, for realtime while Unix and thus Linux is designed for multiuser timesharing.

All that said, having a mp3 decoder as a kernel module reading from mlocked ram would a great way to have Amiga-like music replaying ;)

Geert, perhaps you could tell us how linux music playing feels for a desktop m68k machine?

[ I'm CCing you since you are the only one from the m68k port
which I can see posting on a regular basis.]

Quoted 5 lines

And afair it has no real interactivity estimator.

(If you are interested you can always search for Executive on aminet.. It has several scheduler policies including those that work great on small machines (25mhz or so))

For those with no Amiga background, the original Amiga task scheduler can be assumed to work like linux' RR_REALTIME scheduler with 80ms timeslices. Important system tasks such as filesystems, disks and input device handlers ran each on it's own task (shared memory microkernel design) with adjusted priorities, and then all user-initiated tasks, window manager included, ran with default priority zero.

[for more info, there are great discussions about Amiga-internals on very early posts to linux-kernel / linux-activists from about 1991/1992 timeframe]

If the user or a program decided so, it could _always_ change a task priority to upper or lower levels, which is what I did to my mp3 player to avoid skips on my under powered machine (mp3 playing used 85%cpu) ;).

"Executive" was an application which patched the Amiga scheduler and hooked up a priority manager. By altering task' priorities, it managed to get the standard round-robin scheduler to behave like a feedback one. (Executive was _G_R_E_A_T_ :)))

Executive was configured to never touch tasks with elevated priorities, so in fact all user tasks would get the feedback scheduler but system drivers such as keyboard input system would continue running as realtime round-robin.

Quoted 31 lines
Quoted 6 lines
Quoted 3 lines

Since it's rescheduled after a short runtime or, might be. From someones mail i saw (afair), there was much more context switches in 2.6 than in 2.4. And each schedule consumes time and cycles.

Context switches (as in process to process changes) should be about the same?

Apparently they are not... I should have saved the link...

Quoted 2 lines

Interrupt frequency has gone up in x86 (1000 vs 100). Maybe that is what they are seeing.

I dunno, i didn't pay that much attention and i can't find it now =P

Quoted 6 lines
Quoted 2 lines

Oh yes, but otoh, if you are really keen on the latency then you'll do realtime =)

Agreed. But at the same time, not every "interactive" task should be real-time. In fact, nearly all should not. I do not want my text editor or mailer to be RT, for example.

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler. 500 mhz is a lot of horsepower when it comes to playing mp3's and scheduling.. It feels like something is wrong when i see all these discussions but i most certainly don't know enough to even begin to understand it. I only tried to show the thing i thought was really wrong but you do have a point with the runqueues and timeslices =P

Quoted 5 lines
Quoted 1 line

They just need a scheduling boost.

imho, that shouldn't really be needed... =P
(although executive apparently had a pri boost for active window... I doubt that i ran with it though... Been a while =))

Yes, it added +1 to the task which owner the active window (this is also used in Windows if I recall correctly). But even without this "hack", both executive-enabled and standard systems ran great.

Greets, Antonio.

#24 lore raw
Quoted 8 lines · Antonio Vargas
Quoted 2 lines · Ian Kumlien
Quoted 1 line · Robert Love

On Sun, 2003-08-31 at 18:41, Ian Kumlien wrote:

Ian, I came from Amiga to Linux many moons ago, and their target are very different... on Amiga, the mouse pointer is drawn as a hardware sprite (same as an C64 or an arcade machine), and the mouse movement counters are handled in hardware too, so your mouse pointer can't _EVER_ get laggy.

That's not completely true...

The hardware keeps track of the mouse counter (but may overflow). The mouse counters are checked periodically (in an interrupt, IIRC) and the sprite position is updated.

So there's no real difference from a hardware point of view between Amiga mouse/sprite hardware and PCs with PS/2 or serial mice and hardware cursors. Both mouse counters and serial buffers can overflow, though ;-)

Quoted 2 lines

Geert, perhaps you could tell us how linux music playing feels for a desktop m68k machine?

Last time I tried it was worse than AmigaOS.

Quoted 2 lines

[ I'm CCing you since you are the only one from the m68k port
which I can see posting on a regular basis.]

What about Roman Zippel? And you can always try the linux-m68k list ;-)

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines

Agreed. But at the same time, not every "interactive" task should be real-time. In fact, nearly all should not. I do not want my text editor or mailer to be RT, for example.

Well, there is latency and there is latency. To take the AmigaOS example. Voyager, a webbrowser for AmigaOS uses MUI (a fully dynamic gui with weighted(prioritized) sections) and renders images. It's responsive even on a 40mhz 68040 using Executive with the feedback scheduler.

The biggest part of the responsiveness comes from the cheap context switching. Not needing a MMU can have its advantages... Plus there's no demand paging or swapping to wait for.

That's also the reason why you can have higher serial speed under AmigaOS than under Linux/m68k: a serial port with a 1-byte buffer needs fast and cheap context switching.

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

#25 lore raw
In reply to Antonio Vargas
Quoted 8 lines · Antonio Vargas
Quoted 6 lines · Ian Kumlien

Yes, But... When you come from AmigaOS, and have used Executive... things like this is dis concerning. Executive is a scheduler addition for amigaos that has many schedulers to choose from. One of which is the original feedback scheduler. While a feedback scheduler consumes some cpu it still allows you to play mp3's while surfing the net on a 50 mhz 68060. Hearing about 500mhz machines that skip is somewhat.. odd.

Quoted 5 lines

Ian, I came from Amiga to Linux many moons ago, and their target are very different... on Amiga, the mouse pointer is drawn as a hardware sprite (same as an C64 or an arcade machine), and the mouse movement counters are handled in hardware too, so your mouse pointer can't _EVER_ get laggy.

I also joined linux a long time ago... but the hardware pointer is not the issue. I'm more referring to using cpublit and dragging the scrollbar in a window... Like f.ex. Voyager.

(And, in this case, 50Mhz is the limitation not the scheduler. With 10 times that power i bet you could do it all with the cpu, just like a common pc today.)

Quoted 7 lines

The sound system is very different, on Amiga you ask the system to callback to you when audio needs replenishing, and anyways you could boost the player priority so that multichanel or mp3 playing gets more priority than other tasks. I can recall playing mp3 on a 68030/50 and having to boost the player's priority so that it would get no skipping. As you probably know 68060 machines, even if at the same mhz, have about 8x raw calculation power.

Eh, a 060 struggles with a mp3, it consumes most of the cpu and it can still render a browser window (not as fast as it could originally, but thats not my point).

Quoted 5 lines

So, I also feel very bad about linux when my audio skips on my 900mhz machine and I see reports that it does the same on 2400mhz ones, but I can understand that the general design and target is not the same... Amiga was _designed_, both software and hardware wise, for realtime while Unix and thus Linux is designed for multiuser timesharing.

AmigaOS is lowlatency but not realtime. And, with executive you run a unix scheduler (feedback).

Quoted 2 lines

All that said, having a mp3 decoder as a kernel module reading from mlocked ram would a great way to have Amiga-like music replaying ;)

Hummm, Last time i played a mp3 on my amiga i kinda decoded it in the delfina dsp =)
(to bad noone has done that for emu10k1... )

Quoted 8 lines

Geert, perhaps you could tell us how linux music playing feels for a desktop m68k machine?

[ I'm CCing you since you are the only one from the m68k port
which I can see posting on a regular basis.]

Quoted 2 lines

And afair it has no real interactivity estimator.

Quoted 7 lines
Quoted 3 lines

(If you are interested you can always search for Executive on aminet.. It has several scheduler policies including those that work great on small machines (25mhz or so))

If the user or a program decided so, it could _always_ change a task priority to upper or lower levels, which is what I did to my mp3 player to avoid skips on my under powered machine (mp3 playing used 85%cpu) ;).

Heh, what cpu?

But a task raising it's cpu on it's own can be a pain since it could dominate the machine on non executive running machines.

Quoted 4 lines

"Executive" was an application which patched the Amiga scheduler and hooked up a priority manager. By altering task' priorities, it managed to get the standard round-robin scheduler to behave like a feedback one. (Executive was _G_R_E_A_T_ :)))

Executive implements dynamic priorities in a fixed priority OS, ie nice. You select the range it should use to catch processes and where it should place em. And, Executive is still great even though i haven't used it for quite some time.

Quoted 4 lines

Executive was configured to never touch tasks with elevated priorities, so in fact all user tasks would get the feedback scheduler but system drivers such as keyboard input system would continue running as realtime round-robin.

Hummm, input.device would never consume so much cpu that it would need to be penalized.

Quoted 7 lines
Quoted 3 lines

imho, that shouldn't really be needed... =P
(although executive apparently had a pri boost for active window... I doubt that i ran with it though... Been a while =))

Yes, it added +1 to the task which owner the active window (this is also used in Windows if I recall correctly). But even without this "hack", both executive-enabled and standard systems ran great.

Give priority to "front most" program is in Windows and OS/2. I disabled it in OS/2 Warp something on a p120 and watched it crawl =P.

Signature · 1 line
Ian Kumlien <[email protected]>
#26 lore raw
In reply to Robert Love
Quoted 9 lines · Robert Love

Once a task "expires" (exhausts its timeslice), it will not run again until all other tasks, even those of a lower priority, exhaust their timeslice.

...

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

So if I have 1000 low priority tasks and one high priority task, all CPU bound, the high priority task gets 0.1% CPU. This is not the desirable or expected behaviour.

My conclusion is, the strategy of expiring the whole active array before any expired tasks are allowed to run again is incorrect. Instead, each active list should be refreshed from the expired list individually. This does not affect the desirable O(1) scheduling property. To prevent low priority starvation, the high-to-low scan should be elaborated to skip some runnable, high priority tasks occasionally in a *controlled* way.

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Regards,

Daniel

#27 lore raw
Quoted 11 lines · Daniel Phillips
Quoted 9 lines · Robert Love

Once a task "expires" (exhausts its timeslice), it will not run again until all other tasks, even those of a lower priority, exhaust their timeslice.

...

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

Quoted 7 lines

So if I have 1000 low priority tasks and one high priority task, all CPU bound, the high priority task gets 0.1% CPU. This is not the desirable or expected behaviour.

My conclusion is, the strategy of expiring the whole active array before any expired tasks are allowed to run again is incorrect. Instead, each active list should be refreshed from the expired list individually. This does not

AFAIK, this could be implemented with a "list swap" operation, taking the list head for one priority and exchanging them between expired and active, or perhaps more properly, taking the expired list and adding it to the end of the active one. This would be O(1) since the task list for each priority is double-linked and thus has a "last element" pointer on the list header.

Quoted 3 lines

affect the desirable O(1) scheduling property. To prevent low priority starvation, the high-to-low scan should be elaborated to skip some runnable, high priority tasks occasionally in a *controlled* way.

Perhaps this could be done with a random but skewed proportion, similar to the way you select the level to insert into on the "skip list" datastructure.

Quoted 12 lines

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Regards,

Daniel

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 6 lines
winden/network

1. Dado un programa, siempre tiene al menos un fallo.
2. Dadas varias lineas de codigo, siempre se pueden acortar a menos lineas.
3. Por induccion, todos los programas se pueden
   reducir a una linea que no funciona.
#28 lore raw
In reply to Daniel Phillips

[Forgot CC to LKML and Robert Love, sorry ]

Quoted 9 lines · Daniel Phillips
Quoted 3 lines · Robert Love

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

So if I have 1000 low priority tasks and one high priority task, all CPU bound, the high priority task gets 0.1% CPU. This is not the desirable or expected behaviour.

Quoted 6 lines

My conclusion is, the strategy of expiring the whole active array before any expired tasks are allowed to run again is incorrect. Instead, each active list should be refreshed from the expired list individually. This does not affect the desirable O(1) scheduling property. To prevent low priority starvation, the high-to-low scan should be elaborated to skip some runnable, high priority tasks occasionally in a *controlled* way.

I like this idea.
You could handle the priority starvation with a "old process" boost. (i don't know which would be simpler or if there is something even simpler out there)

This would ensure that all processes are run sooner or later. Real cpuhogs would run very seldom due to being starved, but run when they get the boost. On a loaded system this might be desirable since most login tools would be "normal" or "high pri" from the get go. (there might be a problem with locks though)

This should also work hand in hand with timeslice changes imho. Aswell as process preemption. If we assume that cpu hogs has work that they want to get done, let em do it for as long as possible. If something "important" happens, it'll be preempted right?

Quoted 2 lines

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Most definitely.

Signature · 1 line
Ian Kumlien <[email protected]>
#29 lore raw
Quoted 12 lines · Ian Kumlien

[Forgot CC to LKML and Robert Love, sorry ]

Quoted 8 lines · Daniel Phillips
Quoted 4 lines · Robert Love

Priority inversion is bad, but the priority inversion in this case is intended. Higher priority tasks cannot starve lower ones. It is a classic Unix philosophy that 'all tasks make some forward progress'

So if I have 1000 low priority tasks and one high priority task, all CPU bound, the high priority task gets 0.1% CPU. This is not the desirable or expected behaviour.

In my implementation, the high prio guy gets 1.9% CPU and the others get 0.09%. However, in all implementations, the high priority one will be allowed to preempt the any of others, of course.

At this point you can safely abandon the consideration that a user might be running KDE as well ;)

Quoted 15 lines
Quoted 3 lines

My conclusion is, the strategy of expiring the whole active array before any expired tasks are allowed to run again is incorrect. Instead, each active list should be refreshed from the expired list individually. This does not affect the desirable O(1) scheduling property. To prevent low priority starvation, the high-to-low scan should be elaborated to skip some runnable, high priority tasks occasionally in a *controlled* way.

I like this idea.
You could handle the priority starvation with a "old process" boost. (i don't know which would be simpler or if there is something even simpler out there)

This would ensure that all processes are run sooner or later. Real cpuhogs would run very seldom due to being starved, but run when they get the boost. On a loaded system this might be desirable since most login tools would be "normal" or "high pri" from the get go. (there might be a problem with locks though)

Quoted 5 lines

This should also work hand in hand with timeslice changes imho. Aswell as process preemption. If we assume that cpu hogs has work that they want to get done, let em do it for as long as possible. If something "important" happens, it'll be preempted right?

This is really just another variation on the idea of dynamic timeslices. Mine does it explicitly. This idea and the interactivity idea do it implicitly (not that thats bad).

#30 lore raw
In reply to Ian Kumlien
Quoted 5 lines · Ian Kumlien
Quoted 2 lines · Daniel Phillips

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Most definitely.

No, the correct answer is maybe... if after it's redesigned and put through lots of testing to ensure it doesn't create other regressions. I'm not saying it isn't correct, just that it's a major architectural change you're promoting. Now isn't the time for that.

Why not just wait till 2.6.10 and plop in a new scheduler a'la dropping in a new vm into 2.4.10... <sigh>

The cpu scheduler simply isn't broken as the people on this mailing list seem to think it is. While my tweaks _look_ large, they're really just tweaking the way the numbers feed back into a basically unchanged design. All the incremental changes have been modifying the same small sections of sched.c over and over again. Nick's changes change the size of timeslices and the priority variation in a much more fundamental way but still use the basic architecture of the scheduler.

Promoting a new scheduler design entirely is admirable and ultimately probably worth pursuing but not 2.6 stuff.

Con

#31 lore raw
Quoted 7 lines · Con Kolivas
Quoted 5 lines · Ian Kumlien
Quoted 2 lines · Daniel Phillips

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Most definitely.

Quoted 7 lines

No, the correct answer is maybe... if after it's redesigned and put through lots of testing to ensure it doesn't create other regressions. I'm not saying it isn't correct, just that it's a major architectural change you're promoting. Now isn't the time for that.

Why not just wait till 2.6.10 and plop in a new scheduler a'la dropping in a new vm into 2.4.10... <sigh>

Wouldn't a new scheduler be easier to test? And your patches changes it's behavior quite a lot. Wouldn't they require the same testing? (And Nicks for that mater, who changes more)

Quoted 7 lines

The cpu scheduler simply isn't broken as the people on this mailing list seem to think it is. While my tweaks _look_ large, they're really just tweaking the way the numbers feed back into a basically unchanged design. All the incremental changes have been modifying the same small sections of sched.c over and over again. Nick's changes change the size of timeslices and the priority variation in a much more fundamental way but still use the basic architecture of the scheduler.

But, can't this scheduler suffer from starvation? If the run queue is long enough? Either via that deadline or via processes not running...

Wouldn't a starved process boost ensure that even hogs on a loaded system got their share now and then?

You could say that the problem the current scheduler has is that it's not allowed to starve anything, thats why we add stuff to give interactive bonus. But if it *was* allowed to starve but gave bonus to the starved processes that would make most of the interactive detection useless (yes, we still need the "didn't use their timeslice" bit and with a timeslice that gets smaller the higher the pri we'd automagically balance most processes).

(As usual my assumptions might be really wrong...)

Quoted 2 lines

Promoting a new scheduler design entirely is admirable and ultimately probably worth pursuing but not 2.6 stuff.

Well, discussing and creating it is one thing. Implementing it is another. Accepting the patch is still up to the-powers-that-be(tm)

Signature · 1 line
Ian Kumlien <[email protected]>
#32 lore raw
Quoted 11 lines · Ian Kumlien
Quoted 9 lines · Con Kolivas
Quoted 7 lines · Ian Kumlien
Quoted 3 lines · Daniel Phillips

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Most definitely.

Quoted 9 lines
Quoted 4 lines

No, the correct answer is maybe... if after it's redesigned and put through lots of testing to ensure it doesn't create other regressions. I'm not saying it isn't correct, just that it's a major architectural change you're promoting. Now isn't the time for that.

Why not just wait till 2.6.10 and plop in a new scheduler a'la dropping in a new vm into 2.4.10... <sigh>

Wouldn't a new scheduler be easier to test? And your patches changes it's behavior quite a lot. Wouldn't they require the same testing? (And Nicks for that mater, who changes more)

Well a new scheduler needs the same testing as an old scheduler. The difference is less of it has been done.

Quoted 18 lines
Quoted 3 lines

The cpu scheduler simply isn't broken as the people on this mailing list seem to think it is. While my tweaks _look_ large, they're really just tweaking the way the numbers feed back into a basically unchanged design. All the incremental changes have been modifying the same small sections of sched.c over and over again. Nick's changes change the size of timeslices and the priority variation in a much more fundamental way but still use the basic architecture of the scheduler.

But, can't this scheduler suffer from starvation? If the run queue is long enough? Either via that deadline or via processes not running...

Wouldn't a starved process boost ensure that even hogs on a loaded system got their share now and then?

You could say that the problem the current scheduler has is that it's not allowed to starve anything, thats why we add stuff to give interactive bonus. But if it *was* allowed to starve but gave bonus to the starved processes that would make most of the interactive detection useless (yes, we still need the "didn't use their timeslice" bit and with a timeslice that gets smaller the higher the pri we'd automagically balance most processes).

Quoted 2 lines

(As usual my assumptions might be really wrong...)

First off, no general purpose scheduler should allow starvation depending on your definition. The interactivity stuff, and even dynamic priorities allow short term unfairness.

A cpu hog is not a starved process. It becomes a CPU hog because it is running all the time. True, it mustn't be starved indefinitely by a lot of higher priority processes. This is something Con's and my schedulers both ensure.

Hmm... what else? The "didn't use their timeslice" thing is not
applicable: a new timeslice doesn't get handed out until the previous one is used. The priorities thing is done based on how much sleeping the process does.

Its funny, everyone seems to have very similar ideas that they are expressing by describing different implementations they have in mind.

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Quoted 11 lines · Ian Kumlien
Quoted 9 lines · Con Kolivas
Quoted 7 lines · Ian Kumlien
Quoted 3 lines · Daniel Phillips

IMHO, this minor change will provide a more solid, predictable base for Con and Nick's dynamic priority and dynamic timeslice experiments.

Most definitely.

Quoted 9 lines
Quoted 4 lines

No, the correct answer is maybe... if after it's redesigned and put through lots of testing to ensure it doesn't create other regressions. I'm not saying it isn't correct, just that it's a major architectural change you're promoting. Now isn't the time for that.

Why not just wait till 2.6.10 and plop in a new scheduler a'la dropping in a new vm into 2.4.10... <sigh>

Wouldn't a new scheduler be easier to test? And your patches changes it's behavior quite a lot. Wouldn't they require the same testing? (And Nicks for that mater, who changes more)

Well a new scheduler needs the same testing as an old scheduler. The difference is less of it has been done.

Quoted 18 lines
Quoted 3 lines

The cpu scheduler simply isn't broken as the people on this mailing list seem to think it is. While my tweaks _look_ large, they're really just tweaking the way the numbers feed back into a basically unchanged design. All the incremental changes have been modifying the same small sections of sched.c over and over again. Nick's changes change the size of timeslices and the priority variation in a much more fundamental way but still use the basic architecture of the scheduler.

But, can't this scheduler suffer from starvation? If the run queue is long enough? Either via that deadline or via processes not running...

Wouldn't a starved process boost ensure that even hogs on a loaded system got their share now and then?

You could say that the problem the current scheduler has is that it's not allowed to starve anything, thats why we add stuff to give interactive bonus. But if it *was* allowed to starve but gave bonus to the starved processes that would make most of the interactive detection useless (yes, we still need the "didn't use their timeslice" bit and with a timeslice that gets smaller the higher the pri we'd automagically balance most processes).

Quoted 2 lines

(As usual my assumptions might be really wrong...)

First off, no general purpose scheduler should allow starvation depending on your definition. The interactivity stuff, and even dynamic priorities allow short term unfairness.

A cpu hog is not a starved process. It becomes a CPU hog because it is running all the time. True, it mustn't be starved indefinitely by a lot of higher priority processes. This is something Con's and my schedulers both ensure.

Hmm... what else? The "didn't use their timeslice" thing is not
applicable: a new timeslice doesn't get handed out until the previous one is used. The priorities thing is done based on how much sleeping the process does.

Its funny, everyone seems to have very similar ideas that they are expressing by describing different implementations they have in mind.

#33 lore raw
Quoted 9 lines · Nick Piggin
Quoted 8 lines · Ian Kumlien

You could say that the problem the current scheduler has is that it's not allowed to starve anything, thats why we add stuff to give interactive bonus. But if it *was* allowed to starve but gave bonus to the starved processes that would make most of the interactive detection useless (yes, we still need the "didn't use their timeslice" bit and with a timeslice that gets smaller the higher the pri we'd automagically balance most processes).

Quoted 5 lines
Quoted 1 line

(As usual my assumptions might be really wrong...)

First off, no general purpose scheduler should allow starvation depending on your definition. The interactivity stuff, and even dynamic priorities allow short term unfairness.

When you reach a certain load you *have to* allow starvation. Ie, you can't work around it... All i say is that if we have a more relaxed method we might benefit from it.

Quoted 4 lines

Hmm... what else? The "didn't use their timeslice" thing is not
applicable: a new timeslice doesn't get handed out until the previous one is used. The priorities thing is done based on how much sleeping the process does.

And not the amount of cpu consumed by the app / go?

Quoted 2 lines

Its funny, everyone seems to have very similar ideas that they are expressing by describing different implementations they have in mind.

Yes =), I'm mailing Con directly now as well, to save some unwanted traffic here =). I just hope that we'll reach a agreement somewhere about whats sane or not...

Mail me if you're interested as well.

Signature · 1 line
Ian Kumlien <[email protected]>
#34 lore raw
Quoted 14 lines · Ian Kumlien
Quoted 12 lines · Nick Piggin
Quoted 10 lines · Ian Kumlien

You could say that the problem the current scheduler has is that it's not allowed to starve anything, thats why we add stuff to give interactive bonus. But if it *was* allowed to starve but gave bonus to the starved processes that would make most of the interactive detection useless (yes, we still need the "didn't use their timeslice" bit and with a timeslice that gets smaller the higher the pri we'd automagically balance most processes).

(As usual my assumptions might be really wrong...)

Quoted 9 lines
Quoted 4 lines

First off, no general purpose scheduler should allow starvation depending on your definition. The interactivity stuff, and even dynamic priorities allow short term unfairness.

When you reach a certain load you *have to* allow starvation. Ie, you can't work around it... All i say is that if we have a more relaxed method we might benefit from it.

Depending on your definition. If 1000 processes get 10ms CPU every 10000ms I would not call that being starved. Maybe thats misleading.

Quoted 9 lines
Quoted 6 lines

Hmm... what else? The "didn't use their timeslice" thing is not
applicable: a new timeslice doesn't get handed out until the previous one is used. The priorities thing is done based on how much sleeping the process does.

And not the amount of cpu consumed by the app / go?

Well yeah in a way. Consuming CPU lowers priority, sleeping raises.

Quoted 11 lines
Quoted 4 lines

Its funny, everyone seems to have very similar ideas that they are expressing by describing different implementations they have in mind.

Yes =), I'm mailing Con directly now as well, to save some unwanted traffic here =). I just hope that we'll reach a agreement somewhere about whats sane or not...

Mail me if you're interested as well.

OK CC me

#35 lore raw
Quoted 7 lines · Nick Piggin
Quoted 3 lines · Ian Kumlien

When you reach a certain load you *have to* allow starvation. Ie, you can't work around it... All i say is that if we have a more relaxed method we might benefit from it.

Depending on your definition. If 1000 processes get 10ms CPU every 10000ms I would not call that being starved. Maybe thats misleading.

[Sorry, i'm tired, i hope this comes out right ]

What i'm thinking of is more of a, "Hey, hog, we didn't manage to get you in on this 'system wide schedule' (doing all the tasks before restarting) due to heavy load, so we'll give you this boost so that you can compete better next time".

Quoted 3 lines
Quoted 1 line

And not the amount of cpu consumed by the app / go?

Well yeah in a way. Consuming CPU lowers priority, sleeping raises.

Thought so. And afair it does use "timeslice useage" at one time or has that changed?

Quoted 3 lines
Quoted 1 line

Mail me if you're interested as well.

OK CC me

As soon as Con has me straight on a few things... =)

Signature · 1 line
Ian Kumlien <[email protected]>
#36 lore raw
Quoted 8 lines · Ian Kumlien
Quoted 4 lines · Nick Piggin
Quoted 1 line · Ian Kumlien

And not the amount of cpu consumed by the app / go?

Well yeah in a way. Consuming CPU lowers priority, sleeping raises.

Thought so. And afair it does use "timeslice useage" at one time or has that changed?

I think that's part of the interactivity estimator Nick removed in his patches...

#37 lore raw
In reply to Con Kolivas
Quoted 6 lines · Con Kolivas

...

The cpu scheduler simply isn't broken as the people on this mailing list seem to think it is. While my tweaks _look_ large, they're really just tweaking the way the numbers feed back into a basically unchanged design.

...

For what it's worth, I haven't had any problems with Con's O19int. I've been trying to repeat a case of priority inversion I experienced with O18.1...but it seems to be cured (and that was really my only problem with it). I was already getting fewer skips in XMMS with 2.6.0-test3-mm2 than I did with 2.4.18 and the same sort of workload. I can't really test xmms now that the ACPI changes have obliterated my chances of freeing IRQ 5 for my sb16 -- but from the improvements I feel in the last few patches from Con, I imagine that it wouldn't skip anymore. (On a side note, I really miss xmms where random means quite random, unlike my CD changer which is repeat the same songs in a four hour block.) I certainly am not running any sort of high-end machine with a K6-2 400 ;-) The mouse might lag slightly for a few seconds when starting up a build, but as soon as the scheduler adjusts, I can't tell whether I have four builds running at the same time or just one. In 2.4.18, it has a slow feeling that let's you know the system is loaded -- and it never goes away (well, until the compiling's done).

-Wes-