교착 상태(Dead Lock)에 대해

교착 상태(Dead Lock)

교착 상태의 배경: 다중 프로그래밍 시대가 오다!

옛날 컴퓨터는 작업을 할 때 하나만 할 수 있었다. 

( 예로 음악을 들으면서 웹서핑을 하고 싶어도 음악만 듣거나 웹서핑만 하거나 둘 중 하나만 가능.)

그런데 컴퓨터가 발전하면서 여러 작업을 동시에 하고 싶어졌다. 

그치만 CPU가 하나라 동시에 처리하지 못하는 문제가 있었고, 이 문제를 해결하기 위해 생각해 본 결과 

공학자들은 컴퓨터는 빠르니까 여러 가지 일을 빨리 반복하면 사람의 지각 능력으로는 동시에

하는 것 처럼 느껴지지 않을까? 라는 생각을 했고, 그래서 생긴 것이 멀티프로세싱과 멀티쓰레딩이다.

교착 상태는 바로 이런 다중프로그래밍 환경에서 여러 프로세스(혹은 쓰레드)가 간섭하면서 생기는 문제를 말한다.

교착상태(Dead Lock)란?

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

이미지 출처: NAVER

교착 상태의 발생 조건.

아래 4가지 조건을 동시에 만족하면 교착 상태가 발생된다.

1. Mutual Exclusion(뮤텍스 - 자원에 대한 동시접근 불가)

한 번에 여러 프로세스(혹은 쓰레드)가 한 자원에 접근하지 못하도록 막는다.

즉, A가 프로세스 'X'를 사용 중이면, B는 프로세스 'X'를 사용하지 못한다.

2. Hold and Wait(점유하고 기다리기)

자원을 가지고 있는 상태에서 다른 프로세스가 쓰는 자원(변수 같은 것)을 반납하길 기다리는 상태다.

즉, A가 사용하는 프로세스 'X'를 반납하길 기다리는 B의 상태를 말함.

3. No Preemption(자원 뺏어오지 못함)

다른 프로세스가 이미 점유한 자원을 강제로 뺏어오지 못한다.

(Preemption은 우선한다는 뜻의 선점이다.)

4. Circular Wait(순환 형태로 대기함)

프로세스가 뭔가를 하려고 다른 프로세스를 기다리고 있고, 그 프로세스는

또 다른걸 기다리고, 이러한 상태로 이어질 때 마지막에 처음 프로세스가 나오는 모순적인 상황.

즉, 'A' 프로세스가 다음 작업을 진행하기 위해서는 'A' 프로세스의 작업이 끝나야만 진행 할 수 있다.

교착 상태의 해결 방법.

예방(Prevention) 기법

이 기법은 대부분 자원을 낭비하는 경향이 크다.

회피(Avoidance) 기법

원칙적인 발생 가능성은 두고, 발생을 막는 알고리즘을 적용하는 방법. 

대표적으로 은행가 알고리즘(Banker's Algorithm)이 있는데,

이 것은 프로세스가 자원을 요구하는 시점에 자원을 할당해도 안전하지를 검사하여 교착 상태를 방지하는 방법이다.

탐지(Detection) 기법

교착상태가 발생하면 해결하는 방법.

교착 상태의 탐지를 위해 현 시스템의 상황을 그래프로 많이 표현하는데, 

이 것을 자원 할당 그래프(Resource Allocation Graph, RAG)라 한다.

RAG에 대한 그래프 제거(Graph Reduction)법으로 교착 상태를 탐지한다.

회복(Recovery) 기법

교착 상태로부터 벗어나기 위한 방법이다. 교착 상태에 포함되어 있는 한 개 이상의 프로세스를

강제로 종료시켜 이들로부터 반납되는 자원들을 나머지 프로세스들에게 줌으로써 해결하거나,

아니면 교착 상태를 벗어나기 위해 필요한 추가의 자원을 어디서든 갖고와 할당해 줌으로써

해결한다. 프로세스 종료 방식과 자원의 선점에 의한 방식으로 나뉜다.

교착 상태 무시.

무시해도 괜찮은 확률로 발생된다고 판단되면 무시한다.

왜냐하면 교착 상태는 해결하려면 성능상 손해를 봐야하기에

안정성과 성능을 고려해야하기 때문이다.

참고 문서:

http://webie.tistory.com/99