Resource allocation and quotas

intermediateCommon atAnthropicGoogleAmazonStripeRead firstIntervalsGreedySorted containersPractise in the Sandbox →

Resource allocation is bookkeeping with one invariant: what you have handed out never exceeds what exists, and every unit is either free or owned by exactly one holder. On top of that you choose a policy: where to place a request (first fit, best fit), who gets scarce capacity (first come, proportional, max-min fair), and what each tenant may hold (quotas cap usage, reservations guarantee a floor). The hard part is usually not the arithmetic but fragmentation and fairness.

The idea in plain words

Picture a car park. Some spaces are taken, some free. A driver arrives with a van that needs three spaces side by side.

• Placement is which three spaces you send them to. Take the first gap big enough? The tightest gap? It matters: send the van to a big gap and the next bus might not fit anywhere.
• Fragmentation is when the car park has 20 free spaces in total but no 3 in a row. Nothing is technically full, yet the van is turned away.
• Quotas are “a company may hold at most 10 spaces”, however empty the car park is.
• Reservations are “these 4 spaces are kept for the night shift”, even when the night shift has not arrived.
• Fairness is how you split the car park when everyone wants more than there is.

Every allocator (malloc, a Kubernetes scheduler, GPU slots for model serving, a per-customer budget) is some mix of these five decisions.

See it

Four allocators receive the same requests on a 32-unit address space. Click a block to free it, or allocate your own sizes, then run the clock to replay history one request at a time. Watch where each policy leaves its holes, and which one fails first.

Same requests, four placement policies

sandbox + replay

size

allocate K (5)preset workloadempty heap

Click a block to free it. Last request: allocate J (6 units)

first fitlowest-address hole that fitsplaced at 16 · 2 holes checked

G·2

I·3

B·3

H·4

2

D·2

J·6

F·4

5

free 8largest hole 5holes 3external fragmentation 38%failed 0

best fitsmallest hole that fitsplaced at 8 · 3 holes checked

G·2

I·3

B·3

J·6

D·2

7

F·4

H·4

free 8largest hole 7holes 2external fragmentation 13%failed 0

worst fitlargest holeFAILED · 4 holes checked

I·3

2

B·3

H·4

2

D·2

G·2

5

F·4

5

free 14largest hole 5holes 4external fragmentation 64%failed 1

next fitfirst fit, resuming where the last search stoppedplaced at 16 · 2 holes checked

H·4

B·3

I·3

3

D·2

J·6

▲

F·4

G·2

3

free 8largest hole 3holes 4external fragmentation 63%failed 0

Run the clock to replay the requests one at a time. External fragmentation = 1 − largest hole / total free: high means plenty of free space in total but no single hole big enough. Replay the preset (worst fit fails on J), then allocate 7 units: only one policy still has a hole that big.

request failedbadly fragmented

↺◀▶ Run▶request 13 / 13

Placement is half the story. The other half is who gets capacity when demand exceeds it. Drag the sliders: reservations come off the top, limits cap each tenant, and a policy splits what remains.

Sharing capacity: reservations, limits and a fairness policy

drag the sliders

policy for the shared poolfirst come, first servedproportional to demandmax-min fair

capacity = 20 cores

searchgets 3 of 3 wanted

demand = 3reserved = 2limit = 16

batchgets 5.5 of 14 wanted, 8.5 unmet

demand = 14reserved = 0limit = 10

apigets 6 of 6 wanted

demand = 6reserved = 4limit = 16

mlgets 5.5 of 9 wanted, 3.5 unmet

demand = 9reserved = 0limit = 16

capacity20

reserved6

in use20

idle but reserved0

idle, unreserved0

unmet demand12

water level5.5

Reservations are carved out first and stay held even when unused (striped). A limit caps what a tenant can get even if capacity is idle. Switch policies: first-come starves later tenants, proportional rewards whoever asks for most, max-min fills small demands completely and splits the rest evenly.

reserved and usedreserved, idlefrom the shared poolunmet demand

When to reach for it

