Dead Lock

Deadlock이란?

 

 

교착 상태(膠着狀態) 또는 데드락은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태이다. 예를 들어 하나의 사다리가 있고, 두 명의 사람이 각각 사다리의 위쪽과 아래쪽에 있다고 가정한다. 이때 아래에 있는 사람은 위로 올라 가려고 하고, 위에 있는 사람은 아래로 내려오려고 한다면, 두 사람은 서로 상대방이 사다리에서 비켜줄 때까지 하염없이 기다리고 있을 것이고 결과적으로 아무도 사다리를 내려오거나 올라가지 못하게 되듯이, 전산학에서 교착 상태란 다중 프로그래밍 환경에서 흔히 발생할 수 있는 문제이다. 이 문제를 해결하는 일반적인 방법은 아직 없는 상태이다. (위키백과)

 

Deadlock의 발생 이유와 조건

 

Deadlock이 발생하려면 네 가지 조건이 동시에 충족되어야 한다:

 

1. 상호 배제 (Mutual Exclusion): 하나의 자원은 한 번에 하나의 프로세스만이 사용할 수 있어야 한다.
2. 점유 대기 (Hold and Wait): 프로세스는 최소한 하나의 자원을 보유한 채로 다른 자원을 기다려야 한다.
3. 비선점 (No Preemption): 다른 프로세스가 이미 보유한 자원을 강제로 빼앗을 수 없어야 한다.
4. 순환 대기 (Circular Wait): 프로세스 간에 자원 요청의 순환 사이클이 형성되어야 한다.

이러한 네 가지 조건이 동시에 충족되면 시스템은 deadlock에 빠질 수 있다.

 

Deadlock이 발생하는 예시

 

 

가장 간단한 예로, 두 프로세스 P1와 P2가 서로가 가진 자원을 요청하고 대기하는 상황이 있을 수 있다. P1이 자원 R1를 가지고 있고 R2를 기다리며, P2는 자원 R2를 가지고 있고 R1를 기다릴 때, 이들은 서로가 가진 자원을 점유 대기하면서 deadlock에 빠질 수 있다.

deadlock을 해결하기 위한 방법들

 

1. 예방 (Prevention)

 

 

Deadlock이 발생하는 조건 중 하나 이상을 막는 방법. 예를 들어, 상호 배제, 점유 대기, 비선점, 순환 대기 중 하나라도 없으면 deadlock이 발생하지 않는다. 

• 상호 배제(Mutual Exclusion) 조건 제거 시: 한 번에 여러 프로세스가 한 자원을 사용할 수 있게 한다 ⇒ 동기화 관련 문제가 발생할 수 있다.
• 점유 대기(Hold and Wait) 조건 제거 시: All or Nothing 방식으로, 프로세스가 자원을 점유하거나 점유하지 않거나의 방식이다. ⇒ 자원의 효율성이 급격하게 나빠질 수 있다. (기아 상태)
• 비선점(Non-Preemption) 조건 제거 시: 어떤 자원을 점유한 상태에서 우선순위가 낮으면 점유한 자원을 빼앗기게 된다. 어떤 자원을 점유한 상태에서 다른 자원 요청 시 거부되면, 자원을 반납하고 대기한다. (자원 낭비 발생)
• 순환 대기(Circuit Wait) 조건 제거 시: 자원에 고유 번호를 매기고 번호 순서대로 특정 방향으로만 자원을 요구하도록 함.(자원 낭비 발생)

하지만 교착 상태는 필요악이다. 필요 조건 중 하나를 거부하고 예방한다면, 자원을 효율적으로 사용할 수 없다는 치명적인 단점이 존재하기 때문이다.

 

2. 회피 (Avoidance)

 

deadlock가 발생하기 전 deadlock을 예측하고 회피하는 방법이다. 회피할 수 있는 조건을 달성하기 어렵고 자원을 요청할 때마다 회피 알고리즘(ex. 은행원 알고리즘)을 사용하면 오버헤드가 크기 때문에 현실성 없는 방법이다.

