7주차

교착상태와 자원 할당 문제

개요

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

핵심 개념

상세 내용

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

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

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

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

3. 교착 예방 전략

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

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

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

5. 교착 복구 방법

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

6. 다이닝 철학자 문제

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

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

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

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

요약

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