Re: O(1) scheduler
Posted May 31, 2006 7:55 UTC (Wed) by mingo
In reply to: The kernel lock validator
Parent article: The kernel lock validator
Oh, and the scheduler doesn't run in constant time. It just delegates the job to small trivial chunks that run when each process starts+stops using the CPU, so technically it's still O(n), not O(1).
this statement doesnt parse for me. Sure, if you execute an O(1) operation N times that makes it O(N). What matters is the overhead of context-switching and wakeup, and those are O(1)!
just look at an example: sys_getpid(), the simplest system-call in existence, does:
that's as O(1) as it gets - a handful of instructions. But by your argument, since applications may execute getpid() lots of times, in reality it's O(N)? By that argument there would be code at all that would qualify as O(1) code!
to post comments)