O(1) count_active_tasks()

PATCH William Lee Irwin III 2 participants 6 messages May 26, 2002 – May 28, 2002 Scheduler

Share & tools

William Lee Irwin III

author

2002-05-26 03:51 UTC #0 lore raw

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

include/linux/sched.h +1 -0

diff -Nru a/include/linux/sched.h b/include/linux/sched.h
@@ -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>

kernel/sched.c +18 -0

diff -Nru a/kernel/sched.c b/kernel/sched.c
@@ -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;
 }

kernel/timer.c +1 ~~-11~~

diff -Nru a/kernel/timer.c b/kernel/timer.c
@@ -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;
 }
 
 /*

Robert Love

2002-05-26 22:18 UTC #1 lore raw

Quoted 4 lines · 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).

I like. Very clean.

One question...

kernel/sched.c line 337

Quoted 10 lines

kernel/sched.c +4 -0

 	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

William Lee Irwin III

author

2002-05-26 23:03 UTC #2 lore raw

In reply to William Lee Irwin III

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines
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).

Quoted 1 line · Robert Love

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).

Quoted 16 lines · Robert Love

One question...
kernel/sched.c line 337
Quoted 10 lines
kernel/sched.c +4 -0
 	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.

Quoted 7 lines · Robert Love

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

Robert Love

2002-05-28 15:33 UTC #3 lore raw

Quoted 6 lines · William Lee Irwin III

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.

Quoted 5 lines

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.

Quoted 4 lines

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

2002-05-28 18:08 UTC #4 lore raw

Quoted 3 lines · Robert Love

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

William Lee Irwin III

author

2002-05-28 18:56 UTC #5 lore raw

In reply to William Lee Irwin III

Quoted 10 lines · Robert Love

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