데드락(DeadLock)이란?
프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태로, ‘교착 상태’라고도 하며 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생하게 된다.
데드락이 발생하는 경우
- 멀티 프로그래밍 환경에서 한정된 자원을 사용하려고 서로 경쟁하는 상황이 발생 할 수 있다.
- 어떤 프로세스가 자원을 요청 했을 때 그 시각에 그 자원을 사용할 수 없는 상황이 발생할 수 있고 그 때는 프로세스가 대기 상태로 들어 간다.
- 대기 상태로 들어간 프로세스들이 실행 상태로 변경 될 수 없을 때 이러한 상황을 교착 상태라 한다.
데드락 발생 조건
4가지 모두 성립해야 데드락 발생 (하나라도 성립하지 않으면 데드락 문제 해결 가능)
-
상호 배제(Mutual exclusion)
자원은 한번에 한 프로세스만 사용할 수 있음 -
점유 대기(Hold and wait)
최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함 -
비선점(No preemption)
다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음 -
순환 대기(Circular wait)
프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 함
데드락 처리
-
교착 상태 예방 및 회피
교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법 -
교착 상태 탐지 및 회복
교착 상태가 되도록 허용한 다음에 회복시키는 방법 -
교착 상태 무시
대부분의 시스템은 교착 상태가 잘 발생하지 않으며, 교착 상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.
데드락 예방 & 회피
-
예방(prevention)
교착 상태 발생 조건 중 하나를 제거하면서 해결한다 (자원 낭비 엄청 심함)상호배제 부정 : 여러 프로세스가 공유 자원 사용
점유대기 부정 : 프로세스 실행전 모든 자원을 할당
비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구 -
회피(avoidance)
교착 상태 발생 시 피해나가는 방법
은행원 알고리즘(Banker's Algorithm)
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
데드락 탐지(Detection)
자원 할당 그래프를 통해 교착 상태를 탐지할 수 있다.
-
프로세스 Pi로부터 자원 Rj로의 방향 간선은 Pi ->Rj로 표현하며 이것은 프로세스 Pi가 자원 꺼을 요청하는 것으로 현재 이 자원을 기다리는 상태이다.
-
자원 Rj로부터 프로세스 Pi로의 방향 간선은 Rj->Pi로 표현하며 이것은 자원 꺼가 프로세스 Pi에 할당된 것을 의미 한다.
-
자원을 요청할 때마다 탐지 알고리즘을 실행하면 오버헤드가 발생한다.
데드락 회복(Recovery)
교착 상태 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복시키는 방법
-
프로세스 종료 방법
교착 상태의 프로세스를 모두 중지
교착 상태가 제거될 때까지 하나씩 프로세스 중지 -
자원 선점 방법
교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당 (해당 프로세스 일시정지 시킴)
우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
출처
