Skip to contentSkip to conversation

rework of "prioritize non-migratable tasks over migratable ones"

sched-devel, patch-rfc Dmitry Adamushko 4 participants 16 messages Jun 10, 2008 – Jul 15, 2008

lore
Share & tools
lore
#0 lore raw

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and twice so on x86_64), let's add "exclusive" (the ones that are bound to this CPU) tasks to the head of the queue and "shared" ones -- to the end.

In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not queued as now), meaning that a task {i+1} is being placed in front of the previously woken up task {i}. But I don't think that this behavior may cause any realistic problems.

There are a couple of changes on top of this one.

(1) in check_preempt_curr_rt()

I don't think there is a need for the "pick_next_rt_entity(rq, &rq->rt) != &rq->curr->rt" check.

enqueue_task_rt(p) and check_preempt_curr_rt() are always called one after another with rq->lock being held so the following check "p->rt.nr_cpus_allowed == 1 && rq->curr->rt.nr_cpus_allowed != 1"
should be enough (well, just its left part) to guarantee that 'p' has been queued in front of the 'curr'.

(2) in set_cpus_allowed_rt()

I don't thinks there is a need for requeue_task_rt() here.

Perhaps, the only case when 'requeue' (+ reschedule) might be useful is as follows:

i) weight == 1 && cpu_isset(task_cpu(p), *new_mask)

i.e. a task is being bound to this CPU);

ii) 'p' != rq->curr

but here, 'p' has already been on this CPU for a while and was not migrated. i.e. it's possible that 'rq->curr' would not have high chances to be migrated right at this particular moment (although, has chance in a bit longer term), should we allow it to be preempted.

Anyway, I think we should not perhaps make it more complex trying to address some rare corner cases. For instance, that's why a single queue approach would be preferable. Unless I'm missing something obvious, this approach gives us similar functionality at lower cost.

Verified only compilation-wise.

(Almost)-Signed-off-by: Dmitry Adamushko <[email protected]>

---

kernel/sched.c +2 -4
index 268a850..e1c382d 100644
@@ -155,8 +155,7 @@ static inline int task_has_rt_policy(struct task_struct *p)
  */
 struct rt_prio_array {
 	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
-	struct list_head xqueue[MAX_RT_PRIO]; /* exclusive queue */
-	struct list_head squeue[MAX_RT_PRIO];  /* shared queue */
+	struct list_head queue[MAX_RT_PRIO];
 };
 
 struct rt_bandwidth {
@@ -7661,8 +7660,7 @@ static void init_rt_rq(struct rt_rq *rt_rq, struct rq *rq)
 
 	array = &rt_rq->active;
 	for (i = 0; i < MAX_RT_PRIO; i++) {
-		INIT_LIST_HEAD(array->xqueue + i);
-		INIT_LIST_HEAD(array->squeue + i);
+		INIT_LIST_HEAD(array->queue + i);
 		__clear_bit(i, array->bitmap);
 	}
 	/* delimiter for bitsearch: */
kernel/sched_rt.c +9 -35

104 lines not on this page · raw message

---

#1 lore raw
Quoted 8 lines · Dmitry Adamushko

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

Quoted 7 lines

Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and twice so on x86_64), let's add "exclusive" (the ones that are bound to this CPU) tasks to the head of the queue and "shared" ones -- to the end.

In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not queued as now), meaning that a task {i+1} is being placed in front of the previously woken up task {i}. But I don't think that this behavior may cause any realistic problems.

Doesn't this violate POSIX ?

#2 lore raw

2008/6/11 Peter Zijlstra <[email protected]>:

Quoted 13 lines · Dmitry Adamushko
Quoted 12 lines

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and twice so on x86_64), let's add "exclusive" (the ones that are bound to this CPU) tasks to the head of the queue and "shared" ones -- to the end.

Quoted 6 lines
Quoted 3 lines

In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not queued as now), meaning that a task {i+1} is being placed in front of the previously woken up task {i}. But I don't think that this behavior may cause any realistic problems.

