Re: fairsched + O(1) process scheduler

[William Lee Irwin III]

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