05 OS - 교착상태와 기아상태

1. 교착상태

1. 교착상태

• 둘이 상의 작업이 대기 상태로 중요한 자원을 사용하려고 기다릴때 발생함. 어떤 작업에 필요한 자원을 다른 작업이 점유하여 사용할 수 없어, 프로세스가 결코 일어나지 않을 사건을 기다릴때 교착상태에 빠졌다라고 표현함.
• 초기 일괄 처리 시스템에서는 사용자가 작업 제어카드에 작업을 완료하는데 필요한 자원을 명시해서 교착상태가 발생하지 않았으나, 대화식 시스템에서 동적자원을 공유하여 사용하면서 교착상태가 발생할 가능성이 생김.

2. 교창상태 발생조건

| 조건 이름| 설명| 예시| | - | - | - | | 상호 배제(Mutual Exclusion) | 한 자원은 한 번에 하나의 프로세스만 사용할 수 있음 | 프린터 한 대를 여러 프로세스가 공유함| | 점유 대기(Hold and Wait) | 자원을 점유한 프로세스가 다른 자원을 기다림 | P1이 프린터를 점유하면서 스캐너를 기다림 | | 비선점(No Preemption) | 자원을 강제로 뺏을 수 없음. 자원은 스스로 반납해야 함 | CPU가 P1에게 할당되면, P1이 끝내기 전까지 빼앗을 수 없음 | | 순환 대기(Circular Wait) | 프로세스들이 원형으로 자원을 기다림 | P1 → P2 → P3 → P1 순으로 자원을 기다림 |

2. 교착상태 해결

1. 교착상태 예방

• 자원의 상호배제(Mutual Exclusion) 조건 방지
  • 공유 가능한 자원으로 설계하여 상호배제가 필요 없게 함
  • 예: 읽기 전용 파일은 여러 프로세스가 동시에 읽을 수 있음 → 락 불필요
• 점유 대기(Hold and Wait) 조건 방지
  • 프로세스가 자원을 요청할 때, 필요한 모든 자원을 한 번에 요청하게 강제함
  • 예: 프린터와 스캐너를 둘 다 확보한 경우에만 실행 가능
• 비선점(No Preemption) 조건 방지
  • 자원을 요청할 때 이미 점유 중인 자원을 강제로 회수함
  • 예: 프로세스가 다른 자원을 요청하면, 기존 자원을 모두 반납하고 다시 시도하게 함
• 순환 대기(Circular Wait) 조건 방지
  • 자원에 고정된 우선순위 번호(Resource Ordering)를 부여하고, 오름차순으로만 요청하게 함

2. 교착상태 회피

• 교착상태가 발생하지 않도록 현재 상태에서 자원 할당이 안전한지 미리 검사하는 방식
• 주요 방법은 은행가 알고리즘(Banker’s Algorithm)
  • 자원을 요청받았을 때, 해당 요청을 승인하면 교착상태 없이 완료 가능한지 시뮬레이션
  • Safe State인 경우만 자원을 할당
  • 자원 요청:
    • 현재 사용량(Allocation)
    • 최대 필요량(Max)
    • 남은 필요량(Need) = Max - Allocation
    • 여유 자원(Available)을 고려하여 결정
  • 예: 고객이 은행에 대출 요청 → 해당 대출을 승인해도 은행이 파산하지 않는 경우에만 대출 승인

3. 교착상태 회복

구분	설명	예시 또는 적용 방식
교착상태 탐지	시스템 내에 교착상태가 발생했는지를 검사하는 알고리즘 사용	- 자원 할당 그래프(Resource Allocation Graph) - Wait-for 그래프 (WFG, 선점 불가 시스템)
교착상태 회복	교착상태가 탐지된 이후, 시스템을 복구하여 정상 상태로 만드는 방법들
└ 프로세스 중단	교착상태에 있는 프로세스를 하나 이상 강제로 종료	- 모든 교착 프로세스 중단 - 한 개씩 중단하며 상태 확인
└ 자원 선점	프로세스가 가진 자원을 빼앗아(선점) 다른 프로세스에게 재할당	- 우선순위 낮은 프로세스의 자원을 회수 - 선점은 일반적으로 비선점 시스템에선 어려움

3. 기아상태

1. 기아 상태

• 프로세스가 자원을 요청했지만, 장시간 동안 할당받지 못하고 대기만 하는 상태.
• 이로 인해 실행되지 못한 채 영구적으로 기다리게 되는 문제

2. 특징

항목	설명
무한 대기(Infinite Wait)	요청은 했으나, 절대 자원이 주어지지 않음
자원 할당 불균형**	스케줄러나 락 정책이 공정하지 않으면 발생
우선순위 역전(Priority Inversion	우선순위가 낮은 프로세스가 계속 자원을 점유하면, 높은 우선순위의 프로세스는 대기만 함
Deadlock과 차이	교착상태는 상호 간 자원을 기다리는 순환 상태, 기아 상태는 한쪽만 계속 기다리는 상황

3. 해결

해결책	설명
에이징(Aging)	시간이 지나면 대기 중인 프로세스의 우선순위를 점점 높임
공정한 스케줄링(Fair Scheduling	Round Robin, FIFO 등으로 모든 프로세스에게 기회 제공
락 공정성 보장(Fair Lock)	예: ReentrantLock의 공정 모드 (fair=true) 사용 시 대기 순서대로 락 획득

4. 교착상태와 기아상태

항목	교착상태 (Deadlock)	기아상태 (Starvation)
정의	여러 프로세스가 서로 자원을 기다리며 영원히 대기	하나의 프로세스가 오랫동안 자원을 받지 못함
대기 구조	순환적 (프로세스 간 상호 대기)	일방적 (특정 프로세스만 계속 대기)
발생 조건	상호배제, 점유와 대기, 비선점, 순환대기 조건 필요	일반적으로 우선순위 기반 스케줄링에서 발생
자원 상태	자원을 서로 점유하고 있으며 잠겨 있음	자원은 계속 사용되지만 특정 프로세스는 못 받음
탐지 가능 여부	자원할당그래프 등으로 탐지 가능	명확한 탐지 방법이 없고 시간 기반 추적 필요
해결 방법	예방, 회피, 탐지 및 회복 알고리즘 사용	에이징, 공정 스케줄링 등으로 해결
영향 범위	여러 프로세스가 모두 멈춤	특정 프로세스만 오랫동안 멈춤
예시	P1이 P2의 자원 요청, P2는 P3, P3는 다시 P1 요청	우선순위 낮은 프로세스가 계속 자원을 못 받음