Doesn't this violate POSIX ?

If so, then the idea of "prioritize non-migratable tasks over migratable ones" violates it, not just an artefact of this particular implementation.

No matter which implementation is used, we have a situation when a woken-up single-CPU-bound task (let's call it 'p') can preempt a current task with effects as follows:

- 'current' is not guaranteed to get another CPU;

- there might have been other pending tasks (of equal prio) on this queue. As a result, 'p' starts running before them violating currently used (explicitly requested by POSIX?) round-robin behavior.

Anyway, the original (and my rework) algorithm is somewhat sub-optimal. It considers only "p->rt.nr_cpus_allowed == 1", while the ideal algorithm would behave as follows:

1) we get a newly woken-up task on CPU_i;

2) this task have a number (!= 1) of allowed CPUs (which is a sub-set of all) _but_ all of them are busy at the moment serving high prio tasks;

3) there are no other pending tasks on the queue (of equal prio) that are in the same condition as 'p' (that's they can't be migrated to other CPUs at the moment and to wait for CPU_i is the 'best' effort for them);

4) 'current' is guaranteed to start running immediatelly on another CPU (apparently, its affinity allows CPUs that can be used neither by 'p', nor by tasks from (3) ), should we preempt it now.

5) then let 'p' preempt 'current'.

We do cause some 'troubles' (in a way of 'cache' efficienty) for the 'current' but probably we win CPU-time-distribution-wise.

Note, hard real-time tasks would not like to find themselves in the aforemnetioned situation. But then, one probably should have initially taken care of assigning different prios or better off, isolating dedicated CPUs for some tasks wrt how much CPU-time they consume/latency they expect.

All in all, I think that the initial implementation is sub-optimal in any case and it's not worth introducing additional overhead (another priority queue array) to address this issue (which is kind of a corner case).

We may just consider dropping this idea completely. (my 0.02$)

Signature · 2 lines
Best regards,
Dmitry Adamushko
#3 lore raw
Quoted 29 lines · Dmitry Adamushko

2008/6/11 Peter Zijlstra <[email protected]>:

Quoted 13 lines · Dmitry Adamushko
Quoted 12 lines

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and twice so on x86_64), let's add "exclusive" (the ones that are bound to this CPU) tasks to the head of the queue and "shared" ones -- to the end.

Quoted 6 lines
Quoted 3 lines

In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not queued as now), meaning that a task {i+1} is being placed in front of the previously woken up task {i}. But I don't think that this behavior may cause any realistic problems.

Doesn't this violate POSIX ?

If so, then the idea of "prioritize non-migratable tasks over migratable ones" violates it, not just an artefact of this particular implementation.

No matter which implementation is used, we have a situation when a woken-up single-CPU-bound task (let's call it 'p') can preempt a current task with effects as follows:

Quoted 8 lines

- 'current' is not guaranteed to get another CPU;

- there might have been other pending tasks (of equal prio) on this queue. As a result, 'p' starts running before them violating currently used (explicitly requested by POSIX?) round-robin behavior.

We may just consider dropping this idea completely. (my 0.02$)

If we cannot guarantee POSIX compliant scheduling I think we should get rid of this.

#4 lore raw
In reply to Dmitry Adamushko

Hi Dmitry,
Just catching up on mail. I haven't had a chance to review your patch, so I am only responding to the comments in this thread.

Quoted 1 line
Quoted 1 line
Quoted 1 line

On Wed, Jun 11, 2008 at 6:05 AM, in message

<[email protected]>, "Dmitry

Quoted 20 lines · Adamushko

2008/6/11 Peter Zijlstra <[email protected]>:

Quoted 10 lines · Dmitry Adamushko
Quoted 9 lines

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

Instead of having 2 separate arrays (which is + ~800 bytes on x86_32 and

twice so on x86_64),

Quoted 1 line
Quoted 1 line

let's add "exclusive" (the ones that are bound to this CPU) tasks to the

head of the queue

Quoted 3 lines
Quoted 3 lines

and "shared" ones -- to the end.

In case of a few newly woken up "exclusive" tasks, they are 'stacked' (not

queued as now), meaning that

Quoted 1 line
Quoted 1 line

a task {i+1} is being placed in front of the previously woken up task {i}.

But I don't think that

Quoted 8 lines
Quoted 4 lines
Quoted 1 line

this behavior may cause any realistic problems.

Doesn't this violate POSIX ?

If so, then the idea of "prioritize non-migratable tasks over migratable ones" violates it, not just an artefact of this particular implementation.

This isn't entirely accurate though. Your proposal does alter the behavior from the original patch. In fact, I put in the xqueue/squeue concept specifically to *avoid* the condition that you are creating. I think this was the point Peter was making.

However, to your point: I can agree that either implementation creates the possibility for creating strange scheduling artifacts. And I think the point you are making is that once we have the artifact, whats another one? ;)

