Deadlock, liveness, Live lock, Starvation

Critical Section 을 지키고 Race Condition 을 피하려고 애쓰는동안, Multithread code 의 미묘한 "논리적인 오류" 가 생길수도 있다. 그 논리적인 오류들의 패턴은 다음과 같다.

 

 

Deadlock

deadlock 은 두개 이상의 thread 가 진행을 할 수 없을 경우에 발생한다. 첫번째 스레드가 필요로 하는 resource 를 두번째 스레드가 보유하고 있고, 두번째 스레드가 필요로 하는 resource 를 첫번째 스레드가 보유하고 있을 경우 발생한다.

 

예를 들어, 아래와 같은 코드에서 increment 의 mutex A 획득과 decrement 의 mutex B 획득이 동시에 이루어졌을때, 그 다음 mutex 를 획득하기 위해 두개의 thread 는 무한히 대기할 것이다.

 

public void increment() {
 // acquire mutex A
 // acquire mutex B
 
 // do work here
 
 // release mutex B
 // release mutex A
}


public void decrement() {
 // acquire mutex B
 // acquire mutex A
 
 // do work here
 
 // release mutex A
 // release mutex B

}

 

 

Liveness

프로그램이 적시에 실행되는 능력을 liveness 라고 부른다. 만약 deadlock 상황이라면 liveness 가 나타나지 않는다.

 

 

Live-Lock

live-lock 은 두개의 thread 가 각각 다른 thread 의 응답을 가지고 action 을 취할때 발생한다. 예를 들면 복도에서 두사람이 마주쳤는데 서로 길을 비키려고 한다고 해보자. 그런데 계속 같은 방향으로 길을 비키는 것이다. 그들은 결코 서로 복도를 지나갈 수 없을것이다. 이것이 바로 live lock 이다. 즉, 실패할 수 밖에 없는 기능을 계속해서 재시도 하는 것

 

아래 예제를 살펴보자. 아래 코드는 남편과 와이프가 스프를 먹고자 하는데 스푼은 하나밖에 없는 상황에서 남편과 와이프는 둘다 모두 너무나 정중해서 상대방이 먹지 않았다면 스푼을 상대방에게 넘기는 상황이다.

 

public class Livelock {
    static class Spoon {
        private Diner owner;
        public Spoon(Diner d) { owner = d; }
        public Diner getOwner() { return owner; }
        public synchronized void setOwner(Diner d) { owner = d; }
        public synchronized void use() {
            System.out.printf("%s has eaten!", owner.name);
        }
    }

    static class Diner {
        private String name;
        private boolean isHungry;

        public Diner(String n) { name = n; isHungry = true; }
        public String getName() { return name; }
        public boolean isHungry() { return isHungry; }

        public void eatWith(Spoon spoon, Diner spouse) {
            while (isHungry) {
                // Don't have the spoon, so wait patiently for spouse.
                if (spoon.owner != this) {
                    try { Thread.sleep(1); }
                    catch(InterruptedException e) { continue; }
                    continue;
                }

                // If spouse is hungry, insist upon passing the spoon.
                if (spouse.isHungry()) {
                    System.out.printf(
                        "%s: You eat first my darling %s!%n",
                        name, spouse.getName());
                    spoon.setOwner(spouse);
                    continue;
                }

                // Spouse wasn't hungry, so finally eat
                spoon.use();
                isHungry = false;
                System.out.printf(
                    "%s: I am stuffed, my darling %s!%n",
                    name, spouse.getName());
                spoon.setOwner(spouse);
            }
        }
    }

    public static void main(String[] args) {
        final Diner husband = new Diner("Bob");
        final Diner wife = new Diner("Alice");

        final Spoon s = new Spoon(husband);

        new Thread(new Runnable() {
            public void run() { husband.eatWith(s, wife); }
        }).start();

        new Thread(new Runnable() {
            public void run() { wife.eatWith(s, husband); }
        }).start();
    }
}

 

 

Starvation

다른 ‘greedy’ 한 스레드가 자원을 모두 소비함으로써, 또 다른 thread 는 자원에 접근할 수 없는 상태이다.

즉, 스레드가 작업을 진행하는데 꼭 필요한 자원을 영영 할당받지 못하는 것이라고 할 수 있다.

 

예를 들어, 특정 스레드가 파일시스템에서 허용하는 용량을 모두 차지하여, 나머지 스레드가 파일을 쓰지 못하고 계속 대기하는 상황을 생각해볼 수 있다.