Re: fairsched + O(1) process scheduler

[Antonio Vargas <wind@cocodriloo.com>]

On Fri, Apr 04, 2003 at 06:04:47AM -0800, William Lee Irwin III wrote:
> 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?

First and foremost, root user is handled as usual, so kernel tasks should
also be handled as usual if they always run as root...
but I've yet to find out how to check if a task is a kernel thread or not,
and skip these explicitely just to be safe.

Also, while I've coded it on a kernel thread, I'd settle perfectly to a
periodic timer, but I don't know yet ask for one... perhaps a
self-propagating workqueue entry with a delay?

> 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.

So, when trying to add a task to the per-user pending tasks, I'd have
to do this:

1. spin_lock_irqsave(uidhash_lock, flags)
2. spin_lock(my_user->user_lock)
3. spin_unlock_restore(uidhash_lock, flags);

Is this any good?

Could I simply do "spin_unlock(my_user->user_lock)" at end without
taking the uidhash_lock again?

> The code looks reasonable now, modulo that race you asked about.

What do I need to lock when I want to add a task to a runqueue?
I'm doing a "spin_lock_irq(this_rq()->lock);"

As you can see, I'm not yet at speed with the locking rules... any
online references to the latest locking rules? The BKL was really
easy to understand in comparison! *grin*

Greets, Antonio.