livelock

Name

livelock — livelock — run at full effort and arrive nowhere

Synopsis

livelock [--after-you]... [--politeness=FLOAT] [--no-jitter] PARTIES
while (both_yield) { yield() }
busy == true, progress == 0

Description

livelock places two or more parties in continuous, mutually reactive motion. Each observes the other, defers, adjusts, and retries. Every thread stays runnable and its state changes on every tick. The single quantity that never changes is progress.

It is not deadlock(8). Deadlock blocks: the threads are parked, the CPU is idle, and a scheduler can at least see that nothing is happening. livelock keeps everyone pinned at 100 percent — yielding, backing off, and re-acquiring in lockstep — so the machine reports as fully utilized and remains fully useless. It is starvation with excellent posture.

Termination requires that the symmetry be broken exactly once: a random delay, a timeout, or a single party that declines to be accommodating. Absent that, livelock runs until the power does.

Options

--after-you

Yield to the other party. Repeatable. The other party is also passing --after-you.

--politeness=FLOAT

Courtesy coefficient, 0.0 to 1.0. At 1.0 no party ever passes. Default 0.92.

--no-jitter

Disable randomized backoff. Default. Guarantees the two parties retry on the same instant.

--harder

Retry with greater conviction. The other party also retries harder, in perfect time. No effect on throughput.

--break-symmetry

Permit one party, exactly once, to refuse to yield. The only flag that permits an exit. Rarely supplied.

Exit Status

—

does not exit; the non-exit is the condition being reported

0

one party, at last, declined to yield and the corridor cleared

1

both parties yielded successfully — which is the failure

100

cpu, in case you were wondering. it was busy the whole time.

History

The word is a play on deadlock, substituting live to mark that the processes never actually stop: they stay in the run or ready state, which makes livelock a species of starvation rather than of blocking. Its most cited treatment is Jeffrey Mogul and K. K. Ramakrishnan's "Eliminating Receive Livelock in an Interrupt-Driven Kernel" (USENIX 1996; ACM TOCS 1997), which described network kernels spending the entire CPU servicing interrupts while delivering zero packets to applications. The standard remedies — randomized backoff, timeouts, and priority asymmetry — all work by guaranteeing that the contending parties stop behaving identically.

Bugs

--break-symmetry works as documented. It is almost never passed. The parties consider it rude.

Two operators racing to resolve a livelock by hand reliably reproduce the livelock they are resolving.

Not to be confused with deadlock(8), which at least has the decency to stop.

See Also

thrashing(8), backpressure(3), quiescence(1). The living exhibit demonstrates the word in motion:

▸ operate livelock

Author

Maintained by the two figures in the Corridor, THREAD_α and THREAD_β, who step aside for each other in perfect time and have never once passed. Each is certain the other will go first. Each is correct. Neither has filed a bug; each assumes the other will get to it.