7. 교착상태

 

💡 1분 핵심 요약 (TL;DR)

• ✅ 교착 상태란 2개 이상의 프로세스가 서로의 자원 해제만 기다리며 무한정 멈춘 상태
• ✅ 필요조건 4가지 : 상호 배제 · 비선점 · 점유와 대기 · 원형 대기 (모두 충족해야 발생)
• ✅ 해결 방법 4가지 : 예방 · 회피 · 검출 · 회복 — 실무에서는 검출+회복이 가장 현실적
• ✅ 자원 할당 그래프로 프로세스의 자원 점유·대기 관계를 시각적으로 파악 가능
• ✅ 교착 상태 vs 기아 상태 — 발생 원인과 대기 상태가 서로 다름

 

 

 

01 교착 상태(Deadlock)란?

서로의 자원을 기다리며 영원히 멈춰버린 프로세스들

 

📖 핵심 개념
2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 더 이상 작업을 진행하지 못하는 상태입니다. 다중 프로그래밍 시스템에서 결코 일어나지 않을 사건(event)을 기다리는 셈입니다. 프로세스가 교착 상태에 빠지면 작업이 정지되어 더는 명령을 진행할 수 없으며, 운영체제가 해결하지 못하면 시스템 운영자나 사용자가 작업을 강제 종료하는 외부 간섭으로 해결해야 합니다.

 

⚠️ 왜 더 심각한 문제인가
교착 상태는 시스템 자원에 대한 요구가 뒤엉킨 상태로, 두 프로세스가 서로 사용 중인 자원을 기다리고 있을 때 발생합니다. 하나 이상의 작업에 영향을 주기 때문에 무한 대기나 기아 상태보다 더 심각한 문제를 야기합니다. 자원 해제 요청이 받아들여질 때까지 프로세스들은 작업을 진행할 수 없고, 현재 보유한 자원도 해제할 수 없습니다.

 

🔒 교착 상태 (Deadlock) · 여러 프로세스가 작업을 진행하다   자연 발생적으로 일어나는 문제 · 대기 상태에 존재   (자원·사건을 무한정 기다림)

🍽️ 기아 상태 (Starvation) · 운영체제가 잘못된 정책을 사용해   특정 프로세스의 작업이 지연 · 준비 상태에 존재   (CPU 할당을 기다림)

 

교착 상태가 발생하는 대표 사례

 

사례	발생 원인
스풀링 시스템	디스크 스풀 공간 출력 미완료 상태에서 다른 작업이 공간을 모두 차지하면 발생. 스풀링 파일의 포화 임계치를 설정해 예방
디스크 공유	디스크 사용 제어가 없으면 프로세스들이 서로 충돌하는 명령을 요청할 때 발생. 디스크 제어기가 프로세서와 독립적으로 작동할 때도 발생
네트워크	네트워크가 붐비거나 입출력 버퍼 공간이 부족할 때, 메시지 흐름을 제어하는 적절한 프로토콜이 없으면 발생

 

 

 

02 교착 상태의 발생 원인 & 자원 할당 그래프

시스템 자원, 공유 변수, 응용 프로그램에서 비롯되는 문제들

 

원인	내용
시스템 자원	다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생. 임계구역으로 보호되는 프린터, 스캐너, CD 레코더 등을 할당받은 후 양보하지 않는 경우
공유 변수	임계구역 문제를 해결하기 위한 코드가 무한 대기를 막지 못해 발생하는 경우
응용 프로그램	데이터베이스처럼 데이터 일관성 유지를 위해 잠금(Lock)을 사용하는 과정에서 발생할 수 있음

 

📊 자원 할당 그래프 (Resource Allocation Graph)
프로세스가 어떤 자원을 사용 중이고 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현한 것입니다. 이 그래프를 사용하면 어떤 프로세스에 자원이 할당되어 있는지, 어떤 프로세스가 자원을 기다리고 있는지를 한눈에 파악할 수 있습니다.

