{"title":"Livelock","description":"","content":"A livelock happens when threads are not blocked, but the system still makes no progress. Instead of waiting, the threads keep reacting to each other in a way that prevents either from completing work. CPU usage can be high, logs can be noisy, and yet nothing useful finishes.\n\n\n> **Real-World Analogy**\n>\n> Two people meet in a narrow hallway. Both step aside to let the other pass. They step in the same direction. They step aside again, same direction. And again. \n>\n> Both are actively trying to be polite, both are moving, but neither makes any progress down the hallway.\n\n\nIn many ways, livelock is more insidious than deadlock. With deadlock, you notice immediately because everything stops. With livelock, the system looks busy. Threads are executing, network requests are flying, logs are filling up with retry messages. It might take hours before someone realizes that despite all this activity, no actual work is completing.\n\n---\n\n# What is Livelock?\n\nLivelock occurs when threads are not blocked but continuously change state in response to each other without making progress. Unlike deadlock where threads are stuck waiting, in livelock threads are actively running but trapped in an unproductive loop.\n\nThe key distinction:\n\n\n| Aspect | Deadlock | Livelock |\n|--------|----------|----------|\n| Thread state | BLOCKED (waiting) | RUNNING (executing) |\n| CPU usage | Near zero | High (often 100%) |\n| Activity | None | Lots of retries, state changes |\n| Detection | Thread dumps show blocked threads | Thread dumps show running threads |\n| Root cause | Circular wait for locks | Overly reactive retry logic |\n\n\n---\n\n# Why Livelock Happens\n\nLivelock typically emerges from code designed to be helpful. Retry logic, conflict resolution, and polite backoff can all cause livelock when they interact badly.\n\n### 1. Overly Polite Algorithms\n\nBoth participants back off under the same conditions, using the same strategy.\n\n\n```plaintext\nThread A: \"Lock 1 acquired, can't get Lock 2, I'll release Lock 1 and retry\"\nThread B: \"Lock 2 acquired, can't get Lock 1, I'll release Lock 2 and retry\"\n[Both release at the same time]\n[Both retry at the same time]\n[Same situation repeats infinitely]\n```\n\n\nThe problem: both threads are too accommodating. Neither asserts priority or breaks the symmetry.\n\n### 2. Retry Without Randomization\n\nWhen multiple components retry at fixed intervals, they stay synchronized.\n\n\n```shell\nt=0: Service A calls API\nt=0: Service B calls API\nt=0: Service C calls API\n [API overloaded, all fail]\n\nt=1000: Service A retries\nt=1000: Service B retries\nt=1000: Service C retries\n [API still overloaded, all fail again]\n```\n\n\nWithout randomization, the retry storm repeats forever at the same interval.\n\n### 3. Collision Resolution Without Jitter\n\nNetwork protocols like Ethernet's CSMA/CD and distributed systems often use backoff after collisions. Without randomness, collisions keep happening.\n\n\n```shell\nDevice A: Transmit → Collision → Wait 1ms → Transmit → Collision\nDevice B: Transmit → Collision → Wait 1ms → Transmit → Collision\n[Infinitely synchronized collisions]\n```\n\n\n### 4. Thundering Herd\n\nWhen many threads wait for a resource and all wake up simultaneously when it becomes available, they all compete, most fail, and all go back to waiting. The cycle repeats.\n\n\n```shell\n[100 threads waiting for connection]\n[1 connection freed]\n[100 threads wake up, 99 fail to get it]\n[99 threads go back to waiting]\n[Next connection freed, same thing happens]\n```\n\n\n---\n\n# How to Detect Livelock\n\nLivelock is harder to detect than deadlock because the system looks active. Here are the symptoms:\n\n### Symptoms\n\n**High CPU with no throughput:** CPU pegged at 100%, but requests per second is zero or near zero. Work is being done, but it's all overhead.\n\n**Retry logs exploding:** Log files fill with retry messages. You see patterns like \"Retry attempt 1... Retry attempt 2... Retry attempt 3...\" repeating infinitely.\n\n**Metrics show activity but no completion:** Queue depth grows, in-flight requests increase, but completed requests flatline.\n\n**Patterns in timing:** If you plot retry attempts, you might see synchronization: many retries at exactly the same timestamps.\n\n### Detection Approach\n\n1. **Compare CPU usage vs. throughput:** High CPU with low throughput is suspicious.\n2. **Check retry counts:** If retries are unbounded and growing, investigate.\n3. **Analyze thread dumps:** Unlike deadlock (BLOCKED threads), livelock shows RUNNABLE threads all executing similar retry logic.\n4. **Profile hotspots:** Profilers will show all time spent in retry/backoff code, not in actual business logic.\n\n\n```java\n// Detecting livelock: monitor retry counts\npublic class LivelockDetector {\n private final AtomicLong retryCount = new AtomicLong(0);\n private final AtomicLong successCount = new AtomicLong(0);\n\n public void recordRetry() {\n long retries = retryCount.incrementAndGet();\n long successes = successCount.get();\n\n // If retries >> successes, possible livelock\n if (retries > 1000 && successes == 0) {\n System.err.println(\"WARNING: Possible livelock detected. \" +\n \"Retries: \" + retries + \", Successes: \" + successes);\n }\n }\n\n public void recordSuccess() {\n successCount.incrementAndGet();\n retryCount.set(0); // Reset on success\n }\n}\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\n// Detecting livelock: monitor retry counts\npublic class LivelockDetector\n{\n private long _retryCount = 0;\n private long _successCount = 0;\n\n public void RecordRetry()\n {\n long retries = Interlocked.Increment(ref _retryCount);\n long successes = Interlocked.Read(ref _successCount);\n\n // If retries >> successes, possible livelock\n if (retries > 1000 && successes == 0)\n {\n Console.Error.WriteLine($\"WARNING: Possible livelock detected. \" +\n $\"Retries: {retries}, Successes: {successes}\");\n }\n }\n\n public void RecordSuccess()\n {\n Interlocked.Increment(ref _successCount);\n Interlocked.Exchange(ref _retryCount, 0); // Reset on success\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"fmt\"\n \"sync/atomic\"\n)\n\n// Detecting livelock: monitor retry counts\ntype LivelockDetector struct {\n retryCount int64\n successCount int64\n}\n\nfunc (d *LivelockDetector) RecordRetry() {\n retries := atomic.AddInt64(&d.retryCount, 1)\n successes := atomic.LoadInt64(&d.successCount)\n\n // If retries >> successes, possible livelock\n if retries > 1000 && successes == 0 {\n fmt.Printf(\"WARNING: Possible livelock detected. \"+\n \"Retries: %d, Successes: %d\\n\", retries, successes)\n }\n}\n\nfunc (d *LivelockDetector) RecordSuccess() {\n atomic.AddInt64(&d.successCount, 1)\n atomic.StoreInt64(&d.retryCount, 0) // Reset on success\n}\n```\n\n\n---\n\n# Backoff Strategies\n\nThe key to preventing livelock is breaking synchronization between competing threads. Backoff strategies determine how long to wait before retrying.\n\n### Linear Backoff\n\n\n```shell\nAttempt 1: Wait 100ms\nAttempt 2: Wait 200ms\nAttempt 3: Wait 300ms\nAttempt 4: Wait 400ms\n...\n```\n\n\n**Problem:** If two threads start at the same time, they stay synchronized. Thread A waits 100ms, Thread B waits 100ms. Both retry at the same time. Both wait 200ms. Same problem.\n\n### Exponential Backoff\n\n\n```shell\nAttempt 1: Wait 100ms\nAttempt 2: Wait 200ms\nAttempt 3: Wait 400ms\nAttempt 4: Wait 800ms\n...\n```\n\n\n**Problem:** Slightly better because waits grow faster, but still synchronized if threads start together. Also, waits can grow very large very quickly.\n\n### Exponential Backoff with Jitter (Recommended)\n\n\n```shell\nAttempt 1: Wait random(0, 100ms)\nAttempt 2: Wait random(0, 200ms)\nAttempt 3: Wait random(0, 400ms)\nAttempt 4: Wait random(0, 800ms)\n...\n```\n\n\n**Why it works:** The randomness breaks synchronization. Even if two threads start at exactly the same time and fail at exactly the same time, their random waits will differ. One will retry first and likely succeed before the other interferes.\n\n\n```mermaid\nflowchart TD\n subgraph Linear[\"Linear Backoff\"]\n L1[100ms]:::orange --> L2[200ms]:::orange --> L3[300ms]:::orange\n end\n\n subgraph Exponential[\"Exponential Backoff\"]\n E1[100ms]:::orange --> E2[200ms]:::orange --> E3[400ms]:::orange\n end\n\n subgraph Jitter[\"Exponential + Jitter\"]\n J1[\"random(0-100ms)\"]:::green --> J2[\"random(0-200ms)\"]:::green --> J3[\"random(0-400ms)\"]:::green\n end\n\n Problem1[Stays synchronized]:::red --> Linear\n Problem2[Still synchronized]:::red --> Exponential\n Solution[Breaks synchronization]:::green --> Jitter\n\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef red fill:#ff8787,stroke:#000,color:#000\n```\n\n\n### Jitter Variations\n\nThere are several ways to add jitter:\n\n**Full Jitter:** `wait = random(0, base * 2^attempt)`\n\nMost aggressive randomization. Wait time is completely random within the range.\n\n**Equal Jitter:** `wait = base * 2^attempt / 2 + random(0, base * 2^attempt / 2)`\n\nHalf deterministic, half random. Provides a minimum wait while still randomizing.\n\n**Decorrelated Jitter:** `wait = min(cap, random(base, previous_wait * 3))`\n\nEach wait depends on the previous wait, creating more variation over time.\n\n\n```java\nimport java.util.Random;\n\npublic class BackoffStrategies {\n private static final Random random = new Random();\n private static final long BASE_MS = 100;\n private static final long CAP_MS = 10000;\n\n // Full jitter: random(0, base * 2^attempt)\n public static long fullJitter(int attempt) {\n long maxWait = Math.min(CAP_MS, BASE_MS * (1L << attempt));\n return random.nextLong(maxWait);\n }\n\n // Equal jitter: half + random half\n public static long equalJitter(int attempt) {\n long maxWait = Math.min(CAP_MS, BASE_MS * (1L << attempt));\n long halfWait = maxWait / 2;\n return halfWait + random.nextLong(halfWait);\n }\n\n // Decorrelated jitter\n private static long previousWait = BASE_MS;\n\n public static long decorrelatedJitter() {\n long wait = Math.min(CAP_MS, random.nextLong(BASE_MS, previousWait * 3));\n previousWait = wait;\n return wait;\n }\n}\n```\n\n```python\nimport random\n\nBASE_MS = 100\nCAP_MS = 10000\n\ndef full_jitter(attempt: int) -> int:\n \"\"\"Full jitter: random(0, base * 2^attempt)\"\"\"\n max_wait = min(CAP_MS, BASE_MS * (2 ** attempt))\n return random.randint(0, max_wait)\n\ndef equal_jitter(attempt: int) -> int:\n \"\"\"Equal jitter: half + random half\"\"\"\n max_wait = min(CAP_MS, BASE_MS * (2 ** attempt))\n half_wait = max_wait // 2\n return half_wait + random.randint(0, half_wait)\n\nclass DecorrelatedJitter:\n \"\"\"Decorrelated jitter: depends on previous wait\"\"\"\n def __init__(self):\n self.previous_wait = BASE_MS\n\n def next_wait(self) -> int:\n wait = min(CAP_MS, random.randint(BASE_MS, self.previous_wait * 3))\n self.previous_wait = wait\n return wait\n```\n\n```cpp\n#include \n#include \n\nclass BackoffStrategies {\n static constexpr long BASE_MS = 100;\n static constexpr long CAP_MS = 10000;\n\n std::mt19937 gen{std::random_device{}()};\n long previousWait = BASE_MS;\n\npublic:\n // Full jitter: random(0, base * 2^attempt)\n long fullJitter(int attempt) {\n long maxWait = std::min(CAP_MS, BASE_MS * (1L << attempt));\n std::uniform_int_distribution dist(0, maxWait);\n return dist(gen);\n }\n\n // Equal jitter: half + random half\n long equalJitter(int attempt) {\n long maxWait = std::min(CAP_MS, BASE_MS * (1L << attempt));\n long halfWait = maxWait / 2;\n std::uniform_int_distribution dist(0, halfWait);\n return halfWait + dist(gen);\n }\n\n // Decorrelated jitter\n long decorrelatedJitter() {\n std::uniform_int_distribution dist(BASE_MS, previousWait * 3);\n long wait = std::min(CAP_MS, dist(gen));\n previousWait = wait;\n return wait;\n }\n};\n```\n\n```csharp\nusing System;\n\npublic class BackoffStrategies\n{\n private const long BaseMs = 100;\n private const long CapMs = 10000;\n\n private readonly Random _random = new Random();\n private long _previousWait = BaseMs;\n\n // Full jitter: random(0, base * 2^attempt)\n public long FullJitter(int attempt)\n {\n long maxWait = Math.Min(CapMs, BaseMs * (1L << attempt));\n return _random.NextInt64(0, maxWait);\n }\n\n // Equal jitter: half + random half\n public long EqualJitter(int attempt)\n {\n long maxWait = Math.Min(CapMs, BaseMs * (1L << attempt));\n long halfWait = maxWait / 2;\n return halfWait + _random.NextInt64(0, halfWait);\n }\n\n // Decorrelated jitter\n public long DecorrelatedJitter()\n {\n long wait = Math.Min(CapMs, _random.NextInt64(BaseMs, _previousWait * 3));\n _previousWait = wait;\n return wait;\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"math/rand\"\n \"time\"\n)\n\nconst (\n baseMs = 100\n capMs = 10000\n)\n\ntype BackoffStrategies struct {\n previousWait int64\n rng *rand.Rand\n}\n\nfunc NewBackoffStrategies() *BackoffStrategies {\n return &BackoffStrategies{\n previousWait: baseMs,\n rng: rand.New(rand.NewSource(time.Now().UnixNano())),\n }\n}\n\n// FullJitter: random(0, base * 2^attempt)\nfunc (b *BackoffStrategies) FullJitter(attempt int) time.Duration {\n maxWait := min(capMs, baseMs*(1<\n\n---\n\n# How to Prevent Livelock\n\n### Strategy 1: Add Randomization to Backoff\n\nThe simplest fix: add random jitter to all retry delays.\n\n\n```java\nimport java.util.Random;\nimport java.util.concurrent.TimeUnit;\n\npublic class RetryWithJitter {\n private static final Random random = new Random();\n private static final int MAX_RETRIES = 10;\n private static final long BASE_DELAY_MS = 100;\n\n public T executeWithRetry(Callable operation) throws Exception {\n int attempt = 0;\n\n while (attempt < MAX_RETRIES) {\n try {\n return operation.call();\n } catch (RetryableException e) {\n attempt++;\n\n if (attempt >= MAX_RETRIES) {\n throw e;\n }\n\n // Exponential backoff with full jitter\n long maxDelay = BASE_DELAY_MS * (1L << attempt);\n long delay = random.nextLong(maxDelay);\n\n System.out.println(\"Attempt \" + attempt + \" failed, \" +\n \"retrying in \" + delay + \"ms\");\n\n Thread.sleep(delay);\n }\n }\n\n throw new RuntimeException(\"Max retries exceeded\");\n }\n}\n```\n\n```python\nimport random\nimport time\nfrom typing import Callable, TypeVar\n\nT = TypeVar('T')\n\nMAX_RETRIES = 10\nBASE_DELAY_MS = 100\n\ndef execute_with_retry(operation: Callable[[], T]) -> T:\n attempt = 0\n\n while attempt < MAX_RETRIES:\n try:\n return operation()\n except RetryableException as e:\n attempt += 1\n\n if attempt >= MAX_RETRIES:\n raise e\n\n # Exponential backoff with full jitter\n max_delay = BASE_DELAY_MS * (2 ** attempt)\n delay = random.randint(0, max_delay)\n\n print(f\"Attempt {attempt} failed, retrying in {delay}ms\")\n\n time.sleep(delay / 1000)\n\n raise RuntimeError(\"Max retries exceeded\")\n```\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\ntemplate\nT executeWithRetry(std::function operation) {\n static constexpr int MAX_RETRIES = 10;\n static constexpr long BASE_DELAY_MS = 100;\n\n std::random_device rd;\n std::mt19937 gen(rd());\n\n int attempt = 0;\n\n while (attempt < MAX_RETRIES) {\n try {\n return operation();\n } catch (const RetryableException& e) {\n attempt++;\n\n if (attempt >= MAX_RETRIES) {\n throw;\n }\n\n // Exponential backoff with full jitter\n long maxDelay = BASE_DELAY_MS * (1L << attempt);\n std::uniform_int_distribution dist(0, maxDelay);\n long delay = dist(gen);\n\n std::cout << \"Attempt \" << attempt << \" failed, \"\n << \"retrying in \" << delay << \"ms\\n\";\n\n std::this_thread::sleep_for(std::chrono::milliseconds(delay));\n }\n }\n\n throw std::runtime_error(\"Max retries exceeded\");\n}\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class RetryWithJitter\n{\n private static readonly Random _random = new Random();\n private const int MaxRetries = 10;\n private const long BaseDelayMs = 100;\n\n public static T ExecuteWithRetry(Func operation)\n {\n int attempt = 0;\n\n while (attempt < MaxRetries)\n {\n try\n {\n return operation();\n }\n catch (RetryableException e)\n {\n attempt++;\n\n if (attempt >= MaxRetries)\n {\n throw;\n }\n\n // Exponential backoff with full jitter\n long maxDelay = BaseDelayMs * (1L << attempt);\n long delay = _random.NextInt64(0, maxDelay);\n\n Console.WriteLine($\"Attempt {attempt} failed, retrying in {delay}ms\");\n\n Thread.Sleep((int)delay);\n }\n }\n\n throw new InvalidOperationException(\"Max retries exceeded\");\n }\n}\n\n// Custom exception for retryable operations\npublic class RetryableException : Exception\n{\n public RetryableException(string message) : base(message) { }\n}\n```\n\n```go\npackage main\n\nimport (\n \"errors\"\n \"fmt\"\n \"math/rand\"\n \"time\"\n)\n\nvar ErrRetryable = errors.New(\"retryable error\")\n\nconst (\n maxRetries = 10\n baseDelayMs = 100\n)\n\nfunc ExecuteWithRetry[T any](operation func() (T, error)) (T, error) {\n var zero T\n rng := rand.New(rand.NewSource(time.Now().UnixNano()))\n attempt := 0\n\n for attempt < maxRetries {\n result, err := operation()\n if err == nil {\n return result, nil\n }\n\n // Check if error is retryable\n if !errors.Is(err, ErrRetryable) {\n return zero, err // Non-retryable error\n }\n\n attempt++\n if attempt >= maxRetries {\n return zero, fmt.Errorf(\"max retries exceeded: %w\", err)\n }\n\n // Exponential backoff with full jitter\n maxDelay := baseDelayMs * (1 << attempt)\n delay := rng.Intn(maxDelay)\n\n fmt.Printf(\"Attempt %d failed, retrying in %dms\\n\", attempt, delay)\n\n time.Sleep(time.Duration(delay) * time.Millisecond)\n }\n\n return zero, errors.New(\"max retries exceeded\")\n}\n\n// Usage:\n// result, err := ExecuteWithRetry(func() (string, error) {\n// return riskyOperation()\n// })\n```\n\n\n### Strategy 2: Asymmetric Behavior\n\nGive different threads different roles or priorities. Not everyone should back off equally.\n\n\n```java\npublic class AsymmetricLocking {\n private final Lock lock1 = new ReentrantLock();\n private final Lock lock2 = new ReentrantLock();\n private static final Random random = new Random();\n\n public void operationWithPriority(int priority) {\n while (true) {\n if (lock1.tryLock()) {\n try {\n if (lock2.tryLock()) {\n try {\n // Critical section\n doWork();\n return;\n } finally {\n lock2.unlock();\n }\n }\n } finally {\n lock1.unlock();\n }\n }\n\n // Asymmetric backoff based on priority\n // Lower priority = longer backoff = more likely to yield\n long baseBackoff = 10;\n long backoff = baseBackoff * (11 - priority) + random.nextInt(10);\n\n try {\n Thread.sleep(backoff);\n } catch (InterruptedException e) {\n Thread.currentThread().interrupt();\n return;\n }\n }\n }\n}\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\npublic class AsymmetricLocking\n{\n private readonly object _lock1 = new object();\n private readonly object _lock2 = new object();\n private static readonly Random _random = new Random();\n\n public void OperationWithPriority(int priority)\n {\n while (true)\n {\n bool gotLock1 = false;\n bool gotLock2 = false;\n\n try\n {\n gotLock1 = Monitor.TryEnter(_lock1);\n if (gotLock1)\n {\n gotLock2 = Monitor.TryEnter(_lock2);\n if (gotLock2)\n {\n // Critical section\n DoWork();\n return;\n }\n }\n }\n finally\n {\n if (gotLock2) Monitor.Exit(_lock2);\n if (gotLock1) Monitor.Exit(_lock1);\n }\n\n // Asymmetric backoff based on priority\n // Lower priority = longer backoff = more likely to yield\n int baseBackoff = 10;\n int backoff = baseBackoff * (11 - priority) + _random.Next(10);\n\n Thread.Sleep(backoff);\n }\n }\n\n private void DoWork()\n {\n // Actual work here\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"math/rand\"\n \"sync\"\n \"time\"\n)\n\ntype AsymmetricLocking struct {\n mu1 sync.Mutex\n mu2 sync.Mutex\n rng *rand.Rand\n}\n\nfunc NewAsymmetricLocking() *AsymmetricLocking {\n return &AsymmetricLocking{\n rng: rand.New(rand.NewSource(time.Now().UnixNano())),\n }\n}\n\nfunc (a *AsymmetricLocking) OperationWithPriority(priority int) {\n for {\n if a.mu1.TryLock() {\n if a.mu2.TryLock() {\n // Critical section\n a.doWork()\n a.mu2.Unlock()\n a.mu1.Unlock()\n return\n }\n a.mu1.Unlock()\n }\n\n // Asymmetric backoff based on priority\n // Lower priority = longer backoff = more likely to yield\n baseBackoff := 10\n backoff := baseBackoff*(11-priority) + a.rng.Intn(10)\n\n time.Sleep(time.Duration(backoff) * time.Millisecond)\n }\n}\n\nfunc (a *AsymmetricLocking) doWork() {\n // Actual work here\n}\n\n// Alternative: Use runtime.Gosched() to yield\nfunc yieldToOtherGoroutines() {\n runtime.Gosched() // Yields the processor, allowing other goroutines to run\n}\n```\n\n\nThreads with higher priority back off less, making them more likely to acquire locks first. This breaks the symmetry that causes livelock.\n\n### Strategy 3: Limit Retry Attempts\n\nDon't retry forever. Set a maximum number of retries and fail gracefully.\n\n\n```java\npublic void operationWithLimit() {\n int maxRetries = 10;\n int attempt = 0;\n\n while (attempt < maxRetries) {\n if (tryAcquireAllLocks()) {\n try {\n doWork();\n return;\n } finally {\n releaseAllLocks();\n }\n }\n attempt++;\n backoffWithJitter(attempt);\n }\n\n throw new OperationFailedException(\"Could not acquire locks after \" + maxRetries + \" attempts\");\n}\n```\n\n\n### Strategy 4: Circuit Breaker Pattern\n\nIf operations keep failing, stop trying for a while. Let the system recover.\n\n\n```mermaid\nstateDiagram-v2\n [*] --> Closed: Normal operation\n\n Closed --> Open: Failures exceed threshold\n Open --> HalfOpen: Timeout expires\n HalfOpen --> Closed: Probe succeeds\n HalfOpen --> Open: Probe fails\n\n classDef closed fill:#69db7c,stroke:#000,color:#000\n classDef open fill:#ff8787,stroke:#000,color:#000\n classDef halfopen fill:#ffd43b,stroke:#000,color:#000\n\n class Closed closed\n class Open open\n class HalfOpen halfopen\n```\n\n\nWhen the circuit is **Open**, all operations fail immediately without trying. This gives the system time to recover and prevents retry storms from making things worse.\n\n---\n\n# Livelock in Practice\n\n### The Bug: Synchronized Retry Loop\n\n\n```java\n// BROKEN: Two threads in livelock\npublic class LivelockDemo {\n private final Lock lock1 = new ReentrantLock();\n private final Lock lock2 = new ReentrantLock();\n\n public void thread1Work() {\n while (true) {\n lock1.lock();\n System.out.println(\"Thread 1: Acquired lock1\");\n\n // Try to get lock2\n if (lock2.tryLock()) {\n try {\n System.out.println(\"Thread 1: Acquired lock2, doing work\");\n doWork();\n return;\n } finally {\n lock2.unlock();\n lock1.unlock();\n }\n }\n\n // Can't get lock2, release lock1 and retry\n System.out.println(\"Thread 1: Can't get lock2, backing off\");\n lock1.unlock();\n\n // Fixed delay - BAD!\n try { Thread.sleep(100); } catch (InterruptedException e) { return; }\n }\n }\n\n public void thread2Work() {\n while (true) {\n lock2.lock();\n System.out.println(\"Thread 2: Acquired lock2\");\n\n // Try to get lock1\n if (lock1.tryLock()) {\n try {\n System.out.println(\"Thread 2: Acquired lock1, doing work\");\n doWork();\n return;\n } finally {\n lock1.unlock();\n lock2.unlock();\n }\n }\n\n // Can't get lock1, release lock2 and retry\n System.out.println(\"Thread 2: Can't get lock1, backing off\");\n lock2.unlock();\n\n // Same fixed delay - BAD!\n try { Thread.sleep(100); } catch (InterruptedException e) { return; }\n }\n }\n}\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\n// BROKEN: Two threads in livelock\npublic class LivelockDemo\n{\n private readonly object _lock1 = new object();\n private readonly object _lock2 = new object();\n\n public void Thread1Work()\n {\n while (true)\n {\n bool gotLock1 = false;\n bool gotLock2 = false;\n\n try\n {\n Monitor.Enter(_lock1);\n gotLock1 = true;\n Console.WriteLine(\"Thread 1: Acquired lock1\");\n\n // Try to get lock2\n gotLock2 = Monitor.TryEnter(_lock2);\n if (gotLock2)\n {\n Console.WriteLine(\"Thread 1: Acquired lock2, doing work\");\n DoWork();\n return;\n }\n\n // Can't get lock2, release lock1 and retry\n Console.WriteLine(\"Thread 1: Can't get lock2, backing off\");\n }\n finally\n {\n if (gotLock2) Monitor.Exit(_lock2);\n if (gotLock1) Monitor.Exit(_lock1);\n }\n\n // Fixed delay - BAD!\n Thread.Sleep(100);\n }\n }\n\n public void Thread2Work()\n {\n while (true)\n {\n bool gotLock2 = false;\n bool gotLock1 = false;\n\n try\n {\n Monitor.Enter(_lock2);\n gotLock2 = true;\n Console.WriteLine(\"Thread 2: Acquired lock2\");\n\n // Try to get lock1\n gotLock1 = Monitor.TryEnter(_lock1);\n if (gotLock1)\n {\n Console.WriteLine(\"Thread 2: Acquired lock1, doing work\");\n DoWork();\n return;\n }\n\n // Can't get lock1, release lock2 and retry\n Console.WriteLine(\"Thread 2: Can't get lock1, backing off\");\n }\n finally\n {\n if (gotLock1) Monitor.Exit(_lock1);\n if (gotLock2) Monitor.Exit(_lock2);\n }\n\n // Same fixed delay - BAD!\n Thread.Sleep(100);\n }\n }\n\n private void DoWork()\n {\n // Actual work\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"fmt\"\n \"sync\"\n \"time\"\n)\n\n// BROKEN: Two goroutines in livelock\ntype LivelockDemo struct {\n mu1 sync.Mutex\n mu2 sync.Mutex\n}\n\nfunc (d *LivelockDemo) goroutine1Work() {\n for {\n d.mu1.Lock()\n fmt.Println(\"Goroutine 1: Acquired mu1\")\n\n // Try to get mu2\n if d.mu2.TryLock() {\n fmt.Println(\"Goroutine 1: Acquired mu2, doing work\")\n d.doWork()\n d.mu2.Unlock()\n d.mu1.Unlock()\n return\n }\n\n // Can't get mu2, release mu1 and retry\n fmt.Println(\"Goroutine 1: Can't get mu2, backing off\")\n d.mu1.Unlock()\n\n // Fixed delay - BAD!\n time.Sleep(100 * time.Millisecond)\n }\n}\n\nfunc (d *LivelockDemo) goroutine2Work() {\n for {\n d.mu2.Lock()\n fmt.Println(\"Goroutine 2: Acquired mu2\")\n\n // Try to get mu1\n if d.mu1.TryLock() {\n fmt.Println(\"Goroutine 2: Acquired mu1, doing work\")\n d.doWork()\n d.mu1.Unlock()\n d.mu2.Unlock()\n return\n }\n\n // Can't get mu1, release mu2 and retry\n fmt.Println(\"Goroutine 2: Can't get mu1, backing off\")\n d.mu2.Unlock()\n\n // Same fixed delay - BAD!\n time.Sleep(100 * time.Millisecond)\n }\n}\n\nfunc (d *LivelockDemo) doWork() {\n fmt.Println(\"Working...\")\n}\n\nfunc main() {\n demo := &LivelockDemo{}\n\n go demo.goroutine1Work()\n go demo.goroutine2Work()\n\n // Wait (will likely hang due to livelock)\n time.Sleep(5 * time.Second)\n}\n```\n\n\n### The Fix: Random Backoff\n\n\n```java\n// FIXED: Random backoff breaks synchronization\npublic class LivelockFixed {\n private final Lock lock1 = new ReentrantLock();\n private final Lock lock2 = new ReentrantLock();\n private static final Random random = new Random();\n\n public void thread1Work() {\n int attempt = 0;\n while (true) {\n lock1.lock();\n try {\n if (lock2.tryLock()) {\n try {\n doWork();\n return;\n } finally {\n lock2.unlock();\n }\n }\n } finally {\n lock1.unlock();\n }\n\n // Random backoff with exponential growth\n attempt++;\n long maxDelay = 100L * (1L << Math.min(attempt, 6));\n long delay = random.nextLong(maxDelay);\n\n System.out.println(\"Thread 1: Backing off for \" + delay + \"ms\");\n\n try { Thread.sleep(delay); } catch (InterruptedException e) { return; }\n }\n }\n\n public void thread2Work() {\n int attempt = 0;\n while (true) {\n lock2.lock();\n try {\n if (lock1.tryLock()) {\n try {\n doWork();\n return;\n } finally {\n lock1.unlock();\n }\n }\n } finally {\n lock2.unlock();\n }\n\n // Random backoff - different random value!\n attempt++;\n long maxDelay = 100L * (1L << Math.min(attempt, 6));\n long delay = random.nextLong(maxDelay);\n\n System.out.println(\"Thread 2: Backing off for \" + delay + \"ms\");\n\n try { Thread.sleep(delay); } catch (InterruptedException e) { return; }\n }\n }\n}\n```\n\n```csharp\nusing System;\nusing System.Threading;\n\n// FIXED: Random backoff breaks synchronization\npublic class LivelockFixed\n{\n private readonly object _lock1 = new object();\n private readonly object _lock2 = new object();\n private static readonly Random _random = new Random();\n\n public void Thread1Work()\n {\n int attempt = 0;\n while (true)\n {\n bool gotLock1 = false;\n bool gotLock2 = false;\n\n try\n {\n gotLock1 = Monitor.TryEnter(_lock1);\n if (gotLock1)\n {\n gotLock2 = Monitor.TryEnter(_lock2);\n if (gotLock2)\n {\n DoWork();\n return;\n }\n }\n }\n finally\n {\n if (gotLock2) Monitor.Exit(_lock2);\n if (gotLock1) Monitor.Exit(_lock1);\n }\n\n // Random backoff with exponential growth\n attempt++;\n long maxDelay = 100L * (1L << Math.Min(attempt, 6));\n long delay = _random.NextInt64(0, maxDelay);\n\n Console.WriteLine($\"Thread 1: Backing off for {delay}ms\");\n\n Thread.Sleep((int)delay);\n }\n }\n\n public void Thread2Work()\n {\n int attempt = 0;\n while (true)\n {\n bool gotLock2 = false;\n bool gotLock1 = false;\n\n try\n {\n gotLock2 = Monitor.TryEnter(_lock2);\n if (gotLock2)\n {\n gotLock1 = Monitor.TryEnter(_lock1);\n if (gotLock1)\n {\n DoWork();\n return;\n }\n }\n }\n finally\n {\n if (gotLock1) Monitor.Exit(_lock1);\n if (gotLock2) Monitor.Exit(_lock2);\n }\n\n // Random backoff - different random value!\n attempt++;\n long maxDelay = 100L * (1L << Math.Min(attempt, 6));\n long delay = _random.NextInt64(0, maxDelay);\n\n Console.WriteLine($\"Thread 2: Backing off for {delay}ms\");\n\n Thread.Sleep((int)delay);\n }\n }\n\n private void DoWork()\n {\n Console.WriteLine($\"Thread {Environment.CurrentManagedThreadId}: Doing work\");\n }\n}\n```\n\n```go\npackage main\n\nimport (\n \"fmt\"\n \"math/rand\"\n \"sync\"\n \"time\"\n)\n\n// FIXED: Random backoff breaks synchronization\ntype LivelockFixed struct {\n mu1 sync.Mutex\n mu2 sync.Mutex\n}\n\nfunc (d *LivelockFixed) goroutine1Work() {\n rng := rand.New(rand.NewSource(time.Now().UnixNano()))\n attempt := 0\n\n for {\n if d.mu1.TryLock() {\n if d.mu2.TryLock() {\n d.doWork(1)\n d.mu2.Unlock()\n d.mu1.Unlock()\n return\n }\n d.mu1.Unlock()\n }\n\n // Random backoff with exponential growth\n attempt++\n maxDelay := 100 * (1 << min(attempt, 6))\n delay := rng.Intn(maxDelay)\n\n fmt.Printf(\"Goroutine 1: Backing off for %dms\\n\", delay)\n\n time.Sleep(time.Duration(delay) * time.Millisecond)\n }\n}\n\nfunc (d *LivelockFixed) goroutine2Work() {\n rng := rand.New(rand.NewSource(time.Now().UnixNano() + 1)) // Different seed\n attempt := 0\n\n for {\n if d.mu2.TryLock() {\n if d.mu1.TryLock() {\n d.doWork(2)\n d.mu1.Unlock()\n d.mu2.Unlock()\n return\n }\n d.mu2.Unlock()\n }\n\n // Random backoff - different random values!\n attempt++\n maxDelay := 100 * (1 << min(attempt, 6))\n delay := rng.Intn(maxDelay)\n\n fmt.Printf(\"Goroutine 2: Backing off for %dms\\n\", delay)\n\n time.Sleep(time.Duration(delay) * time.Millisecond)\n }\n}\n\nfunc (d *LivelockFixed) doWork(id int) {\n fmt.Printf(\"Goroutine %d: Doing work\\n\", id)\n}\n\nfunc min(a, b int) int {\n if a < b {\n return a\n }\n return b\n}\n\nfunc main() {\n demo := &LivelockFixed{}\n\n var wg sync.WaitGroup\n wg.Add(2)\n\n go func() {\n defer wg.Done()\n demo.goroutine1Work()\n }()\n\n go func() {\n defer wg.Done()\n demo.goroutine2Work()\n }()\n\n wg.Wait()\n fmt.Println(\"Both goroutines completed!\")\n}\n```\n","pageType":"concurrency-interview"}

Livelock

Ashish Pratap Singh

Get Premium