경쟁 상태(race condition)

wait() & notify()

wait() 메서드를 호출한 스레드는 획득한 락을 포기하고 대기 상태에 들어가며 다른 스레드가 동일한 객체의 락을 얻은 뒤 notify()나 notifyAll() 메서드를 호출할 때까지 깨어나지 않습니다. 주의하실 점은 락을 얻지 않은 상태에서 wait(), notify(), notifyAll() 메서드를 호출하면 IllegalMonitorStateException 예외가 발생합니다.

대략적으로 나타낸 과정

다른 스레드보다 락을 빠르게 얻기 위해서 경쟁 중인 스레드는 EntryList에 있습니다. 그 중 한 스레드가 객체의 락을 얻어서 실행 상태로 들어갔다가 wait() 메서드를 만나면 락을 포기하고 대기 상태로 들어가 WaitSet으로 이동합니다. 그리고 notify()나 notifyAll()로 깨어난 스레드는 WaitSet에서 EntryList로 이동하여 다시 락을 얻기 위한 경쟁을 시작합니다. 예시를 살펴보면서 감을 잡아보도록 하겠습니다.

예시 살펴보기

class Waiter implements Runnable {
	private final Object lock;
	
	public Waiter(Object lock) {
		this.lock = lock;
	}
	
	public void run() {
		synchronized (lock) {
			System.out.println("Waiter가 락을 포기하고 대기 상태로 들어갑니다.");
			try {
				lock.wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
			System.out.println("Waiter가 깨어났습니다.");
		}
	}
}

class Notifier implements Runnable {
	private final Object lock;
	
	public Notifier(Object lock) {
		this.lock = lock;
	}
	
	public void run() {
		synchronized (lock) {
			System.out.println("Notifier가 알림을 보냈습니다.");
			lock.notify();
			System.out.println("Notifier가 종료됩니다.");
		}
	}
}

public class JavaTutorial26 {
    public static void main(String[] args) throws InterruptedException {
    	final Object lock = new Object();
    	Thread waiter = new Thread(new Waiter(lock));
    	Thread notifier = new Thread(new Notifier(lock));
    	
    	waiter.start();
    	Thread.sleep(2000);
    	notifier.start();
    }
}

코드를 살펴보면 waiter가 lock의 락을 얻고 난 뒤에, wait() 메서드 호출로 인해 얻었던 락을 포기하고 대기 상태로 들어갑니다. 그리고 notifier가 lock의 락을 얻고나서 notify() 메서드 호출로 waiter를 깨웁니다. 하지만 락은 현재 notifier가 잡고 있으므로 동기화 블록을 벗어날 때까지 waiter는 락을 얻을 수 없습니다. 결과를 살펴보면 아래와 같이 출력될 것입니다.

거짓 기상(spurious wakeup)

오라클에서는 이를 아래와 같이 설명하고 있습니다.

스레드는 알림, 인터럽트, 시간 초과 없이도 깨어날 수 있으며, 흔히 거짓 기상(spurious wakeup)이라고 합니다. 실제로 이런 일은 거의 일어나지 않지만, 응용 프로그램은 스레드가 깨어나야 하는 조건을 검사하고 이러한 조건을 만족하지 않을 경우 계속 대기시킴으로써 이 문제를 방지해야 합니다. 즉, 아래와 같이 항상 루프에서 대기해야 합니다.

wait()을 사용할 때는 아래와 같이 while문과 함께 사용할 것을 강조하고 있습니다. 스레드가 깨어나지 말아야 할 상황에서 깨어났더라도, 스레드가 깨어날 조건을 검사 후 만족하지 않으면 다시 대기시키기 위함입니다.

synchronized (lock) {
     while (!condition)
         lock.wait(timeout);
     ... // 조건을 만족하면 수행할 동작
 }

생산자-소비자 문제(Producer-consumer problem)

이 문제는 한정 버퍼 문제(bounded-buffer problem)라고도 부릅니다. 이 문제에서는 이름 그대로 생산자와 소비자가 등장하며, 크기가 고정된 버퍼(buffer)를 서로 공유합니다. 한 명의 생산자는 제품을 만들고 이를 버퍼에 넣고, 한 명의 소비자는 버퍼에 있는 제품을 꺼내서 소비합니다. 생산자는 버퍼에 제품을 넣기 전에 버퍼가 가득차면 버퍼에 공간이 생길 때까지 기다려야 하며, 소비자는 제품을 꺼내기 전에 버퍼 안에 제품이 없다면 제품이 버퍼로 들어올 때까지 기다려야 합니다.

버퍼(buffer)

버퍼는 많은 의미를 가지고 있지만, 컴퓨터 과학에선 일반적으로 데이터를 한 곳에서 다른 곳으로 보낼 때 데이터가 임시로 저장되는 공간을 말합니다. 이 공간은 보통 데이터를 받는 속도와 처리하는 속도가 다를 때 사용합니다. 생산자와 소비자의 관점에서 바라보면, 생산자의 생산 속도와 소비자의 소비 속도가 서로 다르므로 생산자가 생산한 생산품을 임시로 담아두는 공간이 필요한데 그것이 바로 버퍼입니다. 회전초밥집을 비유로 들면, 생산자가 요리사고 소비자는 손님이며 버퍼는 중간에서 돌아가는 컨베이어 벨트라고 할 수 있습니다.

이를 그림으로 나타내면 다음과 같습니다.

우선 생산자(producer)의 코드를 작성해보도록 하겠습니다. 생산자는 버퍼와 생산 횟수를 넘겨받고, 지정된 횟수만큼 생산하여 버퍼에 넣는 역할을 합니다.

class Producer implements Runnable {
	private final BoundedBuffer buffer; // 버퍼
	private final int iterations; // 생산 횟수
	
