[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.020 / U:29.980 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site