Linux Kernel Architecture

Chapter 2: Process Management and Scheduling

allow the kernel to keep track when the last balancing operation has been performed, and when the next

will take place.

So what doesload_balancedo? The function checks if enough time has elapsed since the last

re-balancing operation, and initiates a new re-balancing cycle if necessary by invokingload_balance.

The code flow diagram for this function is shown in Figure 2-26. Notice that I describe a simplified

version because the SMP scheduler has to deal with a very large number of corner cases that obstruct the

view on the essential actions.

More than one process on busiest queue?

Balancing failed? Wake up migration task

load_balance

find_busiest_cpu

move_tasks class->load_balance

Figure 2-26: Code flow diagram forload_balance.

First of all, the function has to identify which queue has most work to do. This task is delegated to

find_busiest_queue, which is called for a specific run queue. The function iterates over the queues

of all processors (or, to be precise, of all processorsin the current scheduling group) and compares their

load weights. The busiest queue is the queue with the largest value found in the end.

Oncefind_busiest_queuehas identified a very busy queue, and if at least one task is running on this

queue (load balancing will otherwise not make too much sense), a suitable number of its tasks are

migrated to the current queue usingmove_tasks. This function, in turn, invokes the scheduler-class-

specificload_balancemethod.

When selecting potential migration candidates, the kernel must ensure that the process in question

❑ is not running at the moment or has just finished running because this fact would cancel out the

benefits of the CPU caches currently filled with the process data.

❑ may execute on the processor associated with the current queue on the grounds of its CPU affin-

ity.

If balancing failed (e.g., because all tasks on the remote queue have a higher kernel-internal priority

value, i.e., a lower nice priority), the migration thread that is responsible for the busiest run queue is

woken up. To ensure that active load balancing is performed that is slightly more aggressive than the

method tried now,load_balancesets theactive_balanceflag of the busiest run queue and also notes

the CPU from which the request originates inrq->cpu.

The Migration Thread

The migration thread serves two purposes: It must fulfill migration requests originating from the sched-

uler, and it is used to implement active balancing. This is handled in a kernel thread that executes

migration_thread. The code flow diagram for the function is shown in Figure 2-27.