Resource Allocation Graph
그래프는 누가 무엇을 들고 무엇을 기다리는지 압축해서 보여준다
프로세스 노드, 자원 노드, 요청 관계, 할당 관계를 분리하면 순환 대기가 있는지 빠르게 확인할 수 있다.
Process
실행 중인 작업 단위, 예시는 P1과 P2
Resource
잠금, 파일, 장치처럼 획득해야 하는 대상
Cycle
닫힌 대기 고리는 교착 가능성의 핵심 신호
P1
R1을 보유
이미 할당된 자원은 반납 전까지 다른 프로세스가 쓸 수 없다.
P1 요청
R2를 기다림
R2가 비어 있지 않으면 P1은 대기 상태로 남는다.
P2
R2를 보유
P2 역시 필요한 자원이 생기기 전까지 R2를 계속 붙잡는다.
P2 요청
R1을 기다림
요청과 할당 관계가 서로 맞물리면 순환 대기가 된다.
표현
읽는 법
판단 포인트
요청 관계
프로세스가 아직 받지 못한 자원을 기다리는 상태
대기 시간이 길어질수록 병목 위치가 된다.
할당 관계
자원이 이미 특정 프로세스에 배정된 상태
반납 전까지 다른 요청은 충족되지 않는다.
단일 인스턴스
자원 종류마다 하나씩만 존재하는 경우
순환이 있으면 교착 상태로 판단하기 쉽다.
다중 인스턴스
같은 자원이 여러 개 존재하는 경우
순환은 위험 신호지만 추가 검사가 필요하다.
노드부터 분리
프로세스와 자원을 먼저 나누면 관계 해석이 흔들리지 않는다.
고리 확인
닫힌 대기 구조가 생기면 데드락 후보로 올린다.
인스턴스 수 확인
자원이 여러 개면 그래프 축소나 은행가식 판단이 필요하다.