교착 상태(Deadlock)
프로세스 집합의 모든 프로세스가 같은 집합 내 다른 프로세스가 보유한 자원을 기다리는 상황을 말한다. 이 경우 더 이상 진행이 불가능하며, 시스템은 교착 상태에 빠지게 된다.
교착 상태 발생의 필요조건 (네 가지)
교착 상태가 발생하기 위해서는 다음 조건이 모두 충족되어야 한다.
| 상호 배제 (Mutual Exclusion) | 자원은 한 번에 오직 하나의 프로세스만 사용할 수 있어야 한다. |
| 점유하며 대기 (Hold and Wait) | 최소 하나의 자원을 점유한 상태에서 다른 자원을 기다려야 한다. |
| 비선점 (No Preemption) | 이미 할당된 자원은 사용이 끝나기 전까지 강제로 빼앗을 수 없다. |
| 순환 대기 (Circular Wait) | 프로세스들이 자원을 기다리면서 원형으로 연결된 형태를 이뤄야 한다. (예: P1 → P2가 가진 자원 요청, P2 → P3 요청, …, Pn → P1 요청) |
CPU 스케줄링에서의 선점/비선점
| 선점형(preemptive) | 이미 CPU를 쓰고 있는 프로세스를 운영체제가 강제로 중단시키고 다른 프로세스에 CPU를 줄 수 있음 (예: Round Robin, SRTF) |
| 비선점형(non-preemptive) | 한 번 CPU를 얻으면 스스로 양보(종료·대기 상태 전환)할 때까지 계속 CPU를 씀. (예: FCFS, SJF) |
여기서의 의미는 "강제로 뺏을 수 있느냐 없느냐"에 대한 것.
자원 할당에서의 선점/비선점
교착 상태 조건 중에서 말하는 비선점(No Preemption) 은 CPU뿐 아니라 모든 자원에 적용되는 일반적 개념이에요.
| 선점 가능 자원(preemptible resource) | 운영체제가 강제로 회수해도 문제 없는 자원 예: CPU 레지스터, 메모리 (저장 후 다시 복원 가능) |
| 비선점 자원(non-preemptible resource) | 사용 중간에 빼앗을 수 없는 자원 예: 프린터 (출력 도중 뺏으면 출력물이 깨짐), 디스크 장치, 네트워크 소켓 등 |
따라서 교착 상태 조건에서 말하는 비선점은 →
한 번 프로세스에게 할당된 자원은, 그 프로세스가 자발적으로 해제할 때까지 운영체제가 강제로 회수할 수 없다는 의미
교착 상태의 처리 방법
| 예방 (Prevention) | 네 가지 조건 중 하나 이상을 발생하지 않도록 설계 현실적으로는 순환 대기 조건 제거 방식이 가장 많이 사용됨. (예: 자원에 고정된 순서를 부여하여, 항상 작은 번호 → 큰 번호 순서로만 자원을 요청) |
| 회피 (Avoidance) | 은행원 알고리즘(Banker's Algorithm)을 사용 시스템 상태가 교착 가능성이 있는 불안전 상태(unsafe state) 로 가지 않도록, 자원 요청을 미리 시뮬레이션 후 허용 여부 결정 |
| 탐지 (Detection) | 자원 할당 그래프(Resource Allocation Graph, RAG) 또는 탐지 알고리즘을 통해 교착 상태 여부를 주기적으로 검사 RAG에서 사이클이 존재하면 교착 상태 발생을 의미 |
| 복구 (Recovery) | 교착 상태가 탐지되면 시스템이 강제로 해결 교착 상태에 빠진 프로세스를 중단(terminate)하거나 프로세스가 점유한 자원을 선점(preempt)하여 다른 프로세스에게 재할당 |
은행원 알고리즘 (Banker's Algorithm)
개념
- 은행은 고객에게 대출을 해줄 때, 모든 고객이 최대한 대출을 요청하더라도 결국 상환(반납)이 가능해야 안전하다고 생각하고 돈을 빌려줍니다.
- 운영체제도 비슷하게, 프로세스에게 자원을 할당할 때 미래에 교착 상태가 생기지 않는다면 허용, 교착 상태가 발생할 가능성이 있다면 거부합니다.
주요 개념
| 최대 요구량 (Max) | 각 프로세스가 자원 유형별로 최대 몇 개까지 필요할 수 있는지. |
| 할당량 (Allocation) | 현재 각 프로세스에 이미 할당된 자원의 수 |
| 요청량 (Need) | 각 프로세스가 앞으로 더 필요로 하는 자원의 수 Need = Max - Allocation |
| 가용 자원 (Available) | 현재 시스템에 남아 있는 자원의 수 |
알고리즘 동작
- 프로세스가 자원을 요청하면, 우선 요청 ≤ Need인지 확인. (최대 요구량을 넘는 요청은 불법)
- 요청한 자원을 주고 나서 시스템이 안전 상태(Safe State) 에 머무는지 시뮬레이션.
- 안전 상태란: 모든 프로세스가 어떤 순서로 실행되더라도 결국 자원을 얻고 종료할 수 있는 상태.
- 즉, Deadlock으로 가지 않는 상태.
- 시뮬레이션 후 안전 상태라면 자원 요청 허용, 아니면 거부.
예시
자원 종류: A, B (각 1개씩 있다고 가정)
- P1: 최대 1개 필요, 현재 0개 보유
- P2: 최대 1개 필요, 현재 0개 보유
- P1이 1개 요청 → 허용 가능
→ P1 실행 후 자원 반납 → P2 실행 가능
(안전 상태) - 만약 세 번째 프로세스 P3가 최대 2개 필요하다고 하고 현재 자원 2개를 모두 달라고 하면?
→ P1, P2는 실행 불가능 → 교착 가능성 존재 → 요청 거부
은행원 알고리즘 (Banker's Algorithm) 장단점
- 장점: 교착 상태 자체를 피할 수 있음.
- 단점:
- 프로세스의 최대 요구량(Max) 을 미리 알아야 함 (현실적으로 어려움)
- 매 요청마다 안전 상태 검사를 수행해야 해서 오버헤드 큼
한 줄 요약
- 교착 상태 = 4가지 조건이 동시에 충족될 때 발생
- 예방, 회피, 탐지, 복구의 네 가지 방식으로 대응
- 현실적으로는 순환 대기 제거(예방) 또는 은행원 알고리즘(회피) 이 핵심