Skip to contentSkip to conversation

O(1) Entitlement Based Scheduler

RFC PATCH Albert Cahalan 2 participants 5 messages Feb 26, 2004 – Mar 1, 2004

lore
Share & tools
lore
#0 lore raw
Quoted 6 lines · John Lee

The usage rates for each task are estimated using Kalman filter techniques, the estimates being similar to those obtained by taking a running average over twice the filter _response half life_ (see below). However, Kalman filter values are cheaper to compute and don't require the maintenance of historical usage data.

Linux dearly needs this. Please separate out this part of the patch and send it in.

Right now, Linux does not report the recent CPU usage of a process. The UNIX standard requires that "ps" report this; right now ps substitutes CPU usage over the whole lifetime of a process.

Both per-task and per-process (tid and tgid) numbers are needed. Both percent and permill (1/1000) units get reported, so don't convert to integer percent.

#1 lore raw
Quoted 11 lines · Albert Cahalan
Quoted 6 lines · John Lee

The usage rates for each task are estimated using Kalman filter techniques, the estimates being similar to those obtained by taking a running average over twice the filter _response half life_ (see below). However, Kalman filter values are cheaper to compute and don't require the maintenance of historical usage data.

Quoted 2 lines

Linux dearly needs this. Please separate out this part of the patch and send it in.

This information can be determined from the SleepAVG: field in the /proc/<pid>/status and /proc/<tgid>/task/<pid>/status files by subtracting the value there from 100. Without our patch this value is a directly calculated estimated of the task's sleep rate which is available because it used by the O(1) scheduler's heuristics. With our patches, it is calculated from our estimate of the task's usage because we dispensed with the sleep average calculations as they are no longer needed. We decided to still report sleep average in the status file because we were reluctant to alter the contents of such files in case we broke user space programs.

Quoted 9 lines

Right now, Linux does not report the recent CPU usage of a process. The UNIX standard requires that "ps" report this; right now ps substitutes CPU usage over the whole lifetime of a process.

Both per-task and per-process (tid and tgid) numbers are needed. Both percent and permill (1/1000) units get reported, so don't convert to integer percent.

I think a modification to fs/proc/array.c to make this field a per million rather than a percent value would satisfy your needs. It would be a very small change but there would be concerns about breaking programs that rely on it being a percentage.

Peter

Signature · 4 lines
Dr Peter Williams, Chief Scientist                [email protected]
Aurema Pty Limited                                Tel:+61 2 9698 2322
PO Box 305, Strawberry Hills NSW 2012, Australia  Fax:+61 2 9699 9174
79 Myrtle Street, Chippendale NSW 2008, Australia http://www.aurema.com
#2 lore raw
Quoted 11 lines · Peter Williams
Quoted 10 lines · Albert Cahalan
Quoted 6 lines · John Lee

The usage rates for each task are estimated using Kalman filter techniques, the estimates being similar to those obtained by taking a running average over twice the filter _response half life_ (see below). However, Kalman filter values are cheaper to compute and don't require the maintenance of historical usage data.

Quoted 6 lines
Quoted 2 lines

Linux dearly needs this. Please separate out this part of the patch and send it in.

This information can be determined from the SleepAVG: field in the /proc/<pid>/status and /proc/<tgid>/task/<pid>/status files by subtracting the value there from 100.

This doesn't seem to be the case. For example, a fork() causes the value to be adjusted in both child and parent.

Also, perhaps the name is wrong, but I'd think SleepAVG has more to do with the average length of a sleep. It sure isn't documented. (time constant? type of decay?)

There's also a need for whole-process stats and cumulative (sum of exited children) stats. %CPU can go as high as 51200%.

Quoted 8 lines

Without our patch this value is a
directly calculated estimated of the task's sleep rate which is available because it used by the O(1) scheduler's heuristics. With our patches, it is calculated from our estimate of the task's usage because we dispensed with the sleep average calculations as they are no longer needed. We decided to still report sleep average in the status file because we were reluctant to alter the contents of such files in case we broke user space programs.

Generally this is a good move, though I don't expect anything to be using SleepAVG at the moment.

Quoted 5 lines
Quoted 5 lines

Right now, Linux does not report the recent CPU usage of a process. The UNIX standard requires that "ps" report this; right now ps substitutes CPU usage over the whole lifetime of a process.

Quoted 8 lines
Quoted 3 lines

Both per-task and per-process (tid and tgid) numbers are needed. Both percent and permill (1/1000) units get reported, so don't convert to integer percent.

I think a modification to fs/proc/array.c to make this field a per million rather than a percent value would satisfy your needs. It would be a very small change but there would be concerns about breaking programs that rely on it being a percentage.

Nothing can rely on it existing at all, so a name change would solve the problem of apps getting confused.

