Dead Lock

멀티프로그래밍에서 한정된 자원을 사용하려고 할 때 경쟁(Race Condition)이 발생한다. 프로세스 간 서로의 자원을 차지하기 위해 대기 상태로 들어감으로써 이러한 상황을 Dead Lock 상황이라 볼 수 있다.

<쉽게 배우는 운영체제> 책을 참고하였습니다.

---

Dead Lock

• 교착상태라고도 하며, 두 개 이상의 스레드가 자원을 얻지 못해 서로 상대방의 작업이 끝나기만을 기다리며 더 이상 작업을 진행하지 못하는 상태를 말한다.
• 서로 다른 프로세스가 공유할 수 없는 자원을 사용할 때 발생

 

Dead Lock 발생조건

Dead Lock은 아래 4가지 조건을 모두 만족하면 발생한다. 이 중 하나라도 충족하지 않으면 Dead Lock은 발생하지 않는다.

 

1. Mutual Exclusion (상호 배제)

 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 한다. 배타적 자원은 Critical Section으로 보호되기 때문에 다른 프로세스와 동시에 사용할 수 없다.

2. Hold and Wait (점유 대기)

프로세스가 특정 자원을 할당받은 상태에서 다른 자원을 기다리는 상태.

3. No Preemption (비선점)

한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 한다.

4. Circular wait (순환 대기)

Hold and Wait를 하는 프로세스 간의 관계가 원을 이루어 자원을 양보하지 않는 경우 발생한다.

 

Dead Lock 해결법

1. Dead Lock 예방하기

위 4가지 조건(상호 배제, 점유 대기, 비선점, 순환 대기)을 모두 만족하면 Dead Lock이 발생한다. 따라서 4가지 조건 중 하나만이라도 발생하지 않도록 하여 Dead Lock을 예방하자.

• Mutual Exclusion을 예방 : 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 하자. → 자원은 본질적으로 공유가 불가능하다. 여러 스레드에 의해 동시에 자원이 공유될 경우 데이터는 온전하지 못하다. →사실상 불가능
• Hold and Wait를 예방 : 프로세스가 자원을 점유한 상태에서 다른 자원을 가리키지 못하게 하자. All or Nothing 방식(전부 다 갖거나, 전부 다 버리거나)을 말하는데 자원의 활용성이 떨어지고, 일괄 작업 방식으로 처리되어 시스템 효율도 떨어진다. → 가능하나 실용적이지 않다.
• No Preemption 예방 : 모든 자원을 언제든 뺏을 수 있게 하자. lock()을 통해 Critical Section 영역을 보호하면, 자원을 뺏어올 수 없고, 뺏어온다 해도 Mutual Exclusion을 보장할 수 없다.  → 불가능
  • global lock
  • try lock
  • live lock
• Circular Wait 예방 : Hold and Wait를 하는 프로세스들이 원형을 이루지 못하도록 하자. 한쪽 방향으로만 자원을 요구하도록 하여 예방할 수 있다. 하지만 한 방향 요청은 자연스럽지 못하고 방향의 우선순위를 결정하기도 어렵다.

결론 : 예방하는 방식은 프로세스의 작업 방식을 제한하기 때문에 효율적이지 못하다.

 

2. Dead Lock 회피하기

Dead Lock이 발생하지 않도록 하기 위해 사전에 이용 가능한 자원의 개수와 이미 할당된 자원들, 앞으로 요구할 최대 자원을 파악하고 이 정보를 토대로 프로세스에 할당되는 자원의 수를 조절하여 Dead Lock 상황을 피한다. 자원의 수에 따라 안정 상태(할당된 자원이 적다.)인지 불안정 상태(할당된 자원이 많다)인지 파악해서 할당하면 Dead Lock 발생 가능성을 낮출 수는 있지만 완벽히 보장할 수는 없다.

 

Banker Algorithm

• 회피 방법 중 하나로 다익스트라가 제안한 알고리즘으로 프로세스가 자원을 요청할 때마다 수행.
• 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 시스템이 안정 상태로 남아있을 수 있는지를 사전에 검사하여 Dead Lock을 회피한다.
• 각각의 프로세스가 자원을 최대로 요청한다면 어느 정도 인지(MAX), 시스템 내에서 사용할 수 있는 자원은 어느 정도 인지(Available), 현재 각 프로세스에 할당된 자원은 어느 정도인지(Allcated)를 바탕으로 자원을 할당할지를 결정한다.

회피의 문제점

• 각 프로세스는 자신이 사용할 모든 자원에 대해 미리 선언해야 한다. → 어떠한 자원이 필요한지 알 수 없을뿐더러, 정확하지 않을 경우 Dead Lock 발생 가능성이 있다.
• 시스템 전체의 자원 수가 고정적이어야 한다. → 자원의 개수는 유동적이기에 고정할 수 없다.
• 자원이 낭비될 수 있다. → 최악의 상황에 고려하다 보니 자원이 있어도 할당하지 않는 경우가 있다. 이것은 자원의 낭비로 이어진다.

 

3. Dead Lock 탐지 및 회복

운영체제가 프로세스의 작업을 관찰하면서 Dead Lock 발생 여부를 계속 확인한다. Dead Lock이 발생된다면 Check point , Roll back을 통해 회복단계를 밟는다. 타임아웃을 이용하거나 자원 할당 그래프를 통해(사이클이 존재하는 경우) Dead Lock을 감지한다.

check point : 작업 도중 문제 발생 시에 되돌아올 수 있도록, 현재 시스템의 상태를 하드디스크에 저장한다.

roll back : 과거 check point로 되돌아가는 행위

 

문제점

• 엉뚱한 프로세스가 강제 종료 될 수 있음
• 모든 시스템에 적용할 수 없음 
• →  타임 아웃 방법으로는 한계가 있지만 많이 쓰인다.

회복

• Dead Lock을 일으킨 모든 프로세스를 동시에 종료
• Dead Lock이 해결될 때까지 하나씩 프로세스를 종료
• Dead Lock 상태인 프로세스의 자원을 선점해서 , Dead Lock이 해결될 때까지 그 자원을 다른 자원에게 위임
  • 우선순위가 낮은 프로세스, 수행 횟수가 적은 프로세스의 자원을 선점하자

 

4. Dead Lock 무시

Dead Lock이 일어나지 않는다고 가정하고 조치를 취하지 않는다.

Dead Lock은 매우 드물게 발생하기 때문에 Dead Lock을 조치하려는 것 자체가 큰 Overhead일 수 있다. 따라서 발생한다면, 프로세스 강제 종료를 함으로써 조치를 취한다.

 

---

참고하면 좋은 사이트

[운영체제(OS)] 7. 데드락(Deadlocks)

 

Deadlock의 발생 조건과 해결법