O(1) count_active_tasks()

O(1) count_active_tasks()

[William Lee Irwin III]

rml, I heard you're interested in this, but regardless, here it is.
AFAICT it computes a faithful load average. Against latest 2.5.18 bk.
rml, don't worry about stomping on this if you need the counters
ticking for something else and you can do the same thing(s).

mingo, I've cc:'d you on this because it touches the scheduler.

Also available from:

ftp://ftp.kernel.org/pub/linux/kernel/people/wli/task_mgmt/count_active_tasks-2.5.18-1

This patch is part of my for_each_tasks() project.


Cheers,
Bill


diff -Nru a/include/linux/sched.h b/include/linux/sched.h
--- a/include/linux/sched.h	Sat May 25 20:29:51 2002
+++ b/include/linux/sched.h	Sat May 25 20:29:51 2002
@@ -80,6 +80,7 @@
 extern int nr_threads;
 extern int last_pid;
 extern unsigned long nr_running(void);
+extern unsigned long nr_uninterruptible(void);
 
 #include <linux/time.h>
 #include <linux/param.h>
diff -Nru a/kernel/sched.c b/kernel/sched.c
--- a/kernel/sched.c	Sat May 25 20:29:51 2002
+++ b/kernel/sched.c	Sat May 25 20:29:51 2002
@@ -133,6 +133,7 @@
 	spinlock_t lock;
 	spinlock_t frozen;
 	unsigned long nr_running, nr_switches, expired_timestamp;
+	signed long nr_uninterruptible;
 	task_t *curr, *idle;
 	prio_array_t *active, *expired, arrays[2];
 	int prev_nr_running[NR_CPUS];
@@ -240,6 +241,8 @@
 static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
 {
 	rq->nr_running--;
+	if (p->state == TASK_UNINTERRUPTIBLE)
+		rq->nr_uninterruptible++;
 	dequeue_task(p, p->array);
 	p->array = NULL;
 }