The problem says…	What you are really designing
“allocate / free a contiguous range of size n”	An address-space allocator: free list, placement policy, coalescing of neighbours.
“each user / tenant has a capacity or quota”	A per-owner usage counter checked before the change is applied (admission control).
“guaranteed minimum” / “requests vs limits”	Reservations (a floor that is held) plus limits (a ceiling that is enforced).
“N jobs share K GPUs / slots / tokens”	A fairness policy over a shared pool: FCFS, priority, proportional, max-min, weighted.
“pack these items into as few machines/bins as possible”	Bin packing: NP-hard, so a greedy (first-fit decreasing) with a known bound.
“budget that refills over time”	That is rate limiting: see Rate limiting.

How it works

Placement in an address space

An allocator keeps a set of holes (free ranges). On a request for n units it picks a hole by policy, carves n units off it, and leaves the remainder as a smaller hole. On free it returns the range and coalesces it with any free neighbour, otherwise the space shatters into slivers that each look too small.

Policy	Picks	Effect
first fit	lowest-address hole that fits	Fast; small leftovers gather near the start. Knuth found it competitive in practice.
next fit	first fit, resuming where the last search stopped	Spreads allocations; often fragments more than first fit.
best fit	the smallest hole that fits	Saves big holes for big requests, but leaves tiny unusable slivers.
worst fit	the largest hole	Leftovers stay large; in studies it is generally the worst, as the name suggests.

Wilson et al.’s survey found address-ordered first fit and best fit both fragment little on real program traces; the bigger wins came from coalescing promptly and from segregating requests by size class (as jemalloc, tcmalloc and the Linux slab allocator do).

Internal vs external fragmentation. Internal: waste inside a block you handed out (asked for 5, got a rounded-up 8). External: waste between blocks (free holes too small to use). A common external-fragmentation measure is 1 − largest_hole / total_free, the stat the simulator shows.

Compaction fixes external fragmentation by sliding live blocks together so all free space becomes one hole. It costs a copy of every moved byte and requires that nobody holds a raw address into a moved block, which is why managed runtimes (the .NET and JVM garbage collectors) can compact but C’s malloc cannot. Systems that can’t move data use paging instead: fixed-size pages make every hole the same size, trading external fragmentation for a little internal fragmentation.

Quotas and reservations

1. Check before you change. Admission control: if used + n > quota, refuse and change nothing. Never apply first and roll back on overflow; a concurrent reader might see the overdraft.
2. Account per owner. Keep used[owner] updated on every allocate, free, move and ownership transfer, so checks stay O(1) instead of re-summing.
3. Reserve, then commit. For multi-step work, place a hold first (counts against capacity), then commit it to real usage or release it. Give holds an expiry so a crashed client can’t leak capacity forever (see TTL and expiry).
4. Reservations hold capacity. The sum of guaranteed floors must not exceed capacity. Refuse a reservation that would overbook, unless you deliberately overcommit and accept that guarantees can fail.

Splitting scarce capacity fairly

Max-min fairness maximises the smallest allocation, then the next smallest, and so on. Its “water-filling” form: sort by demand, give each tenant min(demand, remaining / tenants_left), and let the unused share of small tenants flow to the bigger ones.

Python

max_min_fair.py

def max_min_fair(capacity: float, demands: list[float]) -> list[float]:
    """Max-min fair share ("water-filling"): nobody gets more than they asked for,
    and no one can get more without taking from someone who has less."""
    alloc = [0.0] * len(demands)
    order = sorted(range(len(demands)), key=lambda i: demands[i])  # 1. smallest demand first
    left = capacity
    for k, i in enumerate(order):
        fair = left / (len(order) - k)       # 2. equal split of what is left among the rest
        alloc[i] = min(demands[i], fair)     # 3. small demands are fully met...
        left -= alloc[i]                     # 4. ...and their unused share flows to the others
    return alloc


if __name__ == "__main__":
    assert max_min_fair(10, [2, 8, 4]) == [2, 4, 4]      # 2 is met; 8 and 4 split the other 8
    assert max_min_fair(12, [1, 2, 3]) == [1, 2, 3]      # enough for everyone
    assert max_min_fair(9, [5, 5, 5]) == [3, 3, 3]       # nobody satisfied: equal split
    assert max_min_fair(10, []) == []
    print("ok")

TypeScript

max_min_fair.ts

import assert from "node:assert/strict";

