Skip to content

Lock Preemption

Recovery method — instantiates Deadlock Resolution

Revokes or transfers one exclusive claim from its current holder — against the holder's will — so a single link in the cycle is severed while the rest of that holder's work survives.

Once a deadlock is confirmed, the narrowest possible intervention is to take back exactly one thing. Lock Preemption revokes or reassigns a single exclusive claim — a lock, a lease, a checked-out resource — from the participant currently holding it, without that participant's consent, so the edge it represents disappears from the cycle. Its defining move is surgical and against the no-preemption assumption: unlike killing the whole holder, the holder keeps running and keeps its other resources; only the one contested claim is pulled. That precision is also its hazard — the holder made decisions assuming it still owned that claim, so preemption is only safe when the holder can be suspended and later handed the claim back cleanly.

Example

A version-control system enforces exclusive checkout on binary assets that can't be merged — a texture file, say. Artist A holds the exclusive lock on hero.psd and is now blocked waiting for the lock on hero.mesh, which Artist B holds; B is blocked waiting on hero.psd. Classic two-party cycle, and nobody will voluntarily give up a half-finished edit. An administrator with preemption rights picks the lower-cost victim claim — B has only just acquired hero.mesh and made no local changes — and transfers that lock to A. A proceeds, finishes, releases both; the cycle is gone.

Preemption's whole discipline shows up in what happens to B. Because B's claim was pulled mid-flight, B is not simply told "no" — B is placed in a re-entry queue and re-granted hero.mesh the moment A releases it, with a warning that any uncommitted local edit must be re-based. The break is one lock, chosen for cheap reversibility, with a defined path back in for the party that lost it — not a blanket override.

How it works

What distinguishes preemption from the blunter recoveries is that it operates at the granularity of a single claim:

  • Select the victim claim, not the victim participant. From the cycle's cuttable edges, pick the one exclusive claim whose removal frees the loop at the least cost — favoring claims that are freshly acquired, uncommitted, or cheap to reacquire.
  • Suspend and revoke. Freeze the holder with respect to that claim and pull it, transferring it to the waiter or returning it to the pool. The holder's other holds are untouched.
  • Queue the loser's re-entry. The dispossessed holder is not aborted; it is registered to reacquire the claim under a re-entry rule so it can resume rather than restart.
  • Guard against re-deadlock. Ensure the preemption plus re-entry ordering can't immediately re-form the same cycle (e.g. the loser can't instantly grab back and re-block).

Tuning parameters

  • Victim-cost function — what makes a claim the one to pull: age, uncommitted-work size, holder priority, reacquisition cost. Choosing "cheapest to the system" versus "fairest to holders" tunes who bears the disruption.
  • Preempt vs. transfer — release the claim back to the pool, or hand it directly to a waiter. Direct transfer is faster but bakes in a winner; releasing is neutral but may let a third party grab it.
  • Re-entry priority — how soon and how favorably the dispossessed holder gets the claim back. Set it too low and preemption becomes starvation for that party.
  • Consent boundary — how far preemption may reach (only uncommitted claims, or committed ones too). Widening it resolves more deadlocks but risks violating more holder assumptions.

When it helps, and when it misleads

Its strength is proportionality: it breaks a deadlock by removing the minimum — one claim — leaving the holder's remaining work and progress intact, which makes it far cheaper than terminating a participant when only one resource is contended. It directly negates the no-preemption condition that circular waits depend on.[1]

It misleads when the holder's assumptions can't actually be unwound. Pulling a claim the holder has already built irreversible state on top of doesn't free the system, it corrupts it — preemption is safe only where the holder's state around that claim can be checkpointed or cleanly rebased. Repeated preemption of the same low-priority holder becomes starvation dressed as resolution. And preemption presumes something can even be revoked; a social commitment or an external approval has no lock to pull. The discipline is to preempt only claims with a clean rollback-or-rebase story and a real re-entry path — which is why preemption typically consumes a checkpoint from Rollback to Safe State so the holder returns to consistency, not chaos.

How it implements the components

Lock Preemption fills the pin-point break components — selecting and severing one link, then routing the loser back:

  • break_point_selection — it chooses the single exclusive claim whose revocation cuts the cycle at least cost, rather than acting on a whole participant.
  • bounded_break_action — the intervention is exactly the revoke-or-transfer of that one claim; bounded by construction to a single resource.
  • participant_reentry_rule — the dispossessed holder is queued to reacquire and resume, so the break doesn't silently discard its work.

It does not itself save or restore the holder's data (safe_state_checkpoint, recovery_path) — it relies on Rollback to Safe State for that — and it carries no external legitimacy of its own (resolver_authority), which is Escalation to Authority's and Arbitration Decision's domain.

Notes

Preemption and Forced Release Protocol both end with a held thing being given up, but the mechanics differ: preemption seizes the claim unilaterally, mid-flight, in real time; forced release requires the holder to perform the release itself under criteria agreed in advance. The first is an override; the second is a rule the holder pre-consented to. Choosing between them is really choosing whether legitimacy comes from authority-at-the-moment or from prior agreement.

References

[1] No preemption — that a resource can't be forcibly taken from its holder — is one of the four Coffman conditions necessary for deadlock. Making resources preemptible removes that condition; the cost is that whatever the holder built on the assumption of exclusivity must be safely unwound. ↩