Skip to contentSkip to conversation

time slice cfq comments

DISCUSSION Con Kolivas 3 participants 4 messages Dec 10, 2004 – Dec 11, 2004

lore
Share & tools
lore
#0 lore raw

Hi Jens

Just thought I'd make a few comments about some of the code in your time sliced cfq.

+ if (p->array)
+ return min(cpu_curr(task_cpu(p))->time_slice,
+ (unsigned int)MAX_SLEEP_AVG);

MAX_SLEEP_AVG is basically 10 * the average time_slice so this will always return task_cpu(p)->time_slice as the min value (except for the race you described in your comments). What you probably want is

+ return min(cpu_curr(task_cpu(p))->time_slice,
+ (unsigned int)DEF_TIMESLICE);

Further down you do:
+ /*
+ * for blocked tasks, return half of the average sleep time.
+ * (because this is the average sleep-time we'll see if we
+ * sample the period randomly.)
+ */
+ return NS_TO_JIFFIES(p->sleep_avg) / 2;

unfortunately p->sleep_avg is a non-linear value (weighted upwards towards MAX_SLEEP_AVG). I suspect here you want

+ return NS_TO_JIFFIES(p->sleep_avg) / MAX_BONUS;

I don't see any need for / 2.

Cheers,
Con

#1 lore raw
Quoted 30 lines · Con Kolivas

Hi Jens

Just thought I'd make a few comments about some of the code in your time sliced cfq.

(quoted diff) +3 -0
+	if (p->array)
+		return min(cpu_curr(task_cpu(p))->time_slice,
+					(unsigned int)MAX_SLEEP_AVG);

MAX_SLEEP_AVG is basically 10 * the average time_slice so this will always return task_cpu(p)->time_slice as the min value (except for the race you described in your comments). What you probably want is

(quoted diff) +2 -0
+		return min(cpu_curr(task_cpu(p))->time_slice,
+					(unsigned int)DEF_TIMESLICE);

Further down you do:

(quoted diff) +6 -0
+	/*
+	 * for blocked tasks, return half of the average sleep time.
+	 * (because this is the average sleep-time we'll see if we
+	 * sample the period randomly.)
+	 */
+	return NS_TO_JIFFIES(p->sleep_avg) / 2;

unfortunately p->sleep_avg is a non-linear value (weighted upwards towards MAX_SLEEP_AVG). I suspect here you want

(quoted diff) +1 -0
+	return NS_TO_JIFFIES(p->sleep_avg) / MAX_BONUS;
Quoted 1 line

I don't see any need for / 2.

Ingo donoted that code, perhaps he would like to comment?

Signature · 1 line
Jens Axboe
#2 lore raw
In reply to Con Kolivas
Quoted 4 lines · Con Kolivas

Hi Jens

Just thought I'd make a few comments about some of the code in your time sliced cfq.

(this code was actually a quick hack from me.)

Quoted 7 lines
(quoted diff) +3 -0
+	if (p->array)
+		return min(cpu_curr(task_cpu(p))->time_slice,
+					(unsigned int)MAX_SLEEP_AVG);

MAX_SLEEP_AVG is basically 10 * the average time_slice so this will always return task_cpu(p)->time_slice as the min value (except for the race you described in your comments). What you probably want is

the min() is there to not get ridiculous results due to the runqueue race, nothing else. Basically i didnt want to lock the runqueue to do something that is an estimation anyway, and rq->curr might be invalid. This was a proof-of-concept thing i wrote for Jens, if it works out then i think we want to lock the runqueue nevertheless, to not dereference possibly deallocated tasks (and to not trip up things like DEBUG_PAGEALLOC).

Review

Quoted 12 lines

Further down you do:

(quoted diff) +6 -0
+	/*
+	 * for blocked tasks, return half of the average sleep time.
+	 * (because this is the average sleep-time we'll see if we
+	 * sample the period randomly.)
+	 */
+	return NS_TO_JIFFIES(p->sleep_avg) / 2;

unfortunately p->sleep_avg is a non-linear value (weighted upwards towards MAX_SLEEP_AVG). I suspect here you want

(quoted diff) +1 -0
+	return NS_TO_JIFFIES(p->sleep_avg) / MAX_BONUS;

