Scheduling Policy: Allocating Limited Cores Among Competing Jobs Diagram

A small cluster has five nodes and 160 CPU cores in total; the scheduler receives two job requests, each wanting 100 cores to complete its work
One option is to run 80 tasks of each job and start the remaining 20 tasks of each job as earlier tasks complete
If the second request arrives much later than the first, the scheduler has incomplete information: it must guess whether a future job might or might not ever come
Every allocation decision must balance fairness against efficiency

Gang scheduling holds cores until all 100 are free at the same time: nodes sit idle, resource utilization drops, and a deadlock can occur if other jobs also try to reserve cores
If the scheduler simply waits for 100 cores to become available, other jobs may grab the cores in the meantime — the cluster might not free 100 cores for a very long time, which is starvation
Preemption kills some of the first job's tasks to make room for the second; the killed tasks must be restarted later, so cluster efficiency falls again

Scaling the dilemma up to hundreds or millions of job requests makes an optimal allocation intractable: the problem is NP-hard, prohibitively slow to solve exactly except on the smallest examples
In practice schedulers therefore make nonoptimal but reasonable decisions with first-in first-out (FIFO), dominant resource fairness (DRF), priority queues, capacity or quota-based scheduling, and various bin-packing algorithms
A centralized scheduler works together with application-specific subschedulers — YARN calls them ApplicationMasters, Kubernetes calls them operators — to decide how best to execute tasks