Scheduing: A Comparison

Burton Rosenberg,
29 Sept 2006


Both Linux and Win-NT use multilevel feedback schedulers. Linux has 160 levels and Win-NT has 32 levels. The thread of highest priority runs, lower priority must wait until no higher priority thread is ready and unexpired.

Linux has two scheduling classes: Normal and Real-Time, Win-NT has three Normal, Real-Time and System. Both map these classes into the levels so that Real-Time has priority over Normal. Win-NT reserves the lowest priority for System class.

Both OS's use dynamic adjustment of priority and quantum to the Normal processes, but static priority to the Real-Time processes. However Win-NT will let Normal tasks boost into the Real-Time range if they have the privlege to do this, and certain system tasks take advantage of this boost. Linux makes no exception to the rule that tasks in the Real-Time range have static priorities.

Linux has two Real-Time disciplines, Round-Robin and First-Come-First-Served, Win-NT has one discipline for real time.

Both boosts or decreases priority by automatic means. Linux uses the interactivity of the process to boost plus or minus 5 levels, with no other special measures. Win-NT boosts priority after I/O waits and to avoid starvation. (Linux avoids starvation by depriving tasks of renewed quantum until all tasks have expired their quantum.)

Win-NT boosts the priority of each thread in the process when the process is boosted. Linux does not recognize threads, hence each thread has it's own scheduling decision.

Linux awards quantum according to the static priority of the task, with higher priority tasks getting larger quantum. The range is very large, from 5 ms for mininum priority up to 800 ms for maximum priority.

Win-NT has a single quantum value for all tasks but can boost the quantum of the foreground task by up to three times the normal value. The system is configured to award either long or short quantum (presumably to adapt to either server or workstation), either fixed or variable (i.e. foreground task boost), and if variable, the boost amount. Expressed in quantum, the values are:

Linux and Win-NT run their priority queues very differently. Linux will take round robin until expiration of the task's quantum. Once a task has expired its quantum it receives no further time until its quantum is reset. This happens when all processes have expired their quantum, except that sufficiently interactive processes will never be expired.

Win-NT uses the quantum only to preempt. If a process is preempted by a higher priority task, it is placed at the head of the queue for its priority and runs again up to the remainder of its quantum once the high priority process yields. If a process expires its quantum it is preemtped and placed at the back of the queue for it's priority. In this case its quantum is restored to its full value.