Re: 2.6 Scheduler of O(1)

From: Fabiano (fabiano.ramos_at_gmail.com)
Date: 02/10/05 

Date: 10 Feb 2005 05:50:59 -0800

jhumo2002@YAHOO.COM (Milind Dumbare) wrote in message news:<a8dfd22c.0502090558.545978b8@posting.google.com>...
> fabiano.ramos@gmail.com (Fabiano) wrote in message news:<5afb2c65.0502081517.60b96d12@posting.google.com>...
> > jhumo2002@YAHOO.COM (Milind Dumbare) wrote in message news:<a8dfd22c.0502060009.4ccd6548@posting.google.com>...
> > > how the scheduler is having O(1) property in 2.6 ....
> > >
> > > I mean how does it pick the process from queue without scanning the
> > > whole ready queue
> > >
> > > does any body have theoratical documentation of this
> > >
> > > or where should I refer in the code..(line no)
> >
> >
> > In a few words:
> >
> > - every processor has a runqueue associated with it (what you call
> > ready queue).
> > - each runqueue has 2 priority arrays, the active and the expired.
> > The active array stores the processes that still have some time slice.
> > Once this time finished, they go to the expired array.
> > Each array has 140 entries (queues), one for each privilege level.

> are they sorted if yes who sort them ( it can (must )not be scheduler()
> because it would cause one more overhead

sorted by .... ? Everyone in a queue has the same priority. As their
timeslices left reaches 0, they are moved to the expired array. When
all processes timeslices are gone, the expired and active arrays are
swapped, and voilá ... everybody is ready to run again!

> > So, picking a process to run is as simple as picking the first
> > process of the first non-empty queue. As the number of queue
> > is fixed (140) and independent of the number of processes running,
> > the scheduler is O(1).

> if its that much easy then what was the problem to not to implemented in earlier
> versions

it seems you did not like it :) This question is somewhat innocent.
Occam's Razor: "The world is simple". Some things just does not come
to mind when we want. Better understanding of the problem, which takes
time, also leads to better and simpler solutions.

> >
> > Why don't you try Love's Linux Kernel Development?

> please give me some URL or should I search on gooooooogle for above line
> >

I don't think this book is available online. I bought my copy from
Bookpool.com

Up the irons!

> > Cheers,
> > Fabiano

Relevant Pages

  • Re: -mm seems significanty slower than mainline on kernbench
    ... according to nice much more effectively than previously where by their very nature, low priority tasks were balanced more frequently and ended up getting their own cpu. ... This means that programs with high nice values will tend to spend more time on the expired array than the active array. ... So the patch works by reducing the chance of any tasks being moved during an idle rebalance. ...
    (Linux-Kernel)
  • Re: [PATCH] sched: Fix adverse effects of NFS client on interactive response
    ... length of the CPU runs that the task does and not allowing them to defer the shift to the expired array if this average run length is greater than some specified value. ... The hardest bit would be deciding on the "limit" to be applied when deciding whether to let a supposed interactive task stay on the active array. ... To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ ...
    (Linux-Kernel)