⇒ 이런 이유들로, 교착 상태가 자주 발생하는 시스템에서는 일반적으로 예방이나 회피보다는 데드락이 발생했을 때 탐지하고 회복하는 방법을 채택한다.

 

3. 탐지 및 회복 (Detection and Recovery)

 

Deadlock이 발생하면 이를 탐지하여 복구하는 방법이다. 탐지 알고리즘을 통해 deadlock이 발생했음을 감지하고, 복구 알고리즘을 통해 deadlock을 해결한다. 다음은 탐지 알고리즘의 종류인 대기 그래프에 대한 설명이다.

 

 

대기 그래프 (https://blog.kakaocdn.net/dn/cSRAEJ/btq1jliEVVv/btBjPNxU57eztN4ylZ6Gd1/img.png)

 

각 자원 유형 마다 인스턴스가 하나가 있는 경우 자원 할당 그래프를 변형한 대기 그래프(wait-for graph)를 사용하여 교착 상태를 탐지한다. (a) 자원할당 그래프, (b) 대기 그래프에서 Pi→Pj는 프로세스 Pi가 Pj프로세스가 보유하고 있는 자원을 기다리고 있음을 나타낸다. 주기적으로 대기 그래프에 주기가 있는지 탐지 알고리즘을 호출하여 deadlock을 탐지한다.

 

탐지 알고리즘 호출 상황 및 주기

 

탐지 알고리즘은 오버헤드가 있기 때문에 얼마나 자주 deadlock이 발생하는지 얼마나 많은 프로세스가 교착 상태에 연루되어 있는지에 따라 호출 빈도를 조절해야 한다.

• 자원을 요청했는데 즉시 할당되지 못하는 시점에 호출
• 주기적으로 일정 시간마다 호출
• cpu 이용률이 특정 값 이하로 떨어지는 시점에 호출

•  

회복 - 교착 상태 복구 (Recovery)

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

복구 방식에는 크게 두 가지가 있다.

1. 프로세스 종료

deadlock에 있는 프로세스를 종료하는 방식이다. 프로세스 종료에는 다시 두가지 방법이 있다.

• 교착상태 프로세스를 모두 중지
• 한 프로세스씩 중지: 한 프로세스가 중지될 때 마다 교착상태 탐지하여 확인
• 부분 종료 방식: 어느 프로세스를 중지시킬지 결정(프로세스 스케줄링과 유사), 최소비용으로 프로세스들을 중지시키는 방법을 찾아야 함

2. 자원 선점

교착 상태에 있는 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하여 해당 프로세스를 일시 정지시키는 방법이다. 자원 선점에 있어서 다음 사항들을 고려해야 한다.

1. 희생자 선택 (selection of a victim)
   • 최소의 피해를 줄 수 있는 프로세스를 선택
2. 롤백(rollback)
   • 선점 된 프로세스를 문제 없던 이전 상태로 롤백
   • 보통 가장 안전한 방법은 프로세스를 중지시키고 재시작
3. 기아 상태(starvation)
   • 한 프로세스가 계속 선점되어 기아상태가 되는 것을 방지
   • 다른 방법은 우선 순위를 사용하여 선점 될때마다 프로세스 우선순위를 높임

4. 무시 (Ignore)

 

 일부 운영체제(Window, Unix)에서는 deadlock을 무시하고, 대신 주기적으로 시스템을 재시작하여 deadlock을 회피하는 방법을 사용하기도 한다.

 

참고 사이트

https://dockdocklife.tistory.com/entry/Dead-lock%EA%B3%BC-%ED%95%B4%EA%B2%B0-%EB%B0%A9%EB%B2%95

Dead-lock과 해결 방법

https://yoongrammer.tistory.com/67#%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C_%EC%98%88%EB%B0%A9_(Deadlock_Prevention)

교착상태(Dead Lock) 해결 방법