· 자원 2개 이상의 프로세스를 동시에 허용하는 경우도 있음
· 여러 프로세스가 하나의 자원을 동시에 사용하면 이를 다중 자원이라 함
· 다중 자원은 수용 가능한 프로세스 수를 사각형 안에 작은 동그라미로 표현

 

 

💡 시험 단골 함정 — 사이클이 곧 교착 상태일까?
자원당 인스턴스가 1개뿐이라면 사이클 발생 = 교착 상태가 맞습니다. 하지만 다중 자원(인스턴스가 여러 개)인 경우, 사이클이 존재하더라도 다른 프로세스가 자원을 반납해 사이클이 깨질 수 있으므로 교착 상태일 수도 있고 아닐 수도 있습니다.

 

 

 

03 교착 상태의 4가지 필요조건

네 조건을 동시에 충족해야만 교착 상태가 발생한다

 

① 상호 배제 배타적 자원 사용

+

② 비선점 자원 강탈 불가

+

③ 점유와 대기 보유하며 대기

+

④ 원형 대기 순환 구조

 

 

① 상호 배제 (Mutual Exclusion)
한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 합니다. 자원을 최소 하나 이상 비공유, 즉 한 번에 프로세스 하나만 해당 자원을 사용할 수 있어야 합니다. 사용 중인 자원을 다른 프로세스가 사용하려면 자원이 해제될 때까지 대기해야 합니다.

 

② 비선점 (Non-preemption)
한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 합니다. 자원을 강제로 빼앗을 수 없고, 자원을 점유하고 있는 프로세스가 끝나야만 자원이 해제됩니다.

 

③ 점유와 대기 (Hold and Wait)
프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 합니다. 자원을 최소한 하나 정도 보유하면서, 다른 프로세스에 할당된 자원을 얻으려고 대기하는 프로세스가 있어야 합니다.

 

④ 원형 대기 (Circular Wait)
점유와 대기를 하는 프로세스 간의 관계가 원형을 이루어야 합니다. 단순히 점유와 대기를 한다고 모두 교착 상태에 빠지는 것은 아니며, 프로세스들이 서로 방해하는 방향이 원을 이루어 서로 양보하지 않을 때 교착 상태가 발생합니다.

 

 

💡 조건의 두 가지 성격
· 상호 배제 + 비선점 : 자원이 어떤 특징을 가지는지 나타내는 조건. 동시 공유도 안 되고 중간에 빼앗을 수도 없다면 자원을 가진 프로세스가 내놓을 때까지 무작정 기다리게 됨
· 점유와 대기 + 원형 대기 : 프로세스가 어떤 행위를 하는지 나타내는 조건. 점유·대기 상태에서 방해하는 방향이 원을 이루면 서로 양보하지 않아 교착 상태 발생

 

 

 

04 교착 상태 해결 방법 — 예방 · 회피 · 검출 · 회복

네 가지 접근법과 각각의 현실적 한계

 

해결 방법	특징
예방	교착 상태를 유발하는 네 가지 조건을 무력화한다
회피	교착 상태가 발생하지 않는 수준으로 자원을 할당한다
검출	자원 할당 그래프를 사용하여 교착 상태를 발견한다
회복	교착 상태를 검출한 후 해결한다

 

 

 

① 교착 상태 예방 — 네 조건을 하나씩 무력화

 

대상 조건	예방 방법	단점
상호 배제	독점적으로 사용 가능한 자원을 모두 없애 공유 자원으로 전환	사실상 무력화 어려움
비선점	모든 자원을 빼앗을 수 있도록 허용 (대기 시 보유 자원 해제)	기아 현상 유발
점유와 대기	"전부 할당 또는 전부 미할당" 방식 — 시작 초기에 모든 자원을 한꺼번에 점유	자원 활용성 저하, 일괄 처리화
원형 대기	모든 자원에 번호를 부여하고 숫자가 큰 방향으로만 할당	유연성 저하, 번호 부여 난이도

 

❌ 점유와 대기 예방의 추가 단점
· 프로세스가 자신이 사용할 모든 자원을 자세히 알기 어려움
· 앞으로 사용할 자원까지 미리 선점해버려 다른 프로세스의 작업이 지연됨
· 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함

 

