CSE221 - lec14: Scheduling:Scheduler Activation & Decades of Wasted Cores

Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism

Threading Model

User Level Threads v.s. Kernel Level Threads

Scheduler Activations

• OS allocate cores to user-level by creating and handing a scheduler activation to user level library.

• user level library schedules threads on cores

• when OS want to remove a core from user-level, it preempt 2 scheduler activations, (one for upcall) and upcall to user-level library, user-level library can make decisions on scheduling according to this action.

Summary

• pros & cons of user-level and kernel level threads

• use upcall to delegate decision to user-level

The Linux Scheduler: a Decade of Wasted Cores

Scheduler Goals

• enforce policy (e.g. fairness, priority …)

• no starvation

• work conservation: no cores sit idle when there are threads waiting

• performance

• efficient: power consumption, cache behavior

• general purpose

Single Core Scheduling

Trivial Scheduler

• use a FIFO queue to schedule threads

CFS(Completely Fair Scheduling)

• preemptive: make scheduling periodically (timeslice)

• weighted

• implemented via RB Tree (key is vruntime)

Multi-core CPU Scheduling

• use per-core run queue to reduce contention

Challenges on Scheduling with Multi-core CPU

• how to address imbalanced load (combined with priority requirement)

• complex cache hierarchy: try to avoid unnecessary migration (how to balance this with utilization goal, since migrate to idle cpu improve utilization)

• (below is a NUMA node that shows cache hierarchy)

Linux Load Balancing

• “emergency”: idle core try to steal work from busy cores

• periodically do load balancing

• on-wakeup: try to wake up on idle cores

• load metric: combine weight and average CPU utilization

• balance load bottom up

Summary

• scalable scheduler design with per-core run queue

• different approach to balance load

• cpu scheduling can be tricky