sleep_avg might be nonlinear, but nevertheless it's an estimation of the sleep time of a task. It's different if the task is interactive. We cannot know how much the task really will sleep, what we want is a good guess. I didnt want to complicate things too much, as long as the ballpark figure is right. (i.e. as long as the function returns '0' for on-runqueue tasks, returns a large value for long sleepers and returns something inbetween for short/medium sleepers.) We can later on complicate it with things like looking at p->timestamp to figure out how long it has been sleeping (and thus the ->sleep_avg is perhaps not authorative anymore), but i kept it simple & stupid for now.

Quoted 1 line

I don't see any need for / 2.

the need for /2 is this: ->sleep_avg tells us the average _full_ sleep period time (roughly). The CFQ IO-scheduler is sampling the task _sometime_ during that period, randomly. So on average the task will sleep another /2 of the sleep-average. Ok?

Ingo

#3 lore raw
Quoted 10 lines · Ingo Molnar
Quoted 4 lines · Con Kolivas

Hi Jens

Just thought I'd make a few comments about some of the code in your time sliced cfq.

(this code was actually a quick hack from me.)

Heh I wondered why Jens was diddling with cpu scheduler code ;)

Quoted 4 lines
Quoted 4 lines
(quoted diff) +3 -0
+	if (p->array)
+		return min(cpu_curr(task_cpu(p))->time_slice,
+					(unsigned int)MAX_SLEEP_AVG);
Quoted 11 lines
Quoted 3 lines

MAX_SLEEP_AVG is basically 10 * the average time_slice so this will always return task_cpu(p)->time_slice as the min value (except for the race you described in your comments). What you probably want is

the min() is there to not get ridiculous results due to the runqueue
race, nothing else. Basically i didnt want to lock the runqueue to do
something that is an estimation anyway, and rq->curr might be invalid. This was a proof-of-concept thing i wrote for Jens, if it works out then i think we want to lock the runqueue nevertheless, to not dereference
possibly deallocated tasks (and to not trip up things like
DEBUG_PAGEALLOC).

I understood that. I just thought that DEF_TIMESLICE would be a better upper bound.

Quoted 23 lines

Review

Quoted 11 lines

Further down you do:

(quoted diff) +6 -0
+	/*
+	 * for blocked tasks, return half of the average sleep time.
+	 * (because this is the average sleep-time we'll see if we
+	 * sample the period randomly.)
+	 */
+	return NS_TO_JIFFIES(p->sleep_avg) / 2;

unfortunately p->sleep_avg is a non-linear value (weighted upwards towards MAX_SLEEP_AVG). I suspect here you want

(quoted diff) +1 -0
+	return NS_TO_JIFFIES(p->sleep_avg) / MAX_BONUS;

sleep_avg might be nonlinear, but nevertheless it's an estimation of the
sleep time of a task. It's different if the task is interactive. We
cannot know how much the task really will sleep, what we want is a good
guess. I didnt want to complicate things too much, as long as the
ballpark figure is right. (i.e. as long as the function returns '0' for
on-runqueue tasks, returns a large value for long sleepers and returns
something inbetween for short/medium sleepers.) We can later on
complicate it with things like looking at p->timestamp to figure out how long it has been sleeping (and thus the ->sleep_avg is perhaps not authorative anymore), but i kept it simple & stupid for now.

Quoted 7 lines
Quoted 1 line

I don't see any need for / 2.

the need for /2 is this: ->sleep_avg tells us the average _full_ sleep period time (roughly). The CFQ IO-scheduler is sampling the task _sometime_ during that period, randomly. So on average the task will sleep another /2 of the sleep-average. Ok?

sleep_avg accumulates over time or can be gathered all within one sleep period so as well as being non-linear we have the situation of not knowing if it gradually accumulated or sleeps for > 1 second at a time. I still think it needs to be divided by the number of timeslices that fit into MAX_SLEEP_AVG, which by design is MAX_BONUS as the likely thing is it accumulates over time. Either way I think we'll be way out so it probably wont matter since this ends up being a weighting rather than an accurate measure.

I don't feel strongly about these values, I just originally thought it was Jens' interpretation of the values.

Cheers,
Con