데드락(DeadLock)

데드락(DeadLock)

교착 상태라고도 한다. 둘 이상의 프로세스나 스레드가 서로가 서로에게 필요한 다음 자원을 가지고 있어 다음 자원을 얻지 못하여 명령을 실행하지 못하는 상태가 영원히 지속되는 상태를 말한다.

조건

데드락이 발생하기 위해선 4가지 조건이 필요하며, 하나라도 성립 되지 않을 경우 데드락 문제를 해결할 수 있다.

1. 상호 배제 (Mutual exclusion)

   자원은 한번에 한 프로세스만 사용 가능

2. 점유 대기(Hold and Wait)

   최소 하나 이상의 자원을 점유하고 있으면서, 다음 자원을 기다리는 프로세스가 존재

3. 비 선점(No preemption)

   다른 프로세스가 점유한 자원은 강제로 빼앗을 수 없음

4. 순환 대기(Circular wait)

   프로세스 집합에서 순환 형태로 자원을 기다림

데드락 문제를 해결하기 위해 애초에 데드락이 발생하지 않도록 예방하는 방법과, 데드락 상태를 피해가는 방법, 발생 시 회복하는 방법 등이 있다.

예방

교착 상태가 발생하는 조건 중 하나를 제거한다. 장비 낭비가 심하다.

1. 상호 배제

   여러 프로세스가 공유 자원 사용할 수 있도록 허용한다.

2. 점유 대기

   프로세스 실행 전 모든 자원을 할당한다.

3. 비 선점

   다른 프로세스가 점유한 자원을 빼앗을 수 있다.

4. 순환 대기

   자원에 고유 번호를 할당하고, 각 프로세스가 현재 점유한 자원의 고유 번호 앞이나 뒤 한쪽 방향으로만 자원을 요구하도록 한다.

회피

은행원 알고리즘

• 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
• 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있는지 사전에 검사하여 교착 상태 회피
• 안전 상태면 자원을 할당하고 아닌 다른 프로세스가 자원을 해지할 때까지 대기한다.

탐지

• 자원 할당 그래프를 통해 교착 상태를 탐지할 수도 있다.

• 자원 요청 시, 탐지 알고리즘을 실행시켜 그에 대한 오버헤드 발생

회복

교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제하여 데드락을 회복한다.

1. 프로세스 종료

   교착 상태의 프로세스를 모두 중지 시키거나, 교착 상태가 해소될 때까지 프로세스를 하나씩 중지한다.

2. 자원 선점

   교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. (해당 프로세스는 일시 정지)

   우선 순위가 낮은 프로세스나 수행 횟수가 적은 프로세스의 자원 위주로 선점