데드락 - (1)

데드락

데드락

둘 이상의 프로세스들이 서로가 점유한 자원을 기다리면서 무한 대기에 빠진 상태

데드락 발생 4가지 조건

Mutual Exclusion 상호 배제 : 한 자원은 한번에 한 프로세스만 사용 가능
No Preemption 비선점 : 프로세스는 자원을 강제로 빼앗을수없다
Hold and wait 점유대기 : 자원을 점유하면서 다른 자원을 기다림
Circular Wait 순환대기 : 자원을 기다리는 프로세스 사이에 사이클 존재

데드락 처리 방법

예방, 회피, 탐지, 복구, 무시

1. Prevention

조건 4가지 중 하나 제거

상호 배제 : 보통 제거 불가능
점유대기 : 자원 요청할 때 점유하고있는 자원 가지고있으면 안된다 --> 프로세스 시작시 자원 모두 할당 / 자원 요청시 점유자원 반환후 요청
비선점 : 자원 기다려야하는 경우 점유하고있는 자원 선점됨
순환대기 : 자원에 할당순서를 정해서 a자원 얻어야 b자원 얻을수있도록 순서대로 자원 할당

2. Avoidance

자원에 대한 부가정보를 이용해서 데드락에 안전한 경우에만 할당, Safe State에만 자원 할당

Resource Allocation Graph Algorithm : cycle 여부 조사해서 없으면 할당, 사이클 여부 조사시 O(n^2) 시간 걸림
Banker's Algorithm(은행원 알고리즘) : 자원이 멀티 인스턴스인 경우, 다익스트라가 제안, 프로세스들이 평생 최대로 쓸 자원을 미리 알고있음. 자원을 모두 할당할수있는 경우에만 자원 할당해줌, 항상 safe state 유지

3. Detection and Recovery

현재가 데드락 아닌지 확인, 데드락 탐지로 데드락 확인했으면 회복

은행원 알고리즘과 유사한 방식 사용 or 자원 할당 그래프를 통해 탐지
모든 프로세스 중단
프로세스 하나씩 중단
자원 선점

4. Ignorance

데드락이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

데드락은 드물게 발생하므로 데드락에 대한 조치 자체가 더 큰 오버헤드일수있음
유닉스, 윈도우 등 대부분의 범용 OS가 채택