Quoted 6 lines

No matter which implementation is used, we have a situation when a woken-up single-CPU-bound task (let's call it 'p') can preempt a current task with effects as follows:

- 'current' is not guaranteed to get another CPU;

Right. I admit this is one of the sticking points that has potential for creating artifacts. [1] The downside is there is no real way to avoid this. You can't atomically guarantee a position on another core until current has been preempted. So its always going to be a best-effort assessment of the state of the system prior to the preemption. Not ideal.

Fortunately, this is all w.r.t. equal prio tasks. And as you state below, if this was an issue the designer should have placed the tasks at different prios. This fact is what led me to ultimately feel somewhat comfortable with the concept. [2] A related issue is the potential to have an unbounded task be ping-ponged around (ehem) unbounded. ;)

Quoted 4 lines

- there might have been other pending tasks (of equal prio) on this queue. As a result, 'p' starts running before them violating currently used (explicitly requested by POSIX?) round-robin behavior.

Yes, except your patch also allows other bound tasks to preempt each other, which adds an additional artifact that is not present in mine nor is it strictly necessary. [3] You could probably work around this by having the enqueue_task_rt() seek out the first non-bound task position and insert there, instead of HEAD. In fact I had contemplated doing exactly that, but then decided the memory/speed tradeoff with the xqueue/squeue was better. I am not against going the other way if the memory cost of the xqueue is too great.

Quoted 10 lines

Anyway, the original (and my rework) algorithm is somewhat sub-optimal. It considers only "p->rt.nr_cpus_allowed == 1", while the ideal algorithm would behave as follows:

1) we get a newly woken-up task on CPU_i;

2) this task have a number (!= 1) of allowed CPUs (which is a sub-set of all) _but_ all of them are busy at the moment serving high prio tasks;

I don't understand the significance of the stipulation that its a "sub-set of all". Can you elaborate? Or did you mean to say "it *may* be a sub-set of all"?

Quoted 5 lines

3) there are no other pending tasks on the queue (of equal prio) that are in the same condition as 'p' (that's they can't be migrated to other CPUs at the moment and to wait for CPU_i is the 'best' effort for them);

Note that this is already accounted for with xqueue/squeue, or with my proposed modifications [3] above

Quoted 4 lines

4) 'current' is guaranteed to start running immediatelly on another CPU (apparently, its affinity allows CPUs that can be used neither by 'p', nor by tasks from (3) ), should we preempt it now.

As per [1], we unfortunately can never guarantee this.

Quoted 2 lines

5) then let 'p' preempt 'current'.

I think everything except your (4) is achieved in my patch, and could be in yours with the slight modification proposed in [3]. So the real question is whether the lack of your point (4) or the issue I mentioned in [2] is acceptable or not.

Quoted 3 lines

We do cause some 'troubles' (in a way of 'cache' efficienty) for the 'current' but probably we win CPU-time-distribution-wise.

True, but this in essence is what load-balancing is all about.

Quoted 6 lines

Note, hard real-time tasks would not like to find themselves in the aforemnetioned situation. But then, one probably should have initially taken care of assigning different prios or better off, isolating dedicated CPUs for some tasks wrt how much CPU-time they consume/latency they expect.

