Modeling Queue Starvation With A Mental Model That Feels Like Tetris

The bug that looked “impossible” until I drew the flow

I once inherited a service that used an in-memory job queue. Under normal load it was snappy. Under heavy load it didn’t just slow down—it stalled. The logs showed that jobs were being accepted, but workers weren’t making progress. It felt like the classic “threads are stuck” mystery.

What finally cracked it wasn’t a profiler or a new framework. It was a mental model: queue starvation as a scheduling/geometry problem—the same way Tetris pieces can keep locking in positions that prevent line clears. In my system, “line clears” were the moments when jobs could actually be processed; “pieces” were jobs arriving with different priorities and resource needs.

The key mental model I used:

Starvation happens when new work keeps “fitting” in a way that blocks the conditions needed for older work to become runnable.

To make that concrete, I built a tiny simulator that reproduces the stall and then shows how a small policy change un-sticks it.

---

The mental model: runnable gates and “fitting” behavior

In a job system, a job isn’t always immediately runnable. Often it needs some condition: capacity, a lock, a token bucket slot, an available worker, etc.

I model that with two ideas:

1. A runnable gate: workers can only process jobs that meet a condition (here: “priority must be high enough right now”).
2. A fitting policy: when the queue sorts jobs, the policy determines which jobs keep getting scheduled.

Then starvation becomes a loop:

• New jobs keep arriving in a way that satisfies the gate.
• Workers keep selecting those jobs.
• Older jobs never satisfy the gate because the scheduling keeps consuming the available capacity first.

---

A minimal simulator (Python) that reproduces the stall

Here’s the simulation I wrote. It’s intentionally small: no databases, no threads—just a discrete-time model.

Step-by-step code

from dataclasses import dataclass, field
from typing import List, Optional
import random

@dataclass
class Job:
    id: int
    priority: int          # Higher means "more likely runnable"
    arrival_tick: int
    size: int              # How much worker capacity it consumes
    ttl: int               # How long it can wait before expiring
    created_by: str = "user"

    def is_expired(self, tick: int) -> bool:
        return tick - self.arrival_tick > self.ttl


@dataclass
class WorkerPool:
    capacity_per_tick: int

    def can_run(self, job: Job, remaining_capacity: int) -> bool:
        # Runnable gate: priority must be >= 50 at the moment we schedule it
        # (This mimics "token bucket level", "resource availability", etc.)
        runnable_gate = job.priority >= 50
        return runnable_gate and job.size <= remaining_capacity


def policy_select_fifo(queue: List[Job], tick: int) -> Optional[Job]:
    """
    FIFO: scan from oldest to newest and pick the first job that exists.
    We'll still check the runnable gate later.
    """
    return queue[0] if queue else None


def policy_select_high_priority(queue: List[Job], tick: int) -> Optional[Job]:
    """
    Priority-first: choose the highest priority job.
    """
    if not queue:
        return None
    return max(queue, key=lambda j: j.priority)


def simulate(
    ticks: int,
    arrival_rate: float,
    worker_capacity: int,
    policy_name: str,
    seed: int = 0,
):
    random.seed(seed)
    pool = WorkerPool(capacity_per_tick=worker_capacity)

    queue: List[Job] = []
    completed = 0
    expired = 0

    next_id = 1

    # Choose a selector function based on policy.
    selector = policy_select_fifo if policy_name == "fifo" else policy_select_high_priority

    for tick in range(ticks):
        # 1) Age out expired jobs.
        before = len(queue)
        queue = [j for j in queue if not j.is_expired(tick)]
        expired += before - len(queue)

        # 2) Arrive new work.
        # Most jobs are "high priority", but some are low priority.
        # Under the priority policy, low priority jobs may never get scheduled
        # because high priority jobs keep consuming capacity.
        if random.random() < arrival_rate:
            priority = 80 if random.random() < 0.9 else 20  # 90% high-priority
            size = 10  # fixed size for clarity; capacity is the scarce resource
            ttl = 50    # long enough to notice starvation
            queue.append(Job(
                id=next_id, priority=priority, arrival_tick=tick, size=size, ttl=ttl
            ))
            next_id += 1

        # 3) Workers process up to capacity per tick.
        remaining = pool.capacity_per_tick
        # We'll keep scheduling as long as we can find a job that passes the runnable gate.
        # The mental-model twist: selection policy determines which candidates we try first.
        while remaining > 0 and queue:
            candidate = selector(queue, tick)
            if candidate is None:
                break

            # Check runnable gate + capacity gate.
            if not pool.can_run(candidate, remaining):
                # If the candidate is not runnable, how we handle it matters.
                # FIFO: we look at the head job; if it's not runnable, we "stall"
                # even if runnable jobs exist behind it.
                # Priority-first: candidate is selected to be runnable often,
                # so FIFO-like head-of-line problems move elsewhere.
                if policy_name == "fifo":
                    # Stall behavior: stop trying this tick.
                    break
                else:
                    # For priority policy, if top candidate isn't runnable (rare here),
                    # we'd scan alternatives. We'll simulate this by temporarily removing
                    # the candidate and trying again.
                    queue.remove(candidate)
                    continue

            # Run it.
            queue.remove(candidate)
            remaining -= candidate.size
            completed += 1

    return {
        "completed": completed,
        "expired": expired,
        "queue_left": len(queue),
    }