@@ -319,11 +322,16 @@
 {
 	unsigned long flags;
 	int success = 0;
+	int uninterruptible = 0;
 	runqueue_t *rq;
 
 	rq = task_rq_lock(p, &flags);
+	if (p->state == TASK_UNINTERRUPTIBLE)
+		uninterruptible = 1;
 	p->state = TASK_RUNNING;
 	if (!p->array) {
+		if (uninterruptible)
+			rq->nr_uninterruptible--;
 		activate_task(p, rq);
 		if (p->prio < rq->curr->prio)
 			resched_task(rq->curr);
@@ -425,6 +433,16 @@
 
 	for (i = 0; i < smp_num_cpus; i++)
 		sum += cpu_rq(cpu_logical_map(i))->nr_running;
+
+	return sum;
+}
+
+unsigned long nr_uninterruptible(void)
+{
+	unsigned long i, sum = 0;
+
+	for (i = 0; i < smp_num_cpus; i++)
+		sum += cpu_rq(cpu_logical_map(i))->nr_uninterruptible;
 
 	return sum;
 }
diff -Nru a/kernel/timer.c b/kernel/timer.c
--- a/kernel/timer.c	Sat May 25 20:29:51 2002
+++ b/kernel/timer.c	Sat May 25 20:29:51 2002
@@ -597,17 +597,7 @@
  */
 static unsigned long count_active_tasks(void)
 {
-	struct task_struct *p;
-	unsigned long nr = 0;
-
-	read_lock(&tasklist_lock);
-	for_each_task(p) {
-		if ((p->state == TASK_RUNNING ||
-		     (p->state & TASK_UNINTERRUPTIBLE)))
-			nr += FIXED_1;
-	}
-	read_unlock(&tasklist_lock);
-	return nr;
+	return (nr_running() + nr_uninterruptible()) * FIXED_1;
 }
 
 /*

Re: O(1) count_active_tasks()

[Robert Love]

On Sat, 2002-05-25 at 20:51, William Lee Irwin III wrote:
> rml, I heard you're interested in this, but regardless, here it is.
> AFAICT it computes a faithful load average. Against latest 2.5.18 bk.
> rml, don't worry about stomping on this if you need the counters
> ticking for something else and you can do the same thing(s).

I like.  Very clean.

One question...

>  	rq = task_rq_lock(p, &flags);
> +	if (p->state == TASK_UNINTERRUPTIBLE)
> +		uninterruptible = 1;
>  	p->state = TASK_RUNNING;
>  	if (!p->array) {
> +		if (uninterruptible)
> +			rq->nr_uninterruptible--;
>  		activate_task(p, rq);
>  		if (p->prio < rq->curr->prio)
>  			resched_task(rq->curr);

Why only decrement nr_uninterruptible if it is not already on a
runqueue?  I suspect because then you assume it is a spurious wakeup and
did not have a corresponding deactivate_task?  Same reason we increment
nr_running in activate_task and not here, I suspect... makes sense.

One thought on a quick way to test if the new method is returning
accurate results would be to leave the current count_active_task code
and then add:

	if (nr != (nr_running() + nr_uninterruptible()))
		printk("Danger Will Robinson!\n");

but you probably already did something similar.

	Robert Love

Re: O(1) count_active_tasks()

[William Lee Irwin III]

On Sat, 2002-05-25 at 20:51, William Lee Irwin III wrote:
>> rml, I heard you're interested in this, but regardless, here it is.
>> AFAICT it computes a faithful load average. Against latest 2.5.18 bk.
>> rml, don't worry about stomping on this if you need the counters
>> ticking for something else and you can do the same thing(s).

On Sun, May 26, 2002 at 03:17:52PM -0700, Robert Love wrote:
> I like.  Very clean.

Thanks, I took some time to go over it and make it so, as I don't
really do scheduling, I just needed a statistic there for this. It's
not actually claimed to have any optimization value (though it may as
a side-effect), it only addresses a pet peeve of mine. I originally
tried avoiding sched.c by having set_current_state() tick per-cpu
counters but that caused enormous code bloat (or did as I wrote it).


On Sun, May 26, 2002 at 03:17:52PM -0700, Robert Love wrote:
> One question...
>>  	rq = task_rq_lock(p, &flags);
>> +	if (p->state == TASK_UNINTERRUPTIBLE)
>> +		uninterruptible = 1;
>>  	p->state = TASK_RUNNING;
>>  	if (!p->array) {
>> +		if (uninterruptible)
>> +			rq->nr_uninterruptible--;
>>  		activate_task(p, rq);
>>  		if (p->prio < rq->curr->prio)
>>  			resched_task(rq->curr);
>
> Why only decrement nr_uninterruptible if it is not already on a
> runqueue?  I suspect because then you assume it is a spurious wakeup and
> did not have a corresponding deactivate_task?  Same reason we increment
> nr_running in activate_task and not here, I suspect... makes sense.

When it was not there load averages were dramatically unfaithful, and I
traced down the cause of that to this branch.


On Sun, May 26, 2002 at 03:17:52PM -0700, Robert Love wrote:
> One thought on a quick way to test if the new method is returning
> accurate results would be to leave the current count_active_task code
> and then add:
> 	if (nr != (nr_running() + nr_uninterruptible()))
> 		printk("Danger Will Robinson!\n");
> but you probably already did something similar.
> 	Robert Love

This is an approximate method. I did not collect detailed statistics on
how widely it varied from the prior method, though I did manually check
the results against mainline for large variations or gross unfaithfulness.
If you'd like to hold off on this until I do so, that's fine. I can get
back to my SMP targets Tuesday and follow up then.

Going back and looking at it, weaker memory consistency models may want
the increment/decrement to be atomic operations, which would probably
want some migration code to keep the counters positive. I can arrange
that for a follow-up as well.


Thanks,
Bill

Re: O(1) count_active_tasks()

[Robert Love]

On Sun, 2002-05-26 at 16:03, William Lee Irwin III wrote:

> Thanks, I took some time to go over it and make it so, as I don't
> really do scheduling, I just needed a statistic there for this. It's
> not actually claimed to have any optimization value (though it may as
> a side-effect), it only addresses a pet peeve of mine. I originally
> tried avoiding sched.c by having set_current_state() tick per-cpu
> counters but that caused enormous code bloat (or did as I wrote it).

Yah, set_current_state is inlined so it would lead to a bit of code
bloat.

> This is an approximate method. I did not collect detailed statistics on
> how widely it varied from the prior method, though I did manually check
> the results against mainline for large variations or gross unfaithfulness.
> If you'd like to hold off on this until I do so, that's fine. I can get
> back to my SMP targets Tuesday and follow up then.

If I get a chance, I'll run some tests on my dual 2.5 machine and see if
they match.  But I would not let that stop anything ... this is mergable
in 2.5 imo.

One thing I notice is the patch only increments in one case:

	TASK_RUNNING -> TASK_UNINTERRUPTIBLE

whether we ever go -> TASK_UNINTERRUPTIBLE from a state other than
running I am unsure.

> Going back and looking at it, weaker memory consistency models may want
> the increment/decrement to be atomic operations, which would probably
> want some migration code to keep the counters positive. I can arrange
> that for a follow-up as well.

Personally, I would not worry about this.  This is only a statistic
after all - I am more interested in whether we are properly accounting
for everything in general.  Screw weak memory consistency computers <g>
- they need to fix nr_running too, anyhow.

	Robert Love

Re: O(1) count_active_tasks()

[Robert Love]

On Tue, 2002-05-28 at 08:33, Robert Love wrote:

> If I get a chance, I'll run some tests on my dual 2.5 machine and see if
> they match.  But I would not let that stop anything ... this is mergable
> in 2.5 imo.

Well, I did some tests.  I changed count_active_tasks to calculate using
both methods and whine if they did not match.  I then put the machine
under extreme load with a lot of I/O.  Finally, I ran `uptime(1)' in a
tight loop and watched the console.

Over a long period of constant count_active_tasks calls via `uptime(1)',
I had only a couple messages.  This is most likely <=1% of the calls and
in each case we were one to high with the new method (140 vs 141, for
example).

Not sure why, or if it is even us or nr_running() or even the old method
that is off ... but who cares.  It is a statistic.

	Robert Love

Re: O(1) count_active_tasks()

[William Lee Irwin III]

On Tue, May 28, 2002 at 11:08:35AM -0700, Robert Love wrote:
> Well, I did some tests.  I changed count_active_tasks to calculate using
> both methods and whine if they did not match.  I then put the machine
> under extreme load with a lot of I/O.  Finally, I ran `uptime(1)' in a
> tight loop and watched the console.
> Over a long period of constant count_active_tasks calls via `uptime(1)',
> I had only a couple messages.  This is most likely <=1% of the calls and
> in each case we were one to high with the new method (140 vs 141, for
> example).
> Not sure why, or if it is even us or nr_running() or even the old method
> that is off ... but who cares.  It is a statistic.


Thanks a million for doing some independent testing! I should have
been more clear about the fact that it was an approximate method, and
that it varies from mainline occasionally and slightly. But this is the
nature of the patch I proposed.


Thanks,
Bill