📚 교착 상태 (deadlock)

자바 코드를 기반으로 설명됩니다.

✅ 도입

📌 멀티 프로세스 & 멀티 쓰레드

교착 상태는, 멀티 프로세스와 멀티 쓰레드 환경에서 공유 자원에 접근할 때 발생할 수 있는 문제 입니다.

참고하면 좋은 포스팅
프로세스와 쓰레드
프로세스, 쓰레드 공유자원 동기화

✅ 정의

📌 교착상태 란?

프로세스를 실행하기 위해서는, 자원이 필요 하다.
그런데, 만약 A 프로세스가 동작하기 위해서, a1 리소스를 점유중인 상태에서 b1라는 자원이 필요하고, B 프로세스는 동작하기 위해서 b1 리소스를 점유중인 상태에서 a1이라는 자원이 필요하다고 하면 어떨까?

작업A는 자신의 작업을 마치기 위해, 자원 b1 이 필요하고, 작업B는 마찬가지로 a1 이 필요한 상태입니다.
서로가 서로의 작업을 마치기 위해 한쪽이 먼저 작업을 포기해야 하는 상황에 빠지게 됩니다.
이러한 상황을 교착 상태 (dead lock) 이라고 표현합니다.

📌 정의

일어나지 않을 사건을 기다리며 프로세스의 진행이 멈춰버리는 현상

📌 발생 조건

교착상태가 일어나기 위해서는 4가지 필요 조건이 있습니다.
4가지가 모두 만족한다면, 교착 상태(deadlock)이 발생하게 될 가능성이 생기게 됩니다.

상호 배제
교착 상태가 일어나는 근본적인 원인은, 하나의 프로세스만 해당 자원을 이용 가능했기 때문입니다.
동기화 전략 등에서 소개되는 다양한 lock 기법 등을 활용하여 동기화 제어를 한다면, 하나의 프로세스만 접근 가능하도록 통제하기 때문에 이러한 문제가 발생할 수 있습니다.

점유와 대기
한 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 할당받기를 기다린다면 교착 상태가 발생할 수 있습니다.
위의 작업A, 작업B 예제가 딱 그 상태 입니다.
작업A는 작업을 완료하기 위해, a1 및 b1 리소스를 할당 받기 위해 대기하는 상황이 발생합니다.

비선점
비선점이란, 자원을 이용하는 프로세스의 작업이 끝나야만 비로소 자원을 이용할 수 있다는 것을 의미합니다.
위 예제 작업A가 원하는 b1리소스는, 작업B가 b1 리소스를 반납해줘야만 가능하지만, 그렇지 않게 설계되어 있습니다.
즉, 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 경우 (비선점), 교착 상태가 발생할 수 있습니다.

원형 대기
프로세스와 프로세스가 요청한 자원이 원의 형태를 이루는 경우입니다.
각각의 프로세스가 서로 점유한 자원을 할당 받기 위해 원의 형태로 대기할 경우, 교착 상태가 발생할 수 있습니다.
일상적인 예시로, 중고거래를 위해 만난 사람끼리 "먼저 물건을 주세요", "먼저 돈을 입금해주세요" 하고, 무한히 반복하며 거래가 되지 않는 상태라고 말할 수 있습니다.

📌 Java 코드

해결 방법을 알아보기에 앞서, 간단하게 deadlock 이 발생하는 예제 코드를 만들어 보겠습니다.

public class DeadlockExample {
	private final Object lockA = new Object();
	private final Object lockB = new Object();

	public void threadA() {
		synchronized (lockA) {
			System.out.println("ThreadA: lockA 점유");
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
			}
			synchronized (lockB) {
				System.out.println("ThreadA: lockB 점유");
			}
		}
	}

	public void threadB() {
		synchronized (lockB) {
			System.out.println("ThreadB: lockB 점유");
			try {
				Thread.sleep(100);
			} catch (InterruptedException e) {
			}
			synchronized (lockA) {
				System.out.println("ThreadB: lockA 점유");
			}
		}
	}

	public static void main(String[] args) {
		DeadlockExample example = new DeadlockExample();
		new Thread(example::threadA).start();
		new Thread(example::threadB).start();
	}
}

threadA 와 threadB는 각각 하나의 자원을 가지고, 0.1초 뒤, 반대 측에서 점유 중인 lock에 대해 접근을 하는 코드 입니다.
위에 소개된 4가지의 필수 조건이 모두 포함된 완벽한(?) 코드 입니다.

ThreadA: lockA 점유 ThreadB: lockB 점유 ... 다음 응답이 없음 ...

📌 해결 방법

해결 방법은 간단하고 정말 다양합니다.
크게 3가지 방법으로 나눠 해결 및 회피 할 수 있습니다.

📌 교착 상태 예방

교착 상태 예방은 위의 소개된 4가지 필요 조건 중 하나라도, 깨트려 deadlock 이 절대 발생하지 않도록 만드는 방법입니다.
너무나 다양하고 방법들이 많기 때문에, 이러한 관점으로도 회피가 가능하다 라는 걸 아래의 예시를 통해 참고만 하시면 좋습니다.