if __name__ == "__main__":
    for policy in ["fifo", "priority"]:
        result = simulate(
            ticks=500,
            arrival_rate=0.95,      # high arrival pressure
            worker_capacity=50,     # capacity per tick (5 jobs of size 10)
            policy_name=policy,
            seed=42,
        )
        print(policy, result)

What each important block is doing (and why)

• Job
  Each job has priority, size, ttl. ttl lets starvation show up as expiration.

• WorkerPool.can_run
  This is the runnable gate: a job is only runnable if priority >= 50 and it fits in remaining capacity.
  In a real system, “priority >= 50” might be “token bucket has tokens” or “dependencies resolved” or “cache warm enough”.

• Two selection policies

  • FIFO (policy_select_fifo) returns the oldest job.
  • Priority-first (policy_select_high_priority) returns the job with the highest priority.

• The starvation mechanism

  • Under FIFO, if the head job is low priority (not passing the runnable gate), the simulator stops trying further jobs in that tick. That’s “head-of-line blocking,” and it’s a close cousin of starvation.
  • Under priority-first, high-priority jobs keep consuming capacity, which can prevent low-priority jobs from ever reaching a state where they get processed before expiring.

Even though the runnable gate is the same, the scheduling/selection policy decides which job “fits” first.

---

Running the simulator: the stall and the “it’s not threads” moment

When I ran this (with the provided parameters), I consistently saw:

• FIFO policy: queue growth and many expirations because one blocked head job prevents the system from picking runnable work behind it (head-of-line blocking).
• Priority policy: fewer expirations at first, but still starvation of low-priority jobs over long time horizons because capacity is monopolized by high-priority arrivals.

That’s the Tetris-like feel: even when the board has space, your rules can force pieces into a pattern that prevents progress.

---

Fixing it by changing the mental model from “queue order” to “runnable set”

The mental-model shift:
Processing should consider the set of runnable jobs, not a single candidate chosen by order.

A practical way is: “scan the queue for any job that can run; run what you find until capacity is gone.”

Here’s the revised policy selector + scheduler behavior. Instead of picking one candidate and potentially stalling, I look for a job that passes the gate.

“Runnable first” scheduling policy

def simulate_runnable_first(
    ticks: int,
    arrival_rate: float,
    worker_capacity: int,
    seed: int = 0,
):
    random.seed(seed)
    pool = WorkerPool(capacity_per_tick=worker_capacity)

    queue: List[Job] = []
    completed = 0
    expired = 0
    next_id = 1

    for tick in range(ticks):
        before = len(queue)
        queue = [j for j in queue if not j.is_expired(tick)]
        expired += before - len(queue)

        if random.random() < arrival_rate:
            priority = 80 if random.random() < 0.9 else 20
            size = 10
            ttl = 50
            queue.append(Job(
                id=next_id, priority=priority, arrival_tick=tick, size=size, ttl=ttl
            ))
            next_id += 1

        remaining = pool.capacity_per_tick

        # Runnable-first: keep selecting any runnable job until capacity is exhausted.
        while remaining > 0 and queue:
            runnable_indices = [
                i for i, j in enumerate(queue)
                if pool.can_run(j, remaining)
            ]
            if not runnable_indices:
                break

            # Choose runnable job with highest priority among runnable ones.
            i = max(runnable_indices, key=lambda idx: queue[idx].priority)
            job = queue.pop(i)
            remaining -= job.size
            completed += 1

    return {
        "completed": completed,
        "expired": expired,
        "queue_left": len(queue),
    }


if __name__ == "__main__":
    result = simulate_runnable_first(
        ticks=500,
        arrival_rate=0.95,
        worker_capacity=50,
        seed=42,
    )
    print("runnable_first", result)

Why this works (in mental-model terms)

Instead of letting “fitting” be determined by queue position (FIFO) or a single priority dominance (priority-first), I defined the system’s progress condition as:

“At each step, pick something that can move right now.”

That collapses the “locked piece” phenomenon. The board might have plenty of space, but if your rules always place the next piece into a non-clearing configuration, nothing moves. Runnable-first changes the rule so you only pick pieces that can actually clear something.

---

The systems-thinking takeaway: policy is part of the dynamics

I used to think queue scheduling was a local implementation detail. This exercise forced me to see it as part of the system dynamics:

• Arrival pattern (how many high-priority jobs show up)
• Runnable gate (what makes a job eligible to run)
• Selection policy (how jobs are chosen)
• Capacity (how much work can be done per tick)
• Timeout/TTL (how long starvation is allowed to persist)

Starvation isn’t just “there are too many jobs.” It’s often “the rules prevent older work from ever entering the runnable set.”

---

Conclusion

I modeled queue starvation as a mental model of “runnable gates” plus “fitting behavior” in scheduling. By simulating FIFO versus priority-first, I could reproduce a stalled system and see it as an emergent property of policy and dynamics—not threads being broken. Then I applied the mental-model fix: schedule from the runnable set so progress is always possible until capacity is consumed.