Intro
교착상태
둘 이상의 프로세스가 각자의 자원을 보유한 채로 영원히 기다리는 현상(외부의 조치가 없는 이상) (무한 대기-starvation 와 구분 필요!)
문제점
- 프로세스를 종료할 수 없으므로 사용자에 응답 불가능
- 교착상태와 연관된 자원들은 활용되지 못함
-> 시스템 성능 저하 야기
자원
선점 가능자원 vs 선점 불가능 자원
선점 가능 자원 : 사용중이었는데 다른 프로세스에게 선점되었다가 다시 할당받아도 괜찮은 자원
선점 불가능 자원 : 선점될 경우 프로세스의 정상적 진행을 포기해야 할 정도의 불이익을 받는 자원 ex) 프린트
공유 가능 자원 vs 배타적 사용 자원(cpu, 메모리, 키보드, 모니터 등)
순차적 재사용 가능 자원(cpu, 메모리 등) vs 소모성 자원(시그널, 메세지)
프로세스의 선택지
- 필요 자원에 대한 요청 - 할당/대기(대기상태에서는 자원 요청/반납이 불가)
- 자원 반납 - (프로세스가)시스템 콜 > 운영체제가 처리 > 대기중인 자원에 할당
같은 자원을 사용하는 프로세스들이 모두 1.번 상태이며 2. 수행 불가 시 데드락 발생
데드락 원인
- 자원의 배타적 사용
- 자원의 부분 할당 - 프로세스는 실행 과정 중에 자원을 확보해 나감
- 자원의 선점 불가능성
- 자원에 대한 환형 대기 - 두개 이상의 프로세스가 자신의 자원을 보유한 채로 서로의 자원을 요청할 시
해결
-
예방(Prevention)
- 자원의 배타적 사용 조건 배제 (불가능)
- 자원의 부분 할당 배제 - 자원 낭비 및 무한 대기 야기
- 선점 불가능성 배제 - 자원 낭비 및 무한 대기 야기 (수행중이던 프로세스가 손상되어 비정상 종류 후 다시 처음부터 수행해야 하는 경우)
- 환형 대기 상황 배제: 모든 자원들을 프로세스 내부 사정과 관련없이 순차적으로만 소유(?) 가능 - 자원 낭비 및 무한 대기 야기
-
회피(Avoidance)
- 안전 상태: 프로세스가 유한한 시간 내 정상적으로 종료될 수 있는 상태 - 자원 할당 결과 안전 상태일 경우에만 자원 할당하는 기법
- 회피를 위한 가정 넷- 시스템 내 프로세스 수 고정
- 자원의 수 고정 (불가능)
- 프로세스가 요구할 수 있는 최대 자원의 수 존재 (불가능)
- 프로세스는 자원 사용 후 반드시 반납
- 불가능한 가정이 존재하므로 이론적으로만 접근되는 기법
- 다익스트라의 은행가 알고리즘 (최대요구량 - 현재보유량(프로세스의 현재보유량 + 여유량))
- 안전 상태: 프로세스가 유한한 시간 내 정상적으로 종료될 수 있는 상태 - 자원 할당 결과 안전 상태일 경우에만 자원 할당하는 기법
-
탐지(Detection)
- 교착 상태를 탐지해 해결 (교착상태 발생 허용)
- 자원 할당 그래프(RAG) - 방향성 이분 그래프(자원->프로세스 - 할당, 프로세스 -> 자원 - 대기)
- 그래프 제거(Graph Reduction)법
- 싱크(대기 x 프로세스)의 자원 반납 가정 (자원 -> 싱크 에지 모두 삭제)- 에지 모두 제거 시 교착상태 x
- 지워지지 않는 에지 존재 시 교착상태 o
- 그래프 탐색(Search)법
- 대기상황 나타내는 에지에서부터 탐색 시작- 싱크에 다다르면 교착 x
- 사이클 발생 시(자기 자신으로 되돌아왔을 시) 교착 가능성 up
- 노트(knot) 발생 시 교착상태 확정
-
복구(Recovery)
- 프로세스 종료(Process Termination) 방식: 교착상태에 포함된 프로세스 중 하나를 강제 종료시킨 후 자원 할당
- 종료 비용 발생- Lowest-termination-cost Process First: 교착상태가 제거되었는지 확인 필요
- 교착상태 내 프로세스들의 부분집합 중 최소종료비용인 부분집합 한꺼번에 종료: 비용 계산 복잡
- 자원 선점 방식: 필요 자원을 어떻게든(?) 가져와 할당
- 프로세스 종료와 차이점 - 데드락과 관련없는 프로세스가 자원을 뺏길 수도 있음!
프로세스 강제 종료 > 복구 비용을 키우는 낭비 요인, 보완 방안 -> 검사점 지정(Checkpointing), 재시작(Restart)
- 검사점 지정: 프로세스 실행 중간 시점의 실행 결과 보존 및 표시
- 재시작: 최근의 검사점(Checkpoint)으로부터 차례로 하나씩 복구
- 프로세스 종료(Process Termination) 방식: 교착상태에 포함된 프로세스 중 하나를 강제 종료시킨 후 자원 할당
Reference
김주균, 『OS? Oh Yes!』, Human Science(2013), p107-128.
Study&Work&Log