교착상태 (Deadlock)

I. 멀티 프로세스 환경의 무한 자원대기, 교착상태

가. 교착상태(Deadlock)의 개념

  • 멀티 프로세스 환경에서 두 개 이상의 프로세스가 아무리 기다려도 자원을 사용할 수 없는 무한 대기 상태

나. 교착상태 발생 원인

원인설명
상호배제 (Mutual Exclusion)– 자원 배타 점유, 타 프로세스 사용 차단
점유와 대기 (Block & Wait)– 특정 자원 할당 점유 후 다른 자원을 요구
비선점 (Non-Preemption)– 할당된 자원의 사용이 끝날 때까지 회수 불가
환형대기 (Circular Wait)– 프로세스 간 자원 요구가 하나의 원형 구성
  • 교착상태는 한 시스템에서 위 4가지 조건이 동시 성립 시 발생

 

II. 교착상태 해결 방안

가. 교착상태 해결 방안 분류

나. 교착상태 상세 해결 방안

– 교착상태 예방 (Prevention)

구분설명단점
상호배재 조건 부정– 공유할 수 없는 자원 사용 시 성립 
점유와 대기 조건 부정– 자원 요청 시 다른 자원 요청하지 않음– 자원 낭비, 비용 증가
– 자원 공유 불가능
비선점 조건 부정– 자원 할당 실패 시 점유 자원 반납– Starvation 발생 가능
– 자원 안전선점 불가
환형대기 조건 부정– 모든 프로세스에 각 자원할당 순서 부여– 새로운 자원 추가 시 재구성 필요

– 교착상태 회피 (Avoidance)

알고리즘설명
자원할당
그래프
알고리즘

– 종류 별 자원이 한 개 → 한 개씩 요청 가능
– 자원 요청 시 예약간선은 요청간선으로 전환
은행가 알고리즘
(Banker’s Algorithm)
– OS가 자원 상태 감시, 필요 자원 수 제시 관리
– Available: 사용 가능 자원의 수
– Max: 각 프로세스 최대 요구
– Need: 프로세스 마치기 위해 남은 요구
– Allocation: 각 프로세스에 할당된 자원 수

– 교착상태 발견 (Detection)

– 교착상태 회복 (Recovery)

① 프로세스 종료법

방법세부 기법장단점
전체 종료– 교착상태인 프로세스 모두 종료– 구현 간단/종료 따른 cost 큼
부분 종료– 종료 시 cost가 낮은 Process, 우선순위, 처리시간 등 선정– 종료 프로세스 수 작음

② 자원 선점법

절차세부 기법
대상자원 선정– 자원 점유 중 Process 보유 리소스 수 등 고려
Rollback– 전체 또는 부분 rollback, 관리 지점 필요
기아방지– 선점 count 등 관리하여 특정 프로세스가 지속적 자원 선점 근절 보장

 

One Comment

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^