교착상태

소개

분산시스템에서의 교착상태 탐지 방법 요약

목차

☆ 분산시스템에서의 교착상태 탐지
① 중앙조정자를 통한 접근
② 분산접근

본문내용

☆ 분산시스템에서의 교착상태 탐지
① 중앙조정자를 통한 접근
: 지역 조정자 중 하나를 중앙 조정자로 지정하고 이는 다른 모든 조정자로부터 지역 대기 그래프를 수집하여 완전한 전역 그래프로 모으고 사이클이 있는지 이 전역 그래프를 분석한다. 지역 그래프들은 에지가 더해지거나 제거될 때마다 전역 조정자에게 보내질 수도 있고, 메시지 취급량을 줄이기 위해 여러 개의 변화를 그룹화 시켜 보내질 수도 있다.

문제점1) 전역조정자는 성능의 병목 지점과 단일 장애점이 될 수 있다.
문제점2) 전역 조정자는 환영 교착상태라고 하는 존재하지 않는 교착상태를 탐지할 수 있다.
※ 예) p₄→ p₃, p₃→ p₂, p₂→ p₁에 대한 그래프를 중앙조정자가 가지고 있을 때

사건1) p₁이 p₄가 가지고 있는 자원을 요청 : ( p₁→ p₄) 의 추가
사건2) p₃의 대기 시간이 종료하여 p₂에 대한 대기 에지 ( p₃→ p₂)를 제거
: 이 두 사건에 대한 메시지가 중앙조정자에게 전달되는데 이 때 사건2 보다 사건1이 먼저 중앙조정자에서 도착한다면 아래와 같은 그래프를 만들게 되어 교착상태임을 보고하지만 실제로는 사건2에 의해 ( p₃→ p₂)이 제거되어 교착상태가 아니다.

참고자료

· 운영체제