Right. The key is that bets are off when considering equal-prio tasks. Wake-up order, etc, can create similar concerns. That is what lets this concept be at least semi acceptable.

Quoted 3 lines

All in all, I think that the initial implementation is sub-optimal

Ouch :)

Quoted 7 lines

in
any case and it's not worth introducing additional overhead (another priority queue array) to address this issue (which is kind of a corner case).

We may just consider dropping this idea completely. (my 0.02$)

And based on all this (and as I previously stated) I agree with your assessment that perhaps we should just drop this concept outright.

Regards,
-Greg

#5 lore raw

Hi Gregory,

Quoted 11 lines

[ ... ]

Quoted 6 lines
Quoted 2 lines

Doesn't this violate POSIX ?

If so, then the idea of "prioritize non-migratable tasks over migratable ones" violates it, not just an artefact of this particular implementation.

This isn't entirely accurate though. Your proposal does alter the behavior from the original patch. In fact, I put in the xqueue/squeue concept specifically to *avoid* the condition that you are creating. I think this was the point Peter was making.

However, to your point: I can agree that either implementation creates the possibility for creating strange scheduling artifacts. And I think the point you are making is that once we have the artifact, whats another one? ;)

My guess was that Peter points out at the possibility of task_2 getting ahead of task_1, despite task_1's longer presence on the run-queue and both tasks having equal priority.

IOW., it's not anymore a round-robin distribution for equal-prio tasks (if that's how POSIX requires it... yeah, I'm speculating here :-) but "migratable" vs. "non-migratable" in addition.

With your implementation, a "non-migratable" task gets ahead of "migratable" (and possibly, some "migratable" that are on the queue but for some reason have not been pulled/pushed yet).

With mine, one "non-migratable" can preempt another "non-migratable".

Partly, it could be fixed by : add a "non-migratable" task to the head of the queue _only_ if the "current" task (or better -- if a head-of-the-queue task) is "migratable".

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

By "strict round-robin scheduling" I mean something as follows:

a woken-up task_N can get a CPU _only_ if none of other currently pending tasks in the system (that's on all cpus and, sure, _RR and _FIFO and of equal prio) can run on this CPU.

e.g. the following behavior of the load-balancer would be wrong (migth have been possible with the 'old' scheduler/ load-balancer):

- task_1 is placed on CPU_N upon a wake-up with wake_idle();

- however, there were task_2 (currently running) and task_3 (pending) on CPU_M;

- task_3 was able to run on CPU_N _but_ has not been considered by the load-balancer yet (let's say CPU_M became free just a moment ago, not enough for the load-balancer to notice it).

i.e. task_1 gets ahead of task_3, although both have equal prios and both are able to run on this cpu.

yeah, enough speculations :-)

Quoted 5 lines
Quoted 5 lines

Anyway, the original (and my rework) algorithm is somewhat sub-optimal. It considers only "p->rt.nr_cpus_allowed == 1", while the ideal algorithm would behave as follows:

Quoted 7 lines
Quoted 5 lines

1) we get a newly woken-up task on CPU_i;

2) this task have a number (!= 1) of allowed CPUs (which is a sub-set of all) _but_ all of them are busy at the moment serving high prio tasks;

I don't understand the significance of the stipulation that its a "sub-set of all". Can you elaborate? Or did you mean to say "it *may* be a sub-set of all"?

it should have been "rt_se->nr_cpus_allowed not _necessarily_ equal to 1", meaning rt_se->nr_cpus_allowed is a sub-set of ALL_CPUS, not strictly a single cpu.

We consider a task to be "bound" if

"rt_se->nr_cpus_allowed == 1"

i.e. a task needs to be bound to a _single_ cpu.

what I mean is e.g.

say, there are 4 cpus and cpu_0 and cpu_1 are busy serving task_0 and task_1;

there are also task_3 and task_4 which have equal prios _but_ lower (worse) than those of task_0 and task_1.

