데드락 (DeadLock, 교착상태)
2개 이상의 프로세스 or 스레드가 자원을 할당받지 못해 다음 단계로 넘어가지 못하는 상태
즉, 무한정 다음 자원을 기다리고만 있다.
상황
- P1은 R1을 가지고 있다. P2는 R2를 가지고 있다.
- P1은 R2가 필요하다. P2는 R1이 필요하다.
-> P1, P2가 원하는 자원이 서로에게 할당되어 있어 P1, P2는 무한정 wait 상태에 빠져버림 (데드락 발생!!!)
주로 발생하는 사례
멀티 프로그래밍 환경에서 한정된 자원을 얻기 위해 서로 경쟁할 때
P1 프로세스가 요청한 자원을 사용할 수 없는 상황임.
p1은 wait 상태로 변경됨.
p1이 계속 wait 상태에서 못 벗어남
-> 데드락 발생!
데드락 발생 조건
1 and 2 and 3 and 4
1. 상호 배제
1개 자원은 1개 프로세스만 사용 가능
2. 점유 대기
최소 1개 자원을 가지고 있으며 다른 자원(다른 프로세스가 가지고 있는 중)을 대기하는 프로세스가 있어야 함.
3. 비선점
프로세스가 할당된 자원은 다른 프로세스가 선점해서 가져갈 수 없음
4. 순환 대기
프로세스 집합에서 순환 형태로 자원을 대기하고 있어야 함
데드락 처리
- 예방
데드락 발생 조건 중 1개를 제거하면서 해결 -> 자원 낭비 심함
- 상호 배제 부정: 1개 자원을 여러 프로세스가 사용
- 점유 대기 부정: 프로세스 실행 전 필요한 자원을 미리 모두 할당해버림
- 비선점 부정: 선점 허용, 다른 프로세스가 내가 가진 자원을 요구하면 준다.
- 순환 대기 부정: 자원에 고유번호 할당 후 순서대로 자원 요구
- 회피: 데드락 발생하면 피해나가는 방법
- 은행원 알고리즘 (Banker's Algorithm) -> 은행에서 모든 고객의 요구를 충족시키기 위해 현금을 할당함.
프로세스가 자원을 요구한다면 자원을 할당한 후에도 안정된 상태로 남는지 사전에 검사 후 자원할당 해줌.
안정된 상태로 못남는다면 다른 프로세스들이 가지고 있는 자원이 해지될때까지 대기함.
- 탐지
데드락이 되도록 허용한 다음 회복시키는 방법
- 자원 할당 그래프를 통해 데드락 상태를 탐지함
- 자원 요청 시 탐지 알고리즘을 실행시켜 오버헤드 발생함
- 회복
데드락 발생시킨 프로세스를 종료하거나 할당된 자원을 해제시키는 방법 (프로세스 죽이거나 자원 뺏음)
- 프로세스 종료 방법
- 데드락이 해결될 때가지 하나씩 프로세스 종료시킴 - 자원 선점 방법
- 데드락 상태의 프로세스가 점유하고 있는 자원을 다른 프로세스에게 할당 (자원을 뺏긴 프로세스는 일시정지 됨)- 우선 순위 낮은 프로세스나 수행 횟수 적은 프로세스 위주로 프로세스 자원 선점
