Gang Scheduling

Gang scheduling places a group of tasks, the gang, so that either every member starts together or none does. It is used when the members depend on one another to make progress, which is the case for distributed training: each step ends with a collective operation, such as summing gradients across workers, that cannot complete until every worker takes part. A training job with three of four workers running is not three-quarters of the way to useful work. It is making none, and its three workers occupy accelerators while they wait.

The failure it prevents

A scheduler that places workers one at a time, each as soon as it fits, can reach a state where no job can ever start. Suppose the cluster has four GPUs, and jobs A and B each need three single-GPU workers running simultaneously. If the workers are created interleaved (A0, B0, A1, B1, …), which is what happens when two controllers react to submissions at the same time, the first four placements fill the cluster.

free = 4
pods = ["A0", "B0", "A1", "B1", "A2", "B2"]
held = {"A": 0, "B": 0}
for p in pods:                       # pod-by-pod: place whatever fits
    if free > 0:
        free -= 1; held[p[0]] += 1
print("pod-by-pod  held:", held, "free:", free, "-> running jobs:", [j for j, n in held.items() if n == 3])

free = 4; started = []
for job in ("A", "B"):               # gang: admit a job only if all 3 workers fit now
    if free >= 3:
        free -= 3; started.append(job)
print("gang        started:", started, "free:", free, "(B waits for A to finish)")

This ran under Python 3.12.14 on macOS 26.7.1 and printed:

pod-by-pod  held: {'A': 2, 'B': 2} free: 0 -> running jobs: []
gang        started: ['A'] free: 1 (B waits for A to finish)

Each job holds two GPUs and needs a third that only the other job could release. Neither will release anything, because releasing means giving up progress it has not yet been allowed to make. This is a deadlock in the textbook sense (hold-and-wait with no preemption), and waiting does not resolve it. With gang admission, job A is placed in full, job B stays queued, and B starts when A finishes. One GPU stays idle meanwhile, which is the cost of the guarantee.

How it is implemented

The mechanism is atomic admission of the whole group, which needs the scheduler to know the group exists and how many members it must wait for. Systems differ in where that happens. Kueue, a Kubernetes job queueing system, admits a Workload all-or-nothing: quota is reserved for the whole workload or not at all. Its waitForPodsReady option adds a second stage, evicting and requeuing a workload whose Pods do not all become ready within a timeout, with exponential backoff before retrying. Kubernetes itself documents a gang scheduling policy on a PodGroup, with a minCount of Pods that must be placed atomically. At the time of writing that documentation lists the feature as beta since v1.37 and disabled by default behind the GenericWorkload feature gate, so availability depends on the cluster version and configuration.

What it costs and what it does not solve

• Waiting for a large block. A gang of 32 GPUs waits until 32 are free in the right places, while smaller jobs keep taking the capacity as it appears. Systems bound this with reservations, backfilling of short jobs into the gaps, or priority for the oldest large job; without one of these, a large gang can starve.
• Placement still matters. Atomic admission checks that the gang fits. If the free GPUs are scattered so that no valid placement exists, the gang waits regardless of quota. See GPU fragmentation.
• A member can fail after admission. One lost worker stalls the others, which keep their GPUs. The group has to be torn down and restarted together, which is why gang scheduling is paired with checkpointing.
• Elastic jobs relax the rule. A job that can run with fewer workers needs only a minimum placed together, and can grow later. The minimum is the gang.

The idea is older than GPU clusters. It appeared in parallel computing as coscheduling the threads of a parallel program onto processors at the same time, for the same reason: threads that wait on each other waste the processors they hold.

References

• Kubernetes documentation, Gang Scheduling
• Kueue documentation, Workload