Livelock과 Starvation: 정의와 예시

1. Livelock 소개

deadlock이란 스레드들이 서로를 영원히 기다리며 멈춰 있는 상태라면, livelock(활성 교착)은 스레드들이 겉보기에는 계속 살아 움직이며 무언가를 하고 서로 양보도 하지만… 아무도 앞으로 나아가지 못하는 상태를 말합니다! 좁은 복도에서 두 사람이 동시에 서로에게 “먼저 지나가세요!” — “아니요, 먼저요!” — “아니요, 먼저요!”라고 하며 끝없이 비켜 서는 장면을 떠올려 보세요.

정식 정의

Livelock은 스레드가 블로킹된 것은 아니지만, 다른 스레드의 동작에 반응하여 자신의 상태를 계속 바꾸느라 작업을 끝내지 못하는 상황입니다. 스레드는 “살아” 있어 활발히 반응하지만 유의미한 일을 수행하지 못합니다.

실전에서는 어떻게 보일까?

• 스레드가 영원히 잠기지는 않지만, 끝없는 양보의 루프에 갇힙니다.
• 시스템이 멈춘 것은 아니지만 해야 할 일을 수행하지 못합니다.

생활 속 비유

• 좁은 통로에서 마주친 두 로봇이 동시에 서로를 피해 옆으로 비키는데, 매번 같은 방향으로 움직여 다시 막히는 상황.
• 두 스레드가 매번 자원이 점유되어 있음을 확인하고 서로에게 양보하기를… 끝없이 반복하는 상황.

2. Java로 보는 livelock 예제

코드로 livelock을 모델링해 봅시다. 간단히, 하나의 숟가락이 필요한 두 “작업자”를 가정합니다. deadlock과 달리 숟가락이 점유되어 있으면 서로 예의 바르게 양보하고 다시 시도하는데 — 문제는 둘 다 동시에, 동기적으로 그렇게 한다는 점입니다.

코드 예제: “예의 바른 작업자들”

public class LivelockDemo {
    static class Spoon {
        private Worker owner;

        public Spoon(Worker owner) {
            this.owner = owner;
        }

        public Worker getOwner() {
            return owner;
        }

        public synchronized void setOwner(Worker owner) {
            this.owner = owner;
        }

        public synchronized void use() {
            // 숟가락 사용 (아무 동작 없음)
        }
    }

    static class Worker {
        private final String name;
        private boolean isHungry = true;

        public Worker(String name) {
            this.name = name;
        }

        public String getName() {
            return name;
        }

        public boolean isHungry() {
            return isHungry;
        }

        public void eatWith(Spoon spoon, Worker other) {
            while (isHungry) {
                // 숟가락이 내 것이 아니면 — 기다린다
                if (spoon.getOwner() != this) {
                    try {
                        Thread.sleep(1); // 숟가락이 비워질 때까지 기다린다
                    } catch (InterruptedException ignored) {}
                    continue;
                }
                // 다른 작업자가 배고프면 — 숟가락을 양보한다
                if (other.isHungry()) {
                    System.out.println(name + ": 숟가락을 양보합니다 " + other.getName());
                    spoon.setOwner(other);
                    continue;
                }
                // 먹는다!
                System.out.println(name + ": 나는 먹는 중!");
                spoon.use();
                isHungry = false;
                System.out.println(name + ": 배가 찼어요!");
                spoon.setOwner(other);
            }
        }
    }

    public static void main(String[] args) {
        final Worker alice = new Worker("Alice");
        final Worker bob = new Worker("Bob");
        final Spoon spoon = new Spoon(alice);

        Thread t1 = new Thread(() -> alice.eatWith(spoon, bob));
        Thread t2 = new Thread(() -> bob.eatWith(spoon, alice));

        t1.start();
        t2.start();
    }
}

무슨 일이 벌어지나?