task_3 can run on _any_ cpu but task_4 can run only on 2 of them -- cpu_1 and cpu_3.

task_3 is running on cpu_3

task_4 is woken up... with your/mine implementation it won't get cpu_3 as it's _not_ considered "bound" (rt_se->nr_cpus_allowed == 2)

while in fact, task_4 still might have been preempted and moved onto cpu_4.

that's why I called the current (mine is similar) definition/implementation of "bound" (or "non-migratable" in my terms above) sub-optimal.

hope it's clear now (and none of the important details are escaping me) :-)

Quoted 3 lines
Quoted 1 line

All in all, I think that the initial implementation is sub-optimal

Ouch :)

ok, mine is no way better :-)

repeating myself, they address just a specific case (rt_se->nr_cpus_allowed == 1) of the broader "problem" which I describe above.

Quoted 4 lines

Regards,
-Greg

Signature · 2 lines
Best regards,
Dmitry Adamushko
#6 lore raw
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Mon, Jun 16, 2008 at 1:59 PM, in message

<[email protected]>, "Dmitry Adamushko" <[email protected]> wrote:

[snip]

Quoted 5 lines

that's why I called the current (mine is similar) definition/implementation of "bound" (or "non-migratable" in my terms above) sub-optimal.

hope it's clear now (and none of the important details are escaping me) :-)

Indeed. I understand your point now. To summarize: nr_cpus_allowed is not sufficient to determine if this "load-balancing" operation should be attempted. Rather, we need to consider whether task_4->cpus_allowed results in no preemption when looking at [1,3], but task_3->cpus_allowed shows the cpu_4 could be preempted.

This problem is easily and efficiently solvable, and I think your "HEAD" approach is better than my xqueue/squeue idea. Now the question remains: "Is the whole concept worth it, or should we drop it?"

If we wanted to fix this, we could run both current and the wakee into cpupri for the case where wakee->prio == rq->highest_prio (*). If wakee comes back with 0 targets but rq->HEAD (*) comes back with potential targets, then wakee should insert to the HEAD and preempt. Otherwise, tail-insert as always. (We will still race against the potential targets becoming unavailable to accept current, but as I indicated in the last message, this is unavoidable).

(*) Note that its important to use rq->highest_prio/HEAD and not rq->current so that we don't look at the state of the queue while in the process of rescheduling

Thanks for clarifying, Dmitry. I think you are right.

Regards,
-Greg

#8 lore raw

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

Quoted 1 line
Quoted 1 line
Quoted 1 line

On Mon, Jun 16, 2008 at 3:17 PM, in message

<1213643862.16944.142.camel@twins>, Peter Zijlstra <[email protected]>

Quoted 11 lines · wrote:
Quoted 3 lines · Dmitry Adamushko

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
ag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

Thanks for the link, Peter. When you read that, its pretty clear that this whole concept violates the standard. Its probably best to just revert the patch and be done with it.

Regards,
-Greg

#9 lore raw

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

Quoted 12 lines · Gregory Haskins
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Mon, Jun 16, 2008 at 3:17 PM, in message

<1213643862.16944.142.camel@twins>, Peter Zijlstra <[email protected]>

Quoted 9 lines · wrote:
Quoted 3 lines · Dmitry Adamushko

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
ag_02_08_04_01

Quoted 6 lines
Quoted 2 lines

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

Thanks for the link, Peter. When you read that, its pretty clear that this whole concept violates the standard. Its probably best to just revert the patch and be done with it.

no, there's no spec violation here - the spec is silent on SMP issues.

the spec should not be read to force a global runqueue for RT tasks. That would be silly beyond imagination.

so ... lets apply Dmitry's nice simplification, hm?

Ingo

#10 lore raw

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

Quoted 17 lines · Ingo Molnar
Quoted 15 lines · Gregory Haskins
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Mon, Jun 16, 2008 at 3:17 PM, in message

<1213643862.16944.142.camel@twins>, Peter Zijlstra <[email protected]>

