교착 상태(Deadlock)
교착 상태(Deadlock)란
두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.
(위키백과)
간단하게 말하면 이도저도 못해서 무한 대기에 빠지는 상태를 뜻한다.
교착 상태의 조건으로는
상호배제
프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구
한 번에 한 프로세스만 해당 자원을 사용할 수 있다.
사용 중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 해제될 때까지 기다림
점유대기
프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림
비선점
프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없음
순환대기
각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가짐
이렇게 네가지가 있고 이 조건 중에서 한 가지라도 만족하지 않으면 교착 상태는 발생하지 않는다.
위 4가지 조건은 서로 완전히 독립적인 것은 아니다.
교착 상태를 관리하는 방법도 예방, 회피, 무시, 발견 이렇게 네가지이다.
교착 상태의 관리
현재의 대부분의 운영 체제들은 교착 상태를 막는 것은 불가능하다
교착 상태의 예방
교착 상태의 필요 조건을 제거해서 미리 교착 상태가 일어나지 않도록 예방하는 것이다.
상호배제 방지
한 번에 여러 프로세스가 자원을 사용할 수 있게끔 한다.
하지만 추후 동기화와 관련된 문제가 발생할 수 있다.
점유대기 방지
프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류한다.
비선점 방지
우선 순위가 높은 프로세스가 자원을 선점할 수 있도록 함.
순환대기 방지
자원을 일정한 한 쪽 방향으로만 요구할 수 있도록 함.
교착 상태의 회피
데드락을 발생시키지 않고, 자원을 요청하는 프로세스들 모두에게 할당해 줄 수 있는 상태를 안정 상태(safe state)에 있다고 한다.
데드락이 발생되지 않는 순서를 안전순서(safe sequence)라고 한다.
회피 알고리즘은 자원을 할당한 후에도 시스템이 항상 Safe state에 있을 수 있도록 하는 것이 기본 특징이다.
관련 알고리즘으론 크게 두가지가 있다.
- 자원 할당 그래프 알고리즘
- 은행원 알고리즘
(링크 같음)
교착 상태의 무시
말그래도 데드락을 무시하는 방법이다.
예방과 회피기법을 프로그램에 넣게되면 시스템의 처리량과 효율성을 떨어뜨릴 수 있는 등 프로그램의 성능면에 큰 영향을 미칠 수 있다.
그리하여 데드락 발생 확률이 비교적 낮은 경우는 별다른 조치를 취하지 않기도 한다.
교착 상태의 발견 및 회복
데드락 탐지, 감시 알고리즘을 사용하여 데드락 발생을 체크하는 방법이다.
- 먼저 여러 알고리즘을 사용해 데드락이 발생했는지 여부를 탐색을 한다.
- 데드락이 발견됐다면 순환 대기에서 벗어나 데드락으로부터 회복하기 위한 방법을 사용한다.
프로세스 중지
교착 상태에 빠진 모든 프로세스를 중단을 시키게 되면 잘 작동하던 프로세스들도 모두 중단되어 부분 결과가 폐기되거나 할 수 있다.
프로세스를 하나씩 중단 시킬때마다 탐지 알고리즘으로 데드락을 탐지하고 회복을 시키면 매번 탐지 알고리즘을 호출시켜야 하므로 프로그램에 부담이 갈 수 있다.
자원 선점
프로세스에 할당된 자원을 선점하여, 데드락이 해결될 때까지 다른 프로세스에 할당해 주는 방법이다.
희생자 선정 문제가 발생할 수 있다.
프로세스 롤백
데드락이 발생한 프로세스들의 수행을 롤백시킨다.
미리 정의해놓은 특정 시점까지 되돌린 후 작업 재수행
재수행시 다시 데드락이 발생할 수 있다.
이러하여 이 방식 역시 성능에 큰 영향을 미칠 수 있다.
학습에 참고한 사이트