• Alice와 Bob은 둘 다 배가 고프고, 숟가락은 처음에 Alice에게 있습니다.
• Alice는 Bob도 배고프다는 것을 보고 숟가락을 양보합니다.
• 이제 숟가락은 Bob에게 있지만, Bob도 Alice가 배고프다는 것을 보고 다시 양보합니다.
• 숟가락이 작업자들 사이를 계속 “왔다 갔다” 하지만 아무도 먹지 못합니다 — 진행이 없습니다.

출력은 어떻게 보일까?

Alice: 숟가락을 양보합니다 Bob
Bob: 숟가락을 양보합니다 Alice
Alice: 숟가락을 양보합니다 Bob
Bob: 숟가락을 양보합니다 Alice
...

livelock을 없애려면?

livelock을 없애려면 스레드의 “예의”를 조금만 줄이면 됩니다. 재시도 전에 무작위로 짧은 지연을 넣으면(예: Thread.sleep) 스레드들이 동기적으로 반응하지 않게 됩니다. 또 하나의 방법은 더 “완강한” 전략입니다. 한 번 양보했다면 다음 시도 전 더 오래 기다리도록 하는 것이죠. 알고리즘에서 과도한 신사적인 양보는 지양하세요 — 지나친 양보 역시 정체를 유발합니다.

3. Starvation(스레드 기아)

livelock이 “끝없는 예의”라면, starvation(기아)은 다른 스레드들이 계속 앞지르기 때문에 하나 혹은 그 이상의 스레드가 자원이나 CPU를 전혀 얻지 못하는 상황입니다.

정식 정의

Starvation은 다른 스레드들이 계속 앞서나가서 해당 스레드가 필요한 자원(CPU, 메모리, 락)에 접근하지 못하는 상황입니다. 그 결과 “기아” 상태의 스레드는 거의 실행되지 않거나 아예 실행되지 않습니다.

starvation의 원인

• 불공정한 락. 예를 들어 일반 synchronized 블록은 가장 오래 기다린 스레드가 먼저 들어가도록 보장하지 않습니다.
• 스레드 우선순위. 높은 우선순위 스레드가 CPU를 계속 점유하면 낮은 우선순위 스레드는 “굶주릴” 수 있습니다(setPriority).
• 다른 스레드의 무한 루프. 누군가가 CPU를 양보하지 않으면(Thread.sleep 또는 Thread.yield()를 호출하지 않으면) 다른 스레드가 실행 시간을 받지 못할 수 있습니다.

4. Java로 보는 starvation 예제

예제: 낮은 우선순위 스레드가 실행되지 않음

public class StarvationDemo {
    public static void main(String[] args) {
        Runnable highPriorityTask = () -> {
            while (true) {
                // 고강도 작업, CPU를 양보하지 않음
            }
        };

        Runnable lowPriorityTask = () -> {
            while (true) {
                System.out.println("저는 낮은 우선순위 스레드예요!");
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException ignored) {}
            }
        };

        Thread high1 = new Thread(highPriorityTask);
        Thread high2 = new Thread(highPriorityTask);
        Thread low = new Thread(lowPriorityTask);

        high1.setPriority(Thread.MAX_PRIORITY); // 10
        high2.setPriority(Thread.MAX_PRIORITY); // 10
        low.setPriority(Thread.MIN_PRIORITY);   // 1

        high1.start();
        high2.start();
        low.start();
    }
}

어떻게 나타날까?

• 높은 우선순위 스레드가 계속 작업하며 CPU를 양보하지 않습니다.
• 낮은 우선순위 스레드는 거의 실행되지 않거나(혹은 전혀) 실행되지 않습니다.
• 최신 JVM/OS에서는 스케줄러가 우선순위를 완화하기도 하지만, 일부 시스템에서는 기아 현상이 뚜렷합니다.

또 다른 예: 불공정 락으로 인한 starvation

public class StarvationLockDemo {
    private static final Object lock = new Object();

