Skip to contentSkip to conversation

quell interactive feeding frenzy

RFC PATCH In review Mike Galbraith 5 participants 23 messages Apr 7, 2006 – Apr 13, 2006

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 quell interactive feeding frenzy

Greetings,

Problem: Wake-up -> cpu latency increases with the number of runnable tasks, ergo adding this latency to sleep_avg becomes increasingly potent as nr_running increases. This turns into a very nasty problem with as few as 10 httpd tasks doing round robin scheduling. The result is that you can only login with difficulty, and interactivity is nonexistent.

Solution: Restrict the amount of boost a task can receive from this mechanism, and disable the mechanism entirely when load is high. As always, there is a price for increasing fairness. In this case, the price seems worth it. It bought me a usable 2.6 apache server.

kernel/sched.c renamed from kernel/sched.c.org +7 -1
@@ -3012,14 +3012,20 @@ go_idle:
 	queue = array->queue + idx;
 	next = list_entry(queue->next, task_t, run_list);
 
-	if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
+	if (!rt_task(next) && interactive_sleep(next->sleep_type) &&
+			rq->nr_running < 1 + MAX_BONUS - CURRENT_BONUS(next)) {
 		unsigned long long delta = now - next->timestamp;
+		unsigned long max_delta;
 		if (unlikely((long long)(now - next->timestamp) < 0))
 			delta = 0;
 
 		if (next->sleep_type == SLEEP_INTERACTIVE)
 			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
+		max_delta = (1 + MAX_BONUS - CURRENT_BONUS(next)) * GRANULARITY;
+		max_delta = JIFFIES_TO_NS(max_delta);
+		if (delta > max_delta)
+			delta = max_delta;
 		array = next->array;
 		new_prio = recalc_task_prio(next, next->timestamp + delta);
 
#1 lore raw
Quoted 2 lines · Mike Galbraith

Problem:

I don't know what to do with all these patches you keep sending.

a) The other sched guys seem to be hiding and

b) I'm still sitting on smpnice, and I don't think that's had all its problems ironed out yet, so putting the interactivity things in there as well will complicate getting that sorted out.

But it's always nice to get email from you ;)

#2 lore raw
Quoted 11 lines · Andrew Morton
Quoted 2 lines · Mike Galbraith

Problem:

I don't know what to do with all these patches you keep sending.

a) The other sched guys seem to be hiding and

b) I'm still sitting on smpnice, and I don't think that's had all its problems ironed out yet, so putting the interactivity things in there as well will complicate getting that sorted out.

i think we should try Mike's patches after smpnice got ironed out. The extreme-starvation cases should be handled more or less correctly now by the minimal set of changes from Mike that are upstream (knock on wood), the singing-dancing add-ons can probably wait a bit and smpnice clearly has priority.

Ingo

#3 lore raw
Quoted 5 lines · Ingo Molnar

i think we should try Mike's patches after smpnice got ironed out. The extreme-starvation cases should be handled more or less correctly now by the minimal set of changes from Mike that are upstream (knock on wood), the singing-dancing add-ons can probably wait a bit and smpnice clearly has priority.

