교착상태(Deadlock)

Deadlock

운영체제에서 데드락이란 시스템 자원에 대한 요구가 뒤엉킨 상태이다.

즉, 한 프로세스가 점유하고 있는 자원을 다른 프로세스에서 기다릴 때 무한 대기에 빠지는 상황을 말한다.

 

Deadlock 발생조건

• 상호 배제 : 한 번에 프로세스 하나만 해당 자원을 사용할 수 있다. 사용 중인 자원을 다른 프로세스가 사용하려면 해당 자원이 해체될 때까지 대기해야 한다.
• 점유 대기 : 자원을 최소 하나 보유하고, 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재해야 한다.
• 비선점 : 이미 할당된 자원은 강제로 뺏을 수 없다.
• 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다.

Deadlock 해결법

• 데드락 발생 예방
• 데드락 발생 가능성을 인정하고 적절하게 회피
• 데드락 발생을 허용하지만 이를 탐지하여 회복

Deadlock 예방

4가지 데드락 발생조건을 발생하지 않도록 하는 것이 데드락을 예방하는 방법이다.

• 자원의 상호 배제 조건 방지 : 한번에 여러 프로세스가 공유 자원을 사용할 수 있도록 한다. (동기화 문제가 발생할 수 있다.)
• 점유 대기 조건 방지 : 프로세스 실행에 필요한 모든 자원을 한꺼번에 요구하고 허용할 때까지 작업을 보류함으로서, 나중에 또다른 자원을 점유하기 위한 대기 조건을 성립하지 못하도록 한다.
• 비선점 조건 방지 : 이미 다른 프로세스에게 할당된 자원에 대해 선점권이 없다고 가정할 때, 높은 우선순위를 가진 프로세스가 해당 자원을 선점할 수 있도록 한다.
• 순환 대기 조건 방지 : 자원이 순환 형태로 대기하지 않도록 한 쪽 방향으로만 자원을 요구하도록 한다.

데드락을 예방하는 방법은 시스템의 처리량 및 효율성을 떨어트리는 단점이 발생할 수 있다.

 

Deadlock 회피

프로세스들이 요청하는 모든 자원을 데드락을 발생시키지 않으면서 차례로 모두에게 할당해 줄 수 있는 상태를 safe state(안정 상태 <-> 불안정 상태)라고 한다.

또한 특정한 순서로 프로세스들에 자원을 할당하고, 실행 및 종료 등의 작업을 할 때, 데드락이 발생하지 않는 순서를 safe sequence(안전 순서)라고 한다.

 

자원을 할당한 후에도 safe state에 있을 수 있도록 할당을 허용하는 것이 데드락 회피 알고리즘이다.

 

Deadlock 탐지 및 회복

탐지 기법

• Allocation, Request, Available 등으로 현재 시스템의 자원 할당 상태를 통해 시스템에 데드락이 발생했는지 여부를 탐지한다. 
• 또는 자원 할당 그래프를 통해 탐지한다.

회복 기법(순환 대기에서 벗어나 데드락으로부터 회복)

• 교착 상태에 빠진 모든 프로세스를 중단시키는 방법(연산중인 프로세스들도 중단되어 부분 결과가 폐기될 수 있다는 단점이 있다.)
• 프로세스를 하나씩 중단시키며 탐지 알고리즘을 통해 데드락을 탐지하면서 회복(매번 탐지 알고리즘을 호출 및 수행해야하는 단점이 있다.)
• 프로세스에 할당된 자원을 선점하여 교착 상태를 해결할 때까지 해당 자원을 다른 프로세스에 할당해 주는 방법