Re: O(1) scheduler
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!
The LWN site is currently under high scraper load, so comment display has been suppressed for anonymous users. If you are a human, you may read the comments by clicking the button below:
Note: you can avoid this step in the future by logging into your LWN account.