Thread: Linux Scheduler

Multi-tasking or multi-processing has been an inevitable feature of operating systems since their inception. Multi-tasking provides the as a capability to run multiple processes-although, one by one, yet appearing simultaneous. The component that makes the as capable of multi-tasking is known as a scheduler. The scheduler has the responsibility of determining if a process should or shouldn't continue to run, or which processes should run next and on which CPU.

While a scheduler can be as simple as selecting all the ready-to-run processes in round-robin order, modern ass use a very complex algorithm to ensure fairness to all the processes, while maintaining optimum CPU utilisation; and Linux is no exception. The scheduler has two prime responsibilities: fairness among processes and load balancing among CPUs. While the Linux scheduler uses a complex algorithm and heuristics to determine the nature of process (10 bound, CPU bound, etc), this article focuses only on the load-balancing aspect. Therefore, the term 'scheduling', in this article, should be assumed as a scheduler activity to reduce load imbalance among CPUs. The scheduler does it by moving processes from busy to idle CPUs, yet not compromising with system performance.



Now, with the advent of more sophisticated and improved hardware fabrication technologies, CPU architectures have gone through radical changes. Modern high-end systems are SMP-enabled, where more than one CPU shares the processing. This was made more complex by hyper threading, introduced by Intel, where a single processor can run more than one process at a time.

Since a high-end system has multiple CPUs sharing common resources (memory, the bus, etc), the common resources become a bottleneck in performance. To eliminate this bottleneck, another architecture improvement, popularly known as NUMA, was introduced. NUMA architecture allows a subset of CPUs to have faster access exclusively to certain resources. Lastly, multi-core architectures are making a mark in new systems.

wpile these architecture innovations showed great potential to improve system performance, they posed a big challenge to the scheduler because a scheduling decision has to be made iRtelligently to satisfy the various requirement.s of the architecture. Before we move forward to understand how the Linux scheduler dealt with these architectures, it's time to look into some details of the above-mentioned architectures and their requirements, with respect to the scheduler.