데드락(교착 상태)은 프로세스가 자원을 얻지 못해서 다음 처리를 하지 못해 무한정 대기하는 상태입니다.
시스템에서 교착상태는 프로세스가 요구하는 자원이 엉켜서 더 이상 작업을 더 실행할 수 없는 상태를 의미합니다.
초기 일괄 처리 시스템에서는 교착상태가 발생하지 않았지만, 제한된 자원의 이용률을 높이고
시스템 효율성을 증가시키기 위해 사용하는 병렬처리 기술과 자원 공유때문에 발생합니다.
주로 비공유 자원에서 발생합니다.
데드락 발생조건은 4가지 입니다. 이 4가지 모두 성립해야 데드락이 발생하며,
하나라도 성립하지 않으면 데드락은 해결 가능합니다.
- 상호배제 (Mutual exclusion) : 자원은 한번에 한 프로세스만 사용 가능합니다.
- 점유대기 (Hold and Wait) : 최소한 하나의 자원을 점유하며, 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야합니다.
- 비선점 (No Preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날때까지 강제로 뺏을 수 없습니다.
- 순환대기 (Circular wait) : 프로세스의 집합에서 순환 형태로 자원을 대기하고 있어야 합니다.
데드락이 발생했을 경우 해결방법은 다음과 같습니다.
- 예방 (prevention) : 교착 상태 발생 조건 중 하나를 제거하면서 해결하는 방법으로 자원낭비가 심합니다.
- 상호배제 부정 : 여러 프로세스가 공유 자원 사용
- 점유대기 부정 : 프로세스 실행전 모든 자원을 할당
- 비선점 부정 : 자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
- 순환대기 부정 : 자원에 고유번호 할당 후 순서대로 자원 요구 따라서 프로세스의 속도를 떨어뜨리고 자원의 접근을 불필요하게 거부하여 비효율적입니다. - 회피(avoidance) : 교착 상태 발생 시 피해나가는 방법입니다. 대표적으로 은행원 알고리즘이 있습니다.
- 탐지(Detection) : 자원 할당 그래프를 통해서 교착상태를 탐지하고, 자원요청시 탐지 알고리즘을 실행시켜 오버헤드를 발생합니다.
- 회복(Recovery) : 교착상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제시켜 회복하는 방법입니다.
프로세스 종료 방법으로는 교착상태의 프로세스를 모두 중지하거나, 교착상태가 제거될때까지 하나씩 프로세스를 중지하는 방법이 있습니다.
자원선점 방법으로는 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 해당 프로세스는 정지시키고 다른 프로세스에게 할당하거나 우선순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위 주로 프로세스 자원 선점을 하는 방법이 있습니다.
<추가 - 교착상태 해결방법 점유대기와 비선점>
- 점유대기
-
- 프로세스가 작업을 시작하기 전에 필요한 모든 자원을 요청하여 할당받도록 하는 것입니다.
-
- 프로세스가 전혀 자원을 갖지 않은 상태에서만 자원 요청을 허용하고, 프로세스가 자원을 추가 요청하려면
가지고 있는 자원을 모두 해제해야만 요청을 승인합니다.
예를 들어 DVD 드라이버에서 디스크로 파일 하나를 복사해서 정렬 후 프린터로 출력한다고 했을 때,
1의 방법은 제일 나중에 필요한 프린터도 프로세스 초기에 점유해서 다른 프로세스가 프린터를 사용하지 못하게 하는 것입니다.
2의 경우, DVD 드라이버에서 디스크로 파일 하나를 복사한 후 DVD 드라이버와 디스크 파일을 모두 해제하고,
다시 디스크 파일과 프린터를 점유한 후 프린트를 한 후 디스크 파일과 프린터를 해제합니다.
점유 대기의 단점은 자원의 효율적인 사용이 안되고, 특정 프로세스가 자주사용하는 자원이 다른 프로세스에 의해 장기 점유되면 기아상태가 발생합니다.
- 프로세스가 전혀 자원을 갖지 않은 상태에서만 자원 요청을 허용하고, 프로세스가 자원을 추가 요청하려면
가지고 있는 자원을 모두 해제해야만 요청을 승인합니다.
예를 들어 DVD 드라이버에서 디스크로 파일 하나를 복사해서 정렬 후 프린터로 출력한다고 했을 때,
1의 방법은 제일 나중에 필요한 프린터도 프로세스 초기에 점유해서 다른 프로세스가 프린터를 사용하지 못하게 하는 것입니다.
2의 경우, DVD 드라이버에서 디스크로 파일 하나를 복사한 후 DVD 드라이버와 디스크 파일을 모두 해제하고,
다시 디스크 파일과 프린터를 점유한 후 프린트를 한 후 디스크 파일과 프린터를 해제합니다.
- 비선점
-
- 어떤 프로세스가 자원을 가지고 실행 중에 다른 자원을 요청했는데 그 자원을 점유할 수 없다면 지금까지 가지고 있던 자원을 모두 해제하도록 합니다. 그 후, 프로세스는 원래 자원과 새로 원하는 자원을 함께 요청해야합니다.
-
- 한 프로세스에서 다른 프로세스가 점유한 자원을 원하면, 운영체제는 다른 프로세스가 점유한 자원을 강제적으로 반납시키고 그것을 원하는 프로세스에게 할당할 수 있다. 이 방법은 프로세스들이 서로 다른 우선순위를 갖고 있을 때 우선순위를 기준으로 선점하여 교착상태를 예방할 수 있다. 비선점의 단점은 프로세서 레지스터나 기억장치 레지스터와 같이 쉽게 저장된고 이후 복원이 쉬운 자원에는 사용가능하지만 프린터와 같은 자원은 활용이 어렵습니다.