	public Producer(BoundedBuffer buffer, int iterations) {
		this.buffer = buffer;
		this.iterations = iterations;
	}
	
	public void run() {
		// 지정된 생산 횟수만큼 생산하고 버퍼에 넣는다.
		for (int i = 1; i <= iterations; i++) {
			buffer.put(i);
		}
	}
}

다음으로 소비자(consumer)의 코드를 작성해보도록 하겠습니다. 소비자는 버퍼와 소비 횟수를 넘겨받고, 지정된 횟수만큼 버퍼에서 제품을 꺼내 소비하는 역할을 합니다.

class Consumer implements Runnable {
	private final BoundedBuffer buffer; // 버퍼
	private final int iterations; // 소비 횟수
	
	public Consumer(BoundedBuffer buffer, int iterations) {
		this.buffer = buffer;
		this.iterations = iterations;
	}
	
	public void run() {
		// 지정된 소비 횟수만큼 버퍼에서 제품을 꺼내 소비한다.
		for (int i = 0; i < iterations; i++) {
			buffer.take();
		}
	}
}

이번에는 버퍼(buffer)의 코드를 작성해보도록 하겠습니다. 간단히 구현하기 위해서 여기서는 순환 큐(Circular Queue)라는 자료구조를 사용합니다.

class BoundedBuffer {
	private final int[] buffer; // 버퍼
	private final int capacity; // 최대 크기
	private int in, out; // 쓰기 인덱스와 읽기 인덱스
	
	public BoundedBuffer(int size) {
		capacity = size;
		buffer = new int[capacity];
	}
	
	public void put(int product) {
		// 버퍼가 가득 찼으면 무한 루프를 돌면서 계속 대기한다.
		while (isFull());
		// 버퍼에 제품을 넣는다.
		buffer[in] = product;
		in = (in + 1) % capacity;
		System.out.println("생산됨: " + product);
	}
	
	public int take() {
		// 버퍼가 비어 있으면 무한 루프를 돌면서 계속 대기한다.
		while (isEmpty());
		// 버퍼에서 제품을 꺼내 소비한다.
		int product = buffer[out];
		out = (out + 1) % capacity;
		System.out.println("소비됨: " + product);
		return product;
	}
	
	public boolean isEmpty() {
		return in == out;
	}
	