② 교착 상태 회피 — 자원 할당량 조절

 

📖 핵심 개념
어느 수준 이상의 자원을 나누어 주면 교착 상태가 발생하는지 파악하여, 그 수준 이하로만 자원을 할당하는 방법입니다. 교착 상태가 발생할 범위에 있는 프로세스는 대기시킵니다.

문제점
· 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
· 시스템의 전체 자원 수가 고정적이어야 함
· 자원이 낭비됨

 

🏦 대표 알고리즘 — 은행원 알고리즘 (Banker's Algorithm)
교착 상태 회피의 대표적인 방법은 다익스트라(Dijkstra)가 제안한 은행원 알고리즘입니다. 시스템을 안전 상태(Safe State)와 불안전 상태(Unsafe State)로 나누고, 자원을 할당한 후에도 시스템이 안전 상태를 유지할 수 있을 때만 자원을 빌려주는(할당하는) 보수적인 방식입니다.

 

③ 교착 상태 검출 — 발생 여부를 계속 주시

 

⏱️ 타임아웃 이용 검출 일정 시간 동안 작업이 진행되지 않는 프로세스를 교착 상태로 간주. · 교착 상태가 자주 발생하지 않는다는 가정 · 별도 알고리즘 없이 쉽게 구현 가능

📊 자원 할당 그래프 이용 검출 그래프를 모니터링하며 사이클 발생 여부를 확인. · 프로세스 작업 방식을 제한하지 않고 정확히 파악 가능 · 그래프 유지·갱신·사이클 검사로 오버헤드 발생

 

④ 교착 상태 회복 — 강제 종료로 마무리

 

📖 핵심 개념
교착 상태가 검출된 후, 이를 푸는 후속 작업입니다. 회복 기법은 크게 두 가지 축으로 나뉩니다.

① 프로세스 종료 (Process Termination)
교착 상태를 유발한 프로세스를 강제로 종료합니다.
· 교착 상태를 일으킨 모든 프로세스를 동시에 종료하는 방법
· 교착 상태를 일으킨 프로세스 중 하나씩 순서대로 종료하는 방법

② 자원 선점 (Resource Preemption)
교착 상태가 깨질 때까지 특정 프로세스(희생자)의 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 방식입니다.

 

✓ 실무적 결론
예방과 회피는 자원 활용성 저하·실효성 부족 문제로 잘 사용되지 않습니다. 교착 상태를 검출한 후 회복시키는 방식이 결론적으로 교착 상태를 해결하는 가장 현실적인 접근 방법입니다.

 

 

 

📌 핵심 정리

· 교착 상태 : 2개 이상의 프로세스가 서로의 자원 해제만 기다리며 정지된 상태
· 교착 상태 vs 기아 상태 : 교착은 대기 상태(자원 대기), 기아는 준비 상태(CPU 대기)
· 자원 할당 그래프 : 프로세스의 자원 점유·대기 관계를 방향성 그래프로 표현
· 필요조건 4가지 : 상호 배제 + 비선점 + 점유와 대기 + 원형 대기 (모두 충족 시 발생)
· 예방 : 네 조건 중 하나를 무력화 — 실효성 낮음
· 회피 : 자원 할당량을 조절 — 은행원 알고리즘(안전 상태 유지)이 대표적, 자원 낭비 발생
· 검출 : 타임아웃 또는 자원 할당 그래프로 발생 여부 모니터링
· 회복 : 프로세스 종료 또는 자원 선점(희생자 선택) — 검출+회복이 가장 현실적
· 사이클 vs 교착 : 단일 인스턴스 자원이면 사이클=교착, 다중 자원이면 사이클≠교착일 수 있음

 

 

태그 : 교착상태란데드락 발생 조건교착상태 기아상태 차이자원 할당 그래프상호배제 비선점이란원형대기 점유와대기교착상태 예방 회피 차이교착상태 검출 회복운영체제 데드락 정리운영체제 교착상태 해결