Quoted 11 lines · wrote:
Quoted 3 lines · Dmitry Adamushko

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
ag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

Quoted 8 lines
Quoted 3 lines

Thanks for the link, Peter. When you read that, its pretty clear that this whole concept violates the standard. Its probably best to just revert the patch and be done with it.

no, there's no spec violation here - the spec is silent on SMP issues.

the spec should not be read to force a global runqueue for RT tasks. That would be silly beyond imagination.

Sadly, some people do read it like that.

Quoted 1 line

so ... lets apply Dmitry's nice simplification, hm?

As long as it doesn't wreck the per RQ queue model and only affects the SMP interaction that would be acceptable I guess.

#11 lore raw

Re: [sched-devel, patch-rfc] rework of "prioritizenon-migratabletasks over migratable ones"

In reply to Ingo Molnar
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Wed, Jun 18, 2008 at 6:39 AM, in message <[email protected]>,

Quoted 22 lines · Ingo Molnar
Quoted 10 lines · Gregory Haskins
Quoted 1 line
Quoted 1 line
Quoted 1 line

On Mon, Jun 16, 2008 at 3:17 PM, in message

<1213643862.16944.142.camel@twins>, Peter Zijlstra <[email protected]>

Quoted 7 lines · wrote:
Quoted 3 lines · Dmitry Adamushko

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t

Quoted 8 lines
Quoted 4 lines

ag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

Thanks for the link, Peter. When you read that, its pretty clear that this whole concept violates the standard. Its probably best to just revert the patch and be done with it.

Quoted 6 lines

no, there's no spec violation here - the spec is silent on SMP issues.

the spec should not be read to force a global runqueue for RT tasks. That would be silly beyond imagination.

so ... lets apply Dmitry's nice simplification, hm?

Hmm...I guess that is a good way to look at it. Sounds good, thanks!

Perhaps I will write up a patch against his that fixes that suboptimal detection problem that he highlighted, afterall

Thanks,
-Greg

#12 lore raw

Re: [sched-devel, patch-rfc] rework of "prioritize non-migratabletasks over migratable ones"

In reply to Ingo Molnar

2008/6/18 Ingo Molnar <[email protected]>:

Quoted 18 lines · Gregory Haskins
Quoted 16 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

On Mon, Jun 16, 2008 at 3:17 PM, in message

<1213643862.16944.142.camel@twins>, Peter Zijlstra <[email protected]>

Quoted 11 lines · wrote:
Quoted 3 lines · Dmitry Adamushko

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#t
ag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

Quoted 8 lines
Quoted 3 lines

Thanks for the link, Peter. When you read that, its pretty clear that this whole concept violates the standard. Its probably best to just revert the patch and be done with it.

no, there's no spec violation here - the spec is silent on SMP issues.

the spec should not be read to force a global runqueue for RT tasks. That would be silly beyond imagination.

I don't think it would actually make sense to specify behavior in terms of per-cpu queues. This is an implementation detail. So the _global_ (system-wise) queue makes more sense (at least to me :-) if one wants to define user-visible scheduling behavior.

e.g. as follows:
(http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#tag_02_08_04_01)

[quote]
"Threads scheduled under this policy are chosen from a thread list that is ordered by the time its threads have been on the list without being executed;"
[/quote]

Quoted 1 line

From the POV of users, I think only the "global" queue would make

sense. Otherwise, the sentence is rather useless.

[quote]
"generally, the head of the list is the thread that has been on the list the longest time, and the tail is the thread that has been on the list the shortest time."
[/quote]

OTOH, some differences can be justified by this "generally" word :-)

so it might be understood as something like this:

task_N can get a CPU only if all other pending runnable tasks that have been enqueued earlier than task_N (of the same class and prio) can _not_ start running on this CPU (e.g. due to their affinity).

Note, that our case is somewhat more subtle. We preempt a currently running task in the hope that it can start running on another CPU immediately, but we can't guarantee it.

Anyway, we are likely to win wrt cpu time distribution, but this fact of 'preemption' is a new 'artifact' indeed.

