데드락(Deadlock)이란
- 둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황을 일컫습니다.
- 위 상황은 두 프로세스 모두 Resource 1, 2가 필요한 상황입니다. 하지만 서로 자원을 각각 하나씩 점유하고 있고, 상대방이 자원을 해제할때까지 기다립니다. 결국 무한정 대기 상태에 빠지게 됩니다.
데드락 (Dead lock)의 발생 조건
- 데드락의 발생 조건은 4가지가 있습니다. 이 4가지 조건을 모두 만족시켜야 데드락이 발생할 수 있습니다.
상호배제(Mutual Exclusion)
- 자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.
점유 대기 (Hold and wait)
- 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
비선점 (No preemption)
- 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다.
순환대기(Circular Wait)
- 프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.
데드락 (Dead lock) 예방
예방법
- 데드락 예방은 위 발생조건 4가지 중 하나를 부정하므로써 데드락을 예방하는 방법입니다.
- 단, 자원의 낭비가 심합니다.
자원의 상호 배제 조건 방지
- 한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 합니다.
그러나 추후 동기화 관련 문제가 발생할 수 있습니다.
점유 대기 조건 방지
- 프로세스가 실행되기 전 필요한 모든 자원을 할당합니다.
비선점 (No preemption) 방지
- 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 합니다.
순환 대기 조건 방지
- 자원을 순환 형태로 대기하지 않도록 일정한 한 쪽 방향으로만 자원을 요구할 수 있도록 합니다.
데드락 회피
은행원 알고리즘
- 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는데서 유래함
- 프로세스가 자원을 요구할 때, 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피
- 안정 상태면 자원 할당, 아니면 다른 프로세스들이 자원 해지까지 대기
안정상태(safe state)? 시스템의 프로세스들이 요청하는 모든 자원을, 데드락을 발생시키지 않으면서도 차례로 모두에게 할당해 줄 수 있다면 안정 상태(safe state)에 있다고 말합니다.
데드락 탐지 & 회복
- 데드락 상태가 되도록 허용한 뒤, 그것을 탐지하여 회복시키는 방법입니다.
탐지
- Allocation, Request, Available 등으로 시스템에 데드락이 발생했는지 여부를 탐색합니다. 즉, 은행원 알고리즘에서 했던 방식과 유사하게 현재 시스템의 자원 할당 상태를 가지고 파악합니다.
- 이 외에도 자원 할당 그래프를 통해 탐지하는 방법도 있습니다.
회복
- 프로세스를 중단하는 방법과, 자원을 선점해주는 방식으로 회복합니다.
- 프로세스를 모두 중단하거나, 하나씩 중단하여 데드락을 회복합니다.
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당합니다.
- 우선 순위가 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점합니다.
ref.
