7주차

Shared on April 16, 2026

교착상태와 자원 할당 문제

개요

운영체제에서 교착(Deadlock) 은 프로세스가 서로의 자원을 기다리며 무한히 멈추는 상태를 말한다.
교착이 발생하면 OS가 예방(Prevention), 피해(Detection), 복구(Recovery) 를 통해 해결한다.

핵심 개념

항목	설명
교착상태 조건	상호 배제, 점유 및 대기, 비선점, 순환 대기
자원 할당 그래프	프로세스와 자원을 정점으로, 할당과 요청을 방향이 있는 간선으로 표시
Cycle (사이클)	그래프에 순환 경로가 있으면 교착상태 가능
예방	1) 자원 할당 시 조건을 만족하도록 제한 (예: 한 번에 한 자원만 요청) 2) 상호 배제 보장
피해	펜펠프(페일-펠프) 알고리즘: 요청 시 잠재적 교착 여부를 미리 검사
복구	프로세스 중단과 재시작, 자원 회수 두 가지 방안
다이닝 철학자	자원(포크) 공유 예시로 교착 해결 방법 시연

상세 내용

1. 교착상태와 그 발생 원인

상호 배제: 자원은 한 번에 하나의 프로세스만 사용 가능
점유 및 대기: 프로세스가 현재 보유한 자원과 추가로 필요한 자원을 동시에 요청
비선점: 이미 보유한 자원은 다른 프로세스가 강제로 빼낼 수 없음
순환 대기: 프로세스 집합이 서로의 자원을 기다리는 순환 구조

2. 자원 할당 그래프와 사이클 탐지

정점: 프로세스(P)와 자원(R)
간선:
- P → R: P가 R을 요청 중
- R → P: R이 P에 할당됨
그래프에 사이클이 존재하면 교착 가능
단일 자원형은 간단하지만 다중 자원형은 크기 정보를 포함해야 함

3. 교착 예방 전략

사이클 방지: 한 번에 한 자원만 요청하도록 제한
상호 배제 비활성: 가능하면 자원에 상호 배제 비활성화
조건 위반 방지: 요청 시 미리 검사하여 교착 상황을 막음

4. 페일-펠프(페일-페일) 교착 피하기

전 단계 검사: 요청 시 현재 할당과 요청이 합쳐져도 안전한지 판단
안전 상태: 모든 프로세스가 종료될 수 있는 순서가 존재
안전 순서: 우선순위, 요구량, 현재 할당 비교해 결정

5. 교착 복구 방법

방법	장점	단점
프로세스 중단	간단, 확실	비용 높음, I/O 등에서 위험
자원 회수(강제 회수)	비용 낮음	잠재적 데이터 손상

중단 선택 기준: 실행 시간, 남은 작업량, 우선순위 등을 고려
자원 회수: 특정 프로세스가 보유한 자원 차례대로 회수해 필요에 맞게 할당

6. 다이닝 철학자 문제

문제 설정: 5명의 철학자, 5개의 포크(자원)
교착 조건: 각 철학자가 왼쪽 포크를 잡고 오른쪽을 기다리면 순환 대기 발생
해결 전략:
1. 가장 큰 수의 철학자: 4명만 앉히거나 한 철학자에게 두 포크를 한 번에 잡게 함
2. 세마포어 사용: 포크를 세마포어로 모델링하고 wait(2) 방식으로 두 포크가 동시에 잡힐 때만 식사
3. 우선순위 부여: 한 철학자에게 우선권 부여 후 다른 철학자들은 대기

7. 교착 탐지 및 복구 알고리즘

탐지: 자원 할당 그래프에서 사이클 탐색
복구:
1. 프로세스 중단: 가장 적은 비용의 프로세스 중단
2. 자원 회수: 필요 자원만 회수해 다른 프로세스가 종료 가능하도록 함

8. 교착과 기아(Starvation) 차이

항목	교착	기아
정의	프로세스가 자원 때문에 무한 대기	프로세스가 자원 할당을 받지 못해 계속 대기
원인	순환 대기	우선순위 차이, 불균형 할당
해결	중단/회수	재스케줄링, 우선순위 조정

요약

교착상태는 4가지 조건이 동시에 충족되면 발생하며, 자원 할당 그래프를 통해 사이클을 탐지할 수 있다.
예방, 피해(페일-펠프), 복구(프로세스 중단/자원 회수) 세 단계로 대응한다.
다이닝 철학자와 같은 예시를 통해 자원 공유 시 교착 발생 방지와 해결 전략을 실습한다.