Re: Single-threading servers and select()

[skaller <skaller@...>]

On Mon, 2005-01-24 at 04:14, Adrián Pérez wrote:

> > This seems useful, considering OS switching usually has two
> > very bad negatives:
> >
> > (a) its O(n)
> 
> Totally disagree. A «good enough» OS should have an O(1) scheduler,  

Oh, you're not disagreeing! It should be O(1).

> like the one present in Linux 2.6.x, NetBSD 2.0, and so on. Actually  
> there's no practical reason to make a scheduler have O(n) complexity. 

It isn't enough to just schedule in O(1), a scheduler has
to take Real Time priorities and constraints, fairness,
and other things into account.

Whether Linux 2.6 achieves this is not clear -- since it
basically implements Unix which doesn't support RT scheduling.

> So context switching consists in:
> 
> 1.) Running the scheduler to select a new task. A good scheduler should  
> be O(1)!
> 
> 2.) Moving the context of the active task out of the CPU. This involves  
> saving CPU registers (which is O(1)), and removing the process' memory  
> mapping from the MMU (which is O(1), too).
> 
> 3.) Load the context of the selected task in the CPU. This again  
> involves copying saved CPU registers and load a memory map in the MMU.
> 
> So we can conclude that task switching should be O(1)!

You missed one thing -- the speed you described is O(1).
However memory use of the tasks may not be because they
each need O(m) stacks, where m is an arbitrarily
large number. This isn't a scheduling problem though,
but one of representing the process state.

Arbitrarily large heaps cost only what you use -- all
processes can share the same heap. But each needs its
own stack .. and that makes C/Unix style processes
non-scalable -- unless these can operate with a
bounded stack.

Device drivers typically can use a bounded stack,
and some applications can, but many applications
use non-tail recursive functions, which require
an unbounded stack. So the only way to get these
applications scalable is to replace this unbounded
stack with heap storage.

Note modern VM systems do precisely this for
the actual stack memory -- the problem isn't
that unbounded memory is needed, but that
unbounded *address space* is needed.

Interpreters (such as Lua) do not have this problem,
since they can easily emulate the stack on the heap
(at the cost of one extra level of indirection).

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net