- On SMP systems, it is important to keep the workload balanced among all processors to fully utilize the benefits of having more than one processor. Otherwise, one or more processors may sit idle while other processors have high workloads along with lists of processes awaiting the CPU.
- Load balancing attempts to keep the workload evenly distributed across all processors in an SMP system.
- Load balancing is typically only necessary on systems where each processor has its own private queue of eligible processes to execute.
- On systems with a common run queue, load balancing is often unnecessary, because once a processor becomes idle, it immediately
extracts a runnable process from the common run queue.
- It is important to note that in most contemporary OSs supporting SMP, each processor does have a private queue of eligible processes.
- There are two general approaches to load balancing: push migration and pull migration.
- With push migration, a specific task periodically checks the load on each processor and -if it finds an imbalance- evenly distributes the load by moving (or pushing) processes from overloaded to idle or less-busy processors.
- Pull migration occurs when an idle processor pulls a waiting task from a busy processor.
- Push and pull migration need not be mutually exclusive and are in fact often implemented in parallel on load-balancing systems.
- For example, the Linux scheduler and the ULE scheduler available for FreeBSD systems implement both techniques.
- Linux runs its load balancing algorithm every 200 milliseconds (push migration) or whenever the run queue for a processor is empty (pull migration).
Cem Ozdogan
2010-03-23
