Memory-budget job scheduler: a stop-when-over rule overshoots for growing jobs; project growth 2 polls ahead
Setup: a scheduler runs N worker processes under a total RSS budget. It polls RSS every ~0.1 s, and when the sum is over budget it stops the youngest worker and requeues it.
Measured with stand-in workers that really touch memory (20 MB held, then a linear ramp to 60 MB over 4 s), 12 at once, with an external sampler summing the children's RSS every 50 ms: the total went 3-6% over the budget on every run, for up to ~0.2 s at a time. The overshoot is roughly (sum of the growth rates) x (one poll interval + the time a stopped process takes to actually free its memory). A kill isn't instant: SIGTERM handling and page release take a few hundred ms.
A fix that brought it to 0 samples over, with no wall-time change: 1. For each running worker, keep its last (time, RSS) and compute a growth rate, clamped at >= 0. 2. projected = measured_total - memory already being freed by pending stops + sum(rate) x 2 x poll_interval. Two polls: one until the next check, one for a stop to take effect. 3. Stop the youngest while projected > budget. Admit a new worker only if projected + its expected size <= budget. 4. Requeue a stopped worker at the largest size it was seen at, not its starting estimate. Otherwise it is readmitted small, grows again and churns (we saw 19 requeues and 5x wall time). 5. Don't trust an early measurement for bursty admission until RSS has been stable for a few polls.
Caveats: polling can't give a strict bound, because a stopped process can still grow until it dies, so test against budget + a small tolerance (we used 2%). For a hard limit on Linux, put each worker in its own cgroup with memory.max (it may need delegated cgroups or root). Test with an external sampler, not the scheduler's own view: they can disagree.
Follow-up from the same work, after more review rounds: (1) A raw one-poll slope makes a one-off step look like a trend. On real memory it caused 11 needless stops, with workers stopped twice. Use the smaller of the last two per-poll rates. (2) Projection alone misses a worker that steps up after it looked stable (flat for 3 polls, then 10 -> 60 MB at 3 s). The peak hit 2x the budget. What fixed later waves: count every worker that has no prior-run prediction at max(its RSS, the largest RSS any worker has reached), for its whole run, not only until it settles. The first wave can't be protected, since nothing has grown yet. (3) Requeue a stopped worker at the largest RSS seen. Otherwise it restarts small, grows and gets stopped again. (4) Add the growth term to the measured total only, not on top of slot-cap predictions. Stacking them left the last slot waiting about 20 s for headroom that was really there. Test shapes worth keeping: an early step, a late step, a step after a stable stretch, a linear ramp, and a staircase that grows every other poll.