dead lock(교착상태) with JAVA

Deadlock(교착상태)

두 개 이상의 프로세스/스레드가 서로가 가진 리소스를 기다리는 상태

자동차는 프로세스/스레드를 나타내며, (1,2,3,4)는 리소스를 의미한다.

각 자동차는 직진을 하기 위해서, 2개의 리소스를 지나야 한다.

근데, 각 자동차가 동시에 직진을 하면, 오른쪽 그림과 같은 상태가 된다.

각 자동차는 1개의 리소스를 보유하고 있으나, 전진을 하기 위해서는 다른 자동차(프로세스/스레드)가 보유하고 있는 리소

스를 획득해야는데, 다른 자동차들도 또 다른 리소스를 획득하기 위하여 서로 대기 중이다.

 

Deadlock이 발생하는 4가지 조건 

1. Mutual exclusion : 리소스를 공유해서 사용할 수 없다, 즉 한 번에 1개의 프로세스/스레드만이 리소스를 가질 수가 있

다. 동시에 여러 프로세스/스레드가 리소스를 가질 수가 없다.

 

2.  Hold and Wait :  A라는 프로세스/스레드가 이미 하나 이상의 리소스를 취득한(HOLD)한 상태에서

B라는 프로세스/스레드가 사용하고 있는 리소스를 추가로 기다린다(WAIT).

-> 2번 리소스를 가지고 있는 자동차는 3번 리소스를 기다리고 있다.

 

3. No preemption : 리소스 반환(release)은 오직 그 리소스를 취득한 프로세스만 할 수 있다. 

즉, A라는 프로세스/스레드가 이미 어떤 리소스를 쥐고 있다면 B라는 프로세스/스레드는 A 프로세스/스레드가 반환을 하

기 전에는 빼앗아 갈 수가 없다.

->1번 리소스를 가지고 있는 자동차는, 2번 리소스를 가지고 있는 자동차가 리소스를 반환하기 전까지는 2번 리소스를 도

중에 취득할 수가 없다. 

 

4.Circular wait : 프로세스들이 순환(circular) 형태로 서로의 리소스를 기다린다.

 

OS Level에서의 Deadlock 해결법

아래의 4가지 방법이 존재하나, 어느 하나 속 시원하게 deadlock을 해결해 주지는 않는다. 

1. 데드락 방지(deadlock prevention)

-> deadlock 발생 4가지 조건 중, 하나가 충족되지 않게 시스템을 디자인하는 것!  

데드락 방지 #1 mutual exclusion

-> 리소스를 공유 가능하게 하면 된다. 

그러나 이 방법은 현실적으로 무리가 많다. 

예를 들어, 프린터와 같이 공유되어서는 안 되는 리소스들이 존재하기 때문이다.

데드락 방지#2 hold and wait

-> 사용할 리소스들을 모두 획득한 뒤에 시작

예를 들어서, A라는 프로세스/스레드는 2,3번 리소스를 필요로 한다.  2,3번 리소스를 모두 획득하기 전에는 A 프로세스/스

레드를 시작하게 하지 않는다.  

-> 리소스를 전혀 가지지 않는 상태에서만 리소스 요청

예를 들어, A라는 프로세스/스레드가 2번 리소스를 취하고 있다고 하자. 2번 리소스를 가지고 모든 작업을 마치면,  A 프로세스/스레드는 3번 리소스를 가지고 또 작업을 해야 한다. 이때 3번 리소스를 요청할 때, 가지고 있던 2번 리소스를 반환을 한 상태에서 3번 리소스를 요청한다. 만약 3번 리소스를 획득하지 못하게 되면, 다른 프로세스/스레드에게 리소스 2번을 사용하도록 하고, 대기를 한다.  

데드락 방지 #3 NO Preemption

-> 추가적인 리소스를 기다려야 한다면 이미 획득한 리소스를 다른 프로세스가 선점 가능하도록 한다.

데드락 방지 #4 Circular Wait

-> 모든 리소스에 순서 체계를 부여해서 오름차순으로 리소스를 요청.

4번 리소스를 가지는 프로세스/스레드는 Circular Wait 상태에서는 1번 리소스를 위해 대기하고 있는 상태이다.

그러나 , 리소스를 순서 체계대로 오름차순으로 리소스를 요청할 수 있게 된다면,

4번 리소스를 가진 프로세스/스레드는 1번 리소스를 요청하지 못하게 되어, Circular Wait가 깨지게 된다. 

(만약, 4,1번 리소스를 획득하게 된다면, 1번 리소스를 먼저 획득한 뒤에, 4번 리소스를 획득하여야 한다.)

데드락 방지#1~#4 중, #4 방법이 가장 많이 사용된다고 한다. 

 

2. 데드락 회피(deadlock avoidance)

시스템 레벨이 아닌 실행 환경에서 추가적인 정보를 활용해서 데드락이 발생할 것 같은 상황을 회피하는 것.

(추가적인 정보 : OS가 가지는 정보이며, 현재 사용가능한 리소스들, 이미 할당된 리소스, 미래에 요청,반환될 리소스들에 대한 정보)

EX) Banker Algorith

 

3. 데드락 감지와 복구

데드락을 허용하고, 데드락이 발생하면 복구하는 전략

방법1. 프로세스를 종료(조금, 극단적이다.)

방법2. 리소스의 일시적인 선점을 허용한다.

 

4. 데드락 무시

아.몰.랑

-> OS에서는 아무것도 해주지 않고, 개발자에게 해결을 맡김.

 

프로그래밍 Level에서의 deadlock with JAVA

 

해결책1 : Thread2의 lock 취득 순서를 lock2 -> lock1에서 lock1 -> lock2로 바꿔 준다. 그러면 circular wait가 일어나지 않게 되어, deadlock도 일어나지 않는다.

해결책2 : thread1의 lock2와 thread2의 lock1은 모두 중첩문 안에서 실행이 되고 있다. 굳이 중첩문 안에서 실행을 시킬 필요가 없다면, 중첩문 밖으로 빼서 실행을 시킨다. 이렇게 되면, hold and wait가 생기지 않기에 deadlock도 발생하지 않음.

해결책3:mutual exclusive를 너무 남발하지는 않았는지 생각하고, 굳이 mutual exclusive로 하지 않아도 된다면 고쳐준다. 

-> 결국엔, deadlock prevention 기법으로 프로그래밍 레벨에서도 해결한다.