Re: O(1) scheduler

Posted May 31, 2006 7:55 UTC (Wed) by mingo (subscriber, #31122)
In reply to: The kernel lock validator by smurf
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:

return current->tgid;

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!