[Wolves] Kernel 2.6

Aquarius aquarius-lists at kryogenix.org
Sun Apr 25 16:25:02 BST 2004


Old Dan spoo'd forth:
> The scheduler is not O1 precisely -
>> the schedule main loop is O1 in its choice of which process to run next
>> time but this is because some calculations are now done elsewhere.
> 
> ...but must confess to not having the foggiest idea what that statement
> means.  I will google for a Clue(tm).  :)

This is not very interesting, but hey[1]. The speed of an algorithm is
described in Big O notation, and it's described as proportional in
some way to the number of things it has to process. For instance, if
I ask you to find the King of Spades in a shuffled deck, the search
algorithm you'll probably pick is "look through from the beginning
until you find it". That's directly proportional to the number of
cards there are in the deck -- if I made the deck twice as big, it
would in general take you twice as long to find the card -- and
therefore, your algorithm is described as O(n), meaning "time taken
is proportional to the number of cards in the deck (n)". You will
also see algorithms described as O(n^2), meaning that the time taken
is proportional to the number of items squared, i.e., if you double
the number of items, you'll multiply the time taken by the algorithm
by four (which is two squared). O(1) means "not proportional to the
number of items at all", i.e., it doesn't matter how many things you
have, the algorithm always takes the same amount of time. For instance,
the action "take the top card off the deck" is O(1), because it takes
the same amount of time whether there are two cards or two billion.
So, all the noise about the new O(1) scheduler meant that the new
scheduler takes the same amount of time to decide which process to
run no matter how many processes you are running. The previous
scheduler might have been, say, O(n), which would mean that the
time it took to make a decision was directly proportional to the
number of processes you had running, and therefore as the system
got busier the scheduler would take longer to work, making a bad
problem worse. The new O(1) scheduler avoids that problem. This is
pretty damned esoteric, though, and no-one at all needs to worry
about it :-)

Aq -- see, I do remember something from my degree

[1] it's also a bird's eye view of the process, and I've, er, 
glossed over some of the detail. Those of you who know what you're
talking about, do please refrain from picking up on bits of it that
are slightly inaccurate (unless I've got it all totally wrong, which
I don't think I have :))

-- 
You're *not* friends. You'll *never* be friends. You'll be in love
till it kills you both. You'll fight, and you'll shag, and you'll
hate each other till it makes you quiver, but you'll never be *friends*.
	   -- Spike, "Lovers Walk", Buffy the Vampire Slayer



More information about the Wolves mailing list