Multi-Core Software

Process Scheduling Challenges in the Era of Multi-Core Processors

PROCESS SCHEDULER

The process scheduler, which is a critical piece of the operating system software, manages the CPU resource allocation to tasks. The process scheduler typically strives

Figure 1: Process scheduling domain topology setup in the Linux* kernel
click image for larger view
 

for maximizing system throughput, minimizing response time, and ensuring fairness among the running tasks in the system. Process priority determines the allotted time (time-slice) on a CPU and when to run on a CPU. In SMP, the process scheduler is also responsible for distributing the process load to different CPUs in the system.

In NUMA platforms, memory access time is not uniform across all the CPUs in the system and depends on the memory location relative to a processor. System software tries to minimize the access times, by allocating the process memory on the node that is closest to the CPU that the process is running on. As such, the cost associated with the process migration from one NUMA node to another is big. As a result, the process scheduler needs to be aware of NUMA topology. NUMA schedulers use some heuristics (such as tolerating more load imbalances between nodes and tracking the home node of each process, where the majority of process memory resides) to minimize the migrations and costs associated with the migrations.

In SMT (for example, Hyper-Threading Technology), most of the core execution resources are shared by more than one logical processor. The process scheduler needs to be aware of the SMT topology and avoid situations where more than one thread sibling on one core is busy, while all the thread siblings on another core are completely idle. This will minimize the resource contention, maximize the utilization of CPU resources, and thus maximize system throughput. As the logical thread siblings are very close to each other, process migration between them is very cheap and as such, process load balancing between them can be done very often.

The process scheduler needs to consider all these topological differences while balancing process loads across different CPUs in the system. For example, the 2.6 Linux* kernel process scheduler introduced a concept called scheduling domains [8] to incorporate the platform topology information into the process scheduler. The hierarchical scheduler domains are constructed dynamically depending on the CPU platform topology in the system. Each scheduler domain contains a list of scheduler groups having a common property. The load balancer runs at each domain level, and domain properties dictate the balancing that happens between the scheduling groups in that domain. On a high-end NUMA system with SMT capable processors, there are three scheduling domains, one each for SMT, SMP, and NUMA, as shown in Figure 1.

Back to Top