[lkml]   [2003]   [Apr]   [4]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectRe: 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
More majordomo info at
Please read the FAQ at

 \ /
  Last update: 2005-03-22 13:34    [W:0.044 / U:10.688 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site