Messages in this thread | | | Date | Fri, 4 Apr 2003 06:04:47 -0800 | From | William Lee Irwin III <> | Subject | Re: fairsched + O(1) process scheduler |
| |
On Thu, Apr 03, 2003 at 11:22:41AM -0800, William Lee Irwin III wrote: >> Use spin_lock_irq(&uidhash_lock) or you will deadlock if you hold it >> while you take a timer tick, but it's wrong anyway. it's O(N) with >> respect to number of users present. An O(1) algorithm could easily >> make use of reference counts held by tasks. [...] >> This isn't right, when expiration happens needs to be tracked by both >> user and task. Basically which tasks are penalized when the user >> expiration happens? The prediction is the same set of tasks will always >> be the target of the penalty.
On Fri, Apr 04, 2003 at 01:27:04PM +0200, Antonio Vargas wrote: > Just out of experimenting, I've coded something that looks reasonable > and would not experience starvation. > In the normal scheduler, a non-interactive task will, when used all > his timeslice, reset p->time_slice and queue onto the expired array. > I'm now reseting p->reserved_time_slice instead and queuing the task > onto a per-user pending task queue. > A separate kernel thread walks the user list, calculates the user > timeslice and distributes it to it's pending tasks. When a task > receives timeslices, it's moved from the per-user pending queue to > the expired array of the runqueue, thus preparing it to run on the > next array-switch.
Hmm, priorities getting recalculated by a kernel thread sounds kind of scary, but who am I to judge?
On Fri, Apr 04, 2003 at 01:27:04PM +0200, Antonio Vargas wrote: > If the user has many timeslices, he can give timeslices to many tasks, thus > getting more work done. > While the implementation may not be good enough, due to locking problems and > the use of a kernel-thread, I think the fundamental algorithm feels right. > William, should I take the lock on the uidhash_list when adding a task > to a per-user task list?
Possible, though I'd favor a per-user spinlock.
The code looks reasonable now, modulo that race you asked about.
-- wli - 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/
| |