기아상태와 공정성(Starvation and Fairness)

이 글은 원 저자 Jakob Jenkov의 허가로 포스팅된 번역물이다.

원문 URL : http://tutorials.jenkov.com/java-concurrency/starvation-and-fairness.html

어떤 쓰레드가 다른 쓰레드들이 CPU시간을 모두 잡고 있어 CPU시간을 사용할 수 없게 되는 현상을 "기아상태(starvation)" 라 한다. 이 기아 쓰레드는 글자 그대로 "굶어 죽게" 된다. 다른 쓰레드들이 CPU시간을 사용하도록 되어 있기 때문이다. 기아상태의 해결책은 "공정성(fairness)" 이다. 공정성이란, 모든 쓰레드들이 자신의 작업을 수행할 기회를 공정하게 갖는 것을 의미한다.

자바에서의 기아상태의 원인

다음 세 가지는 자바에서 쓰레드의 기아상태를 일으키는 일반적인 원인들이다.

1. 높은 우선순위를 가진 쓰레드들의 CPU시간 독점
2. 동기화 영역 진입을 위한 무한한 대기 중 블록 상태
3. 객체에 대한 무한한 대기 상태(wait() 호출로 인한)

높은 우선순위를 가진 쓰레드들의 CPU시간 독점

자바에서는 쓰레드들 각각에 대한 우선순위를 설정할 수 있다. 이 우선순위가 높은 쓰레드는 더 많은 CPU시간을 획득한다. 우선순위는 1 에서 10 까지 지정할 수 있으며, 지정된 우선순위를 어떻게 해석하고 작업을 수행하게 할 것인지는 어플리케이션이 작동하는 OS에 달려있다. 대부분의 어플리케이션에 있어서 이 우선순위는 지정하지 않고 그냥 두는 편이 낫다.

동기화 영역 진입을 위한 무한한 대기 중 블록 상태

자바의 동기화는 기아상태의 또다른 원인이다. 자바의 동기화는 대기 중인 쓰레드의 순서를 전혀 보장하지 않는다. 이것은 이론적으로 쓰레드가 동기화 영역으로의 진입을 계속 시도하기만 하며 영원히 블록된 상태로 놓일 수 있음을 의미한다. 왜냐하면 이 동기화 영역으로의 진입권을 다른 쓰레드들이 계속, 거듭 획득하기 때문이다. 이 문제를 "기아상태" 라 부르고, 이 현상의 피해자 쓰레드는 "굶어 죽게" 된다. 구체적인 이유는 동기화 영역으로의 진입권을 계속 획득하고 있는 다른 쓰레드들이 CPU시간을 계속 할당받기 때문이다.

객체에 대한 무한한 대기 상태(wait() 호출로 인한)

둘 이상의 쓰레드가 동일한 객체의 wait() 메서드 호출로 대기 상태에 놓였을 때, nofity() 메소드는 이들 중 어떤 쓰레드를 깨울 것인지 전혀 알 수 없다. 즉 어떤 쓰레드 깨어날지 아무도 모른다. 때문에 여기에는 깨어나지 못하고 계속 대기중인 쓰레드가 존재하게 될 위험성이 존재한다. nofity() 메소드가 계속 다른 쓰레드만 깨울 수 있기 때문이다.

자바에서의 공정성 구현

자바에서 100%의 공정성을 구현하기란 불가능하지만 우리는 쓰레드들 사이의 공정성을 높이기 위한 동기화 구성을 구현할 수 있다.

먼저 아래 간단한 코드를 보자.

public class Synchronizer{

  public synchronized void doSynchronized(){
    // 오랜 시간이 소요되는 작업을 수행한다.
  }

}

다수의 쓰레드가 위의 doSynchronized() 메소드를 호출하게 되면 처음 메소드 안으로 진입한-코드를 수행하는-쓰레드를 제외한 나머지 쓰레드들은 모두 블록된다. 메소드 안으로 진입한 쓰레드가 메소드 수행을 마치고 메소드 밖으로 빠져나가게 되면 대기 중이던 쓰레드들 중 하나가 메소드로의 진입권을 획득하게 되는데, 이 쓰레드가 어떤 쓰레드일지에 대한 보장은 전혀 없다.

Synchronized 대신 Lock 사용하기

공정성을 높이기 위한 다른 방법으로 synchronized 를 버리고 Lock 객체를 사용해보자.

