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