(I'm still trying to find ways to do less singing and dancing.)

This patch you may notice wasn't against an mm kernel. I was more or less separating this one from the others, because I consider this problem to be very severe. IMHO, this or something like it needs to get upstream soon.

-Mike

#4 lore raw
Quoted 7 lines · Mike Galbraith
Quoted 5 lines · Ingo Molnar

i think we should try Mike's patches after smpnice got ironed out. The extreme-starvation cases should be handled more or less correctly now by the minimal set of changes from Mike that are upstream (knock on wood), the singing-dancing add-ons can probably wait a bit and smpnice clearly has priority.

Quoted 6 lines

(I'm still trying to find ways to do less singing and dancing.)

This patch you may notice wasn't against an mm kernel. I was more or less separating this one from the others, because I consider this problem to be very severe. IMHO, this or something like it needs to get upstream soon.

Which is a fine observation but your code is changing every 2nd day. Which is also fine because code needs to evolve. However that's not really the way we push stuff upstream...

-ck

#5 lore raw
Quoted 10 lines · Con Kolivas
Quoted 9 lines · Mike Galbraith
Quoted 5 lines · Ingo Molnar

i think we should try Mike's patches after smpnice got ironed out. The extreme-starvation cases should be handled more or less correctly now by the minimal set of changes from Mike that are upstream (knock on wood), the singing-dancing add-ons can probably wait a bit and smpnice clearly has priority.

(I'm still trying to find ways to do less singing and dancing.)

Quoted 8 lines
Quoted 4 lines

This patch you may notice wasn't against an mm kernel. I was more or less separating this one from the others, because I consider this problem to be very severe. IMHO, this or something like it needs to get upstream soon.

Which is a fine observation but your code is changing every 2nd day. Which is also fine because code needs to evolve. However that's not really the way we push stuff upstream...

No, it's not changing much at all, though I wish it would. WRT this patch, you'll note that the mail subject contains the magical incantation [rfc] (didn't work). I care not one whit whether _my_ patch gets sent upstream or to the bit bucket. I care only that the problem gets solved, and preferably sooner than later.

-Mike

#6 lore raw
In reply to Andrew Morton
Quoted 5 lines · Andrew Morton
Quoted 2 lines · Mike Galbraith

Problem:

I don't know what to do with all these patches you keep sending.

Print and place in nearest dentist office? Either that or maybe bounce this one off the distcc problem in your copious spare time.

-Mike

#7 lore raw
In reply to Mike Galbraith
Quoted 8 lines · Mike Galbraith

Greetings,

Problem: Wake-up -> cpu latency increases with the number of runnable tasks, ergo adding this latency to sleep_avg becomes increasingly potent as nr_running increases. This turns into a very nasty problem with as few as 10 httpd tasks doing round robin scheduling. The result is that you can only login with difficulty, and interactivity is nonexistent.

Quoted 4 lines

Solution: Restrict the amount of boost a task can receive from this mechanism, and disable the mechanism entirely when load is high. As always, there is a price for increasing fairness. In this case, the price seems worth it. It bought me a usable 2.6 apache server.

Since this is an RFC, here's my comments :)

This mechanism is designed to convert on-runqueue waiting time into sleep. The basic reason is that when the system is loaded, every task is fighting for cpu even if they only want say 1% cpu which means they never sleep and are waiting on a runqueue instead of sleeping 99% of the time. What you're doing is exactly biasing against what this mechanism is in place for. You'll get the same effect by bypassing or removing it entirely. Should we do that instead?

-ck

#8 lore raw
Quoted 16 lines · Con Kolivas
Quoted 8 lines · Mike Galbraith

Greetings,

Problem: Wake-up -> cpu latency increases with the number of runnable tasks, ergo adding this latency to sleep_avg becomes increasingly potent as nr_running increases. This turns into a very nasty problem with as few as 10 httpd tasks doing round robin scheduling. The result is that you can only login with difficulty, and interactivity is nonexistent.

Quoted 4 lines

Solution: Restrict the amount of boost a task can receive from this mechanism, and disable the mechanism entirely when load is high. As always, there is a price for increasing fairness. In this case, the price seems worth it. It bought me a usable 2.6 apache server.

Since this is an RFC, here's my comments :)

Quoted 7 lines

This mechanism is designed to convert on-runqueue waiting time into sleep. The basic reason is that when the system is loaded, every task is fighting for cpu even if they only want say 1% cpu which means they never sleep and are waiting on a runqueue instead of sleeping 99% of the time. What you're doing is exactly biasing against what this mechanism is in place for. You'll get the same effect by bypassing or removing it entirely. Should we do that instead?

Heck no. That mechanism is just as much about fairness as it is about intertactivity, and as such is just fine and dandy in my book... once it's toned down a bit^H^H^Htruckload. What I'm doing isn't biasing against the intent, I'm merely straightening the huge bend in favor of interactive tasks who get this added boost over and over again, and restricting the general effect to something practical.

Just look at what that mechanism does now with a 10 deep queue. Every dinky sleep can have an absolutely huge gob added to it, the exact worst case number depends on how many cpus you have and whatnot. Start a slew of tasks, and you are doomed to have every task that sleeps for the tiniest bit pegged at max interactive.

Maybe what I did isn't the best that can be done, but something has to be done about that. It is very b0rken under heavy load.

-Mike

#9 lore raw
Quoted 9 lines · Mike Galbraith
Quoted 7 lines · Con Kolivas

This mechanism is designed to convert on-runqueue waiting time into sleep. The basic reason is that when the system is loaded, every task is fighting for cpu even if they only want say 1% cpu which means they never sleep and are waiting on a runqueue instead of sleeping 99% of the time. What you're doing is exactly biasing against what this mechanism is in place for. You'll get the same effect by bypassing or removing it entirely. Should we do that instead?

Quoted 6 lines

Heck no. That mechanism is just as much about fairness as it is about intertactivity, and as such is just fine and dandy in my book... once it's toned down a bit^H^H^Htruckload. What I'm doing isn't biasing against the intent, I'm merely straightening the huge bend in favor of interactive tasks who get this added boost over and over again, and restricting the general effect to something practical.

Have you actually tried without that mechanism? No compromise will be correct there for fairness one way or the other. There simply is no way to tell if a task is really sleeping or really just waiting on a runqueue. That's why Ingo weighted the tasks waking from interrupts more because of their likely intent. It's still a best guess scenario (which I'm sure you know). Wouldn't it be lovely to have a system that didn't guess and had simple sleep/wake cpu usage based heuristics? Oh well.

Quoted 5 lines

Just look at what that mechanism does now with a 10 deep queue. Every dinky sleep can have an absolutely huge gob added to it, the exact worst case number depends on how many cpus you have and whatnot. Start a slew of tasks, and you are doomed to have every task that sleeps for the tiniest bit pegged at max interactive.

I'm quite aware of the effect it has :)

Quoted 2 lines

Maybe what I did isn't the best that can be done, but something has to be done about that. It is very b0rken under heavy load.

Your compromise is as good as any.

Signature · 1 line
-ck
#10 lore raw
Quoted 10 lines · Con Kolivas
Quoted 9 lines · Mike Galbraith
Quoted 7 lines · Con Kolivas

This mechanism is designed to convert on-runqueue waiting time into sleep. The basic reason is that when the system is loaded, every task is fighting for cpu even if they only want say 1% cpu which means they never sleep and are waiting on a runqueue instead of sleeping 99% of the time. What you're doing is exactly biasing against what this mechanism is in place for. You'll get the same effect by bypassing or removing it entirely. Should we do that instead?

Quoted 8 lines
Quoted 6 lines

Heck no. That mechanism is just as much about fairness as it is about intertactivity, and as such is just fine and dandy in my book... once it's toned down a bit^H^H^Htruckload. What I'm doing isn't biasing against the intent, I'm merely straightening the huge bend in favor of interactive tasks who get this added boost over and over again, and restricting the general effect to something practical.

Have you actually tried without that mechanism?

Yes. We're better off with it than without.

Quoted 7 lines
Quoted 5 lines

Just look at what that mechanism does now with a 10 deep queue. Every dinky sleep can have an absolutely huge gob added to it, the exact worst case number depends on how many cpus you have and whatnot. Start a slew of tasks, and you are doomed to have every task that sleeps for the tiniest bit pegged at max interactive.

I'm quite aware of the effect it has :)

Ok. Do we then agree that it makes 2.6 unusable for small servers, and that this constitutes a serious problem? :)

Quoted 4 lines
Quoted 2 lines

Maybe what I did isn't the best that can be done, but something has to be done about that. It is very b0rken under heavy load.

Your compromise is as good as any.

Ok.

-Mike

#11 lore raw
Quoted 5 lines · Mike Galbraith
Quoted 4 lines · Con Kolivas
Quoted 2 lines

Maybe what I did isn't the best that can be done, but something has to be done about that. It is very b0rken under heavy load.

Your compromise is as good as any.

My tree with that change doing make -j100. That change is what's keeping it half sane.

top - 16:58:01 up 21 min, 6 users, load average: 119.54, 96.91, 50.42

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
20902 root      22   0 20580  17m 3680 R  4.4  1.7   0:00.41 cc1
21145 root      19   0 18224  14m 3688 R  4.4  1.5   0:00.30 cc1
22287 root      17   0 12668 7872 1988 R  4.4  0.8   0:00.11 cc1
21238 root      22   0 17020  13m 3724 R  4.0  1.4   0:00.32 cc1
21116 root      22   0 18048  13m 2468 R  4.0  1.3   0:00.30 cc1
21531 root      19   0 25688  22m 3744 R  4.0  2.2   0:01.03 cc1
21608 root      19   0 22512  18m 3720 R  4.0  1.9   0:00.60 cc1
21703 root      19   0 20372  17m 3752 R  4.0  1.7   0:00.72 cc1
21711 root      19   0 23044  19m 3748 R  4.0  1.9   0:00.81 cc1
21755 root      19   0 18072  14m 3696 R  4.0  1.4   0:00.42 cc1
21759 root      19   0 18332  14m 3712 R  4.0  1.5   0:00.43 cc1
22148 root      18   0 11484 6736 1976 R  3.2  0.7   0:00.08 cc1
21913 root      18   0 10304 5300 1952 R  2.0  0.5   0:00.05 cc1
22040 root      18   0 10304 5220 1952 R  2.0  0.5   0:00.05 cc1
22063 root      18   0 10296 5416 1976 R  2.0  0.5   0:00.05 cc1
22065 root      18   0 10300 5388 1976 R  2.0  0.5   0:00.05 cc1
22122 root      18   0 10444 5448 1952 R  2.0  0.5   0:00.05 cc1
22150 root      18   0 10444 5384 1952 R  2.0  0.5   0:00.05 cc1
20771 root      19   0 21412  17m 3740 D  1.6  1.8   0:00.67 cc1
#12 lore raw
In reply to Mike Galbraith
Quoted 2 lines · Mike Galbraith

Ok. Do we then agree that it makes 2.6 unusable for small servers, and that this constitutes a serious problem? :)

You sure? I may be down there in userspace dirt with the other actual Linux users, but I hadn't noticed.

Signature · 2 lines
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services
#13 lore raw
Quoted 6 lines · bert hubert
Quoted 2 lines · Mike Galbraith

Ok. Do we then agree that it makes 2.6 unusable for small servers, and that this constitutes a serious problem? :)

You sure? I may be down there in userspace dirt with the other actual Linux users, but I hadn't noticed.

Ok, unusable may be overstated. Nonetheless, that bit of code causes serious problems. It makes my little PIII/500 test box trying to fill one 100Mbit local network unusable. That is not overstated.

-Mike

#14 lore raw
Quoted 3 lines · Mike Galbraith

Ok, unusable may be overstated. Nonetheless, that bit of code causes serious problems. It makes my little PIII/500 test box trying to fill one 100Mbit local network unusable. That is not overstated.

If you try to make a PIII/500 fill 100mbit of TCP/IP using lots of different processes, that IS a corner load.

I'm sure you can fix this (rare) workload but are you very sure you are not killing off performance for other situations?

I get flashbacks to the old days of the VM where we had lots patches around that would all solve (more or less) real problems, but never all at the same time..

Signature · 2 lines
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services
#15 lore raw
Quoted 10 lines · bert hubert
Quoted 3 lines · Mike Galbraith

Ok, unusable may be overstated. Nonetheless, that bit of code causes serious problems. It makes my little PIII/500 test box trying to fill one 100Mbit local network unusable. That is not overstated.

If you try to make a PIII/500 fill 100mbit of TCP/IP using lots of different processes, that IS a corner load.

I'm sure you can fix this (rare) workload but are you very sure you are not killing off performance for other situations?

Rare? What exactly is rare about a number of tasks serving data? I don't care if it's a P4 serving gigabit. If you have to divide your server into pieces (you do, and you know it) you're screwed.

Quoted 3 lines

I get flashbacks to the old days of the VM where we had lots patches around that would all solve (more or less) real problems, but never all at the same time..

I choose to take the high road here, and will not respond.

-Mike

#16 lore raw
Quoted 3 lines · Mike Galbraith

Rare? What exactly is rare about a number of tasks serving data? I don't care if it's a P4 serving gigabit. If you have to divide your server into pieces (you do, and you know it) you're screwed.

You've not detailed your load. I assume it consists of lots of small files being transferred over 10 apache processes? I also assume you max out your system using apachebench?

In general, Linux systems are not maxed out as they will disappoint that way (like any system running with id=0).

So yes, what you do is a 'rare load' as anybody trying to do this will disappoint his users.

And any tweak you make to the scheduler this way is bound to affect another load.

Bert

Signature · 2 lines
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services
#17 lore raw
Quoted 8 lines · bert hubert
Quoted 3 lines · Mike Galbraith

Rare? What exactly is rare about a number of tasks serving data? I don't care if it's a P4 serving gigabit. If you have to divide your server into pieces (you do, and you know it) you're screwed.

You've not detailed your load. I assume it consists of lots of small files being transferred over 10 apache processes? I also assume you max out your system using apachebench?

It's just retrieving the directory, so it's all cached. Yes, it's ab.

If it had to hit disk constantly, I'd probably be able to login, because the stock scheduler blocks IO bound tasks from achieving max priority.

Quoted 5 lines

In general, Linux systems are not maxed out as they will disappoint that way (like any system running with id=0).

So yes, what you do is a 'rare load' as anybody trying to do this will disappoint his users.

Ok, it's rare... if you buy your hardware 10 sizes too large ;-)

The load just doesn't matter though, this apache load is by the scheduler's own standard a cpu hog. If you eliminate the man made sleep, those httpds drop right down where they belong.

Quoted 2 lines

And any tweak you make to the scheduler this way is bound to affect another load.

It's not a tweak, it's a bug fix, and course it will affect other loads. As things stand, that code is contributing to interactivity, and fairness, but is also contributing heavily to grotesque _unfairness_ to the point of starvation in the extreme.

You may not like the testcase, but it remains a bug exposing testcase.

-Mike

#18 lore raw
Quoted 1 line · Mike Galbraith

You may not like the testcase, but it remains a bug exposing testcase.

That proposed change just became moot. Changing to pulling a 16k file instead of the 20k directory makes it unmanageable with that change, with it completely disabled, and even with a full throttling tree.

Oh well, I wanted to try run limiting queues anyway I guess (sigh).

-Mike

#19 lore raw
Quoted 8 lines · Mike Galbraith
Quoted 1 line · Mike Galbraith

You may not like the testcase, but it remains a bug exposing testcase.

That proposed change just became moot. Changing to pulling a 16k file instead of the 20k directory makes it unmanageable with that change, with it completely disabled, and even with a full throttling tree.

Oh well, I wanted to try run limiting queues anyway I guess (sigh).

Something like below?

This way also allowed me to eliminate the interactive agony of an array switch when at 100% cpu. Seems to work well. No more agony, only tiny pin pricks.

Anyway, interested readers will find a copy of irman2.c, which is nice
for testing interactive starvation, attached. The effect is most
noticeable with something like bonnie, which otherwise has zero chance against irman2. Just about anything will do though. Trying to fire up Amarok is good for a chuckle. Whatever. (if anyone plays with irman2 on 2.6.16 or below, call it with -S 1)

-Mike

kernel/sched.c renamed from kernel/sched.c.org +64 -4
@@ -2578,6 +2578,52 @@ void account_steal_time(struct task_stru
 		cpustat->steal = cputime64_add(cpustat->steal, tmp);
 }
 
+#define TASK_LATENCY(p, nr_running) \
+	JIFFIES_TO_NS(SCALE(USER_PRIO(p->prio), 39, nr_running * \
+	DEF_TIMESLICE + STARVATION_LIMIT))
+
+static inline void requeue_starving(runqueue_t *rq, unsigned long long now)
+{
+	prio_array_t *array = rq->active;
+	unsigned long *bitmap = array->bitmap;
+	int prio = rq->curr->prio, idx = prio + 1;
+	int noninteractive = 0, nr_running = rq->active->nr_active;
+
+repeat:
+	while ((idx = find_next_bit(bitmap, MAX_PRIO, idx)) < MAX_PRIO) {
+		struct list_head *queue = array->queue + idx;
+		task_t *p = list_entry(queue->next, task_t, run_list);
+		unsigned long latency = TASK_LATENCY(p, nr_running);
+
+		if (!TASK_INTERACTIVE(p))
+			noninteractive = idx;
+
+		if (!batch_task(p) && p->timestamp + latency < now) {
+			dequeue_task(p, p->array);
+			if (p->array == rq->active && p->prio > prio)
+				p->prio = prio;
+			enqueue_task(p, rq->active);
+
+			if (array == rq->expired) {
+				int idx = find_next_bit(bitmap, MAX_PRIO, 0);
+				rq->best_expired_prio = idx;
+				if (idx == MAX_PRIO)
+					rq->expired_timestamp = 0;
+			} else return;
+		}
+		idx++;
+	}
+	if (rq->expired_timestamp && array == rq->active &&
+			(!noninteractive || EXPIRED_STARVING(rq))) {
+		array = rq->expired;
+		bitmap = array->bitmap;
+		nr_running = rq->nr_running;
+		idx = 0;
+		goto repeat;
+	}
+
+}
+
 /*
  * This function gets called by the timer code, with HZ frequency.
  * We call it with interrupts disabled.
@@ -2632,6 +2678,11 @@ void scheduler_tick(void)
 		goto out_unlock;
 	}
 	if (!--p->time_slice) {
+		/*
+		 * Slip starving tasks into the stream.
+		 */
+		if (rq->nr_running > 1)
+			requeue_starving(rq, now);
 		dequeue_task(p, rq->active);
 		set_tsk_need_resched(p);
 		p->prio = effective_prio(p);
@@ -2640,7 +2691,7 @@ void scheduler_tick(void)
 
 		if (!rq->expired_timestamp)
 			rq->expired_timestamp = jiffies;
-		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
+		if (!TASK_INTERACTIVE(p)) {
 			enqueue_task(p, rq->expired);
 			if (p->static_prio < rq->best_expired_prio)
 				rq->best_expired_prio = p->static_prio;
@@ -2935,9 +2986,12 @@ need_resched_nonpreemptible:
 	schedstat_inc(rq, sched_cnt);
 	now = sched_clock();
 	if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
+		int active = rq->active->nr_active;
 		run_time = now - prev->timestamp;
 		if (unlikely((long long)(now - prev->timestamp) < 0))
 			run_time = 0;
+		else if (active > 1)
+			run_time *= min(active, 1 + MAX_BONUS);
 	} else
 		run_time = NS_MAX_SLEEP_AVG;
 
@@ -2945,7 +2999,7 @@ need_resched_nonpreemptible:
 	 * Tasks charged proportionately less run_time at high sleep_avg to
 	 * delay them losing their interactive status
 	 */
-	run_time /= (CURRENT_BONUS(prev) ? : 1);
+	run_time /= 1 + CURRENT_BONUS(prev);
 
 	spin_lock_irq(&rq->lock);
 
@@ -3012,18 +3066,24 @@ go_idle:
 	queue = array->queue + idx;
 	next = list_entry(queue->next, task_t, run_list);
 
-	if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
+	if (!rt_task(next) && interactive_sleep(next->sleep_type) &&
+			rq->nr_running < 1 + MAX_BONUS - CURRENT_BONUS(next)) {
 		unsigned long long delta = now - next->timestamp;
+		unsigned long max_delta;
 		if (unlikely((long long)(now - next->timestamp) < 0))
 			delta = 0;
 
 		if (next->sleep_type == SLEEP_INTERACTIVE)
 			delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
 
+		max_delta = (1 + MAX_BONUS - CURRENT_BONUS(next)) * GRANULARITY;
+		max_delta = JIFFIES_TO_NS(max_delta);
+		if (delta > max_delta)
+			delta = max_delta;
 		array = next->array;
 		new_prio = recalc_task_prio(next, next->timestamp + delta);
 
-		if (unlikely(next->prio != new_prio)) {
+		if (unlikely(next->prio > new_prio)) {
 			dequeue_task(next, array);
 			next->prio = new_prio;
 			enqueue_task(next, array);

/*
* irman by Davide Libenzi ( irman load generator )
* Copyright (C) 2003 Davide Libenzi
*

 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

*
* Davide Libenzi <[email protected]>
*
*/

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/time.h>
#include <sys/socket.h>
#include <sys/signal.h>
#include <sys/resource.h>
#include <sys/socket.h>
#include <fcntl.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>

#define BUFSIZE (1024 * 32)

static int *pipes, *child;
static int num_pipes, num_active, num_child, use_socket; static unsigned long burn_ms;
static char buf1[BUFSIZE], buf2[BUFSIZE]; static volatile sig_atomic_t run = 1;
pid_t parent;

static void signal_all(int signum) {
	if (getpid() == parent) {
		while (num_child >= 0) {
			kill(child[num_child], SIGKILL);
			num_child--;
		}
		exit(0);
	} else if (signum == SIGKILL || getppid() == 1)
		run = 0;
}
unsigned long long getustime(void) {
	struct timeval tm;

	gettimeofday(&tm, NULL);
	return (unsigned long long) tm.tv_sec * 1000ULL + (unsigned long long) tm.tv_usec / 1000ULL;
}
int burn_ms_cpu(unsigned long ms) {
	int i, cmp = 0;
	unsigned long long ts;

	ts = getustime();
	do {
		for (i = 0; i < 4; i++)
			cmp += memcmp(buf1, buf2, BUFSIZE);
	} while (ts + ms > getustime());
	return cmp;
}
pid_t hog_process(void) {
	pid_t pid;

	if (!(pid = fork())) {
		while (run) {
			printf("HOG running %u\n", time(NULL));
			burn_ms_cpu(burn_ms);
		}
		exit(0);
	}
	return pid;
}
pid_t irman_process(int n) {
	int nn;
	pid_t pid;
	u_char ch;

	if (!(pid = fork())) {
		if ((nn = n + num_active) >= num_pipes)
			nn -= num_pipes;
		while (run) {
			printf("reading %u\n", n);
			read(pipes[2 * n], &ch, 1);
			burn_ms_cpu(burn_ms);
			printf("writing %u\n", nn);
			write(pipes[2 * nn + 1], "s", 1);
		}
		exit(0);
	}
	return pid;
}

int main (int argc, char **argv) {

	struct rlimit rl;
	int i, c;
	long work;
	int *cp, run_secs = 0;
	extern char *optarg;
	struct sigaction action;

	parent = getpid();
	num_pipes = 40;
	num_active = 1;
	burn_ms = 300;
	use_socket = 0;
	while ((c = getopt(argc, argv, "n:b:a:s:S:")) != -1) {
		switch (c) {
		case 'n':
			num_pipes = atoi(optarg);
			break;
		case 'b':
			burn_ms = atoi(optarg);
			break;
		case 'a':
			num_active = atoi(optarg);
			break;
		case 's':
			run_secs = 1 + atoi(optarg);
			break;
		case 'S':
			use_socket = 1;
			break;
		default:
			fprintf(stderr, "Illegal argument \"%c\"\n", c);
			exit(1);
		}
	}

	rl.rlim_cur = rl.rlim_max = num_pipes * 2 + 50;
	if (setrlimit(RLIMIT_NOFILE, &rl) == -1) {
		perror("setrlimit"); 
		exit(1);
	}

	pipes = calloc(num_pipes * 2, sizeof(int));
	if (pipes == NULL) {
		perror("malloc");
		exit(1);
	}

	child = calloc(num_pipes, sizeof(int));
	if (child == NULL) {
		perror("malloc");
		exit(1);
	}

	for (cp = pipes, i = 0; i < num_pipes; i++, cp += 2) {
		if (!use_socket) {
			if(pipe(cp) == -1) {
				perror("pipe");
				exit(1);
			}
		} else if (socketpair(AF_UNIX, SOCK_STREAM, 0, cp) == -1) {
			perror("socketpair");
			exit(1);
		}
	}

	memset(buf1, 'f', sizeof(buf1));
	memset(buf2, 'f', sizeof(buf2));

	sigemptyset(&action.sa_mask);
	/* establish termination handler */
	action.sa_handler = signal_all;
	action.sa_flags = SA_NODEFER;
	if (sigaction(SIGTERM, &action, NULL) == -1) {
		perror("Could not install signal handler");
		exit(1);
	}

	for (i = 0; i < num_pipes; i++)
		child[i] = irman_process(i);

	child[i] = hog_process();
	num_child = i;

	for (i = 0; i < num_active; i++)
		write(pipes[2 * i + 1], "s", 1);

	while (--run_secs)
		sleep(1);
	signal_all(SIGKILL);
	exit(0);
}
#20 lore raw
Quoted 10 lines · Mike Galbraith

This way also allowed me to eliminate the interactive agony of an array switch when at 100% cpu. Seems to work well. No more agony, only tiny pin pricks.

Anyway, interested readers will find a copy of irman2.c, which is nice
for testing interactive starvation, attached. The effect is most
noticeable with something like bonnie, which otherwise has zero chance against irman2. Just about anything will do though. Trying to fire up Amarok is good for a chuckle. Whatever. (if anyone plays with irman2 on 2.6.16 or below, call it with -S 1)

Comments.

Quoted 2 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -0
+repeat:
+	while ((idx = find_next_bit(bitmap, MAX_PRIO, idx)) < MAX_PRIO) {

...

Quoted 1 line
kernel/sched.c renamed from kernel/sched.c.org +1 -0
+		goto repeat;

...

kernel/sched.c void scheduler_tick(void) · line 2685

Quoted 2 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -0
+               if (rq->nr_running > 1)
+                       requeue_starving(rq, now);

An O(n) function in scheduler_tick is probably not the way to tackle this.

Signature · 1 line
-ck
#21 lore raw
Quoted 13 lines · Con Kolivas
Quoted 4 lines · Mike Galbraith

This way also allowed me to eliminate the interactive agony of an array switch when at 100% cpu. Seems to work well. No more agony, only tiny pin pricks.

Comments.

Quoted 2 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -0
+repeat:
+	while ((idx = find_next_bit(bitmap, MAX_PRIO, idx)) < MAX_PRIO) {

...

Quoted 8 lines
Quoted 1 line
kernel/sched.c renamed from kernel/sched.c.org +1 -0
+		goto repeat;

...

kernel/sched.c void scheduler_tick(void) · line 2685

Quoted 2 lines
kernel/sched.c renamed from kernel/sched.c.org +2 -0
+               if (rq->nr_running > 1)
+                       requeue_starving(rq, now);

An O(n) function in scheduler_tick is probably not the way to tackle this.

Why not? It's one quick-like-bunny stop per occupied queue per slice completion.

-Mike

#22 lore raw
In reply to bert hubert
Quoted 7 lines · bert hubert
Quoted 3 lines · Mike Galbraith

Ok, unusable may be overstated. Nonetheless, that bit of code causes serious problems. It makes my little PIII/500 test box trying to fill one 100Mbit local network unusable. That is not overstated.

If you try to make a PIII/500 fill 100mbit of TCP/IP using lots of different processes, that IS a corner load.

I'm trying to wrap my head around this statement, and failing. I have 10 tasks, I divide 100mbs/10 (_very_ modest concurrency) , and I can't even login.

-Mike