    public static void main(String[] args) {
        // 항상 lock을 잡는 5개의 스레드
        for (int i = 0; i < 5; i++) {
            new Thread(() -> {
                while (true) {
                    synchronized (lock) {
                        // lock을 오래 점유
                        try {
                            Thread.sleep(100);
                        } catch (InterruptedException ignored) {}
                    }
                }
            }).start();
        }

        // 하나의 기아 스레드
        new Thread(() -> {
            while (true) {
                synchronized (lock) {
                    System.out.println("기아 스레드가 lock을 획득!");
                    try {
                        Thread.sleep(100);
                    } catch (InterruptedException ignored) {}
                }
            }
        }).start();
    }
}

이 예제에서 “기아” 스레드는 다른 스레드들이 lock을 계속 점유하면 매우 오랫동안 접근하지 못할 수 있습니다.

5. livelock과 starvation을 발견하고 예방하기

어떻게 발견할까?

• Livelock: 프로그램은 동작하고 스레드도 멈추지 않았지만, 진행이 없습니다(결과가 없거나 루프에서 빠져나오지 않음).
• Starvation: 일부 스레드가 거의 실행되지 않습니다(로그 메시지가 드물거나 없음).

도구

• 로깅: 작업 시작/종료, 자원 획득/해제를 표시하세요.
• 모니터링: VisualVM, Java Mission Control — 어떤 스레드가 활성이고 무엇을 하는지 확인하세요.
• Thread dump: 스레드가 lock 대기에 갇혀 있지 않은지 확인하세요.

어떻게 피할까?

livelock을 위해:

• 너무 “예의 바른” 양보는 피하고, 재시도 전에 짧은 무작위 지연을 추가하세요(Thread.sleep).
• 재시도 순서에 무작위성을 도입해 스레드의 동기화된 행동을 피하세요.
• 논블로킹 구조/알고리즘(원자 변수, CAS 방식)을 사용하세요.

starvation을 위해:

• “공정한” 락을 사용하세요. 예: ReentrantLock의 fairness:

java.util.concurrent.locks.ReentrantLock lock = new java.util.concurrent.locks.ReentrantLock(true); // 공정 모드

• 스레드 우선순위를 남용하지 말고, 가능한 기본값을 유지하세요.
• 임계 구역(synchronized/Lock) 내부 시간을 최소화하세요.
• FIFO에 가까운 처리를 하는 작업 큐를 사용하세요.

표: Deadlock, Livelock, Starvation — 비교

비유와 흥미로운 사실

• Livelock — 서로 비켜서려고 동시에 왼쪽으로 한 발 내딛다 다시 부딪히는 두 사람과 같습니다.
• Starvation — 마트 줄에서 계산원이 “아는 사람”만 처리하고 나머지는 끝없이 기다리는 상황과 같습니다.

흥미로운 사실: livelock은 deadlock보다 드물지만 발견하기는 더 어렵습니다 — 프로그램이 “멈추지” 않고 뭔가를 하니까요!

6. livelock과 starvation 처리 시 흔한 실수

오류 №1: “예의 바른 양보”에 지연이 없음. 스레드가 쉬지 않고 서로 양보만 하면 livelock에 빠질 수 있습니다. 자원 재획득을 재시도하기 전에 짧은 무작위 지연을 추가하세요(Thread.sleep).

오류 №2: synchronized에만 의존하고 공정 락을 쓰지 않음. 스레드가 많을 때 일반 synchronized는 “가장 굶주린” 스레드의 선입장을 보장하지 않습니다. 필요하다면 fairness가 있는 ReentrantLock을 사용하세요.

오류 №3: 스레드 우선순위 남용. 중요한 스레드를 setPriority로 “가속”하려다 다른 스레드에 starvation을 유발하기 쉽습니다. 실제로 필요하지 않다면 우선순위를 건드리지 마세요.

오류 №4: 모니터링과 로깅 부족. Livelock과 starvation은 로그 없이는 알아채기 어렵습니다: 프로그램은 “돌아가는데” 결과가 없습니다. 주요 이벤트를 로깅하고 프로파일러/스레드 덤프를 활용하세요.

오류 №5: 지나치게 긴 임계 구역. 한 스레드가 lock을 오래 쥐고 있으면, 나머지는 기다리거나 “기아” 상태가 됩니다. synchronized/Lock 블록 안의 시간을 최소화하세요.