DeadLock

JESS YANG·2021년 6월 13일

운영체제

목록 보기

1/1

개념

DeadLock(교착상태) : 두 개 이상의 작업(프로세스, 스레드)이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.
시스템에서는 두개 이상의 공유자원을 서로 다른 프로세스가 각각 점유 하면서 동시에 상대 프로세스가 점유하고 있는 자원을 요청하게 되면서 교착상태가 발생한다.

DeadLock 발생 조건

상호배제(Mutual Exclusion) : 여러 프로세스가 동시에 하나의 자원에 접근 하지 못하도록 하는 기법이지만 이러한 이유로 교착상태가 발생 할 수 있다.
점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 점유하기 위해 대기한다.
비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다. 자원의 반환은 사용하는 프로세스가 자발적으로 반납하는 경우에만 가능하다.
순환대기(Circular wair) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

교착상태 구현

public class DeadLock {
	public static Object Lock1 = new Object();
	public static Object Lock2 = new Object();
	   
	public static void main(String args[]) {
		ThreadDemo1 T1 = new ThreadDemo1();
		ThreadDemo2 T2 = new ThreadDemo2();
		T1.start();
		T2.start();
	}
	   
	private static class ThreadDemo1 extends Thread {
		public void run() {
			//lock1 객체 점유
			synchronized (Lock1) {
	            System.out.println("Thread 1: Holding lock 1...");
	            
	            try { Thread.sleep(10); }
	            catch (InterruptedException e) {}
	            System.out.println("Thread 1: Waiting for lock 2...");
	            //lock2 rorcp 점유
	            synchronized (Lock2) {
	               System.out.println("Thread 1: Holding lock 1 & 2...");
	            }
			}
		}
	}
	private static class ThreadDemo2 extends Thread {
		public void run() {
			//lock2 객체 점유
			synchronized (Lock2) {
				System.out.println("Thread 2: Holding lock 2...");
            
				try { Thread.sleep(10); }
			    catch (InterruptedException e) {}
			    System.out.println("Thread 2: Waiting for lock 1...");
			    //lock1 객체 점유 시도
			    synchronized (Lock1) {
			    	System.out.println("Thread 2: Holding lock 1 & 2...");
			    }
			}
		}
	} 
}

결과

Thread 2: Holding lock 2...
Thread 1: Holding lock 1...
Thread 2: Waiting for lock 1...
Thread 1: Waiting for lock 2...

위 코드는 DeadLock 발생조건을 모두 만족한다.
1. 상호배제 : synchronized 키워드를 이용하여 한번에 하나의 스레드만 임계 영역(Lock1, Lock2)에 진입/접근 한다.
2. 점유대기 : Tread1은 Lock1을 점유하고 Lock2가 해제 되기를 기다리고 있고 Thread2는 Lock2를 점유하고 Lock1이 해제 될때까지 기다리고 있다.
3. 비선점 : 각 스레드는 Lock1, Lock2를 가져올 수 없다.
4. 순환대기 : 아래 그림과 같이 순환 구조를 이루고 있다.

DeadLock 해결법

DeadLock의 근본적인 대응 방법은 프로그래머가 프로그램을 작성할때 DeadLock 발생 가능성 자체를 아예 방지를 해서 DeadLock이 발생하지 않게 하는 것이다.
하지만 운영체제와 같은 시스템 입장에서는 DeadLock이 발생 가능성을 가지고 있는 프로그램도 있을수 있기 때문에 일반화된 처리방법을 소개한다.

예방 : 교착상태가 발생하지 않도록 미리 차단시키는 방법으로 교착상태가 발생할 필요 충분 조건 4가지를 부정하는 것이다.(프로그램 작성 시점부터 lock 과 unlock을 적절히 배치)

상호배제 부정 : 동시 접근하는 자원에 대한 상호 배제 무시(일반적으로 허용되지 않음)
비선점 부정 : 다른 자원을 추가 할당 받기 위해 기다리고 있는 프로세스에 의해 점유된 자원이라면 선점하여 할당 (lock의 근본적인 목적에 위배됨. 자원 사용 상태의 저장과 복원이 단순한 경우에 적용)
점유와 대기 부정 : 프로세스가 실행 전에 필요한 모든 자원을 할당(자원의 이용률이 낮아짐)
순환대기 부정 : 자원의 순번을 부여하고, 각 프로세스는 필요의 순서가 아니라 자원의 순번에 따라 오름차순/내림차순으로만 요청

회피 : 교착상태를 인정하고 피하자. 시스템을 안정상태/불안전 상태로 구분하고 불안전 상태일 땐 대기시킨다.(교착상태 회피 알고리즘, 은행원 알고리즘이 대표적인 교착상태 회피 방안이다)
탐지 : 교착 상태 존재 여부 및 교착 상태에 연관된 프로세스와 자원을 알아낸다. 순환대기 존재 여부에 초점을 맞춘다.

프로세스와 자원과의 관계를 그래프로 나타내고 자원노드와 자원으로 화살표를 전부 제거해서 프로세스간의 순환을 알아내는 전략이다.

복구 : 교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 복구를 한다.

이러한 다양한 방법으로 DeadLock을 처리 할 수도 있지만 대부분의 운영체제에서는 DeadLock에 대한 처리를 실제로 하지 않는다고 한다(구현되어 있지 않다). 그 이유는, 이런 DeadLock 처리 방법들이 시스템 자원을 많이 사용 하기 때문이다.

참고문서

https://www.tutorialspoint.com/java/java_thread_deadlock.htm

JESS YANG