public class Synchronizer{
  Lock lock = new Lock();

  public void doSynchronized() throws InterruptedException{
    this.lock.lock();
      // 크리티컬 섹션. 오랜 시간이 소요되는 작업을 수행한다.
    this.lock.unlock();
  }

}

이제 synchronized 선언은 없다. 크리티컬 섹션은 Lock.lock(), Lock.unlock() 이 보호한다.

간단한 Lock 클래스 구현은 다음과 같이 이루어질 수 있다.

public class Lock{
  private boolean isLocked      = false;
  private Thread  lockingThread = null;

  public synchronized void lock() throws InterruptedException{
    while(isLocked){
      wait();
    }
    isLocked      = true;
    lockingThread = Thread.currentThread();
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "호출 쓰레드가 이 락을 소유하지 않음.");
    }
    isLocked      = false;
    lockingThread = null;
    notify();
  }
}

Synchronizer 클래스와 Lock 구현 클래스를 보자. 둘 이상의 쓰레드가 lock() 을 동시에 호출하게 되면 lock() 메소드로의 진입에서 블록된다는 것을 알 수 있다. 그리고 lock이 잠기면(isLocked=true) 쓰레드들은 while 안에서 wait() 을 호출하여 다시 블록 상태에 놓인다(여기서 wait() 메소드 호출은 synchronized 메소드로 진입하며 획득한 락을 해제한다는 사실을 기억하자). 결국 처음 lock() 을 수행한 쓰레드를 제외한 나머지 쓰레드들은 lock() 안에서의 wait() 호출로 모두 블록 상태에 놓이게 된다.

doSynchronized() 메소드의 lock() 과 unlock() 사이의 주석은 lock() 과 unlock() 사이의 코드가 수행에 오랜 시간이 소요됨을 명시하고 있다. 이 코드의 수행이 lock() 메소드로의 진입과 wait() 메소드 호출에 비해 오랜 시간이 소요된다고 가정해보자. 이것은 크리티컬 섹션으로의 진입을 위해 대기한 시간의 대부분이 lock() 메소드로의 진입을 위해서가 아닌, lock() 메소드 안의 wait() 메소드 호출로 인해 블록 상태에 되어 소요됨을 의미한다.

위에서 언급되었듯, synchronized 는 다수의 쓰레드가 경합 중에 있을 때 어떤 쓰레드가 진입권을 획득할지에 대해 보장하지 않는다. wait() 메소드도 마찬가지로 notify() 가 호출될 때 어떤 쓰레드가 깨어날지 보장하지 않는다. 고로, 이 Lock 클래스는 synchronized 로 동기화된 처음 버전의 doSynchronized() 메소드와 그 공정성에 있어 아무런 차이가 없다.

현재의 Lock 클래스는 자신의(this) wait() 메소드를 호출한다. 만약 쓰레드들이 각각 다른 객체의 wait() 을 호출하게끔 하여 한 객체에 대해 wait() 을 호출한 쓰레드를 하나로 만들어 쓰레드와 wait() 객체를 1:1 관계로 구현할 수 있다면, Lock 클래스는 어떤 객체에 대해 notify() 를 호출할지 선택할 수 있고, 즉 정확히 어떤 쓰레드를 깨울지 효과적으로 선택할 수 있을 것이다.

공정한 락

다음은 Lock 클래스를 공정한 락이 구현된, FairLock 으로 바꾼 것이다. 동기화와 wait() / notify() 메소드 활용에 있어 아까의 Lock 클래스와 비교해보면 구현이 다소 바뀐 것을 알 수 있을 것이다.

코드의 디자인이 이전의 Lock 클래스에서 여기에 도달하기까지에는 늘어나는 디자인 과정과 관련된 더 긴 이야기가 있는데, 이전 과정의 문제점을 수정했다: 중첩 모니터 락아웃, 이탈 상태, 신호 소실. 이 논의를 여기에 가져오기에는 이 글이 너무 길어지므로 생략하기로 한다. 각 과정에 대한 내용은 각각에 알맞는 별도의 글에 포함되어 있다(링크를 따라가면 됨).

중요한 것은 이제 lock() 을 호출하는 쓰레드는 큐에 담기게 되고 오직 이 큐에서 처음에 위치한 쓰레드만이 FairLock 인스턴스에 락을 걸 수 있게 된다(물론 아직 락이 걸리지 않을 상태일 경우). 다른 모든 쓰레드들은 큐의 최상위 쓰레드가 될 때 까지 대기 상태로 놓인다.

