round_jiffies and load average

I've modified the driver of an USB device (cxacru) to schedule the next poll for status every 1s using round_jiffies_relative instead of just waiting 1s since the last poll was completed. This process takes on average 11ms to complete and while it is waiting for a response it's considered running.

The load average is calculated every 5 seconds equivalent to round_jiffies, so I have a problem with the load average always tending towards 1.00:

 14:26:19 up 6 days, 14:45,  5 users,  load average: 1.10, 1.04, 1.02
 14:27:19 up 6 days, 14:46,  5 users,  load average: 1.03, 1.03, 1.01
 14:28:19 up 6 days, 14:47,  5 users,  load average: 0.95, 1.01, 1.00
 14:29:19 up 6 days, 14:48,  5 users,  load average: 0.90, 0.97, 0.99
 14:30:19 up 6 days, 14:49,  5 users,  load average: 0.93, 0.96, 0.98
 14:31:19 up 6 days, 14:50,  5 users,  load average: 0.90, 0.94, 0.97
 14:32:20 up 6 days, 14:51,  5 users,  load average: 0.96, 0.95, 0.97
 14:33:20 up 6 days, 14:52,  5 users,  load average: 0.98, 0.95, 0.97
 14:34:20 up 6 days, 14:53,  5 users,  load average: 1.09, 0.99, 0.98
 14:35:20 up 6 days, 14:54,  5 users,  load average: 1.03, 0.99, 0.98
 14:36:20 up 6 days, 14:55,  5 users,  load average: 1.01, 0.99, 0.98
 14:37:20 up 6 days, 14:56,  5 users,  load average: 1.00, 0.99, 0.98
 14:38:21 up 6 days, 14:57,  5 users,  load average: 1.22, 1.05, 1.00
 14:39:21 up 6 days, 14:58,  5 users,  load average: 1.08, 1.04, 1.00
 14:40:21 up 6 days, 14:59,  5 users,  load average: 1.03, 1.03, 1.00
 14:41:21 up 6 days, 15:00,  5 users,  load average: 0.95, 1.01, 0.99
 14:42:21 up 6 days, 15:01,  5 users,  load average: 0.90, 0.97, 0.98
 14:43:21 up 6 days, 15:02,  5 users,  load average: 0.99, 0.99, 0.99
 14:44:22 up 6 days, 15:03,  5 users,  load average: 0.86, 0.94, 0.97
 14:45:22 up 6 days, 15:04,  5 users,  load average: 0.97, 0.95, 0.97
 14:46:22 up 6 days, 15:05,  5 users,  load average: 1.08, 0.99, 0.98
 14:47:22 up 6 days, 15:06,  5 users,  load average: 1.03, 0.99, 0.98
 14:48:22 up 6 days, 15:07,  5 users,  load average: 1.32, 1.07, 1.01

Perhaps the load average count could be run just before or in the middle of a second instead?

Simon Arlott

I've added some printks to show exactly what happens (see below).

Since calc_load() appears to be run as often as possible, would it be ok to move it to run half a second out of step from rounded jiffies? Its count value is initialised to LOAD_FREQ so it would be easy to add HZ/2.

Otherwise every process using round_jiffies to 1s (1.00), 2s (0.50), 3s (0.33), 4s (0.25), 5s (0.00 or 1.00) could affect the load average in a constant way. (Beyond 10s the effect is unlikely to be noticed).

After a while of this (~3min):

[  192.147049] cxacru_poll_status(..), jiffies=4294832000
[  192.151319] cxacru_poll_status(..), jiffies=4294832004, next=996
[  192.463459] calc_load(27), count=-20, jiffies=4294832316
[  192.463472] calc_load(27), count=4980, jiffies=4294832316

Jiffies wraps:

[  327.121469] cxacru_poll_status(..), jiffies=4294967000
[  327.139428] cxacru_poll_status(..), jiffies=4294967018, next=1000
[  327.437739] calc_load(27), count=-20, jiffies=20
[  327.437750] calc_load(27), count=4980, jiffies=20