상호 배제 제거
- 예를 들면, 일반 Lock 을 세마포등으로 변경해, 여러 쓰레드에서 동시에 접근이 가능하도록 만들 수도 있습니다.
- Java에서는, 읽기 작업에 대해서 동시에 여러 스레드가 접근 가능하도록 하는 ReentrantReadWriteLock 이라는걸 제공해줍니다.
- 다음과 같이 코드를 변경한다면, deadlock은 해결됩니다.

public class NoHoldAndWaitExample {
	private final Lock lockA = new ReentrantLock();
	private final Lock lockB = new ReentrantLock();

	public void threadA() {
		while (true) {
			boolean gotLockA = lockA.tryLock();
			boolean gotLockB = lockB.tryLock();
			if (gotLockA && gotLockB) {
				try {
					System.out.println("ThreadA: lockA, lockB 점유");
					break;// 작업 후 종료
				} finally {
					lockB.unlock();
					lockA.unlock();
				}
			}
			// 하나라도 못 잡으면 전부 반환하고 재시도
			if (gotLockA)
				lockA.unlock();
			if (gotLockB)
				lockB.unlock();
			try {
				Thread.sleep(10);
			} catch (InterruptedException e) {
			}
		}
	}

	public void threadB() {
		while (true) {
			boolean gotLockA = lockA.tryLock();
			boolean gotLockB = lockB.tryLock();
			if (gotLockA && gotLockB) {
				try {
					System.out.println("ThreadB: lockA, lockB 점유");
					break; // 작업 후 종료
				} finally {
					lockB.unlock();
					lockA.unlock();
				}
			}
			// 하나라도 못 잡으면 전부 반환하고 재시도
			if (gotLockA)
				lockA.unlock();
			if (gotLockB)
				lockB.unlock();
			try {
				Thread.sleep(10);
			} catch (InterruptedException e) {
			}
		}
	}

	public static void main(String[] args) {
		NoHoldAndWaitExample example = new NoHoldAndWaitExample();
		new Thread(example::threadA).start();
		new Thread(example::threadB).start();
	}
}

ThreadA: lockA, lockB 점유 ThreadB: lockA, lockB 점유
Process finished with exit code 0

이와 같이 해결하는 방법은 정말 다양하고, 위의 소개된 해결 방법이 현재 구조상 어울리지 않아 해결 방법이 되지 않을 수가 있습니다.

📌 교착 상태 회피

교착 상태 회피는, 교착 상태가 발생하지 않을 정도로만 조심하면서 자원을 할당하는 방법입니다.
여기서 교착 상태가 발생하는 원인을, 한정된 자원의 무분별한 할당으로 발생하는 문제라고 판단하고 이를 해결하기 위한 아이디어가 핵심입니다.
대표적인 예시로, 은행가 알고리즘이 대표적입니다.

은행가 알고리즘 살짝
- 자원을 할당할 때 마다, 모든 프로세스가 결국 자원을 얻고 정상 종료를 할 수 있는 안전 상태 인지 시뮬레이션을 통해 확인 후, 자원을 할당합니다.
- 만약 알고리즘에 의해, 위험한 상황이 예상된다면 자원 할당을 거부해서 교착 상태 발생을 회피하는 방식입니다.

📌 교착 상태 검출 후 회복

교착 상태 검출 후 회복은, 교착 상태가 발생한 후 정상적으로 동작하도록 사후 처리를 통해 문제를 해결하는 방법입니다.
자원 할당에 대해 제한을 두지 않고 할당하고, 주기적으로 교착 상태 발생 여부를 검사하여 이를 해결합니다.
만약 검출되면, 자원 선점을 통해 회복 하거나, 문제 프로세스를 강제 종료하여 해결하는 방법들이 존재합니다.

자원 선점을 통한 회복
교착 상태가 해결될 때까지 다른 프로세스로부터 강제로 자원을 빼앗아 한 프로세스에 몰아주는 것을 의미

📌 정리

교착 상태는 개발 중에 흔히 드러나지 않습니다.
단위 테스트, 로컬 환경, 개발 서버에서는 거의 재현되지 않는 경우가 많고, 실제 서비스 환경에서 특정 트래픽 패턴이나 운이 나쁜 타이밍에만 드물게 발생하는 경우가 많습니다.
스레드가 많아지고, 락이나 동기화 자원이 많아질수록 발생 확률이 올라갑니다.
동일한 코드라도, “스레드 스케줄링” “운영체제의 타임슬라이스” “자원 사용량, 네트워크 상황” 같은 외부 요인에 따라 교착상태가 전혀 없이 동작하거나, 갑자기 발생해서 서비스가 멈추기도 합니다.
한 번 발생하면 원인 파악이 매우 어렵고, 스레드 덤프, 로그 분석, 리소스 점유 상태 추적 등 다양한 도구가 필요합니다.
물론, 명확한 교착 상태에 대한 원인 파악이 가장 베이스되어야 한다고 생각합니다.

[운영 체제] 멀티 쓰레드&프로세스의 교착 상태(deadlock)

스택 시리즈운영체제 시리즈