* Esben Nielsen <[EMAIL PROTECTED]> wrote:
> >+ /*
> >+ * Temporarily insert at the last position of the tree:
> >+ */
> >+ p->fair_key = LLONG_MAX;
> >+ __enqueue_task_fair(rq, p);
> > p->on_rq = 1;
> >+
> >+ /*
> >+ * Update the key to the real value, so that when all other
> >+ * tasks from before the rightmost position have executed,
> >+ * this task is picked up again:
> >+ */
> >+ p->fair_key = rq->fair_clock - p->wait_runtime + p->nice_offset;
>
> I don't think it safe to change the key after inserting the element in
> the tree. You end up with an unsorted tree giving where new entries
> end up in wrong places "randomly".
yeah, indeed. I hoped that once this rightmost entry is removed (as soon
as it gets scheduled next time) the tree goes back to a correct shape,
but that's not the case - the left sub-tree and the right sub-tree is
merged by the rbtree code with the assumption that the entry had a
correct key.
> I think a better approach would be to keep track of the rightmost
> entry, set the key to the rightmost's key +1 and then simply insert it
> there.
yeah. I had that implemented at a stage but was trying to be too clever
for my own good ;-)
Ingo
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