BTW, permill is not per-million, it is per-thousand. Per-million or per-billion would be fine as long as it doesn't overflow.

#3 lore raw
Quoted 15 lines · Albert Cahalan
Quoted 13 lines · Peter Williams
Quoted 11 lines · Albert Cahalan
Quoted 6 lines · John Lee

The usage rates for each task are estimated using Kalman filter techniques, the estimates being similar to those obtained by taking a running average over twice the filter _response half life_ (see below). However, Kalman filter values are cheaper to compute and don't require the maintenance of historical usage data.

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines

Linux dearly needs this. Please separate out this part of the patch and send it in.

This information can be determined from the SleepAVG: field in the /proc/<pid>/status and /proc/<tgid>/task/<pid>/status files by subtracting the value there from 100.

This doesn't seem to be the case. For example, a fork() causes the value to be adjusted in both child and parent.

This would be the case with our patch as well as we make children inherit their parent's usage rate to partially reduce the effect of ramp up in the estimation of the child's CPU usage rate.

Quoted 4 lines

Also, perhaps the name is wrong, but I'd think SleepAVG has more to do with the average length of a sleep. It sure isn't documented. (time constant? type of decay?)

My reading of the code caused me to interpret it as a percentage sleep rate i.e. a value of 50 means the task is sleeping 50% of the time. And this has made me realise that without our patches using (100 - SleepAVG) would not really give you CPU usage rate but would instead give RUNNABILITY rate (i.e. the proportion of time the task is spending on the cpu OR on a runqueue waiting for cpu access.

It also makes me realise that the SleepAVG our patch reports is NOT really a sleep rate it's a sleep OR waiting on a runqueue rate.

Quoted 10 lines

There's also a need for whole-process stats and cumulative (sum of exited children) stats. %CPU can go as high as 51200%.

Quoted 1 line

Without our patch this value is a directly calculated estimated of the task's sleep rate which is available because it used by the O(1) scheduler's heuristics. With our patches, it is calculated from our estimate of the task's usage because we dispensed with the sleep average calculations as they are no longer needed. We decided to still report sleep average in the status file because we were reluctant to alter the contents of such files in case we broke user space programs.

Generally this is a good move, though I don't expect anything to be using SleepAVG at the moment.

OK.

Quoted 14 lines
Quoted 7 lines
Quoted 7 lines

Right now, Linux does not report the recent CPU usage of a process. The UNIX standard requires that "ps" report this; right now ps substitutes CPU usage over the whole lifetime of a process.

Quoted 5 lines
Quoted 3 lines

Both per-task and per-process (tid and tgid) numbers are needed. Both percent and permill (1/1000) units get reported, so don't convert to integer percent.

I think a modification to fs/proc/array.c to make this field a per million rather than a percent value would satisfy your needs. It would be a very small change but there would be concerns about breaking programs that rely on it being a percentage.

Quoted 6 lines

Nothing can rely on it existing at all, so a name change would solve the problem of apps getting confused.

BTW, permill is not per-million, it is per-thousand. Per-million or per-billion would be fine as long as it doesn't overflow.

OK. Since SleepAVG does not seem to be entrenched in people's expectations and because of the fact that the value calculated from our usage rates are not really valid (see above), I propose that we change this field's name to CPUrate and report the CPU usage rate directly in permill (unless there are violent objections).

Peter

Signature · 4 lines
Dr Peter Williams, Chief Scientist                [email protected]
Aurema Pty Limited                                Tel:+61 2 9698 2322
PO Box 305, Strawberry Hills NSW 2012, Australia  Fax:+61 2 9699 9174
79 Myrtle Street, Chippendale NSW 2008, Australia http://www.aurema.com
#4 lore raw
Quoted 1 line · Peter Williams

Albert Cahalan wrote:

<snip>

Quoted 9 lines
Quoted 6 lines

Nothing can rely on it existing at all, so a name change would solve the problem of apps getting confused.

BTW, permill is not per-million, it is per-thousand. Per-million or per-billion would be fine as long as it doesn't overflow.

OK. Since SleepAVG does not seem to be entrenched in people's expectations and because of the fact that the value calculated from our usage rates are not really valid (see above), I propose that we change this field's name to CPUrate and report the CPU usage rate directly in permill (unless there are violent objections).

I've analysed the arithmetic and think that we can safely go to 6 decimal places so I'll make this Per-million. The change should appear in the patches to the 2.6.4 kernel when it is available.

Peter

Signature · 4 lines
Dr Peter Williams, Chief Scientist                [email protected]
Aurema Pty Limited                                Tel:+61 2 9698 2322
PO Box 305, Strawberry Hills NSW 2012, Australia  Fax:+61 2 9699 9174
79 Myrtle Street, Chippendale NSW 2008, Australia http://www.aurema.com