if POSIX can be understood as : a SCHED_FIFO/RR task can be preempted _only_ by a task with a higher prio and has to consume cpu-time as long as it wants (FIFO) or till its timeslice expires (RR) , then we violate it with this new behavior.

Quoted 3 lines

Ingo

Signature · 2 lines
Best regards,
Dmitry Adamushko
#13 lore raw
In reply to Peter Zijlstra

2008/6/16 Peter Zijlstra <[email protected]>:

Quoted 11 lines · Dmitry Adamushko
Quoted 4 lines

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#tag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

btw., rt group scheduling seems to well, slightly wreck this (per-rq) FIFO model as well.

say, group_A has N SCHED_FIFO tasks of equal prio. So far so good, they all run strictly one after another.

Now group_B gets task_S. On a group layer, group_B gets enqueued after group_A.

This changes when a current task (that belongs to group_A) relinquishes a CPU: dequeue_stack -> __enqueue_rt_entity() will place group_A in the tail of its list.

So the next task to run is task_S, although group_A migth have plenty of tasks of the same prio that were enqueued ealrier.

We can't get a strict FIFO ordering with this pure tree-like hierarchy.

btw #2,

Gregory, our new modification also doesn't work nicely with group-scheduling.

We may place a task in the head of its queue, yes. But its group will still remain where it was.

rt_se->nr_cpus_allowed just has no adequat sense for groups and __enqueue_rt_entity() always places a group at the tail.

IOW, even if check_preempt_curr_rt() calls resched_task() based on analysis of the newly arrived task 'p', 'p' won't be necessarily picked up by pick_next_task_rt(). Although, there is a way to fix it.

Signature · 2 lines
Best regards,
Dmitry Adamushko
#14 lore raw
Quoted 39 lines · Dmitry Adamushko

2008/6/16 Peter Zijlstra <[email protected]>:

Quoted 11 lines · Dmitry Adamushko
Quoted 4 lines

One way or another, we have different aritifacts (and mine have likely more) but conceptually, both "violates" POSIX if a strict round-robin scheduling is required.

http://www.opengroup.org/onlinepubs/009695399/functions/xsh_chap02_08.html#tag_02_08_04_01

Is quite strict on what FIFO should do, and I know of two points where we deviate and should work to match.

btw., rt group scheduling seems to well, slightly wreck this (per-rq) FIFO model as well.

say, group_A has N SCHED_FIFO tasks of equal prio. So far so good, they all run strictly one after another.

Now group_B gets task_S. On a group layer, group_B gets enqueued after group_A.

This changes when a current task (that belongs to group_A) relinquishes a CPU: dequeue_stack -> __enqueue_rt_entity() will place group_A in the tail of its list.

So the next task to run is task_S, although group_A migth have plenty of tasks of the same prio that were enqueued ealrier.

We can't get a strict FIFO ordering with this pure tree-like hierarchy.

btw #2,

Gregory, our new modification also doesn't work nicely with group-scheduling.

We may place a task in the head of its queue, yes. But its group will still remain where it was.

Quoted 6 lines

rt_se->nr_cpus_allowed just has no adequat sense for groups and __enqueue_rt_entity() always places a group at the tail.

IOW, even if check_preempt_curr_rt() calls resched_task() based on analysis of the newly arrived task 'p', 'p' won't be necessarily picked up by pick_next_task_rt(). Although, there is a way to fix it.

Yeah, I realized this quite a while back, but 1) posix doesn't say anything about group scheduling like this, and 2) all the rt group scheduling stuff is still experimental :-)

I'm open to suggestion though.

#15 lore raw
In reply to Dmitry Adamushko
Quoted 5 lines · Dmitry Adamushko

Hi Gregory,

regarding this commit: 45c01e824991b2dd0a332e19efc4901acb31209f

I think we can do it simpler. Please take a look at the patch below.

applied your simplification to tip/sched-devel for testing. It still maintains strict FIFO queueing on uniprocessors, correct? (which is pretty much the only standards question we care about)

Ingo