/** Max-min fair share ("water-filling"): nobody gets more than they asked for,
 *  and no one can get more without taking from someone who has less. */
export function maxMinFair(capacity: number, demands: number[]): number[] {
  const alloc = new Array<number>(demands.length).fill(0);
  const order = demands.map((_, i) => i).sort((a, b) => demands[a] - demands[b]); // 1. smallest first
  let left = capacity;
  order.forEach((i, k) => {
    const fair = left / (order.length - k); // 2. equal split of what is left among the rest
    alloc[i] = Math.min(demands[i], fair); // 3. small demands are fully met...
    left -= alloc[i]; // 4. ...and their unused share flows to the others
  });
  return alloc;
}

assert.deepEqual(maxMinFair(10, [2, 8, 4]), [2, 4, 4]); // 2 is met; 8 and 4 split the other 8
assert.deepEqual(maxMinFair(12, [1, 2, 3]), [1, 2, 3]); // enough for everyone
assert.deepEqual(maxMinFair(9, [5, 5, 5]), [3, 3, 3]); // nobody satisfied: equal split
assert.deepEqual(maxMinFair(10, []), []);
console.log("ok");

C#

max_min_fair.cs

Check(MaxMinFair(10, [2, 8, 4]), [2, 4, 4]);   // 2 is met; 8 and 4 split the other 8
Check(MaxMinFair(12, [1, 2, 3]), [1, 2, 3]);   // enough for everyone
Check(MaxMinFair(9, [5, 5, 5]), [3, 3, 3]);    // nobody satisfied: equal split
Check(MaxMinFair(10, []), []);
Console.WriteLine("ok");

/// Max-min fair share ("water-filling"): nobody gets more than they asked for,
/// and no one can get more without taking from someone who has less.
static double[] MaxMinFair(double capacity, double[] demands)
{
    var alloc = new double[demands.Length];
    var order = Enumerable.Range(0, demands.Length).OrderBy(i => demands[i]).ToArray(); // 1. smallest first
    double left = capacity;
    for (int k = 0; k < order.Length; k++)
    {
        int i = order[k];
        double fair = left / (order.Length - k);   // 2. equal split of what is left among the rest
        alloc[i] = Math.Min(demands[i], fair);     // 3. small demands are fully met...
        left -= alloc[i];                          // 4. ...and their unused share flows to the others
    }
    return alloc;
}

static void Check(double[] got, double[] want)
{
    if (!got.SequenceEqual(want)) throw new Exception($"got [{string.Join(", ", got)}], want [{string.Join(", ", want)}]");
}

Weighted versions divide by weights instead of counts. For several resources at once (CPU and memory), Dominant Resource Fairness (Ghodsi et al., 2011) equalises each tenant’s share of whichever resource it uses most.

Packing items into bins

Placing VMs on hosts, batches on GPUs or shipments in trucks is bin packing, which is NP-hard. The greedy everyone reaches for is first-fit decreasing: sort items largest first, then put each into the first bin with room.

1. Sort items by size, largest first: big items are the hard ones to place, so place them while there is choice.
2. For each item, use the first open bin with enough room.
3. If none fits, open a new bin.

Python

first_fit_decreasing.py

def first_fit_decreasing(sizes: list[int], capacity: int) -> list[list[int]]:
    """Pack items into as few bins of `capacity` as a simple greedy can.
    Uses at most 11/9 * OPT + 6/9 bins (Dosa, 2007)."""
    if any(s <= 0 or s > capacity for s in sizes):
        raise ValueError("every item must fit in an empty bin")
    bins: list[list[int]] = []
    room: list[int] = []                       # free space left in each bin
    for s in sorted(sizes, reverse=True):      # 1. biggest items first: they are hardest to place
        for b, free in enumerate(room):        # 2. first bin with room wins
            if s <= free:
                bins[b].append(s)
                room[b] -= s
                break
        else:                                  # 3. nothing fits: open a new bin
            bins.append([s])
            room.append(capacity - s)
    return bins