public class FairLock {
    private boolean           isLocked       = false;
    private Thread            lockingThread  = null;
    private List<QueueObject> waitingThreads =
            new ArrayList<QueueObject>();

  public void lock() throws InterruptedException{
    QueueObject queueObject           = new QueueObject();
    boolean     isLockedForThisThread = true;
    synchronized(this){
        waitingThreads.add(queueObject);
    }

    while(isLockedForThisThread){
      synchronized(this){
        isLockedForThisThread =
            isLocked || waitingThreads.get(0) != queueObject;
        if(!isLockedForThisThread){
          isLocked = true;
           waitingThreads.remove(queueObject);
           lockingThread = Thread.currentThread();
           return;
         }
      }
      try{
        queueObject.doWait();
      }catch(InterruptedException e){
        synchronized(this) { waitingThreads.remove(queueObject); }
        throw e;
      }
    }
  }

  public synchronized void unlock(){
    if(this.lockingThread != Thread.currentThread()){
      throw new IllegalMonitorStateException(
        "호출 쓰레드가 이 락을 소유하지 않음.");
    }
    isLocked      = false;
    lockingThread = null;
    if(waitingThreads.size() > 0){
      waitingThreads.get(0).doNotify();
    }
  }
}

public class QueueObject {

  private boolean isNotified = false;

  public synchronized void doWait() throws InterruptedException {
    while(!isNotified){
        this.wait();
    }
    this.isNotified = false;
  }

  public synchronized void doNotify() {
    this.isNotified = true;
    this.notify();
  }

  public boolean equals(Object o) {
    return this == o;
  }
}

먼저 lock() 메소드 선언에는 더이상 synchronized를 사용하지 않는다. synchronized는 메소드 실행 코드에서 필요한 곳에 한하여 사용된다.

FairLock 은 lock() 메소드가 호출되면 새로운 QueueObject 인스턴스를 생성하여 이것을 대기 목록을 의미하는 waitingThreads에 넣는다. unlock() 을 호출하는 쓰레드는 대기 목록에서 가장 상위에 위치한 QueueObject 를 가져와 doNotify() 를 호출하여 대기 중인 쓰레드를 깨운다. 이런 방법으로 쓰레드는 한 번에 오직 하나의 쓰레드를 깨우게 된다. 이것이 FairLock 에서 공정성을 관리하는 부분이다.

여기서 이탈 상태를 피하기 위해 같은 synchronized 블록 안의 상태를 어떻게 체크하고 세팅하는지를 알아야 한다.

또한 QueueObject 는 하나의 세마포어이다. doWait() 과 doNotify() 메소드는 QueueObject 내부에 신호를 저장한다. unlock() 을 호출하는 다른 쓰레드에 의해 수행되는 이 작업은 queueObject.doWait() 호출 직전에 선점되는 쓰레드로 인해 발생하는 신호 소실 문제를 피하기 위함이다. 중첩 모니터 락아웃을 방지하기 위해 queueObject.doWait() 호출은 synchronized(this) 밖에서 이루어진다. 이렇게 함으로써 lock() 메소드 안의 synchronized(this)에 진입한 쓰레드가 하나도 없을 때 다른 쓰레드가 unlock() 을 호출하는 일이 가능해진다.

마지막으로 queueObject.doWait() 이 try-catch 블록 안에서 호출된다는 점을 보자. 이는 InterruptedException 이 발생하면 쓰레드는 lock() 메소드를 벗어나게 되는데, 이 때 queueObject 를 대기 목록(waitingThreads)에서 제거해야 하기 때문이다.

성능

Lock 과 FairLock 클래스를 비교해보면 FairLock 클래스 쪽이 lock() 과 unlock() 메소드에서 뭔가 더 많은 것을 한다는 것을 알 수 있다. 이런 코드들은 FairLock 의 동기화 성능을 Lock 보다 조금 떨어지게 만드는 원인이 된다. 이것이 어플리케이션에 얼마나 영향을 미치느냐는 FairLock 으로 보호되는 크리티컬 섹션 코드의 수행 시간에 달려 있다. 크리티컬 섹션 안의 코드 수행 시간이 길 수록 동기화의 오버헤드는 줄어든다. 물론 이것은 이 코드의 호출 빈도와도 관련이 있다.