[운영체제 공부] 교착상태

교착상태(Deadlock)는 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 결과적으로 아무 일도 일어나지 않는 상태를 말한다.

교착상태의 조건 중 하나인 순환대기 상태

교착상태가 일어나기 위해선 다음 네 조건을 만족해야한다.

1) 상호배제
2) 점유 대기
3) 비선점
4) 순환대기

교착상태는 이 네 조건을 동시에 모두 만족해야 일어나기 때문에, 이 중 하나라도 성립하지 않게 만들면 교착 상태를 해결할 수 있다. 

교착상태를 해결하는 방법에는 예방, 회피, 탐지, 무시가 있다.

1) 예방(Prevention)

교착상태를 예방하는 방법에는 다음과 같은 방법이 있다.

상호배제 조건 제거	여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
점유와 대기조건의 제거	한 프로세스가 수행하기 전에 모든 자원을 할당받고 점유하지 않을 경우 다른 프로세스가 자원을 요구하도록 하는 방법이다. 자원 과다사용으로 인한 효율성 하락, 요구 자원을 파악하는데에 드는 높은 비용, 기아 상태, 무한 대기 등의 문제가 있다.
비선점 조건의 제거	비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어준다.
순환대기 조건의 제거	자원 유형에 따라 순서를 매긴다.

 

2) 회피(Avoidance)

교착상태의 회피는 교착상태의 모든 발생 가능성을 미리 제거하는것이 아닌, 발생 가능성을 인정하고 교착 상태가 발생하려고 할 때 적절히 회피하는것을 말한다.

교착상태의 회피는 다음 두가지 방법이 있다.

1) 프로세스의 시작 중단

2) 자원 할당 거부 (은행가 알고리즘)

은행가 알고리즘은 자원의 할당 허용 여부를 결정하기 전에 미리 결정된 모든 자원의 최대 가능한 할당량을 시뮬레이션 하여 안전 여부를 검사한다. 그리고 대기중인 다른 모든 활동의 교착 상태 가능성을 조사하여 안전 상태 여부를 검사/확인 한다.

안전 상태는 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태로 안전 순서열이 존재하는 상태를 말한다.

불안전 상태는 안전순서열이 없는 상태를 말한다. 교착상태는 불안전상태에서만 발생하지만, 무조건 일어나는것은 아니다.

은행가 알고리즘은 자원 요청을 승낙하는것이 불안전 상태에서 시스템을 배치할 수 있다고 판단하면 이 요청을 연기하거나 거부해 교착 상태를 예방한다.

 

3) 탐지(Detection)

교착상태 탐지는 교착상태의 발생을 허용한다. 그런 다음 교착상태가 발생했는지 탐지하기 위해 시스템 상태를 지속적으로 검사한다. 리소스 할당 및 프로세스 상태를 추적하는 알고리즘이 사용되고, 감지된 교착상태를 제거하기 위해서는 하나 이상의 프로세스를 롤백하고 다시 시작하게 한다. 운영체제의 자원 스케줄러에서 프로세스가 요청하거나 잠근 자원의 정보를 알 수 있기 때문에 이미 발생한 교착상태를 탐지하기는 쉽다.

교착상태가 탐지되면, 다음 방법들로 정정될 수 있다.

1) 프로세스 중단 (process termination)

2) 자원 선점 (resource preemption)

 

4) 무시(Ignore)

교착상태의 무시는 교착 상태 발생 간격이 크고, 발생했을 경우의 데이터 손실이 허용 범위 내일 때 사용 한다.