	public boolean isFull() {
		return (in + 1) % capacity == out;
	}
}

마지막으로 메인 메서드를 작성합니다. 버퍼의 크기는 10이고, 생산자와 소비자는 각각 30번 만큼 생산과 소비를 반복합니다. 문제없이 실행되는 것 같지만 반복 횟수를 올리면 생산자와 소비자 모두 무한 루프에 빠질 수 있으며, 까딱 잘못 구현하면 경쟁 상태에 빠질 수도 있습니다. 무한 루프에 빠지는 원인에는 JIT 컴파일러의 최적화나 캐시 일관성 문제를 들 수 있으나 얘기가 길어지므로 이 부분은 마지막에 설명하도록 하겠습니다.

public class JavaTutorial26 {
    public static void main(String[] args) throws InterruptedException {
    	BoundedBuffer buffer = new BoundedBuffer(10);
    	int iterations = 30;
    	Thread producer = new Thread(new Producer(buffer, iterations));
    	Thread consumer = new Thread(new Consumer(buffer, iterations));
    	
    	producer.start();
    	consumer.start();
    	producer.join();
    	consumer.join();
    	
    	System.out.println("프로그램을 종료합니다.");
    }
}

순환 큐(Circular queue)

순환 큐를 잠깐만 살펴보도록 하겠습니다. 여기서 큐(queue)는 길게 늘어선 줄을 의미하는데 순환(circular) 구조를 상상하면 아래와 같이 시작과 끝이 연결된 줄이 됩니다. 프로그래밍에선 줄을 배열로 바라볼 수도 있으므로, 시작과 끝이 연결된 배열이라고도 할 수 있습니다. 순환 큐는 원형 큐라고 부르기도 하고, 링 버퍼(ring buffer)라고 부르기도 합니다.

코드에서 in은 버퍼 안에서 다음으로 비어 있는 위치를 가리키고, out은 버퍼 내에서 첫 번째로 데이터가 채워져 있는 위치를 가리킵니다. 따라서, BoundedBuffer.put() 메서드를 호출하여 값을 버퍼에 넣을 때는 buffer[in]에 값을 쓰고 in을 (in + 1) % capacity로 변경합니다. 마찬가지로 BoundedBuffer.take() 메서드를 호출하여 버퍼에서 값을 꺼낼 때는 buffer[out]에 있는 값을 읽고 out을 (out + 1) % capacity로 변경하여 다음으로 데이터가 채워져 있는 위치의 데이터를 읽게 됩니다.

원형 큐가 비어있는지 가득찼는지는 아래의 조건으로 확인합니다. 지금의 코드로는 데이터를 최대 capacity - 1개까지만 버퍼에 저장할 수 있습니다. 조금 수정하면 capacity개를 저장할 수 있도록 개선할 수 있으나, 코드가 길어져서 초점이 엇나갈 수 있으므로 여기서는 생산자-소비자 문제를 해결하는 것에 집중하겠습니다.

바쁜 대기(Busy waiting)

아래 코드는 다른 스레드가 어떤 작업을 처리했는지 확인하기 위해서 한 스레드에서 이를 지속적으로 확인합니다. 하지만 이러면 다른 스레드가 그 작업을 처리할 때까지는 하는 게 아무것도 없으므로 CPU 자원을 낭비하게 됩니다. 작업이 끝나기를 기다리며 쉬지 않고 이를 확인하는 것보다, 잠을 잘테니 작업이 끝나면 깨워달라고 하는 것이 좋습니다.

class BoundedBuffer {
	// ...
	public void put(int product) {
		// 버퍼가 가득 찼으면 무한 루프를 돌면서 계속 대기한다.
		while (isFull());
        // ...
    }
    // ...
}

극소수의 경우를 제외하고는 바쁜 대기는 안티패턴(anti-pattern)이라고 여겨집니다.

안티패턴(anti-pattern)

위키피디아에선 이를 아래와 같이 설명하고 있습니다. 간단하게 정리하면, 실제로 사용하고 있는 사람들은 많지만 효율적이지 못하고 생산적이지 못한 패턴을 말합니다.

안티패턴(anti-pattern)은 되풀이하여 일어나는 문제에 대한 일반적인 대응으로, 대개는 효과적이지 않고 기대와는 전혀 다른 결과를 낳을 위험이 있습니다. ... 흔하게 쓰이는 과정, 구조, 행동 패턴으로 처음에는 문제 대응이 적절하고 효율적으로 보이지만 좋은 결과보다 나쁜 결과를 더 많이 낳습니다.

wait() & notify()

위에서 살펴봤던 wait()과 notify() 메서드를 사용하면 위와 같은 문제를 해결할 수 있습니다. BoundedBuffer를 아래와 같이 수정하시면 됩니다.

class BoundedBuffer {
	// ...
	public synchronized void put(int product) {
		// 버퍼가 가득 차 있으면 버퍼에 넣을 수 없으므로 대기한다.
		while (isFull()) {
			try {
				// 제품이 소비될 때까지 기다린다.
				this.wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		// ...
        // 제품을 생산하면 이를 소비자에게 알려준다.
		this.notify();
	}
	
	public synchronized int take() {
		// 버퍼가 비어있으면 소비할 수 없으므로 대기한다.
		while (isEmpty()) {
			try {
				// 제품이 생산될 때까지 기다린다.
				this.wait();
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		// ...
        // 제품을 소비하면 이를 생산자에게 알려준다.
		this.notify();
		return product;
	}
}

라이브락(Livelock)

다른 스레드가 어떻게 행동하는지에 따라서 스레드의 반응이 달라진다면 라이브락이 일어날 수 있습니다. 데드락과 비슷하게 작업을 더 이상 진행할 수 없지만, 차이점이 있다면 스레드가 대기 상태가 아니라 실행 상태라는 것입니다. 오라클의 예시를 살펴보면 다음과 같습니다.

라이브락(livelock)은 복도에서 두 사람이 서로를 지나치려고 하는 것과 비슷합니다. 철수는 영희가 지나갈 수 있도록 왼쪽으로 움직이고, 영희는 철수가 지나갈 수 있도록 오른쪽으로 움직입니다. 서로가 여전히 길을 막고 있는 걸 보고 철수는 오른쪽으로 움직이고, 영희는 왼쪽으로 움직입니다. 아직도 서로가 길을 막고 있어서 ...

여기서는 편의를 위해서 다른 예시를 다루도록 하겠습니다. 예를 들어서 아래와 같은 상황을 상상해봅시다.

납치범은 돈을 먼저 보내주면 인질을 풀어주겠다고 말하고, 협상가는 인질을 먼저 풀어주면 돈을 보내주겠다고 말합니다. 먼저 행동해야 그에 따라서 자신도 행동할 것이라고 말하므로 되풀이되는 이런 상황이 끝나지 않습니다.

이를 코드로 구현하면 아래와 같을 것입니다.

class Kidnapper {
	private boolean hostageReleased = false;
	
	public void negotiateWith(Negotiator negotiator) {
		while (!negotiator.isMoneySent()) {
			System.out.println("납치범: 협상가가 돈을 보내주길 기다리는 중");
			try {
				Thread.sleep(10);
			} catch (InterruptedException ex) {
				ex.printStackTrace();
			}
		}
        // 돈을 보내주면 인질을 풀어준다.
		releaseHostage();
	}
	
	private void releaseHostage() {
		System.out.println("납치범: 인질을 풀어줌");
		hostageReleased = true;
	}
	
	public synchronized boolean isHostageReleased() {
		return hostageReleased;
	}
}

class Negotiator {
	private boolean moneySent = false;
	
	public void negotiateWith(Kidnapper kidnapper) {
		while (!kidnapper.isHostageReleased()) {
			System.out.println("협상가: 납치범이 인질을 풀어주길 기다리는 중");
			try {
				Thread.sleep(10);
			} catch (InterruptedException ex) {
				ex.printStackTrace();
			}
		}
        // 인질을 보내주면 돈을 보내준다.
		sendMoney();
	}
	
	private void sendMoney() {
		System.out.println("협상가: 납치범에게 돈을 보냄");
		moneySent = true;
	}
	
	public synchronized boolean isMoneySent() {
		return moneySent;
	}
}

public class JavaTutorial26 {
    public static void main(String[] args) {
        final Kidnapper kidnapper = new Kidnapper();
        final Negotiator negotiator = new Negotiator();
        
        // 편의를 위해서 익명 클래스를 통해 구현했으며 이는 뒤에서 다룹니다.
        new Thread(new Runnable() {
        	public void run() {
        		kidnapper.negotiateWith(negotiator);
        	}
        }).start();
        
        new Thread(new Runnable() { 
            public void run() {
            	negotiator.negotiateWith(kidnapper);
            }   
        }).start();
    }
}

프로그램을 실행하면 종료하기 전까지는 아래와 같은 상황이 반복됩니다. 라이브락을 해결하기 위한 일반적인 해결책은 없지만, 더 이상 작업의 진척이 없다면 스레드는 같은 작업을 반복하고 있는 것을 멈춰야 합니다. 위의 예에서는 일정 횟수 반복되면 둘 중 하나가 포기한다던가 우선순위를 부여하는 등의 해결책을 떠올려볼 수 있습니다.

한 걸음 더 나아가기

재배열(reordering)

앞에서도 봤듯이 멀티 스레드 프로그램에서는 코드를 동시에 실행할 때 일반적으로 스레드 간섭이 일어날 뿐만 아니라, 성능을 최적화하기 위해서 사용하고 있는 컴파일러나 프로세서에 따라 연산 순서를 재배열(reordering) 할 수도 있다는 것입니다. 이로 인해서 소스 코드를 들여다봐도 연산의 실행 순서가 어떻게 되는지 파악하기 어려울 수 있습니다.

JIT 컴파일러의 재배열

예를 들어서, 아래와 같은 자바 코드가 있을 때 프로그래머는 어떤 순서대로 값이 할당될지 아주 쉽게 예상할 수 있습니다.

a = 1; // a = 1
b = true; // b = true

하지만 JIT 컴파일러는 프로그래머가 재배열이 일어난 것을 인식하지 못하도록 최종 결과에 영향이 가지 않는 선에서 연산을 아래와 같이 재배열 할 수도 있습니다. 재배열이 일어나면 프로그램 실행 중에 변수 a에 1이란 값을 할당하기 전에 변수 b에 true란 값을 할당할 수도 있으며, 이래도 우리가 볼 수 있는 실행 결과는 동일하므로 단일 스레드 프로그램에서 재배열이 일어난다고 해도 프로그래머는 이를 알아차릴 수 없습니다.

0x00000156245a064f:   mov    BYTE PTR [rbx+0x10],0x1      ;*putfield b
0x00000156245a0653:   mov    DWORD PTR [rbx+0xc],0x1      ;*putfield a

실제로 내부를 살펴보면 사용하고 있는 하드웨어나 운영체제, JVM에 따라서 위와 같이 b에 먼저 true를 할당한 뒤에 a에 1을 할당하는 것을 볼 수도 있습니다. 이번에는 위의 예시를 확장하여 두 개의 스레드가 두 개의 서로 다른 코어에서 병렬로 실행된다고 가정해봅시다. 첫 번째 스레드는 변수 a와 b에 값을 쓰고, 두 번째 스레드는 그 변수들의 값을 읽습니다. 여기서 (1)에 있는 조건식이 참이 될 수 있을까요?

class SharedObject {
	public int a = 0;
	public boolean b = false;
}

class WorkerA implements Runnable {
	private final SharedObject sharedObj;
	
	public WorkerA(SharedObject sharedObj) {
		this.sharedObj = sharedObj;
	}
	
	public void run() {
		sharedObj.a = 1;
		sharedObj.b = true;
	}
}

class WorkerB implements Runnable {
	private final SharedObject sharedObj;
	
	public WorkerB(SharedObject sharedObj) {
		this.sharedObj = sharedObj;
	}
	
	public void run() {
		boolean b = sharedObj.b;
		int a = sharedObj.a;
		
		if (a == 0 && b == true) { // (1)
			System.out.println("a에 값이 할당되기 전에 b에 값이 할당되었습니다.");
		}
	}
}

public class JavaTutorial26 {
    public static void main(String[] args) throws InterruptedException {
    	for (int i = 0; i < 1_000_000; i++) {
    		final SharedObject sharedObj = new SharedObject();
    		Thread workerA = new Thread(new WorkerA(sharedObj));
    		Thread workerB = new Thread(new WorkerB(sharedObj));
    		
    		workerA.start();
    		workerB.start();
    	}
    }
}

프로그래머가 예측할 수 있는 경우의 수는 'a = 0, b = false', 'a = 1, b = false', 'a = 1, b = true'와 같이 세 가지입니다. 코드 순서에서 볼 수 있듯이 프로그래머는 b에 값이 할당되기 전에 a에 값이 할당되리라 기대합니다. 하지만 여기서 재배열이 일어나면 'a = 0, b = true'이라는 결과를 볼 수도 있습니다.

재현하기가 상당히 까다로움

만약, 재배열이 일어나지 않더라도 캐싱으로 인해 마치 재배열이 일어난 것처럼 느낄 수도 있으나, 요즘의 CPU는 캐시 일관성 프로토콜(cache consistency protocol) 중 하나인 MESI 프로토콜의 변형을 통해 캐시의 일관성을 유지합니다. 이는 이 글에서 다루려는 범위를 벗어나므로 여기서는 설명하지 않습니다.