The next run occurs during cxacru_poll_status:

[  332.416288] cxacru_poll_status(..), jiffies=5000
[  332.417312] calc_load(1), count=-1, jiffies=5001
[  332.417322] calc_load(1), count=4999, jiffies=5001
[  332.423382] cxacru_poll_status(..), jiffies=5007, next=993

This happens without fail until I reboot:

[  672.350970] cxacru_poll_status(..), jiffies=345000
[  672.351913] calc_load(1), count=-1, jiffies=345001
[  672.351926] calc_load(1), count=4999, jiffies=345001
[  672.367737] cxacru_poll_status(..), jiffies=345016, next=984

It's interesting that calc_load() is run most of the time 19ms later (count=-20) than usual until jiffies wraps, then it runs on time or 1ms late (count=-2). Full log available on request (75K), HZ=1000 with NO_HZ.

(diff below of cxacru.c based on http://lkml.org/lkml/2007/2/23/328)
---

index c8b69bf..4717fa4 100644
@@ -535,6 +535,7 @@ static void cxacru_poll_status(struct work_struct *work)
 	struct atm_dev *atm_dev = usbatm->atm_dev;
 	int ret;
 
+	printk(KERN_DEBUG "cxacru_poll_status(..), jiffies=%lu\n", jiffies);
 	ret = cxacru_cm_get_array(instance, CM_REQUEST_CARD_INFO_GET, buf, CXINF_MAX);
 	if (ret < 0) {
 		atm_warn(usbatm, "poll status: error %d\n", ret);

@@ -599,6 +600,8 @@ static void cxacru_poll_status(struct work_struct *work)
 reschedule:
 	schedule_delayed_work(&instance->poll_work,
 			round_jiffies_relative(msecs_to_jiffies(POLL_INTERVAL*1000)));
+	printk(KERN_DEBUG "cxacru_poll_status(..), jiffies=%lu, next=%lu\n", jiffies, 
+		round_jiffies_relative(msecs_to_jiffies(POLL_INTERVAL*1000)));
 }
 
 static int cxacru_fw(struct usb_device *usb_dev, enum cxacru_fw_request fw,

index cb1b86a..9c2b816 100644
@@ -1230,12 +1230,14 @@ static inline void calc_load(unsigned long ticks)
 	count -= ticks;
 	if (unlikely(count < 0)) {
 		active_tasks = count_active_tasks();
+		printk(KERN_DEBUG "calc_load(%lu), count=%d, jiffies=%lu\n", ticks, count, jiffies);
 		do {
 			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
 			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
 			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
 			count += LOAD_FREQ;
 		} while (count < 0);
+		printk(KERN_DEBUG "calc_load(%lu), count=%d, jiffies=%lu\n", ticks, count, jiffies);
 	}
 }
 

Simon Arlott

This adds an initial 0.5s delay to calc_load so that it avoids updating load at the same time as tasks scheduled using round_jiffies, otherwise the load average is badly affected by tasks that run every time calc_load does (currently every 5s).

I'm assuming this change doesn't affect the intention of round_jiffies, to avoid tasks waking the cpu at different times, because calc_load is already run very often by a call from update_times(ticks) on every timer interrupt.

---
Without this change or an appropriate equivalent, my change to cxacru causes the load to stay around 1.00 even when mostly idle since it now runs every second using round_jiffies:

kernel/timer.c | 2 +-

1 files changed, 1 insertions(+), 1 deletions(-)

index cb1b86a..4bb21b5 100644
@@ -1225,7 +1225,7 @@ EXPORT_SYMBOL(avenrun);

static inline void calc_load(unsigned long ticks) {
unsigned long active_tasks; /* fixed-point */
- static int count = LOAD_FREQ;
+ static int count = LOAD_FREQ + HZ/2;

	count -= ticks;
	if (unlikely(count < 0)) {

1.5.0.1


-- 
Simon Arlott

Whenever jiffies is started at a multiple of 5*HZ or wraps, calc_load is run exactly on the second which is when tasks using round_jiffies will be scheduled to run. This has a bad effect on the load average, making it tend towards 1.00 if a task happens to run every time the load is being calculated.

This changes calc_load so that it updates load half a second after any tasks scheduled using round_jiffies.

---
Without this change or an appropriate equivalent, my change to cxacru causes the load to stay around 1.00 even when mostly idle since it now runs every second using round_jiffies:

kernel/timer.c | 8 +++++---

1 files changed, 5 insertions(+), 3 deletions(-)

index cb1b86a..ee61f6c 100644
@@ -1225,17 +1225,19 @@ EXPORT_SYMBOL(avenrun);

static inline void calc_load(unsigned long ticks) {
unsigned long active_tasks; /* fixed-point */
- static int count = LOAD_FREQ;
+ static int count = LOAD_FREQ + HZ/2;

	count -= ticks;
-	if (unlikely(count < 0)) {
+	if (unlikely(count <= 0)) {
		active_tasks = count_active_tasks();
		do {
			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
			count += LOAD_FREQ;
-		} while (count < 0);
+		} while (count <= 0);
+
+		count = round_jiffies_relative(count + HZ/2) - HZ/2;
	}
}

1.5.0.1


-- 
Simon Arlott

Well, it doesn't reintroduce the for_each_task() (not that it's present in similar form) loop in count_active_tasks(), so it doesn't bother me. You seem to have merely changed some offsets, which resolves the round_jiffies() clash. It's easy to envision similar degenerate cases, though I'm not sure we care enough to drop in a PRNG to handle them.

== wli

Whenever jiffies is started at a multiple of 5*HZ or wraps, calc_load is run exactly on the second which is when tasks using round_jiffies will be scheduled to run. This has a bad effect on the load average, making it tend towards 1.00 if a task happens to run every time the load is being calculated.

This changes calc_load so that it updates load half a second after any tasks scheduled using round_jiffies.

---
This version starts count off at 0, since LOAD_FREQ + HZ/2 is no better than LOAD_FREQ, and avoids rounding it to a negative value.

kernel/timer.c | 8 +++++---

1 files changed, 5 insertions(+), 3 deletions(-)

index cb1b86a..11ccfed 100644
@@ -1225,17 +1225,19 @@ EXPORT_SYMBOL(avenrun);

static inline void calc_load(unsigned long ticks) {
unsigned long active_tasks; /* fixed-point */
- static int count = LOAD_FREQ;
+ static int count = 0;

	count -= ticks;
-	if (unlikely(count < 0)) {
+	if (unlikely(count <= 0)) {
		active_tasks = count_active_tasks();
		do {
			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
			count += LOAD_FREQ;
-		} while (count < 0);
+		} while (count < HZ/2);
+
+		count = round_jiffies_relative(count + HZ/2) - HZ/2;
	}
}

1.5.0.1

-- 
Simon Arlott

Whenever jiffies is started at a multiple of 5*HZ or wraps, calc_load is run exactly on the second which is when tasks using round_jiffies will be scheduled to run. This has a bad effect on the load average, making it tend towards 1.00 if a task happens to run every time the load is being calculated.

This changes calc_load so that it updates load half a second after any tasks scheduled using round_jiffies.

---
This version starts count off at 0, since LOAD_FREQ + HZ/2 is no better than LOAD_FREQ. The previous version is actually wrong, rounding count to a negative value will only happen when getting calc_load running at the right time related to jiffies, it won't be negative running normally - even with NO_HZ.

kernel/timer.c | 8 +++++---

1 files changed, 5 insertions(+), 3 deletions(-)

index 6663a87..4abead0 100644
@@ -1226,17 +1226,19 @@ EXPORT_SYMBOL(avenrun);

static inline void calc_load(unsigned long ticks) {
unsigned long active_tasks; /* fixed-point */
- static int count = LOAD_FREQ;
+ static int count = 0;

	count -= ticks;
-	if (unlikely(count < 0)) {
+	if (unlikely(count <= 0)) {
		active_tasks = count_active_tasks();
		do {
			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
			count += LOAD_FREQ;
-		} while (count < 0);
+		} while (count <= 0);
+
+		count = round_jiffies_relative(count + HZ/2) - HZ/2;
	}
}

1.5.0.1


-- 
Simon Arlott

Simon

I believe this patch is too complex/hazardous and may break exp decay computation.
(Even if nobody care about avenrun[] those days :), do you ? )

You could just change LOAD_FREQ from (5*HZ) to (5*HZ+1)

#define LOAD_FREQ (5*HZ+1)

Mathematical proof (well... sort of)

$ cat prog.c
#define FSHIFT          11              /* nr of bits of precision */
#define FIXED_1         ((double)(1<<FSHIFT))   /* 1.0 as fixed-point */

#include <math.h>
#include <stdio.h>
int main()
{
printf("Old values :\n");
printf("#define EXP_1 %g\n", FIXED_1/exp(5.0/60.0)); printf("#define EXP_5 %g\n", FIXED_1/exp(5.0/(5*60.0))); printf("#define EXP_15 %g\n", FIXED_1/exp(5.0/(15*60.0))); printf("New values :\n");
printf("%g\n", FIXED_1/exp(5.01/60.0)); printf("%g\n", FIXED_1/exp(5.01/(5*60.0))); printf("%g\n", FIXED_1/exp(5.01/(15*60.0))); return 0;
}

# gcc -o prog prog.c -lm
# ./prog
Old values :
#define EXP_1  1884.25
#define EXP_5  2014.15
#define EXP_15 2036.65
New values :
1883.94
2014.08
2036.63

You can see that 5.01 instead of 5.00 second gives the same EXP_xx values.

So (5*HZ + 1) is safe. (because HZ >= 100)

Eric

Only for a single calculation whenever it has to adjust, which should only happen every 49.7 days (on 32-bit archs). (Or 5 minutes after booting... I always wondered why that happened and now I see it's initialised so it always wraps early). Whilst it is in sync with jiffies it will not affect the process - count is just set to the current value every time. Even with NO_HZ because jiffies will be correct when calc_load is called.

On HZ=1000, this would cause the load average to be pushed towards +1.00 for up to 2 minutes every ~83 minutes with no obvious cause. (If a task takes ~10-20ms to run, so 20 runs are needed at HZ=1000 before it passes it again).

On HZ=100 it would happen every ~8 minutes for up to 10 seconds and never be noticed.

Using 5*HZ+2 would move this to ~167 and ~17 minutes which would mitigate the effect further still without changing the exp values.

1884.25 -> 1883.62
2014.15 -> 2014.02
2036.65 -> 2036.61

Will anyone notice if the load is adjusted slightly less frequently?

If this is considered preferable to adjusting calc_load to avoid almost all round_jiffies scheduled tasks (some of which may take longer than ~15ms to run), then I have no problems with it - I just needed something to stop my driver changes doing odd things to the load average for other people. I'll continue to run with this version, is it possible to add a Kconfig option for it somewhere?

Simon Arlott

Nope, you dont quite understand how load (avenrun[]) is computed.

Every 5 seconds, three values are adjusted, based on their previous value and the actual value. Lets focus on the first value (mean load average on one minute)

exp = 1.0 / exp(5.0/60.0);
avenrun[0] = (avenrun[0] * exp) + (active * (1.0 - exp));

If previous value is 0.0, and current active count 1, then next value for avenrun[0] will be : 0.0799556

Not exactly 1.0 as you think !

Then in the next intervals (if active count is 0), it will decrease 'slowly' :
0.0735627
0.0676809
0.0622695
0.0572907

In average, your load factor close to reality.

Just try my suggestion, it should work. I even proved it in my previous mail :)

Eric

I knew that; but the task runs for more than 1 tick and it takes until the next calc_load run before it moves on even 1 tick.

With HZ=1000, the active count will be 1 up to 20 times in a row before it becomes out of sync with when the task is run again. This is ample time for the load value itself to get closer to 1:

$ uptime; (yes>/dev/null &); sleep 100; uptime
20:00:29 up  4:35,  7 users,  load average: 0.33, 0.51, 0.78
20:02:09 up  4:37,  7 users,  load average: 0.97, 0.67, 0.81
(not very useful results since the load isn't at 0.00 very often)

I still don't know why you think it may change the computation of load (aside from at boot or jiffies wrapping), and it's not really complex at all. It is possible that someone will change the value of LOAD_FREQ to something other than a multiple of HZ and this won't work because it'll get rounded up to a whole second. That and the negligible extra processing time of doing round_jiffies every 5 seconds is the only problem I can see.

I accidentally left LOAD_FREQ at 5 instead of 5*HZ and had a printk in there, it still worked fine aside from the load average going up and down every tick.

Simon Arlott

You apparently have no idea of the mathematic formulae used.

This formulae has a meaning *only* if EXP_1, EXP_5, EXP_15 are directly computed from the exact LOAD_FREQ value. If you change it 'randomly' without changing the EXP_... you basically compute a wrong value... So what ? Do you want to impress your boss with a given value ?

Please dont mess it. Just ignore the avenrun values and let it die.

You can change it to suit your needs, but it wont suit every needs.

Imagine for example your task is awaken for 1us periods every HZ. Basically your cpu load should be HZ/1000000 (machine mostly idle)

But computed 'load' will be 1.0

This whole avenrun[] thing is plain stupid anyway. The load should be something between 0 and 1 (per cpu), to get a precise idea of cpu_power used/unused. Nobody mentioned avenrun[] values on lkml in the last decade.

(I've removed the other CC:s for now to avoid annoying them - assuming removing them from the CC: list doesn't do that).

You're right, I've not looked at exactly how it's done. I do know that calling it early/late (by +/- 750ms/250ms) *once* on boot and every 7 weeks is going to have a tiny effect that will go away quickly.

My comment asking about why you say it's complex is about the patch, not the computation. After an initial sync the patch does not change how often the calc_load computation is run or how it works, it will still be run exactly the same way and every 5*HZ ticks as before (try adding a printk to report when the count value's been changed by the call to round_jiffies).

?

I'm not sure you realise the problem the patch fixes, which is that since 2.6.20 tasks can use round_jiffies to run "in around X seconds time" at a time when jiffies % HZ == 0 to avoid waking the CPU several times because of multiple timers firing at random. This affects the calc_load process really badly because it also tends to run at this time too. Moving calc_load to always run halfway between a second will solve the problem.

If you're sure no one here cares about the values then I'll submit a patch to remove them from /proc/loadavg (and wait it to get rejected). Until the whole concept of load average and how it should be better calculated and reported is solved the best that can be done is to not make things worse like round_jiffies has done.

*I* know the values are nowhere near perfect, but I made a change to a driver so that it uses round_jiffies to schedule status checking because it's appropriate and it makes the load average values sit at 1.00 even when idle - someone is going to complain about it and possibly take the time to find out why. If they bisect it, my patch will show up as the cause of the problem. (Assuming someone else uses this device; I sent an email to the accessrunner list once -rc2-mm1 was released asking for people to test it).

Simon Arlott

Hi!

Hmm, otoh this makes calc_load more expensive, power-wise, because it needs to wake the cpu once more?

Timetraveling, sorry.
Pavel

(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

This was something I was concerned about, it's hard to avoid since it shouldn't be run when scheduled tasks are which leaves running it before those tasks run as the only other option. To do that you need some idea of how long it's going to take to run.

Mar  1 22:36:17 redrum [  639.147319] calc_load(1) jiffies=311500 count=0 [start]
Mar  1 22:36:17 redrum [  639.147331] calc_load... count=5000 [run]
Mar  1 22:36:17 redrum [  639.147336] calc_load... count=5000 [finish]

While I really doubt the accuracy of these timings using printk (they vary a lot only going as low as 4 + 4µs), it does show that 1ms is plenty of time and that it *could* be scheduled at 1 tick before the second even at HZ=1000.

Of course then you miss out on ever catching tasks scheduled with round_jiffies since they'd need to run for a full second to affect it.

Also, calc_load with NO_HZ only appears to run every time the system needed to wake up for something else (calc_load itself is already able to handle this appropriately), so this isn't as much of a problem as it might seem. Someone whose CPU only needs to be woken up every 5s (or 4.5s for a round_jiffies task) will find their load being higher than it should be - but the current version does that already. (Mine doesn't stay below 0.5 with NO_HZ because of this).

Since Eric Dumazet seems to have disappeared for now I really need other people to comment on this too. Although you shouldn't literally time travel ;) (Date: Tue, 1 Jan 2002 03:05:07 +0000).

Simon Arlott

I suddenly realised that since calc_load was already being called at second + 1 tick, moving it back 1 tick should mean it gets called and allowed to finish before the other tasks:

[ 1392.745730] cxacru_poll_status jiffies=1064000 [start]
[ 1392.765628] cxacru_poll_status jiffies=1064020 [finish]
[ 1393.745284] calc_load(1) jiffies=1065000 count=5000 count=5000
[ 1393.745320] cxacru_poll_status jiffies=1065000 [start]
[ 1393.754412] cxacru_poll_status jiffies=1065009 [finish]

How will this work in the presence of multiple CPUs? Will the scheduled task be run on another CPU while calc_load is run? I don't have anything I can test it on.

However since 5*HZ is unlikely to be a factor of 2^32, as soon as jiffies wraps a second time it will no longer be in sync:

HZ=100 0 (time after jiffies wrap that calc_load will be run) HZ=100 4
HZ=100 8
HZ=100 12
HZ=100 16
...

It takes 3.2 *years* (increasing 40ms each time) at HZ=100 before it's back in sync. This would be ok for my task which is unlikely to ever take 40ms or more to complete, but could still hit other tasks.

HZ=1000 0
HZ=1000 704
HZ=1000 408
HZ=1000 112
HZ=1000 816
...

It takes 16.9 years (jumping around, only <=40ms 4 times) at HZ=1000 before it's back in sync.

Since calc_load is now running on the second already and this is preferable to different times during a second than other tasks, it can be rounded more easily than before:

kernel/timer.c | 6 ++++--

1 files changed, 4 insertions(+), 2 deletions(-)

index 6663a87..4abead0 100644
@@ -1226,17 +1226,19 @@ EXPORT_SYMBOL(avenrun);

static inline void calc_load(unsigned long ticks)

{
	unsigned long active_tasks; /* fixed-point */
	static int count = LOAD_FREQ;

	count -= ticks;
-	if (unlikely(count < 0)) {
+	if (unlikely(count <= 0)) {
		active_tasks = count_active_tasks();
		do {
			CALC_LOAD(avenrun[0], EXP_1, active_tasks);
			CALC_LOAD(avenrun[1], EXP_5, active_tasks);
			CALC_LOAD(avenrun[2], EXP_15, active_tasks);
			count += LOAD_FREQ;
-		} while (count < 0);
+		} while (count <= 0);
+
+		count = round_jiffies_relative(count);
	}
}

Simon Arlott

Sure confuses Thunderbird. It shows one unread message but "N" does not do anything...