[운영체제] Deadlock(교착 상태)

 

Deadlock(교착 상태) 란?

 자원을 소유한 프로세스들끼리 다른 프로세스가 소유한 자원을 요청하면서 무한정 대기하고 있는 현상.

 

특징

 교착 상태에서 프로세스들은 실행을 끝낼 수 없으며, 자원이 묶여 있어 다른 작업을 시작하는 것도 불가능하다.

 교착 상태는 4가지 필요 조건을 반드시 성립해야 한다.

 1. 상호배제 (Mutual Exclusion) : 각 자원은 한 번에 하나의 스레드에게만 점유 되어야 한다.

 2. 점유하며 대기 (Hold & Wait) : 스레드가 최소한 하나의 자원을 점유한 채, 다른 자원을 얻기 위해 대기해야한다.

 3. 비선점 (No Pre-emption) : 다른 스레드로부터 자원을 선점할 수 없어야 한다.

 4. 순환대기 (Circular Wait) : 각 스레드가 서로 꼬리 물며 자원을 점유하고 있어야 한다.

 

교착상태를 다루는 방법

 1. 예방(prevention) : 시스템 구성시 4가지 필요 조건 중 하나 이상을 성립하지 못하도록 하는 방법.

 2. 회피(avoidance) : 자원 할당 알고리즘에서 교착 상태를 판단하여 발생하지 않는 경우에만 할당 하는 방법.

 3. 감지 및 복구 (detection and recovery) : 교착상태 발생 시 감지하고, 해제하는 프로그램을 미리 구동시키는 방법.

 4. 무시 : 교착상태를 발생하지 않는 것처럼 꾸미는 방법

 

4가지 방법중 예방, 회피, 감지는 오버헤드가 너무 크기 때문에 대부분의 운영체제는 ostrich 알고리즘을 사용한 무시하는 방법을 사용한다. ostrich 알고리즘으로 교착상태가 발생하면 reboot 혹은 특정 프로세스를 강제 종료하는 방식이다.