Deadlock
교착상태란 멀티 프로그래밍 환경에서 나타날 수 있는 문제점이다.
프로세스1은 자원A가 필요한데, 이는 프로세스2가 사용 중이다.
또한 프로세스2는 자원B가 필요한데, 이는 프로세스1이 사용 중이다.
이러한 상황이라면 프로세스1은 자원A를 사용할 수 있을 때까지 자원B를 반환할 수 없으며, 프로세스2 또한 자원B를 사용할 수 있을 때까지 자원A를 반환할 수 없어 무한히 대기만 하는 현상이 발생하며 이 것이 데드락이라 한다.
교착상태의 발생 조건은 다음 4가지를 모두 만족하는 것이다.
상호 배제(Mutual exclusion)- 하나의 자원은 하나의 프로세스만 점유할 수 있다.
점유와 대기(Hold and wait)- 필요한 자원이 다른 프로세스가 점유 중이면, 자원을 점유 중인 채로 기다린다.
비선점(No preemption)- 필요한 자원이 다른 프로세스가 점유 중이면, 빼앗지 않고 반환할 때까지 기다린다.
환형 대기(Circular wait)- Hold and wait 관계인 프로세스들이 서로 기다린다.
그렇다면 교착상태는 어떻게 해결할 수 있을까?
해결 방법으로는 3가지 방법이 있다.
방지- 앞서 4가지의 교착상태 발생 조건을 만족하지 않게 하는 것이다.
회피- 교착상태 발생의 여지가 있는 자원을 할당하지 않는 것이다.
- 알고리즘을 사용하여 회피할 수 있다.
탐지 및 회복(Detection and Recovoery)- 교착상태가 발생하도록 내버려두고 발생한다면 찾아내어 고치는 것이다.
방지의 경우 4가지 조건을 망가뜨리면 또 다른 오류가 발생할 수 있다.
예를 들어 상호 배제를 만족하지 않으면 두 프로세스가 자원에 접근하여 동시성 문제가 발생할 수 있다.
그나마 조건을 깨는 것이 수월한 것이 환형 대기로, 서로 기다리는 환형에서 순차적으로 접근하는 선형 대기로 순서를 정해주는 것이다.
회피의 경우 대표적으로 은행원 알고리즘을 사용할 수 있다.
은행원 알고리즘이란 안전 상태와 불안전 상태로 나누고, 교착상태가 발생할 수 없는 안전 상태일때만 프로세스의 시스템콜을 받아들이고 교착상태가 발생할 수 있는 불안전 상태의 경우 요청을 거절하는 기법이다.
하지만 안전 상태에서만 자원을 할당하기 때문에 자원 사용률이 낮아져 성능이 저하된다는 단점이 있다.
탐지의 경우 각 자원마다 하나의 프로세스가 존재하면 Cycle을 이용한다. 자원 할당 그래프에서 자원을 제거하고 간선을 프로세스로 향하게 하면 Cycle 발생 여부를 확인할 수 있다.
각 자원마다 여러 프로세스가 존재하면 은행원 알고리즘을 사용할 수 있는데, 이는 회피에서 사용한 은행원 알고리즘과 다르다.
각 프로세스의 자원 요청 개수를 확인하여 불안정 상태가 존재하면 교착상태라고 판단하는 것이다.
교착상태가 탐지 되었다면, 프로세스 종료 혹은 자원 선점을 통하여 복구한다.
프로세스 종료- 교착상태가 제거될 때까지 하나씩 프로세스 중지
- 교착상태의 프로세스 모두 중지
자원 선점- 교착상태에 있는 프로세스의 자원을 섬점하여 다른 프로세스에 할당
- 가장 최소 피해를 주는 프로세스를 선점하는 희생자 선택을 고려해야 함
- 선점된 프로세스를 문제 없던 상태로 되돌려야 하며(롤백) 보통 가장 안전한 방법은 중지 후 재시작
- 한 프로세스가 계속 선점되면 자원을 계속 할당받지 못하는 기아상태 될 수 있음
- 선점될 때마다 우선순위를 높여 해결
