[운영체제] 교착상태(Deadlock, 데드락)의 정의, 발생 조건, 해결 방법

교착상태란 두 개 이상의 프로세스가 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며, 서로의 작업을 끝나기만을 기다리며 둘 다 영원히 끝나지 않는 상황을 뜻합니다.

교착상태 발생 조건

교착상태는 다음 네 가지 조건이 모두 충족될 때 발생합니다. 이 조건들은 Coffman의 조건이라고도 합니다.

1. 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있습니다.
2. 점유와 대기(Hold and Wait): 프로세스가 하나 이상의 자원을 점유한 상태에서, 추가적인 자원을 요청하며 기다립니다.
3. 비선점(No Preemption): 다른 프로세스가 점유하고 있는 자원을 강제로 빼앗을 수 없습니다. 프로세스가 스스로 자원을 해제할 때까지 기다려야 합니다.
4. 환형 대기(Circular Wait): 각 프로세스는 자원을 기다리며 순환 형태로 대기합니다. 예를 들어, P1이 P2가 가진 자원을 기다리고, P2는 P3가 가진 자원을 기다리며, P3는 P1이 가진 자원을 기다리는 상황입니다.

교착상태 해결 방법

교착상태는 방지, 회피, 탐지 및 회복 등의 방식으로 해결할 수 있습니다.

1. 교착상태 예방 (Deadlock Prevention)

교착상태가 발생하지 않도록 Coffman 조건 중 하나 이상을 제거하는 방식입니다.

• 상호 배제 조건 제거: 자원을 공유 가능하게 하여 여러 프로세스가 동시에 사용할 수 있도록 합니다. 하지만 일부 자원(프린터, 파일 등)은 본질적으로 상호 배제가 필요합니다.
• 점유와 대기 조건 제거: 자원을 요청하기 전에 필요한 모든 자원을 한꺼번에 할당하는 방식입니다. 하지만 자원의 비효율적 사용으로 이어질 수 있습니다.
• 비선점 조건 제거: 프로세스가 자원을 기다려야 할 경우, 점유 중인 자원을 강제로 해제하게 합니다. 다만, 일부 자원은 선점이 불가능할 수 있습니다.
• 환형 대기 조건 제거: 자원에 순서를 부여하여 순서대로 요청하게 하면, 원형 대기를 방지할 수 있습니다.

2. 교착상태 회피 (Deadlock Avoidance)

교착상태가 발생할 가능성이 있는 경우를 회피하는 방식으로, **은행가 알고리즘(Banker's Algorithm)**이 대표적인 예입니다. 이 방식에서는 시스템이 안전 상태에 있을 때만 자원을 할당하여 교착상태를 회피합니다.

• 은행가 알고리즘: 각 프로세스가 자원을 요청할 때, 시스템이 자원을 할당해도 안전 상태를 유지할 수 있는지를 확인하고, 안전하지 않으면 자원을 할당하지 않습니다.

3. 교착상태 탐지 및 회복 (Deadlock Detection & Recovery)

교착상태가 발생했는지를 탐지하고, 발생 시 이를 해결하는 방식입니다.

• 탐지: 시스템에서 교착상태 탐지 알고리즘을 사용하여 주기적으로 자원 할당 상태를 검사하고, 교착상태가 발생했는지 확인합니다.
• 회복: 교착상태가 발생한 경우, 자원을 해제하기 위해 일부 프로세스를 강제 종료하거나 자원을 선점하여 교착 상태를 해소합니다.

4. 교착상태 무시 (Deadlock Ignorance)

작은 시스템에서는 교착상태가 발생할 확률이 낮기 때문에 교착상태를 고려하지 않고 무시하는 방식입니다. Unix, Windows와 같은 대부분의 운영체제는 교착상태를 방지하지 않고 무시하는 전략을 사용합니다. 단, 교착상태가 발생했을 경우 시스템 재부팅 등의 조치가 필요합니다.

요약

• 교착상태 정의: 자원을 두고 서로 대기하며 프로세스가 영원히 진행되지 못하는 상태.
• 발생 조건: 상호 배제, 점유와 대기, 비선점, 환형 대기.
• 해결 방법: 예방, 회피(은행가 알고리즘), 탐지 및 회복, 무시.

교착상태는 시스템 자원 관리의 핵심 과제로, 운영체제는 성능과 자원 효율성을 고려하여 적절한 방법을 선택하여 교착상태를 해결합니다.