bugger.
All challenges/Pythonhardthe-permit-that-skips-the-queue-v1
THE INVESTIGATION

The permit that skips the queue

A busy worker keeps reacquiring a free permit while older requests starve.

ConcurrencyFairnessResource accounting

What’s going wrong

A worker pool has a FIFO waiter deque, but a fast worker can repeatedly release and reacquire while older work waits. Trace the scheduling gap, not just the counter.

Stdin JSON contains permits (0..8) and at most 200 events. Each acquire event ["acquire", id] uses a globally unique request ID. If no older waiter exists and a permit is free, acquire immediately; otherwise enqueue. ["release", id] returns a permit only for a current holder; other releases do nothing. Release does not run waiting work. ["resume"] grants as many free permits as possible to queued requests in FIFO order. ["cancel", id] removes a queued request only; cancelling holders or unknown IDs does nothing. Only resume runs queued requests.

Print an object with free (available permits), holders (lexically sorted IDs), waiting (FIFO IDs), and grants (every granted ID in grant order). IDs are short ASCII strings. Preserve immediate uncontended acquisition, cancellation and permit conservation. The output may intentionally have both free permits and queued work before resume. This replay models requests, not actual coroutines.

Expected behavior

A busy worker keeps reacquiring a free permit while older requests starve.

Reproduction

01 Reacquisition overtakes an older request
{"permits":1,"events":[["acquire","a"],["acquire","b"],["release","a"],["acquire","c"],["resume"]]}
{"free":0,"holders":["b"],"waiting":["c"],"grants":["a","b"]}
02 Uncontended permits remain immediate
{"permits":2,"events":[["acquire","a"],["acquire","b"]]}
{"free":0,"holders":["a","b"],"waiting":[],"grants":["a","b"]}
03 Release followed by scheduler resumption
{"permits":1,"events":[["acquire","a"],["acquire","b"],["release","a"],["resume"]]}
{"free":0,"holders":["b"],"waiting":[],"grants":["a","b"]}

Before you begin

  • Python state machines
  • Event ordering and invariants
  • Regression test design

Need a nudge?

Reveal one investigation hint at a time. Try each clue before opening the next.

    The bug is intentional. Run the starter code to see it fail, then work toward a fix. Difficulty is provisional.
    Read-only preview
    Ready when you are
    Every fix starts with a failing test.

    Read the report, then sign in to start your investigation.