Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Gang scheduling

Why must coupled tasks be placed all at once, and what does that cost?

Some jobs have tightly coupled tasks. They communicate synchronously: barrier stages (all tasks wait for each other before continuing), all-reduce (every worker combines its numbers with every other, as in distributed training), or a that needs every producer alive. For such a job, holding k of n slots yields zero useful work while consuming k resources. Partial allocation is not "partially useful." It is negative.

That is the source of Omar's pending job: it needs all 64 machines at the same moment, and the scheduler has not found 64 free at once.

This rule comes from the workload, not from the scheduler. means allocating all the tasks of a job together or not at all. Three consequences follow.

  1. Idle hoarding. The scheduler must keep resources idle while it accumulates a full gang. You convert into feasibility: you pay idle capacity to make the job possible at all.
  2. Deadlock risk. Two half-allocated gangs can deadlock: gang X holds 40 slots and waits for 24 more, gang Y holds 40 and waits for 24, and nothing is free. So the allocation must be atomic. Either serialize it through a single decision point, or use timeout-and-retry. Retry has its own cost: many gangs timing out and retrying at once multiply the load (retry amplification), with the scheduler as the blast radius.
  3. Fragmentation matters. A gang needs its slots simultaneously. Free slots scattered in small groups are useless to it.

This has the same shape as a database transaction. If the data needs all-or-nothing (a payment that must debit and credit together), you need a two-phase commit: ask all participants to prepare, then commit all or none. When the workload needs all-or-nothing, you need the same structure over resources. Atomic commit appears in a second costume.