if __name__ == "__main__":
    items = [5, 7, 5, 2, 4, 2, 5, 1, 6]
    bins = first_fit_decreasing(items, 10)
    assert bins == [[7, 2, 1], [6, 4], [5, 5], [5, 2]]
    assert len(bins) == -(-sum(items) // 10)   # 37 units need at least 4 bins: optimal here
    assert sorted(x for b in bins for x in b) == sorted(items)
    print("ok")

TypeScript

first_fit_decreasing.ts

import assert from "node:assert/strict";

/** Pack items into as few bins of `capacity` as a simple greedy can.
 *  Uses at most 11/9 * OPT + 6/9 bins (Dosa, 2007). */
export function firstFitDecreasing(sizes: number[], capacity: number): number[][] {
  if (sizes.some((s) => s <= 0 || s > capacity)) throw new RangeError("every item must fit in an empty bin");
  const bins: number[][] = [];
  const room: number[] = []; // free space left in each bin
  for (const s of [...sizes].sort((a, b) => b - a)) { // 1. biggest items first: hardest to place
    const b = room.findIndex((free) => s <= free); // 2. first bin with room wins
    if (b >= 0) {
      bins[b].push(s);
      room[b] -= s;
    } else { // 3. nothing fits: open a new bin
      bins.push([s]);
      room.push(capacity - s);
    }
  }
  return bins;
}

const items = [5, 7, 5, 2, 4, 2, 5, 1, 6];
const bins = firstFitDecreasing(items, 10);
assert.deepEqual(bins, [[7, 2, 1], [6, 4], [5, 5], [5, 2]]);
assert.equal(bins.length, Math.ceil(items.reduce((a, b) => a + b, 0) / 10)); // optimal here
assert.deepEqual(bins.flat().sort((a, b) => a - b), [...items].sort((a, b) => a - b));
console.log("ok");

C#

first_fit_decreasing.cs

int[] items = [5, 7, 5, 2, 4, 2, 5, 1, 6];
var bins = FirstFitDecreasing(items, 10);
var shape = string.Join(" | ", bins.Select(b => string.Join(",", b)));
if (shape != "7,2,1 | 6,4 | 5,5 | 5,2") throw new Exception($"unexpected packing {shape}");
if (bins.Count != (items.Sum() + 9) / 10) throw new Exception("37 units need 4 bins: optimal here");
if (!bins.SelectMany(b => b).Order().SequenceEqual(items.Order())) throw new Exception("lost an item");
Console.WriteLine("ok");

/// Pack items into as few bins of `capacity` as a simple greedy can.
/// Uses at most 11/9 * OPT + 6/9 bins (Dosa, 2007).
static List<List<int>> FirstFitDecreasing(int[] sizes, int capacity)
{
    if (sizes.Any(s => s <= 0 || s > capacity)) throw new ArgumentException("every item must fit in an empty bin");
    var bins = new List<List<int>>();
    var room = new List<int>();                            // free space left in each bin
    foreach (int s in sizes.OrderByDescending(x => x))     // 1. biggest items first: hardest to place
    {
        int b = room.FindIndex(free => s <= free);         // 2. first bin with room wins
        if (b >= 0) { bins[b].Add(s); room[b] -= s; }
        else { bins.Add([s]); room.Add(capacity - s); }    // 3. nothing fits: open a new bin
    }
    return bins;
}

What it costs

Operation	Plain list of holes	Holes in balanced trees (by address and by size)
first fit	O(h) scan	O(log h) with an augmented tree, else O(h)
best fit	O(h) scan	O(log h): “smallest size ≥ n” in a size-ordered tree
free + coalesce	O(h) to find neighbours	O(log h): predecessor and successor by address
quota check	O(1) with a per-owner counter	same
compaction	O(blocks + bytes moved)	same
max-min fair share	O(t log t) for t tenants (the sort)
first-fit decreasing	O(n log n + n·b) for b bins	O(n log n) with a tree over bin room

Here h is the number of holes, not the size of the space. Model ranges, not individual units: a 10⁹-unit space with a thousand allocations should cost thousands of operations, not billions.

Variations you’ll meet

• Buddy allocator. Sizes are powers of two; a block splits into two “buddies” and merges back only with its buddy. Coalescing is O(log size) and trivial; internal fragmentation can reach ~50%.
• Slab / size-class allocators. One pool per object size (16, 32, 48 bytes…). No external fragmentation inside a class; used by jemalloc, tcmalloc and Linux kernel slabs.
• Overcommit. Hand out more than exists, betting not everyone uses it at once (Linux virtual memory, cloud CPU). Needs a plan for when the bet loses (the OOM killer, eviction, preemption).
• Preemption by priority. When a high-priority request can’t fit, evict lower-priority holders and requeue them. Must avoid starving the low tier forever.
• Hierarchical quotas. An org quota contains team quotas that contain user quotas; a change must pass every level.
• Time-based quotas. “1,000 requests per hour” or “$50 of credit per month” is capacity that refills; that is a token bucket.

Pitfalls

• Check-then-act races. Two concurrent requests each see room for one and both succeed. Do the check and the update atomically (a lock, a compare-and-swap, or a single SQL UPDATE … WHERE used + n <= quota). See Concurrency.
• Forgetting to coalesce on free, or coalescing only one side. Free the middle of three adjacent blocks last and check you end with one hole.
• Partial failure. An allocation that touches several resources (quota, then space) must leave nothing behind when the second step fails.
• Off-by-one on ranges. Pick half-open [start, start + n) and stick to it; then adjacent ranges satisfy a.end == b.start.
• Bad inputs. Size 0, negative sizes, freeing an address that isn’t a block start, double free. Decide and state each behaviour.
• Leaked reservations. A hold with no expiry is capacity lost forever when a client crashes.

In the interview

• Ask: Can a block move once placed? How big is the space versus the number of requests? Is a refusal an error or a normal return? Is it concurrent? Who owns a block, and can ownership move?
• State the invariant: “Free and allocated ranges tile the space exactly, no overlaps, and no two free ranges touch.”
• Name the placement policy and its trade-off before coding; say what you’d measure (largest hole, number of holes, failed requests).
• Expect follow-ups: switch to best fit, add per-owner quotas, release everything an owner holds, compact, make it thread-safe, what happens at 10⁶ blocks.

Check yourself

Check yourself

pick one

A heap has 40 free units in total, spread over eight holes of 5. A request for 6 units arrives. What best describes the situation?

AOut of memory: the allocator is fullBExternal fragmentation: plenty of free space, but no single hole is big enoughCInternal fragmentation: the blocks handed out are too big

Check yourself

pick one

Capacity 12, three tenants demand 2, 5 and 9. What does max-min fair sharing give each?

A4, 4, 4B2, 5, 5C2, 5, 9 scaled to 12: 1.5, 3.75, 6.75D2, 4, 6

Check yourself

pick one

Two requests run at the same time. Each reads used = 9 against quota = 10, decides one more unit fits, and writes used = 10. What went wrong?

ANothing; the final value is 10BA lost update: both units were granted, so real usage is 11 but the counter says 10CThe quota should have been 11

Practice on your own

These are classic textbook exercises, not gym questions:

• Implement a buddy allocator for a 1,024-unit space; verify blocks merge back to one 1,024 block after freeing everything.
• Pack a list of VM sizes onto hosts with first fit, best fit and first-fit decreasing; compare bin counts on 1,000 random items.
• Weighted max-min fairness: tenants with weights 1, 2, 1 share 12 units.
• Dominant Resource Fairness by hand: 9 CPUs and 18 GB, user A’s tasks need ⟨1 CPU, 4 GB⟩, user B’s need ⟨3 CPU, 1 GB⟩ (the DRF paper’s example).
• Simulate 10,000 random alloc/free requests with first fit and best fit; plot external fragmentation over time.

Go deeper

• Knuth, The Art of Computer Programming vol. 1, §2.5 “Dynamic Storage Allocation”: first fit, best fit, boundary tags, the buddy system.
• Wilson, Johnstone, Neely and Boles, Dynamic Storage Allocation: A Survey and Critical Review (1995).
• Ghodsi et al., Dominant Resource Fairness: Fair Allocation of Multiple Resource Types (NSDI 2011).
• Kubernetes docs, Resource Management for Pods and Containers: requests (reservations) vs limits, in production.

Related

IntervalsFree and used ranges are intervals: merging, overlap, adjacency.

Sorted containersFind a range's neighbours or the smallest hole that fits in O(log n).

Memory efficiencyWhat each element really costs, compaction, and fixed-size buffers.

Scheduling and task queuesAllocating time on workers instead of space in memory.