![]() | |||||||||||
Messages in this thread |
* Esben Nielsen <nielsen.esben@googlemail.com> 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 majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ | ||||||||||
| Last update: 2007-04-19 12:15 [from the cache] ©2003-2008 | |||||||||||